Reversi -AI の基本-

将棋・チェスなどボードゲーム系 AI のイロハが知りたくて、JavaScript で簡単な COM 対戦型のリバーシのプログラムを作成しました。
原点は、菅沼様のサイトにあるソースですが、上記の目的のため
・全体構成や表示機能を大幅に簡略化
・ゲーム終了条件を明確化
しました(そのため、COM は「考えている振り」などせずにほぼノータイムで指してきます)。
難しいことは抜きにして、まずは遊んでみてはいかがでしょう?
****************************************************************




*****************************************************************
それほど強いプログラムではありませんが、かといって出鱈目な手を指しているわけではないのはわかったのではないかと思います。

リバーシは、チェス・将棋・碁などと比べ、ゲーム進行の分岐の総量はそれほどでもありませんが、かといって完全解析されているわけではありません。「リバーシの神」はまだみつかってないのです。COM をそこそこ「強く」するためにはどうすればいいでしょうか?

現在、ボードゲーム系の AI でよくとられている手法が、ミニマックス法というものです。ミニマックス法は、おおざっぱに言えば『 n 手先の局面を評価し、「相手プレイヤーは全力でこちらが不利となるような手を選び、自分は評価値が大きくなるような手を選ぶ」という指し手決定法を仮定して、n 手先で自分が有利となるように現在の差し手を決定する」という方法論です。ミニマックスの探索のアルゴリズムは面白く、知的好奇心の上では、そちらの方についつい興味が行きがちですが、プログラム実装的には、局面を評価することの方が重要だったりします。
つまり、「局面ってどう評価すればいいの?」ってことです。
コンピュータ将棋では Bonanza の出現以降、局面評価として機械学習の手法を取り込むことが流行っていますが、ここでこれに触れるのはちょっと早すぎます。
今となっては懐かしい「知識ベース」に基づくプログラミングをしていきます。

もっとも単純なものは「局面の評価=自分の石の数(自分が黒なら、黒石の数)」でしょう。つまり、序盤から「取れるものは取っていこう」とひたすら石の数が増えるように指していくわけです。これはこれで面白いのですが、弱すぎます。
もう一工夫するなら「盤上の位置に得点を割り振り、隅の得点が高くなるように調整する。評価は(石の数)+(石の位置情報)でおこなう」というものです。
ん、これはなかなか現実的です。実装が楽ですから。
上のプログラムもこの方針で局面を評価しています。
具体的には

e1_board[0] = new Array( 30,-15,  0, -2, -2,  0,-15, 30);
e1_board[1] = new Array(-15,-20, -3, -3, -3, -3,-20,-15);
e1_board[2] = new Array(  0, -3,  0, -1, -1,  0, -3,  0);
e1_board[3] = new Array( -2, -2, -1,  0,  0, -1, -3, -2);
e1_board[4] = new Array( -2, -2, -1,  0,  0, -1, -3, -2);
e1_board[5] = new Array(  0, -3,  0, -1, -1,  0, -3,  0);
e1_board[6] = new Array(-15,-20, -3, -3, -3, -3,-20,-15);
e1_board[7] = new Array( 30,-15,  0, -1, -1,  0,-15, 30);

という配列を用意してゲーム序盤では「隅高め、隅周囲低め」の得点調整をしています。
これで、「隅は取りたがるが、隅周囲には打ち込まない」という棋風(?)がでてくるようになります。

プログラムでは、積極的な探索はしていませんが(評価のとき一手先は結果的に読んでいる)、ボードゲーム系の AI を概念的に理解するのには、まずはこんなところから始めてみてはいかがでしょう。



style="display:inline-block;width:336px;height:280px"
data-ad-client="ca-pub-2578173276686777"
data-ad-slot="7164044232">

コメントをどうぞ

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です

*

次のHTML タグと属性が使えます: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>