The Distributed Java Othello Environment

David Coppit - David Engler - Sean McCulloch

Definition and Motivation

People in the field of Artificial Intelligence study board games because, for almost any situation, there is an inherent difficulty of determining optimal or even good solutions. The algorithms used by computers to play humans typically grow exponentially with the desired fitness of the move returned. It is because of this algorithmic complexity that game-playing computers often utilize some sort of parallelism while searching for a move.

Mentat is an environment that frees the programmer of most of the difficulties of parallelizing code. We have used the Mentat Programming Language (MPL) to implement a parallel algorithm for the board game Othello. The MPL code is based on a sequential C version, which enabled us to explore the purported ease at which parallel Mentat applications can be developed from serial code.

The interface to the computer Othello player is through a server that mediates communication between Othello clients, which may be either computers or humans. In building this client-server architecture, many design decisions had to be made regarding such issues as the responsibilities of the various components of the system and the communication protocols between these components.

We have also built a World Wide Web interface to the server that will allow users to request a game against other people or the computer. In fulfilling a request, the computer will start a client program (written in Java) for the user, who will then be able to play the game in a seamless manner using a WWW version of the standard Othello board. This server is quite robust, having stayed running with minimal difficulty for over a week with many different human and computer players competing against each other.

Finally, we have compared the performance of the system between the serial and parallel versions of the computer player algorithm. The results of the tests show that our Mentat version does indeed provide a speedup over the serial version, winning twice as many games as the serial version. As expected, we achieved an order of magnitude gain using the Mentat version, which often searches an entire level deeper. Thus, we have shown that computing in Mentat (in this case) provides a net gain over and above the overhead costs inherent within Mentat.

Build an Othello Server

The Othello Server is a relatively simple set of classes written in Java. The Othello Server serves as a ``go-between'' for players of the game. The Server should be thought of as a meeting ground where all games begin. The Server has certain services that it provides to the connecting players. These services include:

To provide these services the Server must keep a list of all Players currently logged into the server. Certain information about the Players must be stored on the Server for the duration of the session. (login name, opponent) The goal of the server has always been to provide the maximum functionality, with a minimum of commands and protocols. Each time we added a new message to the protocol we attempted to justify its inclusion and make sure that we were not overly complicating the protocol. A brief description of the classes involved in the server:
Client Server Image
Diagram of the client-server relationship

Java Othello Client

The Othello Client interface was written in the Java programming language. A conscious effort was made throughout the project to make the interface as simple and intuitive as possible. Another goal was to make sure that the final product was executable through a Java enabled browser. (i.e. Netscape) We felt that the usefulness and popularity of Java and Netscape would be helpful in making sure our final product was both usable and accessible to new users.

Othello Transport Protocol

The message protocol for Othello was designed to be as simplistic as possible. The following are a list of messages that the Server and Client side respond to. As long as a client and server conform to our specifications then they should work correctly.

Server Messages

Client Messages

Build AI Player in Mentat

In most games, including Othello, there are two players, and one score that both players are trying to affect. One player is trying to maximize the score while his opponent is trying to minimize it. On a player's move, if, for example, he can look at all combination of moves for 3 turns, he wants to pick the move that will give the highest guaranteed score after 3 turns. Notice that this is different from the highest possible score, because the opponent is not likely to play a path that gives our player a high score when a lower one is available!

The algorithm that searches for this best move is called the Minimax algorithm. It remembers the best the score that it can force for all paths, and after all paths are found, picks the path with the best move. We do not need to search every path, however, since we do not need to know all scores, only the best one. Once we find a path in which our opponent can make a move that is worse than a path that we have already explored, we know that we will not be choosing this move, and we do not have to explore the rest of the moves along the current path. This is called Alpha-Beta pruning. For more information, see Patrick Henry Winston, Artificial Intelligence, 3rd Edition.

The strategy we take in creating our Othello program is to use the Alpha-Beta algorithm. However, since we must search for a fixed amount of time, rather than a set depth, we must use an iteratively deepening search, calling alpha-beta first at depth 2, than at depth 3, and so on until our time runs out. In this way, we are always guaranteed to have a result. It also turns out that the number of nodes at level n+1 is much greater than the number of nodes at all previous levels combined, so we can gain this security without much cost.

We can see that the Alpha-Beta algorithm is parallelizable. The best move that we can currently make is the best score that we have found by running Alpha-Beta on the resulting boards of each possible move that we have. In an ideal situation, computing in parallel gives us another level of search depth for free.

This is the strategy that we have used in our program, but there are still difficulties regarding synchronization and reporting scores. For this reason, we have implemented the Mentat Collector Class, described below.

The Design of the Computer Player

The initial step in creating the computer player (named Iago) that operated in parallel was to translate the existing serial LISP code into C++. Once the serial version was debugged, we considered it to be relatively easy to convert the resulting C++ into Mentat-compatible code. In this respect, we were correct --- of the 1462 lines of code, only about a 130 are related to the parallel version. We were able to use the same code for compilation with both g++ and the Mentat compiler MPLC by using a compiler flag ``SERIAL''.

The serial version originally was designed so that a function would search progressively further (i.e. two moves, three moves, etc.), and remember the best score seen. After the time was up, it would stop searching and report the best result thus far. This method did not translate well into the parallel version, however, because our application would have to block while it waits for the results. The solution was to write a collector class that would run concurrently with the main program, which would do the timing. The collector would receive moves from the various workers as they explored the levels. When the time ran out, the main program would query the collector, which would return the best move, score, and depth.

Mentat Image
Diagram of the Mentat Architecture

Initially we had our program work on 30 moves in parallel. In Mentat, these computational processes are called workers. In most cases, there would be more than three redundant workers for each move. Unfortunately, we were still using the original code that tested for a timeout after it had completed a level. As a result, some of our workers were busy thinking on the previous move when a new move began. This resulted in two problems: the collector was receiving moves and scores that no longer were valid, and part of our computational power was being wasted. The solution was to have the workers check more frequently, and to have the collector check that the move being received was not old.

Probably the biggest obstacle when working with Mentat was learning its intricacies. There was a chance, for example, that our workers would get queued on a processor, and would not actually execute. Another problem was the amount of traffic at the collector. Towards the end of the game, the workers were able to look many moves ahead, which resulted in many calls to the register_move function and a subsequent bus error on the collector. To solve this we put a bound on the maximum number of moves that the workers could look ahead.

Other problems with Mentat were related to the overall fragility of this prototype release. Hopefully the new version, being released this summer, will cure some of these ailments. Probably the single most helpful thing we did was to start a subnet of our own that we could run independent of the Legion file system and restart when needed.

Below are a few problems we discovered when working with Legion and Mentat. We list them in order to help other users of the existing system and to highlight areas for improvement in future versions.


Testing was broken up into twenty-five human versus human, twenty-five human versus computer, and 50 computer versus computer games. The latter trials were further divided into 15 serial versus serial and 35 serial versus Mentat games. During testing, we discovered that the serial versus serial games were more deterministic the longer the amount of time that we allowed the computer players to think. As a result, the outcomes of the games became very predictable, and only depended on which computer went first.

The Mentat versus serial games were the most interesting, because they tested our hypothesis that parallelizing the computations would provide better results. fifteen trials were done using a fairly unloaded Sparc20 versus a network of 20 computers of the caliber of a Sparc20 or less. These fifteen trials were broken up into five trials each where the computer was allowed to think five seconds, ten seconds, and thirty seconds. In these runs, the computer only lost five games.

Next, twenty runs were made using the previous network in addition to two compute servers with four processors each. Since Mentat schedules one worker per process, this corresponded to adding eight computers to the subnet. The serial computer used was a compute server. Of these trials, the Mentat Iago lost five games, which gives an overall result of 10 to 35, serial to Mentat.

Qualitatively, the parallel version seemed to go as deep or one level deeper than the serial version. Since distributing the work over multiple computers corresponds to an order of magnitude increase in the number of computations, this result is expected. One shortcoming of the Mentat version, however, was the inclusion of some slow computers in the network. Redundancy helps to alleviate this problem, but on occasion a particular move would not get fully explored in the time allotted and the collector would be forced to make a selection based on less than optimal data. One issue still remaining to be explored is the relationship between redundancy and heterogeneity in the computing network.

Possible Additions

One of the main problems that our program has when playing against other competitive programs around the world is that it is still inefficient. We hope to make some changes to rectify this problem:


The contribution of this project has two major results.

First we have explored Mentat's benefits for complex computations. We have seen a speedup for our parallel implementation. We have also seen at times a very noticable gain of an entire level running in parallel with an exponential algorithm -- which the Othello player is.

Our second goal was to explore the feasibility of having a WWW interface to Mentat objects. Does our system scale well under heavy-load? Our system handles the load that is given now, and in addition we plan to make our server available over the Internet so it will be interesting to see what sort of ``extra'' changes that this will make necessary in our project design.

On the Mentat side, we have implemented sockets in a Mentat application, and have been able to control it via a Java interface, both of which have not been done previously. The Mentat group has expressed interest in using our application for a demonstration.


We would first like to thank the Mentat group for their patience and help with this project. In particular, Anh Nguyen-Tuong and Mark Hyett were very instrumental in solving the various problems we encountered. Mike Nahas also helped during the debugging of the computer player.