Tic Tac Toe game with minimax algorithm c#

Question

I'm trying to implement tic tac toe game with minimax algorithm in c# but I couldn't set up the minimax algorithm correctly. To give an example of one of the cases where the algorithm works incorrectly:

When I put "O" to 1,1 position it has to put x at 2,1 position to prevent me from winning but it puts "X" in the 1,0 position and lets me win.

My code is like this:

public static void AIMove(int[,] board)
{
            int bestScore = int.MinValue;

            for (int i = 0; i < board.GetLength(0); i++)
            {
                for (int j = 0; j < board.GetLength(1); j++)
                {
                    if (board[i, j] == -1)
                    {
                        board[i, j] = 1;
                        //call minimax for player move
                        var score = MiniMax(board, 0, 0);
                        scores.Add(score); //To see the returned values from the minimax algorithm
                        board[i, j] = -1;

                        if (score > bestScore)
                        {
                            bestScore = score;
                            //store index values of new best score
                            index[0] = i;
                            index[1] = j;
                        }
                    }
                }
            }

            //set 1 bestScore position in board
            board[index[0], index[1]] = 1;
        }

        public static int MiniMax(int[,] board, int turn, int depth)
        {
            //turn 1 means ai turn, get a min value otherwise player turn get a max value
            int bestScore = turn == 1 ? int.MinValue : int.MaxValue;

            for (int i = 0; i < board.GetLength(0); i++)
            {
                for (int j = 0; j < board.GetLength(1); j++)
                {
                    // check position is available
                    if (board[i, j] == -1)
                    {
                        //set it to 1 if it's the month's turn and 0 if it's the player's turn
                        board[i, j] = turn;
                        var score = MiniMax(board, 1 - turn, depth + 1);
                        board[i, j] = -1;
                        bestScore = turn == 1 ? Math.Max(bestScore, score) : Math.Min(bestScore, score);
                    }
                }
            }

            if (turn == 1)
                return CheckWinner(board) - depth;
            else
                return CheckWinner(board) + depth;
        }

        public static int CheckWinner(int[,] board)
        {
            int[] results = { board[0, 0],board[0,1],board[0,2],
            board[0, 1],board[1,1],board[2,1],
            board[1, 0],board[1,1],board[1,2],
            board[2, 0],board[2,1],board[2,2],
            board[0, 0],board[1,1],board[2,2],
            board[0, 2],board[1,1],board[2,0],};

            for (int i = 0; i < results.Length; i += 3)
            {
                if (results[i] == 0 & results[i + 1] == 0 & results[i + 2] == 0)
                    return -10;
                else if (results[i] == 1 & results[i + 1] == 1 & results[i + 2] == 1)
                    return 10;
            }

            return 0;
        }
}

I put them in a list to see the values returned from the minimax algorithm as below, when I looked inside the list, I saw that only 0 returned from the minimax algorithm.

I couldn't understand what is wrong in my code, I need help.

Answer 1

If it was a perfect AI then its' second move would have been the bottom left, forcing you into a loss. The game goes like this (where -O- represents forced moves):

 X |   |        X | O |        X | O |        X | O |        X | O |        X | O |-O-     X | O |-O-
---+---+---    ---+---+---    ---+---+---    ---+---+---    ---+---+---    ---+---+---    ---+---+---
   |   |          |   |          |   |       -O-|   |       -O-| X |       -O-| X |       -O-| X |   
---+---+---    ---+---+---    ---+---+---    ---+---+---    ---+---+---    ---+---+---    ---+---+---
   |   |          |   |        X |   |        X |   |        X |   |        X |   |        X |   | X 

(Which incidentally is why you never play a side next to an opening corner.)

Instead your AI is just selecting the first available space that comes up in the scan because your scoring is not working at all. Here are a few reasons why this is happening:

1. You're not stopping at the win condition during your recursive search.
2. You're finding the best score, then ignoring it.
3. MiniMax does a bunch of work, then just returns the win score for the current board.

If you fix that you'll have a slightly more functional AI... but it'll still fall apart against a perfect opponent because:

4. The path with the highest score for you is going to depend on your opponent making mistakes.

That's a lot harder to address. If you have a path that leads to a win in one turn if and only if your opponent makes a bad move, that will likely get selected over a move that wins the game in two turns against a skilled opponent, because the scoring isn't attempting to figure out what move is likely to be made, only what moves result in wins/losses.

If you assume that your opponent is going to play perfectly you will maybe occasionally pick the wrong move, but most often you'll get it right. Rather than scoring on every possible path, have each recursion level pick only the top scoring move or moves for each side.

Also, add some shortcuts. In the game layout above, every move you make after the first error are forced. Choosing any other move loses the game for you. So make your scoring aware of forces and future options:

• If you can win this turn, return immediately with max value.
• If you can make multiple potential rows (a fork), do that at lower value.
• Finally, do a recursive scan for win conditions further down the tree.

Make sure that your weighting doesn't let a potential fork take precedence over blocking an opponent's win. It doesn't help you to have multiple win options after your opponent has already ended the game.