CSC242, AI: Games -- 3-D Tic Tac Toe

3DTTT

There are several versions of three-dimensional Tic Tac Toe (3dttt); you can easily find them on the web.

The 3x3x3 version played in the naive way is always a win for the first player, but you'll see variations on the game (like having to get two complete "rows"). We don't care about any of that (although, done correctly your program should be easily modifiable to play any such variant game, such as N-dimensional TTT).

We are going to play 4x4x4 3dttt. An example game that seems like ours can be found at 3dttt . This game is sometimes (probably due to a commercial version) known as Qubik, and in 1980 there was a weak demonstration (not sure what this means) that it is a win for the first player. This result was not known by the people who, in early 1990s, proved indeed it is a win for 1st player. Approximate reference: [Artificial Intelligence, Spring 2002, special issue on Games, article on "Known Game Results"]. Maks Orlovich (in the 2002 class) found quite a recent approach to analyzing similar games in Victor Allis's Thesis.If this link doesn't work let CB know.

But no matter if this game is a guaranteed win for someone, we're playing it anyway in hopes our opponent isn't an optimal player.

The UR's 3D-TTT Server

UR's TTT Server will let you develop, debug, and play other players (or various versions of your own program). Get to know it and its features...

Coordinates and Display

You're going to need a representation for the game state that lets you evaluate threats, discover wins, etc. Here are some ideas. Read the whole thing, there's a prize at the end.

There are some cute 3dttt displays on the web, but the ones Prof. Brown tried all had their problems. Let's standardize on a simple lowest-common denominator representation: our goal is not to look pretty, it's to beat the other player.

The TTT game space is a three-dimensional cube, and it turns out this is interesting for two reasons. First, moves can be communicated in a one-dimensional space (numbers from 0 to 63, in fact). Whether we actually do this depends on the specs of the 3D-TTT server pointed to above. Second, reasoning about symmetries may be easier in three dimensions. However, CB invented the rather elegant threat assessment method pointed to below and it used one-dimensional space, not three. So it pays to keep an open mind when designing these representations.

The 3dttt game is played in its 4x4x4 "game cube", or "cube". The following is an example of how to describe cells in three dimensions.

Imagine the game cube in front of you, and your face is flat-on, face to face with a face of the cube. Then there are sixty-four "cells" where moves can be made, divided into four horizontal "layers" of sixteen (4x4) cells each. The "front" of the cube is facing you. The lower left front corner of the cube is the origin, and the lower left front cell has coordinates (0,0,0). The "X-direction" runs from the origin out to the right. The "Y-direction" runs from the origin back away from you. The "Z-direction" runs from the origin upwards. Thus you have a right-handed coordinate system. The top layer has Z=3, the bottom layer has Z=0, the face of 16 cells facing and nearest to you has (Y=0), and so on.

Players alternate moves. Each move occupies an unoccupied cell. The first player occupying four collinear cells wins. There are 76 winning "Cube States" (is this claim true?). The "cube state" is equivalent to 65 bits of information that describes whether each cell is occupied or not, and whose move it is. Of course you may want to use integers, not bits, in your implementation.

If you need to display a cube, for instance to play your own program, write it out by layers, with Z increasing left to right. Thus if all play had been taking place on the "top" and "front (facing you)" faces of the cube the display could look like this:

  

. . . . . . . . . . . . . . . X

^ . . . . . . . . . . . . X . O .
|
y . . . . . . . . . . . . . . O .

O . . . . O . . X O X . . . X .

x ->

Z = 0 Z = 1 Z = 2 Z = 3

Communicating Moves: Because of symmetries (see below) it turns out that a move can be communicated with a single integer from 0 to 63. Just imagine the cells of your cube are numbered in scan-line order through any four faces in order (front to back) say. So you number left to right, top to bottom in the front face:

      Front Face           Back Face

0 1 2 3 48 49 50 51

4 5 6 7 ..... 52 53 54 55

8 9 10 11 56 57 58 59

12 13 14 15 60 61 62 63


Now the cool thing is that it doesn't matter if you number right to left, bottom to top, back to front, any of these within any other, *whatever*. As long as you do a sane, consistent, scan-line type numbering you'll be OK. You and your opponent can be playing entirely different-looking games, but they'll be equivalent under some set of rotations, and a win will still be a win, a threat a threat, etc... Cute, eh? You can map such a number to a 3-D cube location with some simple arithmetic (modding, subtracting, etc.)... A simple exercise for the reader.

So when you send a move to an opponent, you'll give him a single integer, and you should expect one back.

The 3-D representation may be useful for symmetries, reasoning about which could give your player a decisive edge. Consider a first move in one of the eight corners of the cube. This move is really no different from a move in any other corner; you can rotate the cube to put any other corner move there. In fact I think there are only four distinct first moves (in regular 3-D TTT there are only three, right?). There is some work involved in translating opponent's moves into their canonical reduced representation, and then in translating your responses back into his space, especially with the one-dimensional move representation mentioned above. Further, the benefits of symmetry fall off after the first few moves. BUT it's an interesting topic, whose theoretical and experimental analysis is worthy perhaps even of a term project, and can be applied to many other games, such as Quarto!

OK here's the prize. CB discovered Threat Space, inspired by linear systems theory. Threat space projects the game into a space of threats and lets you count how many and what type of threats you pose to him and he to you. One simple operation (and it quite possibly can be sped up or improved) is all you need.

What to Write

Cube State Representation. Maintain this as game progresses and use it to reason about game.

Win Detector. Input: Cube State. Output: 1 if win for you, -1 if win for opponent, 0 otherwise. Recognizing a won state is not hard but not totally trivial, and probably can be done very elegantly. Clearly if there are four cells with equal X, Y, or Z there is a win, but then there are the diagonals to check.

Static Evaluator. Input: Cube State. Output: how good is the state for you? Simplest is to use the Win Detector, but this doesn't allow any pruning. Chapter 5 of the text has useful thoughts, and there is more literature out there. Output should be a scalar, but can have any range you like, be integer or real, whatever. Spoiler: Here are some ideas on evaluation and win detection: don't look if you want to do it all yourself!

Minimax Algorithm. Input: Cube State and Maximum ply depth. Output: backed-up evaluation of the input state, looking down the tree to the depth specified by the ply depth. Should be instrumented to count number of evaluations. Notice that in minimax (e.g. p. 165) there is no explicit representation of the tree, nor is there any explicit memory of the best path. The tree is represented only in the recursive nesting, thus the local variables, of the function calls. The path is completely forgotten and only the best next move is returned.

Alpha-Beta Pruning Search. Input: Cube State and Maximum ply depth. Output: backed-up evaluation of the input state, looking down the tree to the depth specified by the ply depth. Difference with Minimax is that this search prunes the space using backed up values. Should be instrumented to count number of evaluations. The effect here is simply to avoid some recursive calls with a simple test. As with minimax, it will return the best next move and that is all. Should do it with fewer evaluations and that is what you can instrument and demonstrate.

If you have the energy, this would be very exciting: Advanced Pruning Search. Input: Cube State and Maximum ply depth. Output: backed-up evaluation of the input state, looking down the tree to the depth specified by the ply depth. Difference with Minimax is that this search prunes the space using backed up values. Should be instrumented to count number of evaluations. You can use one of the algorithms described in the book... there are several references in the book to supposedly-better search algorithms like the B* and SSS*. Your kindly old professor has rooted these references out and placed them conveniently on reserve.

Compute-move. It returns the "best" move your program (search and static evaluation components) came up with. First implement compute-move with minimiax - this will entail some sort of search and static evaluator (an evaluation function that assigns a point value to how good a current state of the game is). Once that is done, you can vary the depth limit to see if your program performs better with a higher search depth (if not, is that interesting?).

Timing. Initially you'll be limited to five seconds of consideration per move. We may change the time limit, so make sure that the time limit is easy to change, that it's not hard coded anywhere.

Statistics package. The idea is to monitor the performance of your code so you can quantify things like the efficacy of your static evaluator and the efficiency of your search. These two attributes of your program are, besides efficiencies of raw speed, about all you can do to smarten up your player. The metrics you should use for evaluation are:

  1. How many games you win, lose, or draw.
  2. For each move and for whole game: Number of moves considered (static evaluations) in move search.
  3. For each move and for whole game: Maximum depth considered.
  4. Amount of time taken per move.
  5. For each move and for whole game: Average branching factor of resulting search tree.
  6. For each move and for whole game: Related to last: how many nodes were pruned?

Because these statistical measures are really all you have to write about (they justify all your creative decisions and quantify your performance ) they should be, in a way, the main point of your work. Experimenting with different algorithms is useless if you don't quantify the results, and if you document your algorithm development with the resulting charts, figures, and graphs, your paper is writing itself while you develop the code.

Please demonstrate each of these functions and representations (e.g. your search, your static evaluator, your board state...) separately. That is, write them as separate chunks of code, not intertwingled with anything else, list them and test them and illustrate how they work, make sure they do what you think and make sure you document your testing enough to convince us. Put all this in your report, possibly in an appendix.

Some sample write-ups and READMEs appear in a section later on this page.

Playing Games

We shall provide the referee program, which will allow you to play against it or against another human's program. It will maintain a cube state, record your move, check for legality, check for a win, pass move on to opponent, and and pass back your opponent's move.

Need to say use any language you please. See 3dttt.lisp, spot.lisp or TTTPlayer.java, Spot.java for examples on connecting, login/out and protocols. Of course you will use all you've learned so far in programming to make sure you have good data abstraction. You may find that working with the Lisp version (or any language with dynamic typing, such as Python) will be less clumsy to work with than statically typed languages.

How To Proceed

First, our recommendation is to implement a basic minimax player, which involves representing the board state, building a static evaluator, and writing the minimax algorithm. Document, test, be sure you include hooks for statistics gathering. Maybe have this program play you or itself as part of the testing.

Next, modify your minimax code to implement alpha-beta pruning and see if that fares better (That is, does it beat your minimax version? if not, is that interesting?). In both cases you should return statistics - such as how many nodes are pruned, how many nodes examined, and the average branching factor. At this point you can do interesting work testing static evaluators.

If you happen to use Lisp, one useful function is time - this tells you how long a function runs. So you might want to do something like this:

  > (start-new-game)
> (time (finish-game))

to time a game.

Please make sure your code is well commented. This involves not only writing what each function does, but also how it works. The TA cannot understand or maybe even debug (hence possibly give more partial credit) code if it isn't commented well.

Write a literate and detailed report describing your algorithms and functions, your code and your findings. Trace the development of your static evaluator and your search algorithm, and whatever else you are proud of. Document the performance of your player. Remember, you have many combinations of components (this static evaluator with that search algorithm....) Play your program against itself and use the results to draw conclusions. You should present your data in the clearest way possible; tables or (better) charts and graphs. You may find useful this sort of advice on writing a paper or this similar but different advice or this Mathematics and Homework Helper page.

Sample Projects

  1. README and Writeup
  2. Fine Writeup
  3. Superb Static Evaluator
  4. Strong Writeup
  5. README for above

This page is maintained by CB.

Last update: 27.12.01.