The Distributed Java Othello Environment

Definition and Motivation

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

• Listing all players connected to the server
• Transporting game messages from player to player
• Providing a means for games to begin and end

• OthelloServer - This class starts off the server.
• PlayerList - This is the class that listens on a well-known port for incoming socket connections. It is responsible for admitting new players on to the server, and for managing any communication or services that should occur between more than one player.
• ZombieKiller - This class is responsible for some clean up operations. It is a separate executable thread that wakes up occasionally and attempts to remove any Players from the PlayerList who are considered to be idle.
• Player - As a new connection is made the PlayerList class will instantiate a Player to handle the new connection. The protocol actions are controlled by the Player. Any services that must go beyond the Player are handled through calls to the PlayerList.

Diagram of the client-server relationship

Java Othello Client

Othello Transport Protocol

Server Messages

• USER name
  request from name to login
• WHO
  request for a list of user names
• MSG to-name ``message''
  send a message (chat functionality)
• QUIT
  log this user off the server
• MATCH name
  request a match from name
  a REQMATCH message is sent to name
• ACCEPT name
  accept a match from name
• MOVE [B|W][A-H][1-8]
  example: MOVE BA1
  letters denote column
  numbers denote rows
  The move is sent to the current opponent.
• ENDGAME
  end this game; message is sent to opponent as well

Client Messages

• BEGWHO ``name1 opp1 name2 opp2 ... nameN oppN'' ENDWHO
  list of player names is received with opponents
• USEROK name
  returned after USER command has been sent; indicates that the name sent is acceptable and that the user is logged in
• USERDUPE name
  this indicates that someone else on the server has this name already
• MSG name ``message''
  received a message from name
• REQMATCH name
  match requested from name; respond with an ACCEPT name message
• NEWGAME opponentname BLACK|WHITE
  indicates a new game has been started
  the player given BLACK starts the game
• MOVE [B|W][A-H][1-8]
  example: MOVE BA1
  letters denote column
  numbers denote rows
  The move is sent to the current opponent.
• ENDGAME
  if this is received then end the current game

Build AI Player in Mentat

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 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.

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.

• Regular constructors and copy constructors are not allowed.
• The name of the Mentat class must be the same as that of the binary.
• The main program must have a dummy Mentat class that does not do anything.
• The full path to the Legion binaries must be given to lreg when registering them.
• MPLC does not automatically invalidate old binaries in the Legion system.
• MPLC can not resolve the size of a reference parameter. (Copy it to a temporary.)
• Spurious lock files occasionally exist on the Legion binaries, and the user does not have permission to remove them.
• Occasionally the system fails to reconfigure itself after a host goes down.
• The use of M_RETURN seems to go against the transparent philosophy of the Mentat language.
• MPLC core dumps when a function call is made to a Mentat class, but the parentheses are forgotten.
• Phoenix core dumps if bash is used as the shell instead of ksh or csh.
• When running a subnet, using Control-C to kill phoenix leaves thermometers on some of the hosts.
• When running an application on Solaris, the computations get slower and slower until the system finally crashes.
• Running Phoenix, the Legion subnet controller, on a SunOS machine causes it to spawn processes until it can not fork any more.

Testing

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

• Instead of dynamically creating and deleting memory for each board position, we hope to implement a stack-like structure, and reuse memory as much as possible
• The Alpha-Beta algorithm prunes the most nodes, and hence is at its fastest, when the first move seen is the best one. We can sort our list of moves by the liklehood that it will be chosen, to try and maximize our pruning.
• Many users have expressed the desire to observe games. One possibility would be to implement a variation on the client, where a user could select a game in progress and have the moves reflected on a board.
• People also have an aversion to playing our computer player because they consider it very difficult to beat. As a way of encouraging games against the computer, we could implement a natural language interface similar to the Eliza program. This way, people would have a harder time differentiating between a human and a computer.
• Lastly, we hope to test the extent to which we can generalize the system by implementing another game, using the same basic architecture and protocol.

Contribution

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.

Acknowledgments