Jacques Frechet's CS20c Project Report: Four-Dimensional Tic-Tac-Toe

Overview

The project consists of a Java applet which can play multiple concurrent Tic-Tac-Toe against human opponents or copies of itself (up to eight per game) on a game board of up to four dimensions. Computer players can use a variety of preprogrammed or custom strategies, all of which automatically adapt themselves to the particular Tic-Tac-Toe variation being played.

It may be helpful to look at this diagram when reading the discussion that follows.

Communication Structure

Each game is represented by an instance of the Game class, which maintains the following information:

• board size
• a list of players and observers
• the game's current state

Here, an "observer" refers to an extra player which never gets to move, such as a BoardWindow displaying a match between two Computer players.

Communication occurs through the various "notify" methods. Whenever a move occurs, the Game class calls the notify method for each player and observer; the parameters indicate what move just occurred and which player's turn it is now. Whenever a player realizes that it needs to move next, it generates a move (either in a subthread or in an event handler) and sends it back to the Game instance through its notify method, which continues the process.

Since the Game instance keeps track of the game state, Player classes can query it for information about the game, such as whose turn it is,can query it for information such as play order, who won, what moves have been made thus far, etc. The Board class, for instance, makes extensive use of this facility, while the Computer class prefers to generate its own, more specialized state information using information received through its notify method.

Game-Tree Engine

The game-tree engine is written in a very general way; it contains no inherent limitations as to number of dimensions or players. It works by generating a random permutation of the list of legal moves, and then applying the standard minimax algorithm with alpha-beta pruning. It uses an incremental board evaluation function to speed things up; see the presentation slide and comments in the Weights class for details.