Game Search Control

State spaces represent game trees, but here each alternate level is played by an adversary who will pessimise the search.

MiniMax Principle

Positive numbers are in favour of one player, negative the other.
- The absolute value determines the magnitude of the favour.
- A static evaluator h(S) is used to evaluate a state in these terms.
The positive player tries to maximise the evaluations, the negative minimises.
- Each must take cognecense of the decisions made at the level below, until the limit is reached. Then h(S) makes the final evaluation.
- MiniMax assumes that the opponent will do the same thing.
- A good h(S) is key to success.

Algorithm

MiniMax(State,Direction,Depth) {
    if (Depth == Limit) {
        return(h(State));
    }
    if (Direction == maximising) {
        Report the maximum of MINIMAX on successors
    }
    if (Direction == minimising) {
        Report the minimum of MINIMAX on successors
    }
}

Notice that in the end the judgment lies with the static evaluator.
The sequence of plays determined by MiniMax is called the main variation.

Example

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

Most CPU time is spent evaluating h(S) for the branching_factor^limit leaf nodes.

Alpha-Beta Pruning

Branches that can be shown to be worse than already searched ones are discarded.

Simple example

                 ?             >=2            2          MAX
                / \            / \           / \
               ?   ?          2   ?         2  <=1       MIN
              /\   /\        /\   /\       /\   /\
             2  7 ?  ?      2  7 ?  ?     2  7 1  ?

Last position is not evaluated.

Algorithm, called MiniMax(InitialState,maximizing,-MAX,MAX,0)

MiniMax(State,Direction,Alpha,Beta,Depth) {
    if (Depth == Limit) {
        return(h(State));
    }
    if (Direction == maximising) {
        while (alpha < beta && there is another Child) {
            Alpha = max(Alpha,MiniMax(Child,minimising,Alpha,Beta,Depth+1));
        }
        return(Alpha);
    }
    if (Direction == minimising) {
        while (alpha > beta && there is another Child) {
            Beta = min(Beta,MiniMax(Child,minimising,Alpha,Beta,Depth+1));
        }
        return(Beta);
    }
}

Example

                                    5                           MAX
                   /                |                \
                  4                 5                 3         MIN
             /    |    \       /    |    \       /    |     \
            8     9     4     5     9     6     3     9      16 MAX
           /|\   /|\   /|\   /|\   /|\   /|\   /|\   /|\    /|\
          8 7 3 9 1 6 2 4 1 1 3 5 3 9 2 6 5 2 1 2 3 9 7 2 16 6 4
* = NE            * *                 *   * *       * * *  * * *

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

Some Analysis
- Does not always help, but can never make things worse.
- As the effort required to establish static evaluations is comaparatively large, the overhead introduced is almost always comparitively negligible.
- The amount of improvement depends on the order of search.
- The best results are achieved if strong moves for each side are looked at first. (This is intuitively true too.)
- In a game tree there are B^D leaf nodes (evaluations) where B is the branching rate and D the depth of search. In the best case with alpha-beta pruning this is reduced to 2B^D/2 evaluations.
- 2B^D/2 / B^D = 2 / B^D/2
  - In terms of time, this means that an algorithm will be able to search twice as deep in the best case.
  - In terms of the effective branching rate, the best case square roots the effective branching rate.

Refinements
- Heuristic pruning: Moves are ordered according to some heuristic, and those branches associated with lower priority moves are left at lower ply.
- Progressive deepening
  - This technique is applicable in games where moves have to be made within a certain amount of time.
  - MINIMAX (optionally with alpha-beta pruning) is successively implemented for increasing ply until time is up.
  - Although this means repeating levels it takes only 1/branching rate to statically evaluate nodes the level above the ply compared to evaluating those leaf nodes at the ply. Given that the static evaluator takes the dominant portion of time this is acceptable especially at high branching rates.
- Horizon pushing: If a situation appears to be particularly turbulent it may be necessary to extend the ply to find effects beyond the horizon. This will mean extending those branches of the tree.
- End play: Seperate specific algorithms may be used to play the final stages of a game, when complete knowledge and search becomes more feasible.

Exam Style Questions

Give the MiniMax algorithm for searching game trees.

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

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

Give the MiniMax algorithm with Alpha-Beta pruning, for searching game trees.

Fill in the internal node values in the following game tree, after traversal by the MiniMax algorithm with Alpha-Beta pruning. Indicate which leaf nodes do not require static evaluation.

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