The problem is that you are always returning the move from the deepest level. In the lines where you check if you have improved
, you should set bestMove
to contain the coordinates i
and j
, not the coordinates from the move one level deeper, namely result
.
Java TicTacToe MiniMax Recursively AI
Question
I'm currently working on an Android App containing TicTacToe with an AI opponent. I've come real far, but for some reason not all moves the opponent calculates are leading him to victory or a tie. I've made a recursive MiniMax algorithm (no pruning yet), and I hope somebody is able to see what's wrong here, since I really couldn't find it. I've drawn many trees so far and I've done a lot of debugging in Eclipse ADE and every step seems to be right, but in the end, it's obviously not.
So here's my function:
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
}
}
As you can see, this function calls itself directly, using middle recursion. It also calls the checkWinner function, which has 4 possible outcomes: 0 if nobody has won yet and the board is not filled, 1 if player 1 (you) has won, 2 if player 2 (AI) has won and 3 if it's a tie (and thus the board is filled).
So yea, I hope somebody finds the solution :D Thanks in advance!
No correct solution
OTHER TIPS