リバーシの作りかた

投稿者: | 2012年5月23日

1.はじめに

今回はリバーシの作り方を解説します。

リバーシは、プログラム初心者でも簡単に作れるわりに、盤面の扱い・CPUの思考ルーチンなどにこだわれば、凝ったプログラムができる、なかなか面白い題材です。

2.盤面の設計

まず、リバーシの盤面の設計をします。クラス図としてはこんな感じです。

石であるStoneクラスを見てみます。属性としては、とりあえず「色」の属性があれば充分です。(サンプルのように、ひっくり返した場合に飛び跳ねるような処理を行いたい場合には、座標の情報などが必要になります)

他に、スタティックな属性として、

  • BLACK
  • NONE
  • WHITE
  • WALL

というものを持っています。

ポイントは、BLACKが「-1」でWHITE「1」となっているところです。これは、reverseメソッドなどで石を反転させる場合、-1をかけるだけでよいため、このようにしています。

もう一つのポイントとしては、WALL属性です。盤面クラス(Boardクラス)のfield属性が、盤面の情報となるのですが、サイズ(RANGE属性)を「10」としています。

これは、盤面のサイズを、本来のサイズである「8」にしてしまうと、盤面探索時に配列オーバーを起こしてしまいます。

そのため、周りに1つ壁を作っているわけです。

さて、続いて盤面である、Boardクラスを見てみます。RANGE、field属性については、先ほど説明したとおり、盤面の石の配置状態を持っています。initメソッド呼び出し時に、Stoneクラスのインスタンスを作り、fieldを初期化します。

cntHand属性は、現在の手数となります。リバーシでは60手を超えると、盤面が全て石で埋まりますので、こういったものがあると何かと便利ですよね。

getCountStoneメソッドは、指定した色がどれだけあるかを返します。putStoneメソッドは、座標と色を指定して、石を置きます。

さて、ここからが盤面クラスのポイントです。まず、getReverseListメソッドですが、座標と色を指定すると、「ひっくり返すことができる石の座標のリスト」を返します。

putStoneメソッドの中で、このgetReverseListメソッドを呼び出し、その結果に基づき、石をひっくり返すようにします。

なぜこのようにgetReverseListメソッドを独立させているのかというと、盤面にひっくり返すことができる数を表示させたり、CPUの思考ルーチンに必要となるからです。

getReverseListメソッドの中では、再帰関数reflexReverseListメソッドを呼び出します。なぜ再帰処理にしているのかというと、ひっくり返すことを探索する場合には、以下の処理を行うためです。

x,yに黒石を置いたとします。この場合、8方向に探索を行うのですが、これには一定のパターンがあります。

  1. 指定した方向に探索し続ける
  2. 探索場所が黒石*-1であれば探索を続ける
  3. 探索場所が黒石であればそれまでにはさんだ黒石*-1をひっくり返すことができる
  4. 探索場所が黒石かつ黒石*-1でもない場合、その方向にひっくり返す石はない

1については、基点となる(x,y)に移動量(dx,dy)を足しこんでいくことで実装します。

2については、探索を続けるのですから、再帰関数を呼び続けることになりますよね。そして、その戻り値がtrueであれば、reverseListに現在の座標を追加します。

3は、戻り値をtrueにすることで、呼び出し元がひっくり返すことできることを教えます。

4は、ひっくり返すことができないので、戻り値がfalseになります。

とまあ、再帰処理に慣れていない人にはナンノコトヤラですが…。繰り返しの処理を行う場合に再帰処理を使うと、すっきりしたコードを書くことができる場合があります。

ですが、再帰処理は普通のループ文と条件式で置き換えることができますので、理解できなかった場合は、その方法で書いたほうがいいかもしれません。

また、再帰処理は、関数呼出しごとにスタックにメモリを積んでいくので、パフォーマンスが落ちます。ですから、スピードが必要な処理の場合は、普通に書いたほうがいいかもしれません。

さて、もう一つのポイントgetReversePointListメソッドです。これは、指定した色を置くことができる座標のリストを返します。これにより、ひっくり返すことができる場所を表示したり、CPUの思考ルーチンを楽に作ることができます。

最後にundoメソッドです。これは、進めた手を戻す処理です。なぜこの処理が必要なのかというと、CPUの思考ルーチンの「先読み」処理を作る場合に必要となるからです。

例えば、3手先まで読む場合には、実際に石を置いて盤面を3手先まで進める、といった処理を行うため、思考ルーチンが終了した場合には、手を戻す必要があるからです。

盤面の設計は以上です。CPUの思考ルーチンはランダムに置くというだけでも、ゲームはできますので、ここまでできれば、一応、完成ですね。

3.CPUの思考ルーチン

CPUの思考ルーチンについて解説します。クラス設計としては、以下のようになります。

executeメソッドを継承したクラスで実装するという、

典型的なストラテジーパターンですね。Evalutionクラスは、手や盤面の評価を行うクラスです。

では、思考ルーチンの基本ともいえる、ミニマックス法について解説します。まずはこの図を見てください。

この図では、自分の選ぶことができる手として、AとBがあります。Aを選ぶと評価としては「+5」、Bを選ぶと評価としては「+3」です。自分の番だけ考えれば、Aを選ぶべきです。

しかし、ここでは次に相手がどんな手を打つかを「先読み」してみます。Aを選ぶと相手にはa1とa2があります。a1は「+4」a2は「+7」です。相手が十分に賢いと仮定すると、a2を選択します。

こうすると、相手にとってのプラスは自分にとってのマイナスですから、Aの評価は、「5-7=-2」となります。それに対して、Bを選択すると、相手はb1を選択しますから、Bの評価は、「3-2=1」となります。

よって、Bを選択する方が、評価は高いことになります。

このように、自分はMaximumとなる評価、相手は自分にとってMinimumとなる評価、を選択することから、ミニマックス法、と呼びます。

では、この「評価」の値を計算するにはどうすればいいのでしょうか。実はこっちの方が重要だったりします。

方針としては、例えば以下のものがあります。

  1. ひっくり返すことのできる石の数
  2. 角に置く
  3. 置く場所が危険地帯
  4. 置くと「確定石」が増える
  5. 置くと「着手点」が多くなる
  6. 開放度

1は真っ先に思いつくと思います。

ゲームの終盤ではたくさんの石をひっくり返すべきですし、全滅を狙うためにも必要です。しかし、少しでもリバーシをやったことがある人には、単純に多く取ればいいものではないことは知ってますよね。むしろ、「角に置く手」が重要ですよね。そして、逆に「相手に角を取られるような手」は危険です。

2の「角に置く」手には高い評価を与えます。

3の「置く場所が危険地帯(角を取られてしまうような場所)」の手にはマイナスの評価を与えます。これだけでもそれなりに強いですが、さらに強くするためには、以下の評価を考慮します。

4の「確定石」とは、相手にひっくり返されない自分の石のことです。例えば、角は相手に返されません。また、角に隣接する石も相手に返されません。こういった石が増える手は高く評価します。

あと、強い人なら、以下の状況は有利であることを知っています。

  • 置くことができる場所(着手点)が多い
  • 自分の石の周りが相手の石に囲まれている(開放度が低い)

余裕があれば、こういった評価も行います。

評価の方針としては、以上です。

ということで、評価をいくつにするか、ということですが、これに答えはありません。

ここら辺は作る人の個性が出るところですね。

例えば、角に辛くするなら、角に置く手の評価を高くしたりと、まあ、、、実際にゲームをしながら、数値をいじってみるのが一番です。(個人的には、このバランス調整の作業が一番面白かったりします

最後に、、もっと処理にこだわると、α-β法や評価のテーブル化など、処理を軽くすることができたりします。処理を軽くすれば、もっと先の手を読んでもプレイに差支えがないので、さらに強い思考ルーチンが作れますよね。

ちなみに参考書籍としてはこちらです。

思考ルーチンについてかなりマニアックに書かれていてオススメです。