Minmax Tree

Overview

A Minmax (a.k.a. Minimax) Tree is a tree data structure that is meant to represent a two-sided game where each row represents alternating choices between each side back-and-forth from the root, all the way to the very bottom (unless the tree is infinite). Each node has N branches that represent N possible choices. As these opponents alternate sides, their goal is officially to select the next node with the maximum or minimum value (depending on the side) at each turn. These minimum and maximum values (for each side) correspond to state changes in the game that would be either productive or counterproductive for the side that is making the choice (for their turn/row).

The value given each choice depends on the game. A game like chess has an average of 35 branches for each turn. The values for each choice correspond to:

Possession of board pieces (where each piece has a different value).
Mobility available to each piece (where each piece’s mobility has a different value).
Protection provided to each piece — meaning that if a piece were captured, there would be some repercussion to the other side through a capture (this value can be complex and turn into a tree of possibilities that has its own evaluation mechanism).
Threats to the other side (of their pieces being captured — different value for each piece).
Threats from the other side (this value would be negative for the maximum side, and it would be positive for the minimum side).

Approaches

It was mentioned in the Overview that the goal of Minmax Trees is officially (i.e. by the book) to select either the absolute minimum or the absolute maximum at each turn for each side. This approach is greedy. It is not forward looking as it selects the best next choice.

If the tree does have an end (i.e. it’s not infinite), then the optimal approach is to make decisions (even if they are not good in the short term) that bring you closer to groups (i.e. clusters) of tail (i.e. end) nodes that are positive for your side. However, if the game is one where it’s not a simple win/loss and there is a magnitude to wins and losses, then taking riskier paths could make sense. Simulations need to be run to properly weigh the risk vs reward.

In very complex games where future nodes are not determined from the start of the game, you influence the existence of those future nodes through your choices along the way. It is possible for negative short-term choices to have surprising long-term benefits. Your heuristics are responsible for guiding the way.

It’s important to note that half of the movements down a Minmax tree belong to the opponents, so being informed to the decisions they are likely to take provides a huge benefit. If an opponent always takes the greedy optimal choice, then this information can be used to inform your choices to help traverse to a location of the tree that has the best chance of winning. Similarly, if an opponent’s choices follow choice that is an equal magnitude to yours in the opposite direction, then this can also be incorporated into a heuristic that guides you to your goal.

An opponent’s unpredictability can result in your suboptimal choices if their past choices are used to guide yours, yet something suddenly changes. However, even unpredictability can typically be modeled to have some predictability using machine learning techniques.

If you ever find yourself in a position where all the available choices in a turn benefit the opponent (or vice versa), then the game could already be over. However, comebacks are always possible, and it’s important to be vigilant until the very end — if the game does have an end.

Conclusion

Minmax Tree algorithms are a fun way to experiment with artificial intelligence.

To be updated after running simulations to gain data from benchmarks.

A section has been temporarily omitted. Looking forward to sharing it.

Author

Sam Malayek works in Vancouver, using this space to fill in a few gaps. Opinions are his own.