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.
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.
It might also be possible to cut off the tree at tie games, although this is harder to discern from just looking at the board: rather, you might want to generate the whole game tree below the node and if, coming back out of the recursion, you see that there are only ties below, then trim the tree on the way back out.
See if you can measure this and report back on it.
One possibility here is to dynamically generate parts of the tree as you go; this won't allow you to provide feedback to the user or to the program about relative wins and losses, but you could still play the game.
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.