# 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:
• how to represent the board: there are several ways you might represent a "current board": you might use a list of strings, with Xs, Os and spaces, or you might use three lists of points, with each point being a co-ordinate pair of numbers between 0 and 2, and the three lists representing X moves, Y moves and open moves (the latter representation would make it easier to find legal moves, the former perhaps easier to gague wins and losses).

• how to represent a move: a move is probably easiest input as a pair of numbers, i.e. a point as above.

• how to represent the whole game tree: the Spread tree is roughly the right structure to use here, but you will want to make allowances for the specific aspects of the game tree. Also, you will want to store at each node the probability of a win or loss for a given player (current-move player versus other player (relative), or X versus O (absolute)?).

• cutting off at wins/losses: when the current board situation is a strict win or loss, you will want to have no children at all, since there is no point counting relative wins/losses or even stroing the tree at all below wuch a node.

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.

• user interaction: you may want to write some practice user interactions for easier problems: for example, keep a list of all poossible moves and just trim it down as the user makes choices, simply allowing or disallowing a move based on its availability. In the real game, these allowable moves will probably be part of node information in the tree (or derivable from it), but it will be easier to understand the interaction pattern if you develop a short version separately.

## Some questions

• how big is the overall game tree, in terms of size (number of nodes) and depth (longest path to a leaf)?

See if you can measure this and report back on it.

• if you can't keep the whole game tree in memory, what can you do?

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.