Search code examples
artificial-intelligencetic-tac-toeminmax

How can i extract my best move from Min Max in TicTacToe?


        int minmax(Board game, int depth)
        {
            if (game.IsFinished() || depth < 0)
                return game.Score(game.Turn);

            int alpha = int.MinValue + 1;
            foreach (Point move in game.Generate_Moves())
            {
                Board currentBoard = game;
                currentBoard.Do_Move(move); 

                alpha = max(alpha, -minmax(currentBoard, depth-1));
                currentBoard.Undo_Move(move);
            }

            return alpha;
        }

The thing is that this little function tells me if the game is a win, a lose or a draw, but how can i get the move that will led me to a win? My Point class is a simple Class With 2 coordinates X, Y and i want to get the answer as a point so i can latter say something like game.Do_Move(myPoint).

In case some functions aren't obvious:

game.IsFinished() - returns true if win/lose/draw else otherwise

game.Score(turn) - returns -1/0/1 in case is a lose/draw/win for the player with the next move

game.Generate_Moves() - returns a List with available moves

game.Do_Move() - void that applies the move to game

game.Undo_Move() - talks for itself


Solution

  • It would be enough if the minimax function which gets called on the root node of the game tree returns both, the choosen move and the score. For all other nodes of the game tree, the function needs only to return the score. Thus the usual way is to implement two slightly different minimax functions – Look at Note #2 in the description to this NegaMax Framework.
    Applied to your minimax interface you would have following additional function:

    int minimaxWithMove(Board game, int depth, Point& choosen)
    {
        assert (!game.IsFinished() && depth > 0); // not possible at root node
        int alpha = int.MinValue + 1;
        foreach (Point move in game.Generate_Moves())
        {
            Board currentBoard = game;
            currentBoard.Do_Move(move);
            int score = -minmax(currentBoard, depth-1);
            if (score > alpha)
            {
                alpha = score;
                choosen = move;
            }
        }
        return alpha;
    }
    

    Note that I have removed the call to Undo_Move as it is not needed because you make a copy of game in each iteration.