Moyoman High-Level Design Document

Moyoman High-Level Design Document

Assumptions and Underlying Principles

The Moyoman Go playing program will be developed using the following design principles:

Make the design as simple as possible

The meaning of this statement is that there should be as few different software components required to run the Moyoman program as possible. For each additional level of complexity that is added, there should be a compelling reason. The client and server are different components for obvious reasons. Adding an http interface would be a compelling reason for adding a requirement for a web server and servlet engine. However, this is okay since these would be optional, and a single user installing the software on his personal computer would not have to install them. A much higher standard would have to be used if required components were to be added, such as adding a database such as mySQL in order to store josekis. While this might benefit the joseki module, it would make installation for the user much more involved, and so might hinder the use of this program. Writing a custom application and format for storing joseki, while possibly less elegant, would be much better for the end user.

Have open, well-defined specifications for the interfaces between components.

The interface between the client and server is contained in the org.moyoman.comm.client package. There are just a few classes such as PlayerManager and CommandExecutor that a client needs to use.

New clients that want to use a different input method, such as communicating with another Go program over a socket using a standard Go protocol would just have to implement one new Player class. Instead of using MousePlayer or MoyomanPlayer, they would write a new Player such as GTPPlayer.

The org.moyoman.comm.client package is designed to allow different means of the client communicating with the server. So, if a client wanted to use GTP to communicate with the server on a different machine, the developer would write a new CommandExecutor such as GTPCommandExecutor to communicate with the server. Of course, the corresponding classes would have to be added to the org.moyoman.comm.server package so that the server could process incoming GTP commands.

In addition to external interfaces, this principle also applies to components of the Moyoman server. The interface for each module of Moyoman will be standardized, and approved by the developers working on Moyoman. It is important that each life and death module have exactly the same external interface. This allows for different life and death modules to be interchangeable. Modules that use information from the life and death module should not need to know which life and death module is being used in any particular version.

Minimize dependencies between components

It should be as easy as possible to replace components in the system with different ones. Any client can be used that can use the org.moyoman.comm.client package. Any module that implements the approved life and death interface can be used. A life and death module will not be allowed to implement additional functionality. If additional functionality related to life and death is to be added to the system, it will be added as a new module which is dependent on life and death. A standard interface will be approved for this new module. In this way, the life and death functionality can be increased, but older life and death modules do not become obsolete. This is especially important in an open source project such as this one, where an excellent implementation of a module may be made by someone who stops work on this project after some time. Their work should never be made obsolete.

Keep components as simple as possible

It is important to keep each module as simple as possible. This is good for a number of reasons. First it avoids the problem of a "super module" where much of the code for making a move resides in just one module. Second, it makes it easier to assemble the best components into one program. If a module performs five tasks, then implementation A might do the best job on two of the components, implementation B might do the best job on two of the components, and implementation C does the best job on the remaining component. There is no easy way to use all of the best components. By making components as simple as possible, this problem is avoided.

There is a tradeoff between making modules simple, and making them easy to use. For example, the Joseki module would probably search for a given line of play in a dictionary, and suggest the moves that continue from the given position. There would also need to be some way of dealing with moves that are not in the joseki dictionary. As mentioned above, one implementation might handle the dictionary best, and another one the out of book moves. One could define two modules, but the users of this module don't care if a move is in the dictionary or not, they just want to know how to play in the corner.

The solution used by Moyoman for this problem is to have helpers. A helper is associated with a given module type, such as joseki, and performs a subtask, such as looking up moves in the joseki dictionary. The advantage of this is that one dictionary helper could be written, and be used by many different groups that try to write the out of book component. Using the helper is not required, so if an implementation of the joseki module uses neural networks and does not distinguish between dictionary and out of book moves, it does not need to use the helper.

Make the design flexible enough to handle experimentation and prototyping of ideas.

Some of the previous design principles have already addressed this. The different Go playing modules should be simple and independent of one another in terms of the way that they are implemented. Thus, one person might implement a life and death module using minimax search, while another might use neural networks or pattern matching. These competing modules can then be compared with each other on the basis of ability to solve life and death problems as well as time to execute, and the amount of memory that they require. In any case, no other modules should know or care what algorithm is used to achieve the result. The well-defined interface allows different people to try out different ideas.

It is obvious that any good Go playing program would need a life and death module, but people may have ideas for module types that are more controversial. The framework would still allow for this type of prototyping and experimentation. An interface could be defined and an implementation written, but if it turns out that this type of module is not useful, then it would just not be used. The Moyoman framework determines the order in which modules run, based on the fact that the board module runs first, and the move generator runs last. Only those modules which are used by other modules which are ultimately used by the move generator will run. This allows for modules to be implemented which may not be used, or which may be used in some configurations of the program and not others.

Most of the flexibility that has been discussed so far is at the module level, where different developers can implement modules in their own way. Some support is also needed for design flexibility at the sub-module level. The helper module approach mentioned above can help with that. If it is not clear how to subdivide the life and death problem, then different helper modules for life and death can be defined. Different developers can implement competing versions of these helper modules, but more importantly, the life and death module implementor can choose which subset of these helpers to use in his life and death module. In that way, different decompositions of the problem can be tried, but the end user will only use the life and death interface, which will remain unchanged, so the experimentation related to the life and death module and helper modules will not require any code changes in the rest of the modules.

Make the design elegant from a Go perspective instead of from a software perspective.

The above design principles should allow for different ideas related to producing the best possible moves for a given position on the Go board. There are many other things that might appeal to software developers, such as having a CORBA interface in the framework to allow for modules to be written in different programming languages, or using cutting edge features of Java J2EE, such as JMS, EJB, JXTA, etc. If this does not add value from a Go playing perspective, then it will not be used. The guideline here is whether you can explain to a novice computer user who is also a strong Go player why this feature is important. If you cannot, then it will not be used, because the concern of this project is to make a strong Go playing program. The technology is of secondary concern, and is chosen to facilitate addressing the primary concern. This cannot be too strongly emphasized. The reason for using Java instead of C++ is not because of someones personal preference, but because certain language features such as the Class.forName() method, and portable support for multi-threading, sockets, and serialization of objects make it the better choice for this project.

Reuse previous analysis as much as possible

This might be the single most important design principle listed here. Unlike the way in which Chess, Checkers, or Othello programs are written, this program is intended to mirror the way that human beings learn and improve at Go. It is not meant to be an exact match, but there will be some similarities in the way that a person learns to play Go and this programs skill develops over time. The basic Go concepts are implemented and made more sophisticated over time, and more sophisticated concepts are added later. It is well known that an experienced player in the middle of a game can make a reasonable move within a few seconds, but if he is shown a game that he has not seen before it might take several minutes for him to analyze it and determine a reasonable move. The same is probably true of the approach that we are taking for Moyoman as well. For the life and death module, if a record is kept of the life and death status of each group on the board, when a move is made, the status of only a few groups will change. It is much easier to do an incremental analysis of those few groups then to recompute the status of every group from scratch. Similarly, if there is a splitting attack analysis module, it is much easier and quicker to determine whether the last move is making a splitting attack, than to look at every single stone on the board and figure out which of them are splitting attacks. It may not be easier to write the code to do the incremental analysis than the analysis from scratch, but it should use much less processor time and memory. This leads to the major assumption of Moyoman, with enough processing, a very good move can be generated. The only major limitation would be the speed and memory of the computer, so by reducing the amount of work that needs to be done by doing the incremental processing, a very good move should be generated in a reasonable amount of time. Note that there may be exceptions to this rule. If a large group of stones is captured, this may affect the safety of a dozen different groups on the board. In this case, the analysis would almost certainly be faster, easier, and less error-prone if done from scratch than if done incrementally. Rather than have an incremental algorithm that can handle any case, it would be easier and more reliable to have an analysis from scratch algorithm that is called in cases like this. This would usually only happen once or twice per game, and so the increased time for that particular move is not important, since the performance goal is based on the time for the program to play a complete game, not the time to make any particular move. Note that the analysis from scratch algorithm can always be implemented as a series of incremental analyses where the stones currently on the board are added to an empty board one move at a time. The incremental analysis is only an optimization, not a fundamentally different type of analysis. However, if saving state between moves is the difference between taking one hour per game versus taking one hour per move, then this would have huge practical consequences.

Components

This document describes the components of the Moyoman program at a high level. There are low level design documents which describe each of these components in a much greater level of detail. The following are the major components of the Moyoman Go playing program:

Client-Server API

The client API provides an easy to use interface that the client program accesses in order to use Moyoman as the server. Any class that uses the org.moyoman.comm.client package can communicate with the server. Currently, the DirectCommandExecutor class makes direct method calls to the server, but other implementations could use the Go Text Protocol (GTP) over a socket, or use JNI to provide an interface to a C language client. The major classes in the org.moyoman.comm.client package are:

CommandExecutor

The CommandExecutor abstract class defines methods for communicating with the server. Currently, there is a DirectCommandExecutor derived class which makes direct method calls to the server. This requires the client to be running in the same JVM as the server. Other derived classes could be written using sockets, CORBA, JNI, etc.

Player

Player is an abstract class which represents one of the players in the game. Currently, there is a MousePlayer derived class which is used by the person at the computer keyboard to make moves, and a MoyomanPlayer which communicates with the server to make moves. Classes would not derive from Player directly, but from either of its two derived classes, NonvalidatedPlayer or ValidatedPlayer.

PlayerManager

The PlayerManager class allows any two objects derived from Player to play a game. The client creates the two Player objects, and passes them to the PlayerManager object.

NonvalidatedPlayer

The NonvalidatedPlayer class is an abstract class derived from Player. Client written Player objects can derive from this if they do not do their own validation. For example, MousePlayer is derived from NonvalidatedPlayer. If the user enters an illegal move, it is detected automatically, and an error is returned.

MoyomanPlayer

This class derives from ValidatedPlayer, and interfaces with the server. This class is passed a CommandExecutor class on construction. It is not necessary to write a new MoyomanPlayer to use sockets or JNI, but just to write a new CommandExecutor class to use instead of DirectCommandExecutor, and pass that to the MoyomanPlayer class.

Server Framework

The server framework itself is composed of a number of sub-components. They are:

Storage

One of the features that the server framework will provide is the ability to take back a move. When relying on algorithms that compute information incrementally, it would be tedious to recompute the previous state. No one will want to wait 45 minutes to take back a move. The storage sub-component handles the details of serializing all of the modules in the program, and restoring the board to a previous state. It also handles resuming a game if the program has crashed and is restarted, or providing the functionality of allowing a user to save a game, and continue playing it later.

Play

This handles the actual playing of the game. This sub-component performs a number of tasks, which include:
Constructing a DAG from the modules
Modules specify at run-time which modules they are dependent on. The reason for this is that the dependencies are not specified as part of the specification for the module, so one ko threat module may be dependent on the life and death module, while another one is not. Each module specifies which other modules it is dependent on. Each module must be dependent on at least one other module, except for the board module, which is first by definition. A directed acyclic graph is generated which shows the dependencies among all of the different modules. The definition of each module has a number associated with it, and modules can only use lower numbered modules. This prevents the problem of cycles in the graph.
Running the modules in a multi-threaded environment
The DAG which was generated by the previous sub-component is used by this component to run each module as its own thread. The algorithm for this is straightforward. The board module is run as its own thread. When this has completed, all modules which are only dependent on the board module are run. From this point on, each time a module completes, any other modules which have not yet run, and for which all the modules that they are dependent on have completed are started in their own thread. This continues until the move generator module has completed.

Text

This handles displayable text and internationalization. The client obtains the displayable text from the Message class based on a symbolic name. There is a tool which allows for the translation of text from one language to another.

Server Modules

Each module is derived from a base class provided by the framework. The base class defines some of the methods that the derived class needs to implement, as well as providing some generic functionality such as retrieving the id of the current game. Additionally, the module must also implement an interface specific for that type of module. For example, joseki and life and death would each extend the same base class, but would implement the joseki interface or life and death interface. A given module may only implement one interface. Deriving from the base class and implementing the interface for the module are the major things that the developer of a module needs to understand. This is discussed extensively throughout the documentation for Moyoman.