Reversi in Java

`To play,`

Click where you wish to move; the user plays Red and moves first. To start over, just press the Start button. The computer responds fairly quickly using a Dell Pentium 90Mhz with MS-IE 3.0, and it responds rather sluggishly using an IBM Aptiva Pentium 100Mhz with Netscape 3.0. It is very slow on a Mac Quadra.

This version runs analysis in the background; as a consequence, if you take a long time to make your move, it is quite possible that the computer will respond instantaneously, having already analyzed and chosen a response for the move you made.

Last Updated: 17 February 1997 Caveats:

This program has been tested under MS-Internet Explorer 3.0 for Win95, and Netscape 3.0 for Win95. The threadless 0.8 version was tested on a Mac Quadra. If you are using a different machine, please send email to SkyHunter Partners Inc. Attn: Marc Stiegler to tell us how it did or did not work. Curiously, the program occasionally silently dies when running the original Sun JDK interpreter for Win95.

This is a work in progress: The user interface will be made more beautiful, and the user will be given more options (who goes first, computer skill level, etc), in the future. There are also a handful of known minor display bugs to be fixed.

Interesting features, from a programming point of view:

Several design changes have been made between the 0.8 and 0.9 versions. These changes include:

Multiple threads. The computer now runs a low-priority analysis thread while the human player is moving, allowing it to respond instantly if the human chooses a move the computer has already analyzed.
Increased symmetry between human and computer player-objects. These 2 objects are now both subclasses of the abstract Player class.
Observable events. The GameManager now has 3 ObservableEvents (a subclass of Observable), the startGame, moveMade, and settingsChanged. The ComputerPlayer observes these events to determine when it needs to stop or modify the background analysis thread.

The computer search algorithm is a simple, brutal minimax algorithm. In the current presentation, the search is 3-ply deep. Having implemented this program in PL/1, Pascal, and FORTRAN before, on mainframes and minis and micros, I am astonished at how good performance is on a Dell Pentium 90 using MS-IE 3.0. Even using a much more sophisticated algorithm (alpha-beta minimax with forward tapered pruning and shallow pre-search prioritization), I have never gotten beyond 5-ply with reasonable play response. On the Dell Pentium 90 with IE-3.0, the 4-ply version of this program responds reasonably. This surprisingly good performance is not a so much a comment on how wonderful current Java JITs are, but more a comment on how powerful a basic Pentium is compared to even a dedicated mainframe of 2 decades ago.

The Piece objects are implemented as "flyweights" as described in Design Patterns by Gamma et al. The Square object contains state information; the Piece objects are stateless.

The Board, BoardPanel, and GameManager act approximately as a Model/View/Controller pattern.

The minimax algorithm is recursive; it is implemented using object-style recursion as defined by Kent Beck of the Smalltalk community, wherein the BoardEvaluator factory returns a BaseEvaluator for the base case (when the ply to search = 0), and a recursing BoardEvaluator otherwise. Both the BaseEvaluator and BoardEvaluator respond to the same protocol.

There are 4 types of Pieces: white (currently displayed as red), black (currently displayed as blue), empty, and off-edge. By using the off-edge piece and embedding the board in a table with off-edge pieces all the way around, clumsy checking for off-edge conditions is eliminated.

2 performance enhancements appear in this object-oriented version that never appeared in the structured programming versions: the Square keeps a cache of both its locationStrength (used by the BaseEvaluator to compute the value of the board) and its collection of adjacent squares. These values heretofore always had to be computed, since there was not a convenient object to maintain the cache. Also, large numbers of "if" statements have been eschewed by using the Piece as a State object for the Square, which would improve performance enormously compared to structured programming versions, on a pipelined machine like the Pentium, if the code were not being interpreted.

A BoardServer creates new boards for the BoardEvaluators as they recurse through multiple ply. The BoardEvaluators release the boards back to the Server, with the intent that the Server could in the future recycle used boards rather than creating new boards, which are expensive to construct and are constructed in large quantities during the BoardEvaluation. However, this enhancement has not yet been made. Comparing with/without implementations could make an interesting bit of information for old C++ programmers who think full-fledged object-oriented programs with automatic garbage collection cannot be fast.

If you have use for the source code for this program, you can find it here. Please drop a line to Marc Stiegler to let him know what amazing things you're doing with it.