В настоящее время я работаю над приложением для Android, содержащим TicTacToe с противником AI. Я зашел очень далеко, но почему-то не все ходы, которые просчитывает противник, ведут его к победе или ничьей. Я сделал рекурсивный алгоритм MiniMax (пока без обрезки), и я надеюсь, что кто-нибудь сможет увидеть, что здесь не так, поскольку я действительно не мог его найти. До сих пор я нарисовал много деревьев и много отладил в Eclipse ADE, и каждый шаг кажется правильным, но, в конце концов, это явно не так.
Итак, вот моя функция:
public int[] MiniMax( int[][] gameboard, boolean isCPUTurn, int[] move, int depth ){
if (gameboard[1][1]==EMPTY) { // Always take middle if possible
int[] best = {2,1,1};
return best;
}
// Recursion base-case
int winner = checkWinner();
if ( winner == 1 || winner == 2 || winner == 3 ){ // Game is over
int[] returnSet = {-1,-1,-1}; // leeg
// adjust scores for Minimax Player<----Tie---->CPU
// 0 1 2
switch (winner){
case 1:
returnSet[0] = 0 ; // Player wins
break;
case 2:
returnSet[0] = 2; // CPU wins
break;
case 3:
returnSet[0] = 1; // TIE
break;
default: // impossible..
returnSet[0] = 1;
}
// The last move led to the end of the game, return this outcome and move
returnSet[1] = move[0];
returnSet[2] = move[1];
return returnSet;
}
// A move is still possible, the game's not over yet
else{
int[] bestMove = null; // contains the best move found for this turn
for (int i=0; i<3; i++){ // check all child nodes/boards
for (int j=0; j<3; j++){
if( gameboard[i][j] == EMPTY ) // if the spot's not yet filled
{
if (isCPUTurn) gameboard[i][j] = TWO; // this move is CPU's
else gameboard[i][j] = ONE; // this move is Player's
int[] thismove = {i,j}; // {move Row, move Column}
// recursion
int[] result = MiniMax( gameboard, !isCPUTurn, thismove, depth+1);
// result = { winner result, move Row, move Column}
gameboard[i][j] = EMPTY; // delete last move after recursion
// check if child is best option
if (bestMove == null) // first child is always the best initially
bestMove = result;
else {
if (!isCPUTurn) // for CPU, higher is better
{ if (result[0]>bestMove[0])
bestMove = result;
//if (bestMove[0]==2) return bestMove; Pruning thingy
}
else if (isCPUTurn) // for Player, lower is better
{ if (result[0]<bestMove[0])
bestMove = result;
//if (bestMove[0]==0) return bestMove; Pruning thingy
}
}
}
}
}
return bestMove; // returns the best move found after checking all possible childs
}
}
Как видите, эта функция вызывает сама себя напрямую, используя среднюю рекурсию. Он также вызывает функцию checkWinner, которая имеет 4 возможных результата: 0, если никто еще не выиграл и доска не заполнена, 1, если выиграл игрок 1 (вы), 2, если выиграл игрок 2 (ИИ) и 3, если это галстук (и, таким образом, доска заполнена).
Так что да, я надеюсь, что кто-нибудь найдет решение: D Заранее спасибо!
