2011 10.29 Sat リバーシプログラムの作り方 ＣＡＴＥＧＯＲＹ ：ゲームAI

1. リバーシのルール
 冒頭でも簡単に書きましたが、以下のようになります。

白と黒の石を8x8四方のマス目で区切られた盤面に交互に配置していき、

その置いた石の数を競うゲームです。

石は縦、横、斜めのいずれかで相手の石を挟み込むと、自分の石の色に変える事が可能です。

相手の石を挟み込むことのできないマスには置けません。

石を置くことのできるマスがない場合、パスとなります。パスは何回でも可能です。

石がすべてのマスを埋めるか、白と黒、どちらも石を置けなくなった時点でゲーム終了となり、

最終的に石の数が多い側が勝ちになります。


2.開発環境について
 今回はオープンソースで初学者でも分かりやすいProcessingが採用されました。
この言語は、Javaを用いており、ローカル開発はもちろんのこと、
OpenProcessingというウェブブラウザ上での開発と実行が可能です。
Javaのライブラリを使うことも可能でしたが、今回はProcessing標準機能でのみの
実装に留めました。通常のJavaと比べると多少異なっている部分があり、
main関数は存在せず、アプリケーション生成時に一度だけ呼ばれるsetup()、
毎フレーム呼ばれるdraw()関数が標準で呼ばれるようになっています。
個人的に、情報更新と描画は分けたかったのでdraw関数内で最初にupdate関数を呼び、
それから描画処理を行うようにしました。

3.リバーシプログラムの実装
 リバーシプログラムを作るにあたって、一連の流れを見て行きましょう。

1.マス目の中で自分が石を置ける場所に石を置く。
2.置いた石が隣接するマスが相手の石で、その隣が相手の石なら反転する。
3.相手の順番にする
4.相手も手順1と手順2を行い、プレイヤーの順番にする。
5.手順1～4を繰り返し行い、双方石が置ける場所がなくなったら石の数を数える。
6.石の数の多い方を勝者とする。同じ数だったら引き分けとする。

それぞれの手順について解説します。
1.マス目の中で自分が石を置ける場所に石を置く。
  最初に石をどこに置くことが出来るのかを調べなければなりません。
石を置くことの出来る条件は、相手の石を挟むことの出来る位置です。
これを調べるために、後述する石が反転できるかを調べる関数を使います。
この関数により、一箇所でも石が置ける位置が見つかれば、
次の処理に進みます。

次は石を置く処理です。まず、マウスの座標を取得します。
取得したマウスの座標をマス目の情報に変換します。
マス目は2次元の配列変数になっており、添字[xx][yy]のxxやyyの値が
どこのなのかが分かれば石を置くことができます。
これはマウス座標を石のサイズで割ることで求めることができます。

2.置いた石が隣接するマスが相手の石で、その隣が相手の石なら反転する。
 先ほど出てきた石が反転出来るかを調べる関数を使います。
この関数では石を置いた場所(石x, 石y)の周囲8箇所を探索していきます。
左上を例にとると、

(1)(石x - 1, 石y - 1)が自分と同じ石か調べます。
(2)同じ石なら次の周囲探索に移ります。違う石なら(3)に進みます。
(3)左上の左上の石(石x - 2, 石y - 2)を調べます。
(4)上記(3)の石が違う色の石なら数をカウントし、(3)に進みます。
(5)上記(3)の位置が空白なら次の周囲探索に移ります。
(6)上記(3)の石が同じであり、カウントが1以上あれば、反転を行います。
(7)石を置いた場所から上記(3)の位置の間で相手の石があれば、色を変えます。

この手順を周囲8箇所全てに行います。

3.相手の順番にする
順番を格納する変数を用意しておき、値を書き換えます。

4.相手も手順1と手順2を行い、プレイヤーの順番にする。
上記手順と同じように石が置ける位置から任意の位置を選び石を置きます。
現バージョンでは左上から右下に探索を行い、最初に見つかった候補に石を置くようになっています。

5.手順1～4を繰り返し行い、双方石が置ける場所がなくなったら石の数を数える。
6.石の数の多い方を勝者とする。同じ数だったら引き分けとする。
双方石が置ける場所が無くなったら判定に移ります。
マス目に置かれている石の数を数え、数が多い方に応じて表示処理を行います。


4.AI考察
 さて、ここからが本題のAIについてです。
今回AIをどのように実装したのかは上記の通り、左上から右上にかけて探索し、最初に候補に上がった場所に
石を置くようになっています。
この他、どのような物が考えられるか上げていきます。

(1)石が置ける位置のスコアを出して、最もスコアが高い位置を選ぶ
 上述の通り、石を置ける位置は既に見つけることが出来るため、それらの中から一番スコアの高い場所を
見つけ出します。スコアが高いのは4隅、端、そして裏返すことの出来る石が多い場所となります。
これらを考慮し、スコアの高い位置を選ぶことが考えられます。

(2)相手が石を置く場所を予測して置けないようにする
 この方法では逆に、相手が次に石をどこに置くのかを予想しておき、そちらを優先的に潰してしまう方法です。
ただし、相手がどこに石を置くのかは特徴があり、隅を重点的にや、挟める数を優先するなどの癖を見抜くための
学習要素が必要となってきます。

以上、まとめてみました。
冒頭でも書きましたが、ゲームは以下のリンクから遊ぶことができます。
（ソースコードも公開しています）
http://www.openprocessing.org/visuals/?visualID=41854

では～。