Make delicious recipes!

MiniMax Algorithm


MiniMax algorithm comes into play when two intelligent adversaries A and B are trying to win.
Each adversary tries to maximize its winning chances and minimize the opponent's chances.


Suppose A is planning its next move.
Also, suppose at every level, each agent has to choose among two options.
Thus, for every choice A has its disposal, B has two choices to make and for every choice of B, A has two choices to make and so on.


In planning its next move, A will the following points in consideration:
  1. A will choose the node offering maximum value to A. Thus A acts like a maximizer.
  2. B will choose the node offering minimum value to A. Thus B acts like a minimizer.

It is interesting to consider why would B focus more on minimizing the value of A rather than maximizing its own value?
And the answer is that B does not actually do that!
B is only assumed to play the role of a minimizer by A because A wants to prepare for the worst case scenario.
If A is able to handle the worst case scenario of B playing as a minimizer, then all other cases where B plays to maximize his own value will be automatically handled.

So, in the above example, it is A's turn to play and it can choose to select right child or the left child.
For each of its children, A will consider B's possible moves and consider B to be a minimizer.
For each of B's moves, A will have two moves.
Suppose, look-ahead is limited to 2 steps and an evaluation function assigns a numerical value to the situation of the game.
Since A acts as a maximizer, it will choose the maximum values from these and send up the values: 12, 6, 8, 14
B will minimize these values and send up the values: 6, 8
From these, A will choose the maximum of 8 and select the right child.


Code for this can be seen in the context of a game at this link: Optimize pot selection to win game


Alpha-Beta pruning


Game trees as shown above can become very deep and thus more and more unmanageable.
  1. One of the ways to limit the growth of a minimax tree is to limit the depth of the look-ahead.
  2. Other way is to intelligently prune the branches of a minimax tree such that it remains under control.

Consider the leaf node with value 11 in the below tree.

When this node is being considered, the minimizing node B for this node would have got a value of 8 from its left child.
Since the parent for 11 is a maximizer, it would always choose a value >= 11.
But in that case, the minimzer node B would never choose these because it already has a better minimum of 8 from its left child.

Hence, we do not need to consider other siblings of node 11 since they would either be rejected by the maximizer parent or by the minimizer parent.
Cutting out branches from further minimax pruning is called Alpha-Beta pruning




Like us on Facebook to remain in touch
with the latest in technology and tutorials!


Got a thought to share or found a
bug in the code?
We'd love to hear from you:

Name:
Email: (Your email is not shared with anybody)
Comment:

Facebook comments:

Site Owner: Sachin Goyal