CODEWITHSUNDEEP
artificial-intelligenceminimax
LearningMath
LearningMath

Reputation: 861

Does the min player in the minimax algorithm play optimally?

In the minimax algorithm, the first player plays optimally, which means it wants to maximise its score, and the second player tries to minimise the first player's chances of winning. Does this mean that the second player also plays optimally to win the game? Trying to choose some path in order to minimise the first player's chances of winning also means trying to win?

I am actually trying to solve this task from TopCoder: EllysCandyGame. I wonder whether we can apply the minimax algorithm here. That statement "both to play optimally" really confuses me and I would like some advice how to deal with this type of problems, if there is some general idea.

Upvotes: 3

Views: 2668

Answers (2)

Andy Thomas
Andy Thomas

Reputation: 86381

Yes, you can use the minimax algorithm here.

The problem statement says that the winner of the game is "the girl who has more candies at the end of the game." So one reasonable scoring function you could use is the difference in the number of candies held by the first and second player.

Does this mean that the second player also plays optimally to win the game?

Yes. When you are evaluating a MIN level, the MIN player will always choose the path with the lowest score for the MAX player.

Note: both the MIN and MAX levels can be implemented with the same code, if you evaluate every node from the perspective of the player making the move in that round, and convert scores between levels. If the score is a difference in number of candies, you could simply negate it between levels.

Trying to choose some path in order to minimize the first player's chances of winning also means trying to win?

Yes. The second player is trying to minimize the first player's score. A reasonable scoring function will give the first player a lower score for a loss than a tie.

I wonder whether we can apply the minimax algorithm here.

Yes. If I've read the problem correctly, the number of levels will be equal to the number of boxes. If there's no limit on the number of boxes, you'll need to use an n-move lookahead, evaluating nodes in the minimax tree to a maximum depth.

Upvotes: 2

Philipp Claßen
Philipp Claßen

Reputation: 43970

Properties of the game:

  • At each point, there are a limited, well defined number of moves (picking one of the non-empty boxes)
  • 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 leafs. You are right that by applying Minimax, you can find the best move.

Note that you only have to evaluate the game at the final positions (when there are no more moves left). At that point, there are only three results: The first player won, the second player won, or it is a draw.

Note that the standard Minimax algorithm has nothing to do with probabilities. The result of the Minimax algorithm determines the perfect play for both side (assuming that both sides make no mistakes).

By the way, if you need to improve the search algorithm, a safe and simple optimization is to apply Alpha Beta pruning.

Upvotes: 0

Related Questions