CSPP 51091
Winter, 2007

Homework 4
Due 2/13/07

For a change of pace, a small programming project!

Write a program to play tic-tac-toe. The basic
tic-tac-toe program just needs to manage a game
played by (notionally) two human plays entering
moves at the terminal. There will be an extra
credit option to make the program play the game
against a human opponent (or concievably another
tic-tac-toe program).

Your program should do the following:

1. Define types to represent X's and O's (I
recommend a datatype with X and O as constructors,
for ease of pattern matching) and to represent
the tic-tac-toe "board" or game position. The
latter could be an array of nine elements (see
Array in the Basis library), or a 3x3 two dimensional
array (see Array2), or it could be an appropriate
datatype. If you use an array implementation, your
functions will be doing a lot of management of
array indexes, while with a datatype representation
you can do a lot with pattern matching.

2. You need to define functions to make tic-tac-toe
"moves", transforming the board into a new configuration.

3. You need to define a function to test whether a
board is a win for either side. This would be used
after each move to see whether the game is over.

4. You should read move specifications from the
player via the standard input (TextIO.stdIn). These
might be numbers (1 through 9 say), or simple 
phrases like "upper right", "center", etc. For
parsing such phrases, consider String.token.

5. You should provide functions to print a board
configuration on stdOut. This should be used after
every move, followed by a prompt for the next move,
alternating between player A and player B.

6. At the top level, there will be a top function to
call to begin a game, and the game will proceed by
alternately prompting each of the two players for
their move specification, and printing the resulting
configuration, and finally detecting a win or draw.

Bonus: add the ability for the program to play a game
against a single human opponent (not necessarily well,
but we could have a program-to-program tournament to
provide an incentive).

Extra Bonus: add the ability for the program to 
learn to play a better game of tic-tac-toe. This task
was presented many years ago as mathematical recreation
in Scientific American (if I recall correctly), and the
method involved colored glass beads stored in match boxes
with a different tic-tac-toe position pasted on each box.
See, for instance:

  http://web.cecs.pdx.edu/~bart/cs541-fall2001/homework/3-learn.html

Final word: please resist the temptation to go and find a
tic-tac-toe program on the web. If you get stuck, ask me for
hints or advice -- by email, or perhaps better, by the blog.