ゲーム木探索

もはや蟻本ではないけど、アルゴリズム関係は全部蟻本カテゴリーに入れてしまおう。

ゲーム木探索をするときの基本的な方法についてまとめてみる。

minimax法
自分は評価関数が最大になる手を打ち、相手はこちらの評価関数が最小になるように手を打つ。

negamax法
相手の評価値にはマイナスをかけて、常にお互いに評価関数が最大になるように手を打つ。
プログラムが簡単になるので良い。

αβ法
minimax法を枝刈りして高速に計算できるようにしたもの。
例えば評価関数の最小値を求めているときに、枝(評価関数を最大にする)において今現在の最小値より大きな値が出るようであればそこの枝の探索を打ち切るようなもの。言葉ですごい説明しにくい。

negaα法
αβ探索をnegamax法に適用したもの

最優先探索
αβ法のとき、評価値が良いものを先に探索すればより効率が上がります。そのために、ノードを並び替えて評価値が良さそうなものから探索する方法です。