I'm building a tic tac toe game for a fun learning experience. I have constructed a minimax algorithm to return the optimal move for the computer, but somehow I am going wrong and get wierd output like this
TIC TAC TOE V1.0
---
---
---
Enter row, column of your move
1,1
---
-X-
---
...
0, 0: -1038
0, 1: -1470
0, 2: -1038
1, 0: -1470
1, 2: -1470
2, 0: -1038
2, 1: -1470
2, 2: -1038
O--
-X-
---
Enter row, column of your move
1,2
O--
-XX
---
...
0, 1: -15
0, 2: -9
1, 0: -10
2, 0: -1
2, 1: -29
2, 2: -41
O--
-XX
O--
Enter row, column of your move
1,0
O--
XXX
O--
WINNER: PLAYER
You can see that the computer chose the lower left corner rather than cutting off the player. My code attempts to recursively flip flop between turns through all possible gamestates, summing up the score for each win or loss the turn may lead to, then returns the move with the maximum score. The printout is the score of each turn before it is made (you can see it chooses the highest), so why am I not cutting off the player? How can I fix this? Here is my code.
int compMoveScoreRecursive(state_t **board, int dimension, int row, int col, state_t turn) {
board[row][col] = turn;
state_t winner = checkWinner(board, dimension);
if (winner == COMPUTER) {
return 1;
} else if (winner == PLAYER) {
return -1;
} else {
int score = 0;
state_t nextTurn = turn == COMPUTER ? PLAYER : COMPUTER;
for (int i = 0; i < dimension; i++) {
for (int j = 0; j < dimension; j++) {
if (board[i][j] == NIL) {
state_t **boardCopy = copyBoard(board, dimension);
score += compMoveScoreRecursive(boardCopy, dimension, i, j, nextTurn);
destroyBoard(boardCopy, dimension);
}
}
}
return score;
}
}
move_t optimalCompMove(state_t **board, int dimension) {
move_t optMove;
int optScore = INT_MIN;
for (int row = 0; row < dimension; row++) {
for (int col = 0; col < dimension; col++) {
if (board[row][col] == NIL) {
state_t **boardCopy = copyBoard(board, dimension);
int score = compMoveScoreRecursive(boardCopy, dimension, row, col, COMPUTER);
printf("%d, %d: %d\n", row, col, score);
if (score > optScore) {
optMove.row = row;
optMove.col = col;
optScore = score;
}
destroyBoard(boardCopy, dimension);
}
}
}
return optMove;
}
The concept of the minmax algorithm is to « minimize the maximum loss » (Wikipedia), so the first thing wrong with your algorithm is your sum.
For any state S of the game, and for any move M avaialble for the current player (let's say player 1 P1), the value of minmax (S + M, P2) is the maximum possible output for P2 if P1 plays M. So if P1 wants to maximize his chance to win, he should reduce as much as possible the maximum output for P2, i.e. he must find the minimum of the outputs.
In tictactoe minmax, it is possible to test the whole game (at most 9 moves), meaning the you always now if PX win (1), lose (-1) or make a draw (0). So minmax (state, PX) will return only one of these three value.
In many game, you cannot play the whole game (draughts for example), so the returned value is an indication of the state, for instance -oo if you lose, +oo if you win, otherwize the difference between your number of draughts and your opponent.
To my understanding, in the implementation of compMoveScoreRecursive, the recursively calculated score is added via
score += compMoveScoreRecursive(boardCopy, dimension, i, j, nextTurn);
instead of maximizing or minimizing the value. However, the value to be returned shoud be maximized on minimized, depending on the argument turn, which is also the reason why the approach is called MinMax.
It seems like the concept behind your algorithm is flawed. Based on the way you described it, you're considering every single line of play, as opposed to assuming that the opponent is going to make the correct move. Because of this, the fact that the opponent can win with the next move has very little weight, because you also consider all of the options that the other 4 moves offer (despite the fact that those will obviously never be made). You'll have to refine your algorithm to properly min-max as opposed to doing a search of the entire set of board states