コンピュータゲームの実装: リバーシ

1.1 リバーシというゲーム

リバーシ (登録商標オセロとしても知られる) は二人ゼロ和完全情報ゲームでコンピュータゲーム研究の対象として盛んにプログラムが開発されてきた。現在はコンピュータが人間世界チャンピオンよりもはるかに強くなっている。また、先手後手双方が最善を尽くした時引き分けになることをコンピュータプログラムで証明したとする論文が2023年10月に arXiv (アーカイブ) で公開されている。

一方、上のような高度な話題とは別に、リバーシはルールが単純なためプログラムを作りやすく、入門用あるいは教育用ゲームプログラミングの対象として利用されることも多い。

今回は 8マス×8マス のゲームだけでなく、4マス×4マス、6マス×6マス、10マス×10マス にも対応させる。

1.2 データ表現

コンピュータゲームを作るにあたってGUIでなくコンソール上で動作するタイプのプログラムも作られるが、人間が見たときアピールが弱く、プログラミングするやる気も起きにくい。そこで今回はGUIプログラムとするが、C言語やC++言語は標準のGUIライブラリを持たないので、Visual C++ を使って Windows 上で動作するプログラムを作るなど、一般性のない特定環境での開発となりあまり教育的でない。

そこで、様々な環境で動作させられるよう、言語はJavaを使うこととし、雛形を用意しそれに追加・修正を加える演習をやってもらいプログラムを動作させてもらう。演習では極力Java特有の知識が必要なものは避け、C言語の構文の知識+α程度で行えるものを用意する。

とは言え、多くの部分はJavaを用いたオブジェクト指向のプログラムになっている。簡単に、プログラムの構造を示す。

App
アプリケーション (プログラム自身) を表す

Game
一ゲームを表す

Player
プレーヤを表す
ComputerPlayer
コンピュータプレーヤを表す

AlphaBeta
αβ探索をする

Kyokumen
ゲーム中の一状態 (局面) を表す

Sashite
指し手 (リバーシの着手) を表す

Evaluator
局面の評価関数を表す抽象クラス。実際の評価関数はサブクラス

ReversiFrame
メインのフレームウィンドウを表す。

StartGameDialog
「ゲーム」ボタンを押したときのダイアログを表す。

1.2.2 盤の表現

局面を表す Kyokumen クラスの中で、盤は ban という一次元配列で表されている。実際の盤の大きさよりひと回り大きい配列を用意し、外側は盤の外を表すようにする。
配列のインデックスと実際の盤の位置との対応を、4×4盤、6×6盤、8×8盤のそれぞれについて示す。10×10盤のものは省略したが同様になっている。

図1  4x4盤でのban配列

図2  6x6盤でのban配列

図3  8x8盤でのban配列

ban 配列の要素は、

   BLACK = -1 なら黒が置かれている
   EMPTY = 0 なら何も置かれていない
   WHITE = 1 なら白が置かれている

  color
      現在の手番のディスクの色を表す。

  tesuu
      現在の局面の進行手数を表す。

  ishisuu[0]
      現在の局面の黒ディスクの数を表す。
  ishisuu[1]
      現在の局面の白ディスクの数を表す。

  emptyCount
      現在の局面で空いているマスの数を表す。

  xy
      着手の ban 配列上でのインデックスを表す。パスなら 0 がセットされる。

  player[0]
      黒側のプレーヤを表す。
  player[1]
      白側のプレーヤを表す。

  kyokumen
      ゲームにおける現在局面を表す。

  配列 sasiteretu
      ゲームにおいて現在局面までに指された着手を記録してある配列。
      sasiteretu[0] が一手目、sasiteretu[1] が二手目、と続く。

  kyokumen
      ゲームにおける現在局面を表す。

1.3 統合開発環境 Eclipse の使用

これから取り組むリバーシのプログラムでは、統合開発環境 (IDE) として Eclipse を使用する。
Eclipseは大学の演習室PCにインストールされており、そのまま利用できる。

各自のPCで演習を行いたい場合は、各自の責任でmyFITドキュメントにある説明などを参考にして各自のPCに Eclipse をインストールして使用する。

1.4 negamax探索の実装

対象としているゲームは、一方が勝ちで他方が負けになるゼロ和ゲームと言われるものである。
このとき、評価関数を手番が反対だと値のプラスマイナスが反転するようにして、個々の局面における手番側の有利をプラスとするように作ることができる。

      評価関数(自分側から見たとき) + 評価関数(相手側から見たとき) = 0

  つまり、

      評価関数(自分側から見たとき) = - 評価関数(相手側から見たとき)
      評価関数(相手側から見たとき) = - 評価関数(自分側から見たとき)

このような評価関数を使うと negamax探索 が実現できる。

αβ探索 で示したように、固定深さまで一律に探索する単純なnegamax探索は以下の再帰的アルゴリズムで記述できる。

整数型  negamax( 残り深さ, 現在局面, a, b ) {

    「現在局面」で可能な着手をすべて生成

    可能着手数が 0 (末端節点) なら {
        「現在局面」を末端節点用の評価関数によって評価した値を返す
    }

    「残り深さ」が 0 なら {
        「現在局面」を評価関数によって評価した値を返す    // 探索打ち切り
    }

    m = a

    すべての可能着手について {

        「現在局面」を着手によって一手進める

        value = -negamax(「残り深さ」- 1, 現在局面, -b, -m)

        もし value > m または 第一候補着手なら {
            最善着手列として記録
        }
        もし value > m なら {
            m = value
            もし m が b 以上 なら {
                着手によって進んだ「現在局面」を一手戻す
                m を返り値として戻る /* β-cut (MAXノード) または α-cut (MINノード) */
            }
        }

        着手によって進んだ「現在局面」を一手戻す
    }

    m を返り値として戻る
}

上のリストのnegamax探索を使ってある局面の着手を選択させる場合、以下のように下限値 a を -∞ 上限値 b を +∞ でnegamax探索を呼べばよい。なお、プログラム上では ∞ ではなく、局面の評価関数の値にならないような大きい値とすればよい。

        r = negamax( 探索深さ, 局面, -∞, ∞ );

AlphaBeta の中にあるnegamax探索の実装においては、以下で示すコード部品を使用する。

evalPosition( kyokumen )
        パラメータ kyokumen で表されるゲームの一局面を評価関数によって評価した値、すなわち、
        kyokumen の手番側から見た評価値を求める

evalTerminalPosition( kyokumen )
        パラメータ kyokumen で表されるゲームの末端局面 (ゲームの終わった局面) を評価関数によって評価した値、すなわち、
        kyokumen の手番側から見た評価値を求める。
        kyokumen が末端局面であることが前提

Sashite[] moves = new Sashite[ReversiFrame.MAX_SASHITE];
int numMoves = kyokumen.generateMoves(teban, moves);
        kyokumen で可能な teban 側の着手をすべて生成し、
        着手配列 moves のインデックス 0 の要素から順に入れる。
        可能な着手の数が返され、変数 numMoves にセットされる。

kyokumen.makeMove( moves[i] );
        kyokumen を着手 moves[i] によって一手進める

kyokumen.undoMove( moves[i] );
        着手 moves[i] によって進んだ kyokumen を一手戻す

※ プログラムの実行の際、大学PC演習室で Eclipse を使っている場合は正しいソースプログラムであっても実行時エラーで止まってしまう。この現象を解決するための方法をStreamのビデオで公開している。

2.1 評価関数の重要性

人間にとってそこそこに難しい完全情報ゲームでは、現在の高速・大容量なコンピュータでも一般に最後まで読みきることはできない。そのため、コンピュータの探索では探索を途中で止めて評価する評価関数が使われる。評価関数の出来はプログラムの強さに直結するが、確固たる作成指針はなく、各ゲーム種の性質に応じて工夫が必要な部分となっている。

2.2 完全読み用の評価関数

前回の評価関数は単に黒と白の石数の差を求めるものだった。 実際のリバーシでは途中で石が多いのは必ずしも有利ではないので、この評価関数を使っても弱いプログラムにしかならない。

しかし、終り近く、具体的には空きマスの数が十数個程度になれば、探索を途中局面で止めない完全読みが短時間で実行可能になる。 そこで空きマスが 10 ～ 15 個程度で完全読みに切り替える機能をつける。
完全読みでは評価するのがすべて末端局面 (勝負がついて結果が分かった局面) だけなので、石数の差を求める評価関数でよい。

4マス×4マスのゲームでは最初から完全読みが短時間で可能で、石数の差を求める評価関数だけを使えばよい。6マス×6マス以上のゲームでは最初の辺りでは短時間での完全読みはできないので、工夫した評価関数を用意する必要がある。

    もし完全読みでないときは {
      emptyCount = 局面の空きマス数
      もし emptyCount が emptyCountOnPerfectLookup 以下なら {
        完全読みに切り替え
        探索深さ最大を 2 * emptyCount にする  /* 絶対に途中で探索が終わらないようにする */
      }
    }

    if (!isPerfectLookup()) {
      int emptyCount = sakikyokumen.getEmptyCount();
      if (emptyCount <= emptyCountOnPerfectLookup) {
        setPerfectLookup(true);
        maxDepth = 2 * emptyCount;
      }
    }

2.3 各マスに点数付けする評価関数

リバーシでは隅 (☆) や辺 (A, B) を取ることが重要で、隅のナナメのマス (X)・隅の隣のマス (C) は「自分が打つと相手に隅を取られる危険性が高くなる」ので最初のうちは打ってはいけないとされている。

図4  8x8盤でのマスの種類分け

その知識を生かすべく、各マスに点数をつけ、自分の石の点数の和と相手の石の点数の和との差を評価関数にする方法が知られている。 隅のナナメのマス (X) には大きいマイナス点をつけ自分からは極力打たないようにする。隅の隣のマス (C) にも X ほど大きくはないマイナス点をつけて打ちにくくしておく。 また、その他の辺は取っていると有利なことが多いので少しだけプラス点を与えておく。
以上の考えで、例えば図のような隅辺Xのみの点数付けができる。

図5  8x8盤での点数付け例

※ 複数プログラムを同時起動してテストする方法
下にあるように、実行可能ファイル Reversi.jar を作って複数プログラムを同時起動してテストできる。例えば、2プレーヤ同士の対戦なら、10ゲームなら先手・後手を 5-5 になるようにして結果をみる。
実行可能jarファイルでテストする場合は、ソースを修正・保存する度に実行可能jarファイルを作り直す必要があるので注意する。

2.4 本格的な評価関数

各マスに点数付けする評価関数でも人間相手なら中々負けないプログラムになる。しかし、強いコンピュータプログラムには到底かなわない。評価関数も上のような単純なものでなく、いくつもの要素を評価し総合して数値化するものにする必要がある。

考慮すべき要素としては例えば以下のようなものがある。

リバーシのトッププログラムの評価関数は、上で示したような多数のパラメータを持っており、自動学習によってパラメータが調整されている。

講義では詳しく説明しきれないので省略するが、興味のある人は書籍やWebサイトなどで調べてみるとよい。またWebにはソースコード付きで公開されている強いプログラムも多くある。参考にしてみるとよい。

3.1 プログラムの識別

学籍番号でプログラムを識別できるようにする。

  // 名前の自動決定
  void setName() {
    setName("$自分の学籍番号-" + searchDepth + "-" + emptyCountOnPerfectLookup
            + "-" + evalIndex);
  }

  static final String DEFAULT_HUMAN_NAMEBASE = "自分の学籍番号";

 * @author 自分の学籍番号と氏名

  Eval8x8C() {
    name = "自分の学籍番号";
  }

3.2 他プログラムとの対戦による調整・強化

自分のプログラムだけでは強さを高めるにも目標が設定しにくい。そこで、他のプログラムと対戦させ弱点を調べ改良していく手法がよく採られる。

他のプログラムとの対戦には、現在ではネットワークを使った通信を使う場合が多いが、相互のプログラムがネットワーク対応で同一通信プロトコルであることが条件で、ネットワーク対戦ができない場合もある。そこで今回は以下のように人手を介した対戦を行う。

できれば他の人のプログラムと対戦し合って互いに強化し合うとよい。

時間に余裕があれば、黒と白を入れ換えて何ゲームかやって勝敗を見た方がよい。

一台のパソコンで二つプログラムを起動し全部自分一人で対戦させることもできる。

対戦相手を変えてゲームの相手と勝敗を記録していき、適当なところで対戦の状況を分析し、必要ならばプログラムに変更を加えていく。変更したときはその内容を記録しておく。 二回目以降の変更では今までの変更点も参考にできる。

3.3 Eclipseでの、実行可能jarファイルおよびプロジェクトのアーカイブ作成の作成

実行可能jarファイルの作成方法

EclipseでReversiプロジェクトを開いた状態で、

「ファイル(F)」
「エクスポート(O)」

で、

「Java」

の中にある

「実行可能JARファイル」

を選択し、

「次へ(N)」

をクリックする。

次の画面で、

「起動構成(L)」に「App - Reversi」が設定されていなければ、ドロップダウンリストで設定する。
「エクスポート先(D)」の「参照(R)」ボタンをクリックし、保存場所と名前を指定する。
ファイル名は Reversi.jar とする。
「ライブラリー処理」は「生成されるJARに必須ライブラリを抽出(E)」とする。

と入力・設定した上で、

下部にある「完了(F)」ボタンをクリック

すれば、指定した場所に実行可能jarファイルが作成される。

実行可能jarファイルの実行方法

PowerShell または コマンドプロンプト を起動する。まず、下記のようにjarファイルのあるフォルダに移動する。

(PowerShell の場合)

cd    jarファイルのあるフォルダ

(コマンドプロンプト の場合)

cd    /D    jarファイルのあるフォルダ

※ 名前にスペースを含むフォルダがある場合は上記のフォルダ指定で

"jarファイルの ある フォルダ"

のように、フォルダ指定全体をダブルクォーテーションで囲むこと。

次に、以下のコマンドでjarファイルを実行する。

java    -jar    Reversi.jar

また、以下のように、先頭に start を付けたコマンドを何回も実行すれば、すきなだけ複数プログラムを起動できる。

start    java    -jar    Reversi.jar

※ 課題11と課題12は履修者全員のための課題で、よくテスト・調整した上で、指定を守り提出のこと。
提出されていても、正常動作しない、あるいは、著しく弱いプレイをするプログラムの場合は、課題達成と認めない。

プロジェクトのアーカイブ作成方法   (下の 課題13 をやって提出する人のみ)

EclipseでReversiプロジェクトを開いた状態で、

「ファイル(F)」
「エクスポート(O)」

で、

「一般」

の中にある

「アーカイブ・ファイル」

を選択し、

「次へ(N)」

をクリックする。

次の画面では、

プロジェクト Reversi だけにチェックが入っているはず。
「宛先アーカイブ・ファイル(A)」の「参照(R)」ボタンをクリックし、保存場所と名前を指定する。
ファイル名は ReversiSource.zip とする。
オプションは「ZIPフォーマットで保管(Z)」がセットされているはず。

と入力・設定した上で、

下部にある「完了(F)」ボタンをクリック

すれば、指定した場所にZIPファイルが作成される。