Jacques Frechet's CS20 c Project Progress Report:

Four-Dimensional Tic-Tac-Toe

What I Have So Far

I have an applet of sorts which demonstrates the basic user interface. Unfortunately, the part that detects a win is broken right now; I'll see if I can get that working again by the deadline.

The important thing, though, is that the applet implements the basic internal framework I'll be using. Perhaps you'd like to check out the source:

class TTTT: A short test-driver applet that just creates a Game consisting of a BoardWindow and a Computer.
class Game: This class maintains a collection of Players and moderates communication between them.
interface Player: Defines a generic interface for classes which represent one participant in a Game.
class Board: This is a component which implements the Player interface, allowing the user to participate in a Game.
class Computer: Another kind of Player, this class will implement a minimax game-tree search with alpha/beta pruning, running in a separate thread to avoid messing up multiple games. (Currently, the thread just calculates a random legal move.)
class BoardSize: This class actually represents an arbitrary ordered quadruple. You'd think that this would be used for moves as well, but you'd be wrong; actual moves are encoded by this class as integers, such that the set of all possible moves on a board of a given size maps to a set of consecutive integers, starting at zero, with some other useful properties.
class BoardWindow: Right now, this is basically just a wrapper for a Board which displays the component in its own window. Other components (a menu, perhaps) will probably be added.
class Symbol: An abstract superclass (well, right now it's an interface, but it probably ought to be an abstract superclass) for a symbol (such as an X or an O) that can appear on a Board. Basically, this provides a method to draw the appropriate symbol.
class X: Draws an X.
class O: Draws an O.

What Needs To Be Done

The next step will be to implement an efficient board-evaluation routine and replace the dummy makemove() method in class Computer with one that implements minimax/alpha-beta. Currently I'm working on an incremental board-evaluation algorithm which won't need to reexamine the entire board at each node in the game tree. I plan to do a simple, linear evaluation which examines every possible linear arrangement of four (or however many) spaces on the board, and assigns each one a score, then adds the scores together. The order of such an algorithm (incremental or not) seems to be O(n³), where n is the number of dimensions; the non-incremental version also depends linearly on the number of squares on the board, which is itself a degree-n polynomial, so I'd rather avoid that if I can.

If there's any time left once that's done, I'll go on to add a server for human-vs-human games. This will require the addition of a few new classes, such as a new Player subclass, and a class that handles the multiplexing of the client/server connection, at least for incoming messages from the server. Here's a quick summary of a little line-oriented stateless protocol I plan to use:

Messages the server can send:

hello [url] - sent any time the client needs to (re)enter a name, such as when the connection is first established; the URL is just there to help the server find a free port when setting up shop.
welcome [playerid] - assigns the player an ID number after successfully specifying a name; this should also reset the client.
player [playerid] [score] [name] - notifies the client of the arrival of new player, or a change in a player's score.
exit [playerid] - notifies the client that a player has left the server (by closing its connection).
game [gameid] [# players] [playerids] [gamespec] - notifies the client of a game's new or updated status; "gamespec" consists of board size, sequence of moves already made, and other information about the game.
move [gameid] [move] - special form of the above, which just adds a move to an existing game.
message [arbitrary text] - requests that the client display the message, perhaps in a cute little pop-up box thingee.

Messages the client can send:

name [name] - log on to the server under the given name, or change names, or whatever
game [gameid] - attempt to join a game; if the given game doesn't exist, it will be created
move [gameid] [move] - attempt to make a move in the specified game
status - requests that the server resend all status information.

So, for instance, if the client thinks the server has sent it an illegal move, it can send "status," after which the server will respond with the appropriate "welcome," "player," and "game" messages. On the other hand, if the server thinks the client is doing something foolish, like playing out of turn or making an illegal move, it can make arbitary changes in the client's state by sending the appropriate "game" or other messages, perhaps accompanied by some explanatory "message" (such as "Name already in use" if the server is resending "hello" after an invalid "name" command).

The server won't really need to be very complex. All it needs to do is keep track of the state of each game, do some simple sanity checking, and send updates when appropriate.