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.
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.
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:
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.
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.
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.
This page is maintained by CB.
Last update: 27.12.01.