チェスエンジンの反復深化

解説

反復深化では、がまず小さな限界で探索し、その後、限界を徐々に大きくしながら分析を繰り返す。チェスの深度は通常プライで測り、1プライは一方の陣営による1手を指す。

開始局面に近い位置を繰り返し訪れるため、一見すると無駄に思える。しかし前の反復から、暫定最善手、現時点で最善と見なされるラインである主変化、保存済み結果、に使う情報が得られる。次の反復で有望な選択を先に探索すると、より多くの枝を早期に止められることが多く、反復作業の大半を相殺する。

最も明確な実用上の利点は時間管理である。時計の都合で深い反復の途中にエンジンを止めても、直前の反復で完了した結果が残っている。完了しないかもしれない一回の探索へすべてを賭ける必要がない。

反復深化は、一つの好みのラインだけを延ばすことではない。選択的手法が探索木内で異なる局所深度を割り当てる場合はあっても、各反復は開始局面をより大きな限界で再検討する。を遠ざける助けにもなるが、完全には除去しない。

インターフェースは現在の反復で到達した深度を表示することが多いが、数値が大きいだけで、異なる二つのエンジンが同等の作業をしたとは証明できない。

無意味な反復

前の作業から手の順序、主変化、保存済み探索情報が得られるため、次の反復は実際にはゼロから始まらない。

深化と選択的エクステンション

反復深化は各周回の間で全体の限界を引き上げる。エクステンションは特定ラインへ局所的な探索を追加する。