+ 5
The minmax algorithm is used to minimize the maximum possible loss of a game participant (player). In zero-sum games, minimizing the maximum potential loss automatically means maximizing the minimum potential gain. In each game moment (at each game state) you consider all possible move combinations (up to a limited depth level usually) and calculate the game value function at each "leaf" of such a decision tree. Depending on whose move it is, the "min" player then chooses a move which leads to the minimal value, while the "max" player would choose a move leading to the maximal value. For tic-tac-toe the first move actually determines the outcome, so it is relatively easy to derive the optimum game value function. This is why people "know" how to play it to either win or draw. But for more complex games the biggest challenge is to find the game value function adequate to correctly describe the value at each game state.
30th May 2018, 6:04 PM
Kuba SiekierzyƄski
Kuba SiekierzyƄski - avatar