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

SourceForge Logo
Benjamin Miller
Last modified: Sun Sep 8 23:29:25 EDT 2002