COMP 212 Lab 12: Tic-Tac-Toe

This tutorial uses Tic-Tac-Toe (or Naughts and Crosses, for those who prefer the Queen's English) to illustrate the min-max game strategy. It serves to jump start the Othello project.

Playing Tic-Tac-Toe

Copy the package ~comp212/public_html/01-spring/labs/12/TicTac/ and the directory ~comp212/public_html/01-spring/labs/12/players/ into your own directory. 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. (No, we didn't provide the course code for this.) 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.

Implementation of min-max strategy

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

Let's call the players John and Mary. When John is to make a move, we assume he will moves in a way 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. As John considers all the possible futures, the possible board positions represent nodes in a game tree. How are the value of each board position calculated? Here is one such possible computation.

For each of the leaf of the game tree, John assigns a value of 1 if he wins, 0 if he ties, and -1 if he loses. I.e., he defines a pay-off function P:

P(leaf) = 1 if John wins, 0 if John ties, -1 if John loses.

Now, John assigns values to interior nodes:

P(interior) = max {P(c) | c is a child node of X}, if John moves next.
P(interior) = min {P(c) | c is a child node of X}, if Mary moves next.

To implement the above, for the sake of speed, we copy much of the functionality 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:

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

NOTE: 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.
In order to avoid playing the same sequence of moves in different games, write the code for the method randomize to randomize the array (OK, so it's really a Vector) of legal moves. Look at the code in DumbPlayer.java to see how this can be done.