CS 161 Recitation Notes - AND-OR Trees

AND-OR trees are used to represent the state space for two-player games. OR nodes represent your moves, where you can choose which move to take, thus you will choose the move that's best for you. AND nodes represent the opponents's moves. Since you don't get to choose these, you should assume your opponent will choose the move that's worst for you (and thereby best for him).
Since you don't get to make the decision about what the opponent's moves will be, the methods for searching AND-OR trees is very different from that of OR trees. While in OR trees, the goal was to search the tree and find a solution, or the best solution, or the shallowest solution, the goal in AND-OR trees rarely involves finding a solution. This is because the size of the tree is generally much larger than that of typical OR trees, so searching the whole tree isn't feasible.
Instead, searching an AND-OR tree typically consists of looking forward some fixed number of moves, evaluating the state of the game at each possible state at that depth, and then propagating those values back up the tree to decide what is the best move to do now. Writing an evaluation function to tell you how beneficial a particular state of the game is for you is often quite difficult, but there is a very simple algorithm (family of algorithms, actually) for propagating the values back up the tree. This is the minimax algorithm.

Very small games

Consider the behavior of minimax on a game with a very small search tree. Because the tree is small, you can generate the entire search tree. For example, consider the game NIM. In NIM, a number of stones are placed in a pile. On his turn, each player can remove either 1 or 2 stones from the pile. The person who removes the last stone wins.

Let's consider the game tree for the 5 stone version of NIM. Here I'll be using [VAL] to represent a max node and (VAL) to represent a min node:

                         [5]
                     ----/\----
                    /          \
                 (4)            (3)
                /   \          /   \
               /     \        /     \
            [3]      [2]     [2]     [1]
           /  \     /  \     /  \     |
        (2)   (1) (1)  (0) (1)  (0)  (0)
       /  \    |   |        |
     [1]  [0] [0] [0]      [0] 
      |
     (0)

In this tree, if it's your move and the value is 0, then that node indicates a loss for you. Thus, if you're max, then you can label each of the terminal nodes as wins or losses:

                         [5]
                     ----/\-----
                    /           \
                 (4)             (3)
                /   \           /   \
               /     \         /     \
            [3]      [2]      [2]     [1]
           /  \     /  \      /  \     |
        (2)   (1) (1)  (0) W(1)  (0)W (0)W
       /  \    |   |        |
     [1]  [0]L[0]L[0]L     [0]L
      |
     (0)W

To propagate these values back up the list, there's only two simple rules to remember:

if were evaluating a MAX node, and at least one of it's children is a W, then it is a W.
if were evaluating a MIN node, and all of it's children is a W, then it is a W.

The distinction here is that at a MAX node, you choose the move. You can choose one branch OR another. If you find a winning node (and you can ensure that you traverse to it), you win. At a MIN node, on the other hand, the opponent will choose the move. You must ensure that you can win if he chooses the first branch AND you must ensure that you can win if he chooses the next branch AND you must ensure that you can win if he chooses any other branch. Thus, to win, you must for ensure you will win regardless of his choice (i.e. you must make sure you will win under all choices).