The MINIMAX strategy

I have been busy reading up on the MINIMAX strategy lately so I will try to share what I have learned so far. The MINIMAX strategy can be used to find the optimal decision/move in two-player or multiplayer zero-sum games. A zero-sum game is a game there one players gain equals the other players loss. Chess for example is a zero-sum game, either you win, lose or draw, but you can't both win and lose or draw at the same time. Consider the game tree for a trivial two-player game, each player take turns marking the space in a 2x2 grid, each space in the grid represent a specific point and the player who end up with most points wins the game. Let us decide the points for each of the spaces.

Upper-left corner = 1 Upper-right corner = 2 Lower-left corner = 3 Lower-right corner = 4

So, how do we find the optimal move? Basically what we need to do is to traverse trough the whole game tree until we reach the leaves (a leaf is a node without any children), once there we use a so called utility function to calculate a numerical value for the leaf. With the utility values we can now determine the minimax values for nodes higher and higher up in the game tree as we unwinds back up to the initial state. A utility function evaluate the game state to determine how strong the position is for the player. So one player wants to maximize the utility function and the other player wants to do the opposite (minimize). In our example MAX's (A) best move in the initial state is to take the lower-right corner, because it leads to the state with highest minimax value. But let us assume that MAX is malfunctioning and choose to take the upper-left corner instead. What is MIN's (B) best reply? Remember that MIN wants to move to a state with the lowest minimax value and what is MAX's best reply after MIN's turn provided not malfunctioning anymore :).

A (partial) game tree for a trivial game, where the nodes are game states and the edges (lines) are moves.