今回は先読みアルゴリズムを組みます。

はじめのAIですべての手を網羅することはできているので、これを繰り返せば2手目、3手目と先読みすることができます。あとは相手もこちらも、自分が有利になるように試合を進めることを踏まえれば、どの手を打てばよいかを決められます。

1. 先読みアルゴリズムの図解

具体的には以下のようなアルゴリズムで、着手を決めます。

1. 適当な手数を先読みして、起こりうるすべての局面を列挙する。
2. 最初に最深層にあたる局面に評価値を付ける。
3. プレーヤーは最も自分が有利になる手を打つと考えて、1つ手前の手に評価値をつける。
4. 3を繰り返して最上位まで評価値を付けて、自分が最も有利になると考えられる手をうつ。

3の段階でマイナスを付けて評価値を決めているのは、 相手が不利=自分が有利 だからです。

このような、プレーヤーが自分に有利になるように対局を進めることと、相手が不利=自分が有利であることを利用したアルゴリズムをネガマックス法と言います。

2. 枝刈りで高速化

先ほどのネガマックス法ですが、評価値を付ける順番を工夫すると高速化が行えます。

さっきと同じ局面を例にとって、以下のような順番で評価値をつけてみましょう。

すると、評価値を計算する前にその手が打たれないとわかる場面が出てきます。

上の例の場合、同じような場面がもう一回現れるので、計4回の評価関数の呼び出しが省略できます。
このように必要のない計算を省略して、評価関数を呼び出す回数を減らしたアルゴリズムをネガアルファ法と言います。

3. 実践

以上のアルゴリズムを取り入れたAIを作ってみました。

ゲーム開始(swf)

先読みをしてるのは5手ほど(終盤はもうちょっと増える)ですが、だいぶ良い動きをするようになりました。
こちら(GitHub)にコードを置いておきますが、ネガマックス法やネガアルファ法についてはWikipediaのミニマックス法とアルファ・ベータ法の項目にもコード例が載っているのでそちらを参考にするのもいいと思います。

今回はここまで。

きっと続く。