Застрял на алгоритме minmax с альфа-бета-обрезкой
Я пытаюсь реализовать алгоритм minmax с альфа-бета-отсечкой в игре Tic Tac Toe в Java. Когда я заканчиваю кодировать его, я сразу же обнаружил исключение ArrayIndexOutOfBounds поэтому я попытался поставить некоторые выходные данные терминала, чтобы найти ошибку самостоятельно, и обнаружил, что она была вызвана неверным результатом в конечном возвращении: алгоритм наконец возвращает [-1][-1] со счетом -2147483646 и это вызывает исключение, когда остальная часть кода пытается сделать ход и поместить координаты в поле. Я создал схему для имитации некоторых ходов и возможного дерева, но не могу найти ошибку.
/*
* int field[][] is the board array, it may contains 0(empty), 1(opponent's seed), 2(computer's seed)
* nComputer = 2 (computer's seed)
* nPlayer = 1 (opponent's seed)
* computerMove = new int[3]
* remainingMoves has been calculated before the main call
*/
// Main call
computerMove = cMove(remainingMoves, nComputer,Integer.MIN_VALUE + 1, Integer.MAX_VALUE - 1);
field[computerMove[1]][computerMove[2]] = nComputer; // This line cause the exception!!
// MinMax alpha-beta pruning algorithm
private static int[] cMove(int depth, int player, int alpha, int beta) {
int[][] moveList = new int[3][10];
moveList = generateMoves(field); // See below for details
int temp;
int score;
int bestR = -1;
int bestC = -1;
// check function retunrns 1(opponent wins), 2(computer wins), 0(draw) or -1(nothing)
if(moveList[0][0] == 0 || depth == 0) {
score = cScore(player);
return new int[] { score, bestR, bestC };
} else {
for (int i = 1;i < moveList[0][0]; i++) {
// Trying to make a move
field[moveList[1][i]][moveList[2][i]] = player;
if(player == nComputer) { // Maximazing player
score = cMove(depth -1, nPlayer, alpha, beta)[0];
if(score > alpha) {
alpha = score;
bestR = moveList[1][i];
bestC = moveList[2][i];
}
} else { // Minimizing player
score = cMove(depth -1, nComputer, alpha, beta)[0];
if(score < beta) {
beta = score;
bestR = moveList[1][i];
bestC = moveList[2][i];
}
}
field[moveList[1][i]][moveList[2][i]] = 0; // Undo move
if(alpha >= beta) i = 10; // Cut-off
}
if(player == nComputer) temp = alpha;
else temp = beta;
return new int[] { temp, bestR, bestC };
}
}
/*
* generateMoves function returns an array 3x10 where [0][0] is the number
* of possible moves and [0,1,2][1-9] are the score and the
* coordinates(rows and columns) of all the possible moves
*/
private static int[][] generateMoves(int[][] field) {
int[][] result = new int[3][10];
int k = 0;
if(check(4) != -1) {
return result;
}
for (int i = 0; i < field.length; i++) {
for (int j = 0; j < field[0].length; j++) {
if (field[i][j] == 0) {
k++;
result[1][k] = i;
result[2][k] = j;
}
}
}
result[0][0] = k;
return result;
}
// cScore function assign a score for the actual node with an heuristic evaluation
private static int cScore(int p) {
int score = 0;
score += cRow(p, 0, 0, 0, 1, 0, 2);
score += cRow(p, 1, 0, 1, 1, 1, 2);
score += cRow(p, 2, 0, 2, 1, 2, 2);
score += cRow(p, 0, 0, 1, 0, 2, 0);
score += cRow(p, 0, 1, 1, 1, 2, 1);
score += cRow(p, 0, 2, 1, 2, 2, 2);
score += cRow(p, 0, 0, 1, 1, 2, 2);
score += cRow(p, 0, 2, 1, 1, 2, 0);
return score;
}
private static int cRow(int player, int rOne, int cOne, int rTwo, int cTwo, int rThr, int cThr) {
int score = 0;
if (field[rOne][cOne] == nComputer) {
score = 1;
} else if (field[rOne][cOne] == nPlayer) {
score = -1;
}
if (field[rTwo][cTwo] == nComputer) {
if (score == 1) {
score = 10;
} else if (score == -1) {
return 0;
} else {
score = 1;
}
} else if (field[rTwo][cTwo] == nPlayer) {
if (score == -1) {
score = -10;
} else if (score == 1) {
return 0;
} else {
score = -1;
}
}
if (field[rThr][cThr] == nComputer) {
if (score > 0) {
score *= 10;
} else if (score < 0) {
return 0;
} else {
score = 1;
}
} else if (field[rThr][cThr] == nPlayer) {
if (score < 0) {
score *= 10;
} else if (score > 1) {
return 0;
} else {
score = -1;
}
}
return score;
}
Я застрял на этой проблеме в течение одной недели, и я схожу с ума! Спасибо заранее и извините за плохой английский, но это не мой основной язык, и я медленно пытаюсь выучить его
-------------------------------------------------- ---------------РЕДАКТИРОВАТЬ---------------------------------- --------------------------
Добавление функции проверки по запросу:
// check function first check the state of 5 cells that needs to be filled to won([0,0][0,1][0,2][1,0][2,0])
public static int check(int nMove) {
int state = -1;
if(field[0][0] != 0) {
state = col(0,1);
if(state == 1 || state == 2) return state; // Win on first col
state = row(0,1);
if(state == 1 || state == 2) return state; // Win on first row
state = diagonal(1);
if(state == 1 || state == 2) return state; // Win on first diagonal
}
if (field[0][1] != 0) {
state = col(1,2);
if(state == 1 || state == 2) return state; // Win on second col
}
if (field[0][2] != 0) {
state = col(2,3);
if(state == 1 || state == 2) return state; // Win on third col
state = diagonal(2);
if(state == 1 || state == 2) return state; // Win on second diagonal
}
if (field[1][0] != 0) {
state = row(1,2);
if(state == 1 || state == 2) return state; // Win on second row
}
if (field[2][0] != 0) {
state = row(2,3);
if(state == 1 || state == 2) return state; // Win on third row
}
if(nMove == 8) return 0; // Draw
return state;
}
// Check if the entire row is filled (check rows from starting to n points)
private static int row(int start, int n) {
int s = -1;
int k = 0;
int h = 0;
for (int i = start; i < n; i++) {
for (int j = 0; j < (field[0]).length; j++) {
if(field[i][j] == 1) {
k++;
if(k==3) s = 1;
} else if(field[i][j] == 2) {
h++;
if(h==3) s = 2;
}
}
k=0;
h=0;
}
return s;
}
// Check if the entire col is filled (check cols from starting to n points)
private static int col(int start, int n) {
int s = -1;
int k = 0;
int h = 0;
for (int i = start; i < n; i++) {
for (int j = 0; j < (field).length; j++) {
if(field[j][i] == 1) {
k++;
if(k==3) s = 1;
} else if(field[j][i] == 2) {
h++;
if(h==3) s = 2;
}
}
k=0;
h=0;
}
return s;
}
// Check if the entire diagonal is filled (check first diagonal if n=1 and second diagonal if n=2)
private static int diagonal(int n) {
int s = -1;
int k = 0;
int h = 0;
if(n == 1) {
for (int i = 0; i < (field).length; i++) {
int j = i;
if(field[i][j]== 1) {
k++;
if(k==3) s = 1;
} else if(field[i][j] == 2) {
h++;
if(h==3) s = 2;
}
}
} else if (n == 2) {
int j = 2;
for (int i = 0; i < (field).length; i++) {
if(field[i][j] == 1) {
k++;
if(k==3) s = 1;
}
else if(field[i][j] == 2) {
h++;
if(h==3) s = 2;
}
j--;
}
} else { }
return s;
}
1 ответ
Если предположить, что ваша доска больше, чем 3x3, в противном случае тик-тук-тое с 4 в качестве условия выигрыша не имеет особого смысла, ваше исключение будет вызвано здесь:
for (int i = 0; i < field.length; i++) {
for (int j = 0; j < field[0].length; j++) {
if (field[i][j] == 0) {
k++;
result[1][k] = i; // out of bounds
result[2][k] = j; // out of bounds
}
}
}
Для поля размером A x B, когда доска пуста, k станет большим как A*B - 1, За A = B = 7 это станет 48, что больше 9, что является максимальным индексом, разрешенным в result[i],
// ======================= РЕДАКТИРОВАТЬ ======================== =========
Я немного запутался и не уверен, что вы пытаетесь оптимизировать (лучший результат для компьютера или плеера?), Но я нашел кое-что, что объясняет результат.
В каждом рекурсивном вызове у вас есть переменная player,
В зависимости от его значения вы обновляете alpha или же beta,
В конце рекурсивного шага вы возвращаетесь alpha или же beta основанный на значении player,
Но вы обновляете alpha если player == 2
if(player == 2) { // Maximazing player
score = cMove(depth -1, nPlayer, alpha, beta)[0];
if(score > alpha) {
Но вернуть beta если player == 2
if(player == 1) temp = alpha;
else temp = beta;
Так ты всегда возвращаешься MIN_VALUE + 1 за alpha или же MAX_VALUE - 1 за beta,
Therefor if(score < alpha) { или же if(score < beta) { всегда будет ложным для каждого шага, который не вызывает базовый случай. Ваша рекурсия выглядит примерно так:
- глубина = 4, глубина вызова = 3
- глубина = 3, глубина вызова = 2
- глубина = 2, игрок1 выиграл, счет 42
- глубина = 3, обновление альфа = 42, возврат бета =
MAX_VALUE - 1как оценка
- глубина = 3, глубина вызова = 2
- глубина = 4, call3 вернулся
MAX_VALUE - 1что моя бета, так что ничего не изменилось,bestRа такжеbestCостаться -1