Connect Fourソルバーを作る（5）

　Connect FourのAIの進捗を書きます。
　えーと、まずα-β pruningを実装してみました。pruningなしのものと比較して予想通りの動きをしてくれたので、正しく実装できていると思います。

• ver 0.3.0 added Alpha Beta Player

どの辺が追加されたか分かり辛いので、pruning入れる前のものとのdiff。

--- SmartMinMaxPlayer.java  2013-07-15 22:52:02.976994462 +0900
+++ AlphaBetaPlayer.java  2013-07-16 01:10:53.800748315 +0900
@@ -2,16 +2,16 @@
 
 import java.util.Random;
 
-public class SmartMinMaxPlayer extends Player {
+public class AlphaBetaPlayer extends Player {
   
-  private final int DEPTH = 8;
+  private final int DEPTH = 10;
   
   private char[][] board;
     
   @Override
   public int getNextHand(char[][] board) {
     this.board = board;
-    int[] res = dfs(0);
+    int[] res = dfs(0, -Integer.MAX_VALUE, Integer.MAX_VALUE);
     System.out.println("評価値: " + res[0]);
     return res[1];
   }
@@ -20,7 +20,7 @@
     return (c == FIRST_STONE) ? SECOND_STONE : FIRST_STONE;
   }
   
-  private int[] dfs(int turn) {
+  private int[] dfs(int turn, int alpha, int beta) {
     char cur = (turn % 2 == 0) ? getStone() : opponent(getStone());
         
     // 相手の前の手で自分の負けが確定
@@ -56,8 +56,9 @@
       if (i == -1)
         continue;
       
+      alpha = Math.max(alpha, res);
       board[i][j] = cur;
-      int[] tmp = dfs(turn+1);
+      int[] tmp = dfs(turn+1, -beta, -alpha);
       if (-tmp[0] > res || move == -1) {
         res = -tmp[0];
         move = j;
@@ -66,6 +67,9 @@
       board[i][j] = EMPTY;
       if (res == Integer.MAX_VALUE)
         break;
+      if (res >= beta) {
+        return new int[] {beta, -1};
+      }
     }
 
     return new int[] {res, move};
@@ -196,7 +200,7 @@
   
   @Override
   public String getName() {
-    return "Smart Min Max Player";
+    return "Alpha Beta Player";
   }
 
 }

α-βとは関係ないですが、前回まで作ったプログラムにバグがあったので直しました。

• ver 0.2.2 modified a bug related to a winner judgement
• ver 0.2.3 fixed a bug in Smart Min Max Player

Analysis

　まず考慮時間について。枝刈りを入れることで体感だと10倍以上考慮時間が短くなった。深さ20くらいいけるかなと予想していたけど、深さ12の時点で10秒以上かかってしまった。（※このプロジェクトでは10秒以内に指し手を決定するAIを目指している。）
　AlphaBetaPlayer（探索深さ10）を前回まで最強キャラだったSmartMinMaxPlayer（探索深さ8）と戦わせてみた。10戦1勝9分。
ゲームの流れを見ていると、お互いが負けないような手を指しあって引き分けパターンに毎回落ち着いている感じだった。あまり見ていて面白いゲームではなかった。
　これだけだと強くなったかどうか分からないので、MinMaxPlayerと戦わせてみた。100戦91勝7敗。こちらも大きな進歩は見られなかった。うーん、今回の改良はスピードアップができたというだけか。読みの深さが２増える程度だとそんなに結果に影響しないということか。というより評価関数が正確なものじゃないことが問題なのか。

Tasks Ahead

• 評価関数をもう少し練る
• 終盤に近づくに連れて探索の深さを深くしてみる
• GUIのVisualizerを作って人間様と戦わせてみる