Game Search

Fill in the internal node values in the following game tree, after traversal by the MiniMax algorithm:

                          _                             MAX
         /                |                \
        _                 _                 _           MIN
   /    |    \       /    |    \       /    |    \
  _     _     _     _     _     _     _     _     _     MAX
 /|\   /|\   /|\   /|\   /|\   /|\   /|\   /|\   /|\
5 4 3 6 4 3 7 4 3 7 8 9 9 8 7 9 2 2 3 8 2 4 4 4 4 3 4

                          9                             MAX
         /                |                \
        5                 9                 4           MIN
   /    |    \       /    |    \       /    |    \
  5     6     7     9     9     9     8     4     4     MAX
 /|\   /|\   /|\   /|\   /|\   /|\   /|\   /|\   /|\
5 4 3 6 4 3 7 4 3 7 8 9 9 8 7 9 2 2 3 8 2 4 4 4 4 3 4

Trace (like we did in class, and shown in the notes) the MiniMax algorithm with Alpha-Beta pruning for the game tree above. Indicate which leaf nodes do not require static evaluation.

              MAX          MIN          MAX
          alpha beta     alpha beta     alpha beta     Static
          -MAX  MAX      -MAX  MAX      -MAX  MAX      5
                                        5              4 (not used)
                                                       3 (not used)
                                     <- 5 --------------
                               5        -MAX  5        6
                                        6 (stop)
                                     <- 6 --------------
                                        -MAX  5        7
                                        7 (stop)
                                     <- 7 --------------
                      <- 5 -----------------------------
          5              5     MAX      5     MAX      7
                                        7              8
                                        8              9
                                     <- 9 --------------
                               9        5     9        9
                                        9 (stop)
                                     <- 9 --------------
                                        5     9        9
                                        9 (stop)
                                     <- 9 --------------
                      <- 9 -----------------------------
          9              9     MAX      9     MAX      3 (not used)
                                                       8 (not used)
                                                       2 (not used
                                     <- 9 --------------
                               9 (stop)
                      <- 9 -----------------------------

 /|\   /|\   /|\   /|\   /|\   /|\   /|\   /|\   /|\
5 4 3 6 4 3 7 4 3 7 8 9 9 8 7 9 2 2 3 8 2 4 4 4 4 3 4
        * *   * *         * *   * *       * * * * * *