UpperHand Gameを作る

コンピュータに相手をさせる(その2)

それでは、いよいよコンピュータに先読みをさせましょう。

min-max法とは

先読みとは、

1. 現在の局面の複製を作る。
2. 複製した局面に対して着手を行う。

最高の評価値はRの8ですので、Cとなる手を選択すればよさそうですが、 そうは簡単にいきません。 Cとなる手を打った場合、相手にFとなる手を打たれると、 最高でも4の評価値のNにしか到達できません。 ではどうすればよいのでしょう。
ゲームの先読みを行うとき、min-max法と呼ばれる手法がよく使われます。 min-max法では、ゲームの木のすべての節点(四角の部分)に 以下のルールで評価値を与えます。

• 自分の手番の場合、 直下の節点の中で最大の評価値をその節点の評価値とする。
• 相手の手番の場合、 直下の節点の中で最小の評価値をその節点の評価値とする。

これで、Bとなる手を打つのが最善であることがわかりました。

min-max法を実装する

では、min-max法を実装しましょう。

まず最初にUpperHandGameクラスに 自分自身のコピーを作る機能を追加します。
インスタンスのコピーを作る場合 インタフェースCloneableを実装し、 メソッドclone()で自分自身のコピーを作成するのが一般的な方法なので、 それにしたがいました。

//============================================================================= // UpperHandGame // UpperHandのゲーム盤を定義するクラス。 //============================================================================= public class UpperHandGame extends Observable implements Cloneable { ... }

//----------------------------------------------------------------------------- // public Object clone() // UpperHandGameの複製を生成する。 //----------------------------------------------------------------------------- public Object clone() { // UpperHandGameのインスタンスを生成する。 UpperHandGame newObj = new UpperHandGame(); // 位置ごとの状態を複製する。 for (int p = 0; p < 55; p++) { newObj.boardStatus[p] = this.boardStatus[p]; } // 持ち玉を初期化する。 newObj.ball[FIRST] = this.ball[FIRST]; newObj.ball[SECOND] = this.ball[SECOND]; // 手番を初期化する。 newObj.nextPlayer = this.nextPlayer; return newObj; }

つぎにUpperHandPlayerクラスに以下のメソッドを追加します。

メソッド名	意味
int depth(UpperHandGame game)	先読みの深さを返す。
float evaluate(UpperHandGame game)	game で与えられたゲームの状況の自分にとっての評価値を返す。
float evaluate(UpperHandGame game, int depth)	gameで与えられたゲームを depth手分先読みして評価値を返す。

最後のメソッドがmin-max法を実装するメソッドです。 2番目のメソッドは局面を数値で評価するメソッドで、評価関数と呼ばれます。 評価関数については後で説明します。

まず、depth()から実装しましょう。 depth()はプレーヤーの強さ(初級者など)によって 異なった深さを返すようにします。 そこで、UpperHnadPlayerクラスのインスタンス変数に 強さを示す変数を追加しました。 また、局面を評価するときに自分が先手か後手か知っている必要があるので、 手番を示すインスタンス変数も追加しました。

//----------------------------------------------------------------------------- // インスタンス変数定義 //----------------------------------------------------------------------------- ... // 手番 private int player; // 強さ private int rank; // 0 Beginer // 1 Middle Class // 2 Junior Master

これらのインスタンス変数は、コンストラクタで初期化します。

//----------------------------------------------------------------------------- // public UpperHandPlayer(int player, int rank) // UpperHandPlayerのインスタンスを生成し、初期化を行う。 //----------------------------------------------------------------------------- public UpperHandPlayer(int player, int rank) { // 手番を設定する。 this.player = player; // 強さを設定する。 this.rank = rank; ... }

depth()は単に強さをそのまま先読みの深さとして返すだけです。

//----------------------------------------------------------------------------- // private int depth(UpperHandGame game) // 先読みの深さを返す。 //----------------------------------------------------------------------------- private int depth(UpperHandGame game) { return rank; }

では、min-max法を実装しましょう。
局面を複製し次の一手を着手した後、 先読みの深さを1つ減らして自分自身を再帰的に呼び出します。 自分の手番の場合は、最大の評価値を自分自身の評価値とします。 相手の手番の場合は、最小の評価値を自分自身の評価値とします。 先読みの深さが0になったときは評価関数を呼び出して局面の評価値を得ます。

//----------------------------------------------------------------------------- // private float evaluate(UpperHandGame game, int depth) // gameで与えられたゲームをdepth手分先読みして評価値を返す。 //----------------------------------------------------------------------------- private float evaluate(UpperHandGame game, int depth) { if (depth == 0 || game.isFinish()) { // これ以上先読みする必要のない場合 return evaluate(game); // 局面の評価値を返す。 } // さらに先読みを行う場合 float maxEval = 0f; // 最大の評価値 float minEval = 55f; // 最小の評価値 int moves[] = game.moves(); // 着手可能な手を取得する。 boolean myMove = game.nextPlayer() == player; // 着手可能な手の中から優先順位の高い順に先読みを行う。 for (int i = 0; i < priorityOfMove.length; i++) { for (int j = 0; j < moves.length; j++) { if (priorityOfMove[i] == moves[j]) { UpperHandGame newGame = (UpperHandGame)game.clone(); // 局面を複製する。 newGame.makeMove(moves[j]); // 着手してみる。 float eval = evaluate(newGame, depth - 1); // 着手後の局面を評価する。 if (myMove) { // 自分の手番の場合 maxEval = eval > maxEval ? eval : maxEval; } else { // 相手の手番の場合 minEval = eval < minEval ? eval : minEval; } } } } return myMove ? maxEval : minEval; }

selectMove()を改造して先読みを行うようにします。
まず、depth()を呼び出して先読みの深さを得ます。 先読みの深さが0の場合は、今までと同じに優先順位にしたがって着手を決めます。 先読みの深さが1以上の場合は、局面を複製し次の一手を着手した後、 eveluate()を呼び出します。 最大の評価値の手を次の一手として選択します。

//----------------------------------------------------------------------------- // public int selectMove(UpperHandGame game) // gameから着手する位置を選択し返す。 //----------------------------------------------------------------------------- public int selectMove(UpperHandGame game) { // 先読みの深さを得る。 int depth = depth(game); if (depth == 0) { // 先読みしない場合 int moves[] = game.moves(); // 着手可能な手を取得する。 // 着手可能な手の中で優先順位の一番高い手を返す。 for (int i = 0; i < priorityOfMove.length; i++) { for (int j = 0; j < moves.length; j++) { if (priorityOfMove[i] == moves[j]) { return moves[j]; } } } } // 先読みする場合 float maxEval = 0f; // 最高の評価値 int p = -1; // 最高の評価の手 int moves[] = game.moves(); // 着手可能な手を取得する。 // 着手可能な手の中から優先順位の高い順に先読みを行う。 for (int i = 0; i < priorityOfMove.length; i++) { for (int j = 0; j < moves.length; j++) { if (priorityOfMove[i] == moves[j]) { UpperHandGame newGame = (UpperHandGame)game.clone(); // 局面を複製する。 newGame.makeMove(moves[j]); // 着手してみる。 float eval = evaluate(newGame, depth - 1); // 着手後の局面を評価する。 if (eval > maxEval) { // 評価値が最も高い場合。 maxEval = eval; // 現在の評価値を最高の評価値とする。 p = moves[j]; // 現在の手を最高の評価の手とする。 } } } } return p; // 最高の評価の手を返す。 }

評価関数を作る

最後に評価関数を実装します。

最終局面まで読み切った場合は以下の値を評価値とします。

E = 27.5 - 自分の残り玉の数 + 相手の残り玉の数

• 自分の玉が置かれている位置

  P_i = 1

• 相手の玉が置かれている位置

  P_i = 0

• 中立の玉が置かれている位置

  P_i = 0.5

• 玉が置ける位置

  P_i = 0.5

• 玉がおけない位置

  P_i = P_i,1 × P_i,2 × P_i,3 × P_i,4

  + ( 1 - P_i,1) × P_i,2 × P_i,3 × P_i,4

  + P_i,1 × ( 1 - P_i,2) × P_i,3 × P_i,4

  + P_i,1 × P_i,2 × ( 1 - P_i,3) × P_i,4

  + P_i,1 × P_i,2 × P_i,3 × ( 1 - P_i,4)

  + ( 1 - P_i,1) × ( 1 - P_i,2) × P_i,3 × P_i,4 × 0.5

  + ( 1 - P_i,1) × P_i,2 × ( 1 - P_i,3) × P_i,4 × 0.5

  + ( 1 - P_i,1) × P_i,2 × P_i,3 × ( 1 - P_i,4) × 0.5

  + P_i,1 × ( 1 - P_i,2) × ( 1 - P_i,3) × P_i,4 × 0.5

  + P_i,1 × ( 1 - P_i,2) × P_i,3 × ( 1 - P_i,4) × 0.5

  + P_i,1 × P_i,2 × ( 1 - P_i,3) × ( 1 - P_i,4) × 0.5

E = Σ_{i = 0~54} P_i

//----------------------------------------------------------------------------- // private float evaluate(UpperHandGame game) // gameで与えられたゲームの状況の自分にとっての評価値を返す。 //----------------------------------------------------------------------------- private float evaluate(UpperHandGame game) { float eval = 0f; if (game.isFinish()) { // 終局した場合 eval = (player == UpperHandGame.FIRST) ? 27.5f - game.ball(UpperHandGame.FIRST) + game.ball(UpperHandGame.SECOND) : 27.5f - game.ball(UpperHandGame.SECOND) + game.ball(UpperHandGame.FIRST); } else { // 位置ごとの評価値の総和を評価値とする。 float evals[] = new float[55]; for (int p = 0; p < 55; p++) { switch (game.boardStatus(p)) { case UpperHandGame.FIRST: case UpperHandGame.SECOND: evals[p] = (player == game.boardStatus(p)) ? 1f : 0f; // 自分の玉の場合1点、相手の玉の場合0点 break; case UpperHandGame.NUTRAL: case UpperHandGame.MOVABLE: evals[p] = 0.5f; // 0.5点 break; case UpperHandGame.UNMOVABLE: // 1つ下の位置から自分の玉となる確率を計算する。 float e1 = evals[game.downPosition[p][0]]; float e2 = evals[game.downPosition[p][1]]; float e3 = evals[game.downPosition[p][2]]; float e4 = evals[game.downPosition[p][3]]; evals[p] = e1 * e2 * e3 * e4 + (1f - e1) * e2 * e3 * e4 + e1 * (1f - e2) * e3 * e4 + e1 * e2 * (1f - e3) * e4 + e1 * e2 * e3 * (1f - e4) + (1f - e1) * (1f - e2) * e3 * e4 * 0.5f + (1f - e1) * e2 * (1f - e3) * e4 * 0.5f + (1f - e1) * e2 * e3 * (1f - e4) * 0.5f + e1 * (1f - e2) * (1f - e3) * e4 * 0.5f + e1 * (1f - e2) * e3 * (1f - e4) * 0.5f + e1 * e2 * (1f - e3) * (1f - e4) * 0.5f; break; } eval = eval + evals[p]; } } return eval; }

プレーヤーのレベルを追加する

UpperHandクラスに コンピュータのレベルを選択する機能を追加しましょう。
UpperHandクラスのクラス変数playerNameに "Beginer"、 "Middle Class"、 "Junior Master"を追加しました。

//----------------------------------------------------------------------------- // クラス変数定義 //----------------------------------------------------------------------------- ... // プレーヤーの名前 private final static String playerName[] = { "You", "Beginer", "Middle Class", "Junior Master" };

UpperHandクラスのメソッドinitPlayer()では、 現在メニューで選択されているプレーヤーのレベルを UpperHandPlayerクラスのコンストラクタに渡すようにしました。

//----------------------------------------------------------------------------- // private void initPlayer() // プレーヤー選択メニューの状態にしたがいプレーヤーを初期化する。 //----------------------------------------------------------------------------- private void initPlayer() { for (int p = UpperHandGame.FIRST; p <= UpperHandGame.SECOND; p++) { // プレーヤーを初期化する。 int index = playerChoice[p].getSelectedIndex(); if (index == 0) { // 人間が選択されているとき player[p] = null; } else { // コンピュータが選択されているとき // コンピュータのプレーヤーを生成する。 player[p] = new UpperHandPlayer(p, index - 1); } // プレーヤーの名前を初期化する。 playerView[p].playerName(playerChoice[p].getSelectedItem()); } }

あなたのブラウザはJavaに対応していません。

Javaソースコード (Ver. 1.1a11)

• UpperHand.java
• UpperHandGame.java
• UpperHandPlayer.java
• UpperHandBoardView.java
• UpperHandBallView.java
• UpperHandPlayerView.java