c# - Tic-Tac-Toe minimax algorithm - Stack Overflow

admin管理员组

文章数量:1296883

I have been trying to implement a minimax algorithm for Tic-Tac-Toe based off some of my University lectures.

There are two states after the first move has been made that both have a minimax value of 0 according to my algorithm, although I know that one is more favourable, the bot does not. I've tried tweaking it to make it so that losses are heavily penalised but that has no effect.

I'm unsure if my algorithm is maybe just incorrect. I was wondering if there are ways to test the minimax value of any given Tic-Tac-Toe state.

The minimax value of state:

X . O
. . .
. . .

...is equal to 0

and the value of state:

X . .
. O .
. . .

...is also equal to 0

Here X plays first, and O is played by the bot. +10 for a win, 0 for a draw, and -10 for a loss.

However, when playing against the bot the first outcome (which is what my bot produces) is possible to be beaten 100% of the time, whereas the second state (not produced as there is no apparent reason to favour it) would set it up to be able to always win or draw and should therefore be picked.

Algorithm used:

private int minimaxValue(BoardTree state, bool minimising)
{
    // Minimise means opt for lowest score, noughts win = +10, draw = 0, cross win = -10
    if (state.successiveMoves.Count == 0)
    {
        if (state.Board.gameDrawnFlag) return DRAW_VAL;
        switch (state.Board.winner)
        {
            case TicTacToeBoard.Player.Cross: return LOSE_VAL;
            case TicTacToeBoard.Player.Nought: return WIN_VAL;
        }
    }
    
    if (minimising)
    {
        int lowestValue = minimaxValue(state.successiveMoves[0], !minimising); // Get an initial value
        
        for (int i = 1; i < state.successiveMoves.Count; i++) 
        {
            int val = minimaxValue(state.successiveMoves[i], !minimising); // Check each state, maximised this time
            if (val < lowestValue)
            {
                lowestValue = val; // Find the lowest value from the list
            }
        }
        
        return lowestValue;
    }
    else // Maximising
    {  
        int highestValue = minimaxValue(state.successiveMoves[0], !minimising); // Initial base comparison value

        for (int i = 1; i < state.successiveMoves.Count; i++)
        {
            int val = minimaxValue(state.successiveMoves[i], !minimising); // Check each state, minimised this time
            if (val > highestValue)
            {
                highestValue = val;
            }
        }
        
        return highestValue;
    }
}

本文标签： cTicTacToe minimax algorithmStack Overflow