Optimal for MIN in minimax
In the minimax algorithm, the first player plays optimally, which means that he wants to maximize his result, and the second player tries to minimize the chances of the first player to win. Does this mean that the second player is also playing optimally to win the game? Is trying to choose a path to minimize the chances of the first player winning is also trying to win?
I am actually trying to solve this problem from topcoder: EllysCandyGame
I wonder if we can apply the minimax algorithm here. But I do not know if the second player will try to minimize the result of the first player, he will play optimally at the same time. Also, I would like to get a mathematical proof of the correctness if possible. This “play as optimal” statement really confuses me, and I would like some advice on such issues if there is a general idea. Thank.
source to share
Yes, you can use the minimax algorithm here.
The issue statement states that the winner of the game is "the girl with the most candy at the end of the game." Thus, one sensible scoring function you can use is the difference in the number of candies held by the first and second player.
Does this mean that the second player is also playing optimally to win the game?
Yes. When you rate the MIN level, the MIN player will always choose the path with the lowest score for the MAX player.
Note. MIN and MAX levels can be implemented using the same code if you rate each node from the point of view of the player making a move in that round and convert the ratings between levels. If the score is the difference in the number of candies, you can simply deny it between levels.
Is trying to choose a path to minimize the chances of the first player winning is also trying to win?
Yes. The second player tries to minimize the score of the first player. A reasonable scoring feature will give the first player a lower loss score than a tie.
I wonder if we can apply the minimax algorithm here.
Yes. If I read the problem correctly, the number of levels will equal the number of boxes. If there is no limit on the number of boxes, you will need to use n-move lookahead, evaluating the nodes of the minimax tree to their maximum depth.
source to share
Game properties:
- Each point has a limited, well-defined number of moves (choosing one of the non-empty squares)
- The game ends after a finite number of moves (when all boxes are empty)
As a result, the search tree consists of a finite number of leaves. You are correct that with Minimax you can find the best move.
Please note that you should only evaluate the game at the end positions (when there are no more moves). At this point, there are only three outcomes: The first player wins, the second player wins, or is it a draw.
Note that the standard Minimax algorithm has nothing to do with probabilities. The result of the Minimax algorithm determines the ideal game for both sides (provided that both sides do not make mistakes).
By the way, if you need to improve your search algorithm, a safe and easy optimization is to apply alpha-beta cropping .
source to share