COMP3411 Artificial Intelligence
Session 1, 2015

Week 4 Tutorial - Informed Search and Games

  1. Consider the following arrangement of tiles in the 8-puzzle:

    123
    85
    476

    Keeping in mind that the goal state is:

    123
    456
    78

    Trace the A*Search algorithm using the Total Manhattan Distance heuristic, to find the shortest path from the initial state shown above, to the goal state.

  2. 5.9 Tic-Tac-Toe

    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.

  3. Continuing the tic-tac-toe example, if minimax (or alpha-beta) 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 can see that some opening moves are better than others. Explain why.

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

  5. 6.13 (2nd Ed) 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. 5.6 (if time permits) 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.