反復深化は、探索をいきなり深く読むのではなく、浅い深さから順に繰り返し深くしていく手法である。 現在の将棋AIでは、アルファベータ法を運用するための基本フレームワークになっている。
反復深化では、
という流れで探索する。
一見すると、同じ局面を何度も読むので無駄が多そうに見える。 しかし実際には、浅い探索で得た情報が次の反復で役立つため、 固定深さを一気に読むより都合がよいことが多い。
反復深化が有利なのは、浅い反復で得た
が、次の深さで強力な先読み順序になるからである。
とくにアルファベータ法は良い手から先に読むほど効率が上がるため、 前の反復の結果をそのまま次の反復に流用できる反復深化は非常に相性がよい。
反復深化は時間管理にも重要である。
探索途中で時間切れになっても、 直前の反復で求めた最善手が残っているため、 少なくとも「前の深さでは最善だった手」を返せる。
この性質により、実戦エンジンでは探索の打ち切りがしやすい。
Move iterativeDeepening(Position root, int maxDepth) {
Move bestMove = MOVE_NONE;
for (int depth = 1; depth <= maxDepth; ++depth) {
SearchResult result = searchRoot(root, depth);
bestMove = result.bestMove;
if (timeUp()) {
break;
}
}
return bestMove;
}実戦的には、searchRoot の中で
アルファベータ法、
aspiration windows、
置換表などを併用する。
反復深化は単なる「何度も読む手法」ではなく、
をまとめて支える枠組みである。
そのため、多くの将棋AIで探索ループの中心に置かれている。