Solution Set

Game Trees and Computer Vision

1. Consider problem 6.1 in the text. Assuming that the leaves of the game tree represent either a win for black, a win for red, or a repeating board position (representing a draw), give a reasonable estimate of the size of the game tree.
   
   In order to derive a complexity result in regards to a game, or a research problem in general, we usually make assumptions about the structure of the game tree. This way, we can simplify the analysis of an otherwise complicated problem without sacrificing the required accuracy, as long as our assumptions are not flawed. The 4x4-checkers game tree is too  large to draw. However, if we sketch the first few levels, we can see that a good estimate for the average branching factor is two, as long as there are no "kinged" pieces. It takes approximately six moves (that corresponds to six game-tree levels, counting the root level as the zeroth one) to reach a game state where each player has a piece "kinged". Thus, the total number of nodes in those first levels is approximately 2^7-1 with 2^6 of these nodes occupying the leaves of the tree. After the first pieces are "kinged", it only takes a few more levels (2-3) until the other pieces are either "kinged" also or captured. That brings the total number of nodes in the tree to approximately 2^10. After this stage, the game develops a lot faster, that is most of the game-tree paths end very soon, making the tree rather sparse.
    
2. Do problem 6.3. The last question may be hard to answer accurately, but give it your best shot.
   
   There has been a lot of research on evaluation functions for games.  Most such functions are weighted linear ones, that is they have the form of w_1*f_1+w_2*f_2+...+w_n*f_n, where each f_i stands for a particular feature of the game (e.g. number of pieces, position of pieces, kind of moves available, etc.), and each w_i stands for the feature weight. The weights are usually adjusted by having the game-playing program play itself thousands of times. For 4x4 checkers, an example of an evaluation function that takes into consideration only the features given is as follows: add 1 for each of your own pieces, subtract one for each of the opponent's pieces, add 1 for each advance move you can make, subtract 1 for each advance move the opponent can make, add 2 for each jump you can make and subtract 2 for each jump the opponent can make, add 1 for each of your pieces occupying an edge square and subtract 1 for each of the opponents pieces occupying an edge square, subtract 1 for each of your pieces occupying a center square and add 1 for each of the opponent's pieces occupying a center square. If we test alpha-beta with  this evaluation function on the boards of figure 6.1, we will see that it will lead black to a draw, as does minimax.
    
3. Apply the min-max procedure to the following game tree.  Also show the points where alpha-beta pruning would eliminate certain parts of the tree, assuming a left-to-right evaluation strategy.
   
   To describe the game tree, I will just give the values of leaves at level five (i.e. 16 values).  Consider the rest of the tree to be binary, and assume that the first move (i.e. at the root) is a "max" operation:
   
       [ 34, 56, 54, 7, 97, 45, 76, 6, 12, 76, 36, 85, 47, 52, 95, 5 ]                                          
   
   The minimax method is applied as follows:
   
                         36                         MAX
                        /   \
                      /       \
                    /           \
                  /               \
                /                   \
             34                       36             MIN
            /  \                     /   \
           /    \                   /     \
          /      \                 /       \
        34        (45)           36         (47)     MAX
       / \         / \          / \          / \
     34    7     45   (6)     12    36    47   (5)  MIN
   / \   / \   / \   / \   / \   / \    / \   / \
   34 56 54  7 97 45(76)(6)12 76 36 85 47 52(95)(5)
   
   The values in parentheses are pruned when alpha-beta pruning is used.
    
4. Do problem 19.1 in the text.
        ___________________
       |\                   \
       |_\______________    \
           _____________|\   \
          |\             \ \   \
          |_\____________\_\   \
              __________________\
            y|\    -/->? +?      |x
             |_\________________|
   
   Consider the two junctions x and y in the figure. We start the analysis from x, which is an arrow. According to figure 19.3, x initially has two labels, A1 and A2. Both labels say that the line segment xy should be labelled +. Now we look at junction y, which is an arrow too. Hence y can only have label A1 or A2, which means that the label on line the segment xy can only be either - or ->.  However, we already know that the label on xy is +, so it is impossible to decide upon any consistent labeling for the figure.
   
5. The five kinds of line intersections given in Figure 19.2 are not exhaustive, nor are the labels given in Figure 19.3. Come up with at least one other kind of line intersection, and determine its plausible labels.
   
   5. One possible junction is an "X", and some of its plausible labellings are:
   
          |               |               |               | ^
          |+              |-              |c              | |
          |               |               |               |
   ______|______  ______|______  ______|______  ______|______
      +   |   +      -   |    -      c   |   c       ->  |  <-
          |               |               |               |
          |+              |-              |c              | |
          |               |               |               | V
   
                (a)                           (b)                           (c)                           (d)
   
   Interpretations:
   (a) top-view of a pyramid
   (b) top-view of a "negative" pyramid
   (c) four cubes sharing one corner
   (d) two (opposite) cubes sharing one corner