Lab #8: Interactive text game (with game tree)

Assigned: Wed 6 Apr 2005
Due: Wed 13 Apr 2005

In this single-project lab you will write a program which plays a game of tic-tac-toe interactively with the user. The idea behind the lab is to give you some practice in using Haskell's IO features, and especially in integrating them with the more functional style we have been learning and using up until now.

The Interactive Tic-Tac-Toe Game

I assume everyone knows how to play a game of tic-tac-toe on a 3-by-3 board, with X's and O's for "markers". We are not trying to write an especially smart game-playing program here, so we will use only a simple strategy from the computer's side (the other side's strategy is of course up to the user).

In order to provide some basis for strategy, and in order to provide a certain feedback to the user, we will try to construct a full game tree in advance of the game (this may be difficult due to space limitations: I haven't actually tried it myself, but there are some possible optimizations we could use if necessary).

By a game tree, we mean a structure similar to a "Spread tree" from the last few labs: each node in the tree represents a certain board situation, and the children of a given node represent possible moves from that situation to a new one. Game trees also have an alternation of layers which arises from the fact that players alternate moves in the game: one layer represents the X player's choice, the next layer the O player's choice of move. Of course, there are also rules as to how one can move (only into an unoccupied spot) and what constitutes a win (three in a row of your marker, either in a row, a column or along a diagonal).

Your program will need to interact with the user, providing them with a "picture" of the board at each step, accept their desired move, and react with a responce or a complaint about an illegal choice.

In addition, I would like you to print out the probability of a win for the user from the current position, based on the ratio of winning to non-winning (including tying) games which are reachable from, the current position.

This will require you to have the game tree (or at least portions of it) available to the program during the game. It will also allow the program to make a simple choice about which move to take in response to the user, namely that move among the current ones available to it which maximizes its probability of a win.

Some issues and strategies

I haven't actually programmed this game in Haskell in advance of this lab, but I've thought some about how you might want to approach it; below are some tips on various aspects:

Some questions

Please have answers to the above exercises ready for the next lab session on Wednesday 13 April. We will likely use a "demo style" for this program, rather than a static grading.