Connect FourのAIの進捗を書きます。
えーと、まずα-β pruningを実装してみました。pruningなしのものと比較して予想通りの動きをしてくれたので、正しく実装できていると思います。
どの辺が追加されたか分かり辛いので、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";
}
}
α-βとは関係ないですが、前回まで作ったプログラムにバグがあったので直しました。
Analysis
まず考慮時間について。枝刈りを入れることで体感だと10倍以上考慮時間が短くなった。深さ20くらいいけるかなと予想していたけど、深さ12の時点で10秒以上かかってしまった。（※このプロジェクトでは10秒以内に指し手を決定するAIを目指している。）
AlphaBetaPlayer（探索深さ10）を前回まで最強キャラだったSmartMinMaxPlayer（探索深さ8）と戦わせてみた。10戦1勝9分。
ゲームの流れを見ていると、お互いが負けないような手を指しあって引き分けパターンに毎回落ち着いている感じだった。あまり見ていて面白いゲームではなかった。
これだけだと強くなったかどうか分からないので、MinMaxPlayerと戦わせてみた。100戦91勝7敗。こちらも大きな進歩は見られなかった。うーん、今回の改良はスピードアップができたというだけか。読みの深さが２増える程度だとそんなに結果に影響しないということか。というより評価関数が正確なものじゃないことが問題なのか。
Tasks Ahead
- 評価関数をもう少し練る
- 終盤に近づくに連れて探索の深さを深くしてみる
- GUIのVisualizerを作って人間様と戦わせてみる
