Tic-Tac-Toe をプレイする AI を作成する必要がある人工知能クラスを受講しています。
インストラクターは、AI が次の動きを出すときに、AI の意思決定プロセスにアルファ ベータ プルーニングを使用するように指定しました。この時点で私が直面している問題は、AI が意思決定ツリーを作成して移動するのにかかる時間です。通常の 3x3 は問題なく、3x4 と 4x3 は少し時間がかかりますが、4x4 は最初の移動に数分かかります。
私が使用したソースコード：
/** Get next best move for computer. Return int[2] of {row, >col} */
@Override
int[] move() {
int[] result = minimax(2, mySeed, Integer.MIN_VALUE, >Integer.MAX_VALUE);
// depth, max-turn, alpha, beta
return new int[] {result[1], result[2]}; // row, col
}
/** Minimax (recursive) at level of depth for maximizing or >minimizing player
with alpha-beta cut-off. Return int[3] of {score, row, col} >*/
private int[] minimax(int depth, Seed player, int alpha, int >beta) {
// Generate possible next moves in a list of int[2] of {row, >col}.
List<int[]> nextMoves = generateMoves();
// mySeed is maximizing; while oppSeed is minimizing
int score;
int bestRow = -1;
int bestCol = -1;
if (nextMoves.isEmpty() || depth == 0) {
// Gameover or depth reached, evaluate score
score = evaluate();
return new int[] {score, bestRow, bestCol};
} else {
for (int[] move : nextMoves) {
// try this move for the current "player"
cells[move[0]][move[1]].content = player;
if (player == mySeed) { // mySeed (computer) is >maximizing player
score = minimax(depth - 1, oppSeed, alpha, beta)[0];
if (score > alpha) {
alpha = score;
bestRow = move[0];
bestCol = move[1];
}
} else { // oppSeed is minimizing player
score = minimax(depth - 1, mySeed, alpha, beta)[0];
if (score < beta) {
beta = score;
bestRow = move[0];
bestCol = move[1];
}
}
// undo move
cells[move[0]][move[1]].content = Seed.EMPTY;
// cut-off
if (alpha >= beta) break;
}
return new int[] {(player == mySeed) ? alpha : beta, >bestRow, bestCol};
}
}
必要に応じてソースリンク
インストラクターも反復深化検索を使用することを提案しましたが、私はその方法がわからないダミーです。