About this Applet

• Is it Reversi or Othello?
• Version History
• Algorithm
• Implementation highlights
• Acknowledgements
• Other Othello links

Is it Reversi or Othello?

Version History

Version 2.01

This applet is a Java reincarnation of the old Pascal game I wrote in 1991. While both versions seem to have similar functionality, the Java applet has been rewritten from scratch. Not only the interface, but also the algorithm has been dramatically changed .  Old version used pure positional evaluation function, and didn't account for mobility (follow this link for details of Othello strategies)
The old game, however, has one feature that new Java applet misses.  This is the ability to save and restore given position to the disk.  If this feature is important for you, old DOS game can be downloaded here:  reversip.zip

Version 2.5 - (current)

In this version I introduced the following major improvements:
 

• Alpha-Beta optimization of the MiniMax algorithm
• End of game search optimization.
• The applet was profiled using Sun's built-in profiler and optimized.  This optimization resulted in 2-3 fold increase in performance, however the results differ from one Java VM to another.  The Symantec's JIT compiler seems to produce best results outperforming Netscape Communicator 4 to 1.
• Unpredictability.  Game now starts at random starting position and also whenever two or more positions seem to be equally attractive, computer selects between them at random.
• Animations

Algorithm

Apparently the algorithm I used has a scientific name. It is called MiniMax and you can learn more about it at here
The maximum depth of search at which my computer responds in a reasonable time is 4 for Netscape Communicator running on Pentium 90 machine. Depth of search can be changed before each move.
At the end of the game the number of possible positions dramatically decreases and the evaluation criteria is also much more simple: who has more disks wins. This allows the program to calculate moves at much greater depth. When playing at depth 1 the end of game search starts when there are 56 disks on the board, for depth 2 it starts at 55 disks, for depth 3 at 54, etc. In other words end of game depth is determined by the following formula:
end_of_game_depth = 8 + selected_depth_level
Sometimes transition from regular search to end of game search isn't very smooth and there may be a noticeable delay when computer calculates end of game positions for the first time.

The evaluation function which is used to determine the best possible move is assigning credits for mobility and corners and deducts credits for playing bad squares (follow this link for explanation of Othello strategies)
In two respects my algorithm is different from some others that I reviewed.  Firstly, it doesn't assign mobility credit for moves that result in taking "bad" squares.  Secondly, C and X squares are no longer considered "bad" when the corresponding corner is taken.  Moreover, the static evaluation function assures that at this point in the game C-squares start to look very attractive.

Whether these features improve the quality of the game or not I cannot tell, because I am not a good player.  But the applet currently plays far beyond my abilities and therefore I think I did a good job.

I believe that the strength of the game can be somewhat improved by optimizing the  values of credits and debits assigned for mobility, corners and bad squares.  I couldn't find any research materials that would discuss this kind of optimization.  If you are aware of such research or can suggest the optimization algorithm, or know of a self-learning Othello programs that are capable to adjust parameters based on the outcome of the games - please share the information.

Implementation highlights

On the technical side the game implemented as a good illustration to OO design textbooks. It is based on Smalltalk-style Model-View-Controller pattern where Model, View and Controller components are connected using Observable pattern (see "Design Patterns" by Eric Gamma et al.).
The game is multithreaded. Refreshing of the screen, computer calculations, handling of user input, animations, loading of sound and other non-crucial files and timer implemented in separate threads.

In the foundation of the design is class Position which is responsible for calculating value of a position and determining available moves.  Class Game controls the game flow by scheduling user and computer moves.  Class ReversiView provides applet shell and determines the UI.  Finally, class ReversiController is responsible for updating ReversiView based on the state of the Game and informing Game about actions of the human player.

Acknowledgements

• The following pages provided me with many valuable ideas:
• Discussion of Othello rules and strategies
• Discusion of MiniMax algotithm and Alpha-Beta Optimizations
• Rapport de Projet LOthello (en Francais)

Other Reversi Links

• International Internet Othello Association
• 1001 Othello applet and other related links by Alain Beyrand
• Louis Geoffroy's Home Page  - lot's of Othello related links and information.
• Huge collection of Othello links by Bruno Turquet de la Boisserie