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.

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.

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:

• Introduction to Branch and Bound
• Backtracking Vs Branch and Bound
• Dynamic Programming vs Branch and Bound
• Least Cost Branch and Bound
• FIFO Branch and Bound
• Job Sequencing
• Knapsack Problem
• Travelling Salesman Problem
• Minimax Principle

---

Additional Reading: [Wiki]