Differences

This shows you the differences between two versions of the page.

--- chess:programming:minimax_algorithm [2021/10/30 23:20] – peter
+++ chess:programming:minimax_algorithm [2021/10/30 23:40] (current) – peter
@@ Line 11: / Line 11: @@
   * If the minimizer has the upper hand in that board state then it will tend to be some negative value.
   * The values of the board are calculated by some heuristics which are unique for every type of game.
+Since this is a backtracking based algorithm, it tries all possible moves, then backtracks and makes a decision.
 ----
 [[Chess:Programming:Minimax Algorithm:A program to illustrate the Minimax Algorithm|A program to illustrate the Minimax Algorithm]]
+[[Chess:Programming:Minimax Algorithm:A Tic-Tac-Toe example program to illustrate the Minimax Algorithm|A Tic-Tac-Toe example program to illustrate the Minimax Algorithm]]
 ----
@@ Line 40: / Line 44: @@
     return bestVal
 </code>
+----
+===== Example =====
+Consider a game which has 4 final states and paths to reach final state are from root to 4 leaves of a perfect binary tree as shown below.
+  * Assume you are the maximizing player and you get the first chance to move, i.e., you are at the root and your opponent at next level.
+  * Which move you would make as a maximizing player considering that your opponent also plays optimally?
+{{:chess:programming:minmax.png?400|}}
+Since this is a backtracking based algorithm, it tries all possible moves, then backtracks and makes a decision.
+  * Maximizer goes LEFT:
+    * It is now the minimizers turn.
+    * The minimizer now has a choice between 3 and 5.
+    * Being the minimizer it will definitely choose the least among both, that is 3.
+  * Maximizer goes RIGHT:
+    * It is now the minimizers turn.
+    * The minimizer now has a choice between 2 and 9.
+    * He will choose 2 as it is the least among the two values.
+Being the maximizer you would choose the larger value that is 3.
+  * Hence the optimal move for the maximizer is to go LEFT and the optimal value is 3.
+Now the game tree looks like below:
+{{:chess:programming:minmax1.png?400|}}
+The above tree shows two possible scores when maximizer makes left and right moves.
+<WRAP info>
+**NOTE:**  Even though there is a value of 9 on the right subtree, the minimizer will never pick that.
+  * We must always assume that our opponent plays optimally.
+</WRAP>