手の並べ替えは、探索で候補手を調べる順番を工夫する技術である。 アルファベータ法は良い手から先に読むほど枝刈りが増えるため、 探索速度を大きく左右する。
ミニマックス法では手順の順番は結果に影響しない。
しかしアルファベータ法では、
有望な手を先に調べるほど早く alpha や beta の境界が更新され、
後続の枝を省きやすくなる。
そのため、現代的な将棋AIでは 「どの手を先に読むか」は探索アルゴリズムそのものと同じくらい重要である。
典型的には次のような順に試す。
将棋では、
の扱いがチェスより少し複雑になるが、基本思想は同じである。
反復深化の前回反復で最善だった手は、次の反復でも有望であることが多い。
置換表に保存された最善手は、最も重要な順序情報のひとつである。
駒取りについては、
のような方法で優先順位を付けることが多い。
などが使われる。
単純化した例では、各手にスコアを付けて高い順に読む。
int scoreMove(const Move& move, const Position& pos) {
if (move == hashMove(pos)) return 1000000;
if (isWinningCapture(move, pos)) return 900000;
if (isKiller(move)) return 800000;
return historyScore(move);
}
void orderMoves(std::vector<Move>& moves, const Position& pos) {
std::sort(moves.begin(), moves.end(),
[&](const Move& a, const Move& b) {
return scoreMove(a, pos) > scoreMove(b, pos);
});
}実際には全手を完全ソートせず、取り出し時に最大のものを選ぶ形もよく使われる。
手の並べ替えは単独で最善手を決める技術ではないが、 探索効率への影響が非常に大きい。
特に、
と組み合わせると重要性がさらに増す。