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.
- Have open, well-defined specifications for the interfaces between components.
- Minimize dependencies between components.
- Keep components as simple as possible.
- Make the design flexible enough to handle experimentation and prototyping of ideas.
- Make the design elegant from a Go perspective rather than from a software perspective.
- Reuse previous analysis as much as possible.
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
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
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.
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
- Server Framework
- Server Modules
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:
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 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.
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.
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.
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.
The server framework itself is composed of a number of sub-components. They are:
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.
This handles the actual playing of the game. This sub-component performs a number of tasks,
- Constructing a DAG from the modules
- Running the modules in a multi-threaded environment
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
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.
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.