月別アーカイブ: 2012年1月

四目並べ4 『ランダムに手を打たせる』

前回まででだいぶ良くなってきたAIですが、まだ気になる点があります。
それは、

ワンパターンすぎる。

ということ。
ランダム要素が少なすぎるので、一度勝ちパターンを覚えてしまえば負けることはありません。
ですから、今回はAIにランダムに手を打たせる方法を考えてみようと思います。

1. いかにしてランダムに手を打たせるか。

結構な悩みどころです。
ときどき第1候補の手ではなく第2候補や第3候補の手を打たせるようにすればいろいろな手を打つようになるでしょうが、弱くなるのが目に見えてます。モンテカルロ木探索という乱数を使った探索をメインに置いたアルゴリズムもあるのですが、これで強いAIを作るのもなかなか難しいです。

で、思いついたのがこれ。

評価値を付ける際に、ランダムに手を間引いてしまいます。

これだけだと弱くなりそうですが評価値を付けなかった分は高速化されます。その分だけ先読みする手を増やせばうまく相殺できるんじゃないかと考えたわけです。

2. 実践

実際に見てみましょう。

ゲームを開く(swf)

いい感じに手がばらついていますし、さほど弱くなった印象は受けません。
今回のAI(4号)と前回のAI(3号)を対戦させてみると、前回の方がやや勝っている感じがしますが許容範囲内じゃないでしょうか。

とりあえず、今回はここまで。

続くかもしれない。

四目並べ3 『先読みアルゴリズムを組む』

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

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

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

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

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

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

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

2. 枝刈りで高速化

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

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

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

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

3. 実践

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

ゲーム開始(swf)

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

今回はここまで。

きっと続く。

四目並べ2 『どっちが勝ってる?』

いきなりですが問題です。

以下の状態だと、先手と後手どちらが勝っているでしょう?

どっちが勝ってる?

正解はもうちょっと後で。今回はこの判断をコンピュータにやらせようという話です。

1. 局面を評価する

ゲームAIでは、ある局面を見てどちらがどのくらい勝っているか数値化するというのが重要です。

前回は、自分の打てるすべての手を把握するところまでやりました。
これに加えて局面に点数をつけることができるようになれば、すべての手を打ってみてどの手を打った時に自分が有利になっているかが判断できます。自分にとって最善の手が見つけられるわけですね。

ちなみに、「どのくらい勝っているかを評価した値」を評価値といいます。

2. 今回の評価方法

どう評価値をつけるかはAIの強さを決める非常に重要な要素なのですが、今回は評価値がどんなものか知るために簡単な方法で評価値をつけてしまいます。

  1. リーチは1つにつき128点
  2. リーチのリーチは1つにつき16点
  3. リーチのリーチのリーチは1つにつき2点
  4. 次が自分の手番の場合は点数は1.5倍
  5. 勝ちの場合は上に関係なく10000点

以上のルールで、各プレーヤーに点数をふって、自分の点-相手の点 を評価値とします。

とりあえずの評価値なので、細かい配点に深い意味はありません。
四目並びそうなところがあれば加点してやろう。自分の手番だったら加点を大きくしてやろうくらいの気持ちです。

3. 評価値を付ける

それでは、さっきの局面に評価値をつけてみます。

以下のように特定の並び、を見つけていって点数を足していきます。

320点で先手が勝っているという結果が出ました。実際に手を進めてみると先手に必勝パターンがあるのが分かります。

▼この局面まで持って行ければ、先手の勝ち。

4. AIに取り入れる

この評価方法をAIに取り入れてみます。

ゲームを開く(swf)

ソースはこちら
単純な評価方法でしたが、だいぶまともに動くようになりました。でも、まだ自滅したりとあらが目立ちますね。

とりあえず、今回はここまで。

たぶん続く。