Question

        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

Was it helpful?

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.

OTHER TIPS

You need to apply the minimax theorem.

You basically have to make a game tree, where each node in the tree is a board position, and each child is the result of a legal move. The leaf nodes (where the game is ended) will have scores according to game.score(), and one player is trying to pick moves down a path leading to a high score, while the other is trying to pick moves that force a low score. The theorem will help you see how to apply that idea, rigorously.

Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow
scroll top