How can I make this minimax algorithm work perfectly

Question

I've been trying to implement minimax(negamax) C# algorithm in a tic-tac-toe game, unity3d, It works very well in an almost terminal state(about 2pieces from each player pre-placed on the board on start), I just cant get it to make perfect decisions from an empty board on start.

//recursive function call
internal AIMove GetBestMove(char[] board, char player)
{
    // testboard = board;
    AIMove bestMove = null;

    for (int i = 0; i < moveTile.emptyPoints.Count; i++)
    {
        AIMove move = new AIMove();
        move.point = System.Convert.ToInt32(moveTile.emptyPoints[i].name);

        board[System.Convert.ToInt32(moveTile.emptyPoints[i].name)] = player == GameManager.Player2Piece ? GameManager.Player2Piece : GameManager.Player1Piece; // If player is O use O else use X

        var rv = CheckVictorySim(board, player, System.Convert.ToInt32(moveTile.emptyPoints[i].name));
        // print(rv);

        if (rv == 10) //AI wins
        {
            move.score = 1;
        }
        else if (rv == -10) // AI loses
        {
            move.score = -1;
        }
        else if (rv == 0) // draw
        {
            move.score = 0;
        }

        else if (rv == -1) //other
        {
            char[] newboard = new char[9]; //System.Array.Copy(umpire.board, newboard, 9); //board state
            move.score = -GetBestMove(newboard, player == GameManager.Player2Piece ? GameManager.Player1Piece : GameManager.Player2Piece).score; // if player is O use X else use O
        }

        if (bestMove == null || move.score > bestMove.score)
        {
            bestMove = move;
        }
        //aiMoves.Add(bestMove);
        print(bestMove.point);
    }


    //return the best move
    return bestMove;
}

kindanoob kindanoob · Accepted Answer · 2018-07-15T21:21:07

I think one problem is that you're passing an empty (just created) board to the recursive call of GetBestMove:

char[] newboard = new char[9];
move.score = -GetBestMove(newboard, /*other args*/)

So basically all information about previous moves that happened on the board is lost. You should call the GetBestMove function with the copy of actual board.

Another thing is that once you've set

move.point = System.Convert.ToInt32(moveTile.emptyPoints[i].name);

you can use move.point instead of System.Convert.ToInt32(moveTile.emptyPoints[i].name) where it is appropriate to avoid repetition and to make your code more readable.

How can I make this minimax algorithm work perfectly

1 Answers