2
$\begingroup$

tl;dr What does the Minimax algorithm do when all its options are the same?

Consider this Minimax tree: (Green means the ends, orange minimize, blue maximize) enter image description here (Source: Myself)

Imagine this is the tree for a game (tic-tac-toe, maybe?). What should the computer do? Pick one at random? Pick the one which on average has the best score (the second one)?

Background

I'm making a program to play Quoridor, and I figure that the Minimax algorithm is the best choice (with some pruning of the really bad ones; otherwise, it would be way too big). The problem is, every choice you can make (the beginning ones in particular) have a chance to loose, and every loss has the same value (-1). So how can I pick the best moves, if all the options are the same?

Improve this question
$\endgroup$
  • $\begingroup$ I don't know Quoridor, but usually you would have an evaluation function more granular than just win, loss, draw. For example, when I wrote minimax for tic-tac-toe, I valued one in a row at 1, two in a row at 2, three in a row at 300, and negative values for the opponent; the value of a board was the sum of all the row values. That significantly reduces this problem. You do still end up with ties, but they'll be smaller ties, and you can just pick the first move or pick at random. $\endgroup$ – tsleyson Feb 27 '16 at 7:48
  • 1
    $\begingroup$ The raw minimax is just win / loose as you explore the whole tree. After all, if you have a way to win what more do you need ? Most of the time, it's not possible to apply it (the tree being too big) and you do alpha-beta pruning or similar methods that require an heuristic, and therefore more fine-grained value. Even with raw minimax however, you may want to favour shorter path to winning (shorter play) or higher chances to win (in the drawing, the second case: 2 win out of 3). Or if it's to play against a human, insert randomness so that the games are not always the same. $\endgroup$ – Colin Pitrat Feb 27 '16 at 14:17
  • $\begingroup$ To agree with Colin -- In chess, a computer that knows it is losing will try to last as many moves as possible before checkmate; a computer that knows it is winning will try to win in as few moves as possible. If all options are really the same, I'd suggest randomness just so the human player doesn't get bored. $\endgroup$ – usul Feb 27 '16 at 14:35
4
$\begingroup$

Shaull's answer is absolutely correct, and by referring Zermelo's theorem it is pointing in the right direction.

However, beyond the observations done on the rationality of your opponent, the point here is that Minimax is pretty good for strategical games where a single mistake could lead to a disaster, e.g., chess ---where just overlooking a single move can lead to checkmate. On the other hand, if no such strategical flaws are likely (e.g., Omweso and I think Quoridor also to some extent) then Monte-Carlo sampling is a much better option.

For a thorough study on the topic, see:

Raghuram Ramanujan and Bart Selman. Trade-Offs in Sampling-Based Adversarial Planning. Proceedings of the Twenty-First International Conference on Automated Planning and Scheduling. Freiburg, Germany, 2011.

(which was actually awarded a honorable mention for best student paper). In this case, the purpose of such algorithm is to follow good lines of action instead of preventing a loss. Monte-Carlo sampling is also the best option to use in case your branching factor is too large (so that minimax and any of its variants such as alpha-beta become infeasible), e.g., Go.

Be aware however, that one of the options used much often in Monte-Carlo sampling, UCT, does not seem to be so good in the end. For a good discussion on the topic, see:

Carmel Domshlak, Zohar Feldman. To UCT, or not to UCT?. Proceedings of the Sixth Annual Symposium on Combinatorial Search. Leavenworth, Washington, USA, 2013.

Hope this helps,

Improve this answer
$\endgroup$
  • $\begingroup$ Happy to hear you like it! by the way, I think that previous work on hexagon might help you in Quoridor, keep an eye on it! $\endgroup$ – Carlos Linares López Feb 27 '16 at 19:49
3
$\begingroup$

By Zermelo's theorem, which can itself be thought of as a version of minimax, each such game has a winning strategy for one of the players (or a strategy to force a draw).

Thus, if your algorithm encounters a node with all its children having the same value, then conceptually it doesn't matter which option you take, you are guaranteed to get the value of that node.

Having said that, the minimax algorithm computes an optimal strategy against an optimal, rational, opponent. If your opponent is assumed to be "human" (i.e. might be irrational, misinformed, computationally bounded, or plain stupid), then you can perhaps do better than just running minimax. Then, you should consider incorporating heuristics, randomness, etc.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.