Ultra Tic Tac Toe v0.10.1
Written by Benjamin Miller <bmiller@users.sf.net>
Ultra Tic Tac Toe is a console board game package containing three games: Tic Tac Toe, Connect 4, and The K-Map Game. The three games use the same computer AI engine, which can search to a specified depth, and can be run in parallel using MPI or PThreads. Tic Tac Toe can be played on square boards from 3x3 up to 7x7; Connect 4 is played on a 7x6 board; The K-Map Game can be played on a 4-, 5-, or 6-variable K-Map.
INSTALLATION
Ultra Tic Tac Toe uses the standard GNU configuration and build tools. In general, to build and install UTTT, run `./configure', then `make', then `make install'. See the file INSTALL for more details.
USAGE
Both games use the same command-line interface and the same in-game commands. The command-line options are summarized below (substitute `connect4' for `ttt' for connect 4):
Usage: ttt [OPTION]...
-b, --beep beep when the computer makes a move -d DEPTH look ahead DEPTH moves -h, --help display this help and exit -n THREADS use THREADS pthreads** -s SQUARES use a board size of SQUARES -t show the computer's thinking -v, --version display version information and exit -2 two human players, no computer -0 no human players, just watch two computers play
** only valid if UTTT has been configured with PThreads.
Once the program is started, it will prompt the user for any information that was not given on the command line (player to move first, depth of computer AI search (difficulty), size of board), and then the game will begin. Pieces in both connect 4 and tic tac toe are represented by `X's and `O's; pieces in The K-Map Game are represented by `0's and `1's. The prompt
O player, input move>
is displayed when it is the user's turn to make a move.
In tic tac toe, moves are input in chess-style coordinates.
+---+---+---+
3 | | | |
+---+---+---+
2 | | X | |
+---+---+---+
1 | O | | |
+---+---+---+
a b c
In this example, there is an `O' at position `a1', and an `X' at position `b2'. Coordinates can be input in either order (`a1' is equivalent to `1a') and with or without spaces (`a1' is equivalent to `a 1').
In connect 4, only the column of the next move needs to be selected (since the piece will "fall" down to the bottom of the column). So a single letter between `a' and `g' represents a move in connect 4.
In The K-Map Game, moves can be entered in binary (in the order abcd...), or with a decimal square (minterm) number preceded by `m'. For example, to move to square 13 (on a 4-variable map), enter `1101' or `m13'.
The following commands are also accepted at the prompt:
.h - Display in-game help message .r - Redisplay the current board position .q - Quit the game (or hit CTRL-C) .t - Toggle display of thinking .b - Toggle bell .u - Undo move (use .r after this to redisplay the board) .d - Change depth (requires an argument)
Tic tac toe rules:
For a 3x3 board, the standard rules of tic tac toe apply: to win, get
3 of your pieces in a row. For 5x5 and larger boards, filling an
entire row, column, or diagonal will win the game, but there is also a
point system. For each line of 4 pieces, one point is scored.
Similarly (on 6x6 and larger boards), since a line of 5 pieces
contains two lines of 4 pieces, it is worth two points; and a line of
6 pieces (on a 7x7 board) is worth 3 points. It makes sense. Just
try it.
Connect 4 rules:
The rules of connect 4 are just what you'd expect: a player wins by
having 4 pieces in a row.
Note on AI search depths:
The maximum search depth for a given board is the number of squares in
that board (or the maximum number of moves that will be made in the
game). The higher the search depth, the better the computer will
play. The time it takes to compute a move increases exponentially
with the search depth, though, so using the maximum is not always
practical. Below are some times for various boards on a Pentium
II/450 (all are the amount of time it takes the computer to make the
first move of the game):
Tic Tac Toe, 3x3 board, depth = 9 : 0.03580 seconds
Tic Tac Toe, 4x4 board, depth = 10 : 4.87012 seconds
Tic Tac Toe, 5x5 board, depth = 7 : 6.50852 seconds
Tic Tac Toe, 6x6 board, depth = 6 : 2.91699 seconds
Tic Tac Toe, 7x7 board, depth = 5 : 2.68856 seconds
Connect 4, 7x6 board, depth = 10 : 2.33789 seconds
So those depths might be a good place to start if you have a
comparable machine. If you want an easier opponent, or if you have a
slower computer, try bumping them down by one or two.
BUGS/TODO
- A graphical interface would be nice.
- Maybe use a .tttrc file or something to save some options.
- Connect 4 and tic tac toe need toe be separated a little bit better.
- I don't really know if the MPI version works right now. The PThreads version works very nicely, though, as does the sequential version.
- It can always be faster.
- Other board games would work well with the current AI engine. I was thinking about trying to do Othello.
COPYING
This program is licensed under the GPL (see COPYING). If you want to contact me about the program, send me an email (bmiller@users.sf.net).