Using the min-max algorithm to value game states

Say we want to work out the best move in a zero sum, deterministic, perfect information game. How can we do this? Well, first off, given that we have perfect information, we know exactly what moves are available to us. Given that the game is deterministic, we know exactly what state the game will change to due to each of those moves. The same is then true for the opponent's move as well; we know exactly what possible moves they have and how the state would look as a result of each of those moves.

One approach for finding the best move would be to construct a full tree of every possible move for each player at each state until we reach a state where the game is over. This end state of the game is also known as the terminal state. We can assign a value to this terminal state; a win could carry the value 1, a draw 0, and a loss -1. These values reflect the states' desirability to us. We would prefer a win than a draw and a draw to a loss. Figure...