What's wrong with my minimax tactacto algorithm

Question

I create a game with tic tac toe for fun. I built a minimax algorithm to return the optimal move for the computer, but somehow I get it wrong and get a 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, and not cut the player. My code is trying to recursively flip the flop between turns in all possible games, summing up the score for every win or loss that the turn may lead, and then returns the move with the maximum score. A printout is an estimate of each turn before it is made (you can see that it chooses the highest), so why don't I turn 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; } 

Answer 1

The concept of the minmax algorithm is to “minimize maximum loss” ( Wikipedia ), so the first thing that’s wrong with your algorithm is your amount.

For any state S game and for any movement M avaialble for the current player (for example, player 1 P1 ), the value minmax (S + M, P2) is the maximum possible output for P2 if P1 plays M Therefore, if P1 wants to maximize his chance of winning, he should minimize the maximum output for P2 , i.e. Must find a minimum for exits.

In tictactoe minmax, you can test the entire game (no more than 9 moves), which means that you are always now, if PX win (1), lose (-1) or draw (0). Thus, minmax (state, PX) will return only one of these three values.

In many games you cannot play the whole game (for example, drafts), so the return value is an indication of the state, for example +oo if you lose, +oo if you win, otherwize the difference between your number of projects and your opponent.

Answer 2

As far as I understand, when implementing compMoveScoreRecursive recursively calculated score is added through

 score += compMoveScoreRecursive(boardCopy, dimension, i, j, nextTurn); 

instead of maximizing or minimizing the value. However, the value to be returned must be maximized while minimizing, depending on the argument to turn , which is also the reason that this approach is called MinMax.

Answer 3

It looks like the concept of your algorithm is wrong. Based on how you described it, you are considering each line of the game, rather than assuming that the opponent is going to make the right move. Because of this, the fact that the opponent can win with the next move has very little weight, because you also consider all the options offered by the other 4 moves (despite the fact that they obviously will never be made). You will need to refine your algorithm in order to correctly execute min-max and not search for the entire set of board states.