四目並べの完成からだいぶ時間があいてしまいましたが、そろそろブログの内容を完結させとかなきゃと思ったので、あとがきみたいなのを残しときます。
ちなみに完成品はこちら。
AI量産するのに遺伝的アルゴリズム使ったとか、RTMFPっていうのを使ってオンライン対戦できるようにしたとか、まだ書くつもりだった話はあったんですが、間が空きすぎたのと、完成品の人気が出なかったのと、モチベーションの問題で四目並べのログとしては詳しくは書かないです。
とはいえ全部お蔵入りさせるのももったいないので、遺伝的アルゴリズムについては最後に少しだけ書いときます。
遺伝的アルゴリズムっていうのは簡単に言うと、生物の進化の仕組みをプログラムで使う手法です。
むにむにさんという人が作ってる動画が分かりやすいので、それをみるといいと思います。
前回まででだいぶ良くなってきたAIですが、まだ気になる点があります。
それは、
ということ。
ランダム要素が少なすぎるので、一度勝ちパターンを覚えてしまえば負けることはありません。
ですから、今回はAIにランダムに手を打たせる方法を考えてみようと思います。
結構な悩みどころです。
ときどき第1候補の手ではなく第2候補や第3候補の手を打たせるようにすればいろいろな手を打つようになるでしょうが、弱くなるのが目に見えてます。モンテカルロ木探索という乱数を使った探索をメインに置いたアルゴリズムもあるのですが、これで強いAIを作るのもなかなか難しいです。
で、思いついたのがこれ。
評価値を付ける際に、ランダムに手を間引いてしまいます。
これだけだと弱くなりそうですが評価値を付けなかった分は高速化されます。その分だけ先読みする手を増やせばうまく相殺できるんじゃないかと考えたわけです。
実際に見てみましょう。
いい感じに手がばらついていますし、さほど弱くなった印象は受けません。
今回のAI(4号)と前回のAI(3号)を対戦させてみると、前回の方がやや勝っている感じがしますが許容範囲内じゃないでしょうか。
とりあえず、今回はここまで。
続くかもしれない。
今回は先読みアルゴリズムを組みます。
はじめのAIですべての手を網羅することはできているので、これを繰り返せば2手目、3手目と先読みすることができます。あとは相手もこちらも、自分が有利になるように試合を進めることを踏まえれば、どの手を打てばよいかを決められます。
具体的には以下のようなアルゴリズムで、着手を決めます。
3の段階でマイナスを付けて評価値を決めているのは、 相手が不利=自分が有利 だからです。
このような、プレーヤーが自分に有利になるように対局を進めることと、相手が不利=自分が有利であることを利用したアルゴリズムをネガマックス法と言います。
先ほどのネガマックス法ですが、評価値を付ける順番を工夫すると高速化が行えます。
さっきと同じ局面を例にとって、以下のような順番で評価値をつけてみましょう。
すると、評価値を計算する前にその手が打たれないとわかる場面が出てきます。
上の例の場合、同じような場面がもう一回現れるので、計4回の評価関数の呼び出しが省略できます。
このように必要のない計算を省略して、評価関数を呼び出す回数を減らしたアルゴリズムをネガアルファ法と言います。
以上のアルゴリズムを取り入れたAIを作ってみました。
先読みをしてるのは5手ほど(終盤はもうちょっと増える)ですが、だいぶ良い動きをするようになりました。
こちら(GitHub)にコードを置いておきますが、ネガマックス法やネガアルファ法についてはWikipediaのミニマックス法とアルファ・ベータ法の項目にもコード例が載っているのでそちらを参考にするのもいいと思います。
今回はここまで。
きっと続く。
いきなりですが問題です。
以下の状態だと、先手
と後手
どちらが勝っているでしょう？
正解はもうちょっと後で。今回はこの判断をコンピュータにやらせようという話です。
ゲームAIでは、ある局面を見てどちらがどのくらい勝っているか数値化するというのが重要です。
前回は、自分の打てるすべての手を把握するところまでやりました。
これに加えて局面に点数をつけることができるようになれば、すべての手を打ってみてどの手を打った時に自分が有利になっているかが判断できます。自分にとって最善の手が見つけられるわけですね。
ちなみに、「どのくらい勝っているかを評価した値」を評価値といいます。
どう評価値をつけるかはAIの強さを決める非常に重要な要素なのですが、今回は評価値がどんなものか知るために簡単な方法で評価値をつけてしまいます。
以上のルールで、各プレーヤーに点数をふって、自分の点-相手の点 を評価値とします。
とりあえずの評価値なので、細かい配点に深い意味はありません。
四目並びそうなところがあれば加点してやろう。自分の手番だったら加点を大きくしてやろうくらいの気持ちです。
それでは、さっきの局面に評価値をつけてみます。
以下のように特定の並び、を見つけていって点数を足していきます。
320点で先手が勝っているという結果が出ました。実際に手を進めてみると先手に必勝パターンがあるのが分かります。
▼この局面まで持って行ければ、先手の勝ち。
この評価方法をAIに取り入れてみます。
ソースはこちら。
単純な評価方法でしたが、だいぶまともに動くようになりました。でも、まだ自滅したりとあらが目立ちますね。
とりあえず、今回はここまで。
たぶん続く。