[Machine Learning] 順序付け（move ordering）

順序付け（move ordering）：次の局面を，より良さそうな局面の順番に並べ直して，その先頭から先読みすること．

順序付けを行うことで，αβ法の利点を最大限に発揮することができます．

順序付けにおいては，最善の局面を先頭に調べるようにすることがベストです．完全な順序付けをした場合のαβ法によるゲーム木の計算量は min-max戦略の平方根 + 若干になることが知られています．

問題としては，どのような局面（もしくは着手）が良いと判断するのか？どのような順番に並べるのか？という事柄が挙げられます．

解決法：

1. 1手の深さで探索評価して，その評価値を使って順番に並べる．
2. 駒を取る手や，チェックメイトなどの重要手を先頭に持ってくる．
3. 探索木の中で，それ以前に別の枝で最善であった着手を先頭にする（ただし，その着手が現在局面で合法であることの確認が必要）．この方法のうち，同じ深さで示された最善てをとっておいて使う方法をキラー理スティックという．
4. トランスポーテーションテーブル*を参照して，そこに書かれている局面の評価値を使って良い評価順にする．

* トランスポーテーションテーブル：そこまでに訪れた局面の，その時に求めた評価値が入っている表．

関連する投稿

ミニマックス法（min-max method），アルファベータ法（alpha-beta method），