Ultra Tic Tac Toe
Download |
Project Page |
Download at Soft5000
Overview
Ultra Tic Tac Toe (UTTT) is a console game board package
containing tic tac toe (naughts and crosses) and connect 4 games.
The version of tic tac toe in UTTT is an extention of the classic
game: in addition to the traditional 3x3 board, it can be played
on 4x4, 5x5, 6x6, and 7x7 boards (and there are some extra rules
for the larger boards). Connect 4 has the same rules as the
original board game. Both games use the UTTT computer AI engine,
a highly optimized, parallelized, variable-depth search algorithm.
UTTT is distributed under the GNU General Public License, and is
known to work under Linux, Solaris, and Windows (using
Cygwin).
The Games
Tic Tac Toe
Tic tac toe can be played on any size square board from 3x3 up to
7x7. On any size board, filling an entire row, column, or
diagonal wins the game. With 5x5 and larger boards, a point
system is used to determine the winner if neither player fills an
entire line. One point is given for each line of 4 of a player's
pieces.
Connect 4
Connect 4 is played on a 7x6 board. As in the original board
game, pieces are placed at the top of a column, and
"fall" to the bottom of the column. The game is won by
having 4 pieces in a line (horizontal, vertical, or diagonal).
The UTTT Computer AI Engine
The (rather optimistic) goal of the UTTT computer AI engine is to
be the fastest recursive game tree search algorithm out there. I
don't know if I've come anywhere close to meeting this goal, but
the UTTT engine is pretty fast. The algorithm is an alpha-beta
pruning game tree search algorithm (look in a computer science
book or do a Google search for details on the technique). The
search depth can be set at run time to adjust the difficulty of
the game (and the time the computer takes to think about its
moves). The maximum search depth is the number of squares in the
board (or the maximum number of moves that will be made in the
game). Since the computer's thinking time increases exponentially
with search depth, it's not always reasonable to choose the
maximum depth. 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.
Download |
Project Page |
Download at Soft5000
Benjamin Miller
Last modified: Sun Sep 8 23:29:25 EDT 2002