Jacques Frechet's CS20c Project Proposal:
Four-Dimensional Tic-Tac-Toe
Jacques Frechet's CS20c Project Proposal:Four-Dimensional Tic-Tac-Toe |
|
Four-dimensional tic-tac-toe is just like regular tic-tac-toe, except that it is played on a 4x4x4x4 grid; the object, of course, is to get four in a row. The illustration above should make it clear how this works, and how the grid can easily be represented in two dimensions.
The resulting game is surprisingly easy to learn, but is several orders of magnitude more interesting to play than ordinary tic-tac-toe, or even (IMHO) checkers.
Briefly, I propose to write a program that plays 4-D tic-tac-toe.
Because of the large number of possible moves at each stage (44 = 256, minus the number of moves already made by either player), using alpha-beta pruning when searching the game tree would be a virtual requirement for an efficient implementation. Thus, this game should provide a dramatic example of the advantages of using this technique.
Rather than doing the obvious thing and writing a simple Java applet that plays against the user, I'd like to try for a more flexible client-server model. The idea here is to allow gameplay not only against the computer, but also against other users. User interface would be handled by a Java client, while inter-user communication would go through the server, which would probably be written in C++.
The code responsible for formulating the computer's moves could be either built into the server (allowing the computer player to appear to the client as any other player) or in the client (which would allow it to operate independently of the server when playing against the computer). Right now I'm actually leaning towards doing it in the client, but C++ and Java are similar enough that it shouldn't make much difference in how the game-tree-search classes are written.
If there's time, I'd also like to throw in some extra features like custom playing grids, configurable computer players (this would mainly involve letting the user tinker with the algorithm used to assign scores to different board configurations), multi-player games, a facility to observe other games in progress, a chat box . . . .
Just me.
(It's tempting to say that this would make a good two-person project, with one person doing client and one doing server, but it seems to me that that's likely to result in a very lopsided distribution of labor.)
One possibility is just to do a stripped-down Java-only version of the above project. I'm likely to fall back on this if I can't get the networking thing going.
It might also be nice to do some cool FFT application, such as a real-time pitch-to-MIDI converter; I have the necessary hardware over here. This would probably need to be written entirely in C++. If that turned out to be too complicated, perhaps some kind of colorful real-time graphical frequency display would be better. Or the two could be combined . . . .
This isn't exactly an original idea. I actually saw a DOS game many years ago that played 4x4x4x4 tic-tac-toe against the user on a grid like the one in the illustration. Unfortunately, I've no idea who the author was or who came up with the idea in the first place.