ミニマックス

ミニマックスは対局を可能性の木として表す。各枝が一つの手で、各階層では手番が一方から他方へ交代する。局面を分析して手を選ぶプログラムであるチェスエンジンは、自分の選択肢を検討し、その後に相手の最強の応手を考える。中心となる仮定は慎重で、相手のミスを当てにしない。

エンジンが指す階層では、アルゴリズムは最も有利な結果を残す。相手の階層では、相手が可能な限り抵抗すると仮定し、エンジンにとって最も不利な結果を残す。それらの値を将来局面から現在局面へ逆向きに伝えることで、開始手を、最善の防御に対して保証できる結果に基づいて比較できる。

実用的な探索で対局全体を調べられることはほとんどない。深度限界では評価関数、つまりどちらが有利かを推定する式を使う。したがって、深度を制限したミニマックスの選択は絶対的な証明ではなく、探索の深さと推定の正確さに依存する。重要な結果が打ち切りのすぐ先にあるホライズン効果の影響も受け得る。

エンジンは手の順序付けのような技術でこの枠組みを効率化する。有望な選択を先に調べ、無関係な枝を早く排除できるようにする。モンテカルロ木探索など別のシステムは、計算労力を異なる方法で配分するが、より信頼できる手を特定するという同じ実用的目標を追う。