Tutorial 13: Tic-Tac-Toe


Introduction

This tutorial uses Tic-Tac-Toe to illustrate the min-max game strategy.  It serves to jump start the Othello project.


I. Sample Programs

Create a local directory comp212/tutorials/13 for this lab and copy the files ~/comp212/tutorials/13/TicTac/*.java~/comp212/tutorials/13/players/*.java, and ~/comp212/tutorials/13/players/*.class.  These are the Java source code and byte code for a GUI application that plays the game of Tic-Tac-toe.  The design of this program is the same as that of the Othello program.  To see how the application behaves, compile DumbPlayer.java, and run the command: java DumbPlayer. Play against DumbPlayer to see if you can beat it!  Now run SmartPlayer0 and play against it.  You probably will notice a non-trivial delay in the first move.  SmartPlayer0 uses the min-max strategy to search and evaluate the full game tree in order to make its moves.  This is why the first move is slow.   This tutorial will lead you through the process of coding SmartPlayer.java to implement the min-max strategy as illustrated by SmartPlayer0.

II. Implementation of min-max strategy

Here again is the min-max strategy discussed in class.

For the sake of definiteness, we assume the players are John and Mary.  We can imagine when John is to make a move, he will move to a game node that is best for him.   What's best for John is based on some numerical value that he associates with each of next possible moves.  How are the value of each of the game node calculated?   Here is one such possible computation.

For each of the leaf node, John can assign a value of 1 if he wins, 0 if he ties, and -1 if he loses.  Conceptually, John defines a "pay-off" function P as follows:

P (leaf) =

Now, John assigns a value to a non-leaf node X, as follows:

V (X) =

To implement the above, for the sake of speed, we copy many of the functionalities of TTEngine.java, the logic of playing Tic-Tac-Toe into SmartPlayer.java. What you need to do is to study the code for the method NextMove (...) and fill in the code for eval (...).

Exercises:

1. Examine the code and comments inside of eval (...) and complete it.

2. In order to avoid playing the same sequence of moves in different games, write the code for the method randomize to randomize the array (Vector) of  legal moves.  Use the same technique shown in randomizing an array in the sort animation program.

NOTE:  In exercise 1, SmartPlayer.eval () returns an int representing the min-max value.  SmartPlayer.NextMove () then has to recompute some of the min-max values again to find the move whose min-max value matches with best min-max value found.  This is unnecessary because we can compute the min-max value and keep track of the move yielding the best min-max value in the same computation.   SmartPlayer2.eval () shows how this is done.

Have fun!


dxnguyen@cs.rice.edu

revised 12/01/00