======================================================================
     Faculty of Applied Science and Engineering, University of Toronto
               CSC181: Introduction to Computer Programming, Fall 2000

Practical Notes, Week 10: Minimax
======================================================================

The purpose of this practical is to have you work with minimax.

You will not be graded for this practical.

----------
Your Tasks
----------

Consider the game of Tic-Tac-Toe while answering the following
questions.

1. How many possible games of Tic-Tac-Toe are there? Try to find as
   good an upper bound as you can get.

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. You should have 3 positions at level 1 and 12 at level 2.

3. 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. Now, consider the following evaluation
   function:

       e(f) = 3(X_2) + X_1 - (3(O_2) + O_1)

   Using this function, mark on your tree the evaluations of all the
   positions at level 2.

4. Mark on your tree the values for the positions at levels 1 and 0,
   using the minimax algorithm, and use them to choose the best
   starting move.

5. If you want to understand alpha-beta pruning, you should answer the
   following question:

   Circle the nodes at level 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.