Minimax Principle – Be a Master of Game Playing

Minimax principle is a decision rule used in game and decision theory. It is used to minimize the maximum loss in worst case. Initially it was proposed for two player game. In this theorem, we have some bound at every level :

  • Lower bound for minimization problem.
  • Upper bound for maximization problem.

Moves of game are best described by game tree. Both players try to maximize their own profit or minimize opponent’s profit. In game tree, node can have any number of child.

Each move is having some heuristic value associated with it. Heuristic computation would be different for different games. Here in below tree, square represents player min and circle represents player max. Dashed line shows chosen move.

Game tree with heuristic values

Consider the game of tic-tac-toe. Let us assign +1 if X wins and assign -1 if O wins. Max(x) tries to maximize the heuristic value whereas min(O) tries to minimize the heuristic value. Both players select the move which maximize or minimize points. Move is best for max if it maximizes points for him, and move is best for min if it minimizes points for him.

Consider the following scenario : Suppose its max’s turn, so he will try to achieve maximum points, i.e. 9. Min will propagate minimum value from its descendents. If max chose left branch, he will end up with just 2 points. On right branch, min propagates minimum value 5 on level two, so if max chose right branch, he can earn 5 points. Out of all three, right branch can give maximum advantage to max, so he will select right branch move. This is how minimax principle works.

Minimax principle
Instance of game tree

As the possibilities of move increase, depth and state space of tree grows exponentially. In game like chess, generation of game tree require lot of space and time. Branching factor for chess is 35. Each node has approximately 35 children. It is not possible to explore entire tree at a time. For such huge tree, technique like Alpha-Beta pruning can help to find solution in realistic time.

Branch and Bound Problems:

Additional Reading: [Wiki]

Leave a Reply

Your email address will not be published. Required fields are marked *