COMP3411 Artificial Intelligence
Session 1, 2010

Week 5 Tutorial

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

  Eval(s) = 3X₂(s) + X₁(s) - (3O₂(s) + O₁(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.

• Continuing the tic-tac-toe example: If minimax (or alpha-beta) were to search the entire game tree, it would evaluate all three opening moves equally, because it assumes the opponent will play optimally. However, if we assume the opponent could make an error, we can see that some opening moves are better than others. Explain why.

• 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.

  

• Consider this Constraint Satisfaction Problem:

  

  Write a number in each square of the above table so that

  1. each number is either 1 or 2
  2. the sum of each row is odd
  3. the sum each column is even
  4. the sum of all the numbers is greater than or equal to 7.

  Describe an initial configuration which would cause Hill Climbing with Min Conflicts to get stuck in a local optimum. Explain how Simulated Annealing would be able to escape from this local optimum to reach the global solution.

• 6.13 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?

• 6.14 Discuss how well the standard approach to game playing would apply to games such as tennis, pool and croquet, which take place in a continuous physical state space.

• Any Questions about Assignment 1.