COMP3411/9414 Artificial Intelligence
Session 1, 2019

Week 5 Tutorial

Activitity 5.1 Tic-Tac-Toe (Exercise 5.9 from R & N)

This problem exercises the basic concepts of game playing, using tic-tac-toe (naughts and crosses) as an example. We define Xn as the number of rows, columns or diagonals with exactly n X's and no O's. Similarly, On is the number of rows, columns or diagonals with just n O's. The utility function assigns +10 to any position with X3>=1 and -10 to any position with O3>=1. All other terminal positions have utility 0. For the nonterminal positions, we use a linear evaluation function defined as

Eval(s) = 3X2(s) + X1(s) - (3O2(s) + O1(s))

  1. Approximately how many possible games of tic-tac-toe are there?
  2. Show the whole game tree starting from an empty board down to depth 2 (i.e. one X and one O on the board), taking symmetry into account.
  3. Mark on your tree the evaluations of all the positions at depth 2.
  4. Using the minimax algorithm, mark on your tree the backed-up values for the positions at depths 1 and 0, and use those values to choose the best starting move.
  5. Circle the nodes at depth 2 that would not be evaluated if alpha-beta pruning were applied, assuming the nodes are generated in the optimal order for alpha-beta pruning.

Activitity 5.2 Exploiting a Suboptimal Opponent
Continuing the tic-tac-toe example, if minimax (or alpha-beta search) were to search the entire game tree, it would evaluate all opening moves equally - because it assumes the opponent will play optimally, which leads to a draw in the end, no matter what the opening move. However, if we assume the opponent could make an error, we see that one particular opening move is much better than the others. Explain why.

Hint: for each leaf position from Activity 5.1, try to determine whether X or O can force a win from that position.

Activitity 5.3 Applying Alpha-Beta Search
Apply the alpha-beta search algorithm to the following game tree, indicating clearly the values of alpha and beta at each node as the algorithm progresses, and circling the nodes that would not be evaluated.

Activitity 5.4 Pruning in Games with Chance Nodes
This question considers pruning in games with chance nodes. This figure shows the complete game tree for a very simple such game. Assume that the leaf nodes are to be evaluated in left-to-right order, and that before a leaf node is evaluated, we know nothing about its value -- the range of possible values is -∞ to ∞.

  1. Copy the figure, mark the value of all internal nodes, and indicate the best move at the root with an arrow.

  2. Given the values of the first six leaves, do we need to evaluate the seventh and eighth leaf? Given the values of the first seven leaves, do we need to evaluate the eighth leaf? Explain your answers.

  3. Suppose the leaf node values are known to lie between -2 and 2 inclusive. After the first two leaves are evaluated, what is the value range for the left-hand chance node?

  4. Circle all the leaves that need to be evaluated under the assumption in Part 3.

Activitity 5.5 Further Discussion
  1. Describe an optimal strategy for a simple version of the game Nim, which uses only a single heap of n stones. Players take turns to remove either 1, 2 or 3 stones from the heap. The player who takes the last stone (or, all the remaining stones) wins. For what values of n can the first player force a win? For what values can the second player force a win?

  2. Discuss what you found out from the Tree Search for Simple Games activity on the Alpha-Beta Pruning page, concerning one or more of these games:

  3. The Chinook checkers program makes extensive use of endgame databases, which provide exact values for every position with eight or fewer pieces. How might such databases be efficiently generated, stored and accessed?