Moyoman: a Go playing program
There is a long and successful history of Chess playing programs. One of the strongest,
Deep Blue by IBM, is as strong or stronger than the best human players. In other games such as
Checkers or Othello, it is even easier to write a computer program that can outperform the
best human players. Yet for the game of Go, no one has written a program that can play as well as
even a mediocre human player.
The basic algorithm used by all serious Chess programs is a variation of the minimax search. That is,
the program examines all of its possible moves, each of its opponents countermoves, etc. Each possible
board position is then evaluated using a static evaluation function. This is a simple algebraic
algorithm which is the sum of different factors, such as the number and type of pieces on the board
each of which is multiplied by a weighting factor depending on its importance. There are two ways of
improving this procedure; searching more levels ahead, and improving the static evaluation function.
The ability to search more levels deep is the most important factor. As of 2002, Deep Blue
only uses four factors in its static evaluation function, but it is a massively parallel machine with
256 special purpose VLSI Chess processors and is capable of analyzing over 300 million board positions
per second. By searching the problem space enough moves ahead, even a very simple evaluation method
can produce very powerful results.
The total number of possible games in Go is so much larger than the number of possible games in
Chess that the basic algorithm used by Deep Blue and other Chess playing programs is useless for
developing a Go program, at least for the game as a whole. In addition, even if the size of the search
space were not a problem, creating a simple static evaluation function for Go is an even more difficult
problem. Certain clearly defined problems, such as life and death, can make good use of the search
algorithm; however a different approach is needed in order to write a program to play Go. Two
different subproblems need to be addressed: the design and implementation of the software, and the
organization needed to do the work.
The design for the Moyoman Go playing program described here is based on five major assumptions:
- Writing a Go playing program is a very large problem.
- The problem can be broken up into well-defined components
- Analysis can be done incrementally
- We understand what needs to be done much better than how to do it.
- There is a linear ordering of components
Writing a Go playing program is a very large problem.
If you identify all of the types of processing that need to be done in order to have
an amateur dan level program, you will quickly realize that hundreds of person years
of effort will be required. A single person or small group of people will not be able
to write a good Go playing program, because the problem is just too big.
The problem can be broken up into well-defined components
Any competent Go player is aware of the standard way that the game of Go is analyzed.
There are a number of concepts, such as making good shape, specialized moves for the
opening and endgame, life and death, etc. The Moyoman framework treats each of these
problems independently of the others. That is, a module such as LifeAndDeath is
solved independently of a module such as Shape. The only interaction among modules
is that a module can take other modules as inputs. For example, the Life and Death
module may take the Board and Groups modules as inputs. There is an ordered list of
module types, and a module can use the ouput of any modules which preceed it on that list.
Analysis can be done incrementally
If human players are shown a half completed game, it may take them several minutes
of concentrated study to analyze the game and determine the next move, while the players
who have been playing that game can make a reasonable move within several seconds.
It is assumed by the Moyoman framework that many modules can benefit by saving the results
of their analysis, and only doing an incremental analysis for the last move made.
Of course, in some cases such as when a large groups of stones is captured, it may be easier
to analyze the board from scratch. It is expected that this will only happen once or twice
a game, and that for most moves the incremental approach will work better.
We understand what needs to be done much better than how to do it.
As mentioned above, the definitions of the subproblems in analyzing the game of Go are well understood.
What is not at all well understood are the algorithms for solving them. A strong player
may be able to state for a given board position which moves would make good shape and which
would make bad shape, but he would be hard pressed to give an algorithm for generating
this information. Given this fact, the Moyoman framework allows for different implementations
of the same module to be part of the code base. Only one implementation of a given module type
would be executed at one time, but development work can proceed on each implementation
independently. It is easy to substitute one implementation for another since all implementations
of a given module must implement the same interface. This allows for a huge amount of
parallel development and exploration of ideas.
There is a linear ordering of components
The components defined would be given an ordering, where a component could use the
results of any components which preceeded it on the list. Thus, The LifeAndDeath
component could use the results of Board, Groups, Shape, and Tesuji components, but Tesjui
could not use the results of the LifeAndDeath component. This may be the most
problematic of the assumptions since there may appear to be circular dependencies
among the components. This problem will be dealt with as it occurs.
In the past, Go programs have been written primarily by one or a small group of people. There are certain
myths that have arisen about Go playing programs. It is believed that it is very difficult to
write a good Go program. This is a result of many people trying, and none succeeding.
This does not necessarily mean that the problem is hard, merely that it is a large problem. It may
very well be that solving this problem is more than can be done by one or two people in one lifetime.
Of course, it is certainly a hard problem as well as being a big problem.
Given the success that projects such as the Linux operating system and the Apache web server have
enjoyed as a result of being open source and having the contributions of many people working together,
it would be interesting to try a similar strategy with developing a Go playing program. All of the
source code would be freely available. The most important challenge is
to develop a framework within which different people can work and develop their ideas. The difference
between developing a web server or even an operating system, and writing a Go playing program is that
the first two problems are well understood, even if the implementation is technically complex. No one
knows how to write a good Go playing program yet, and so a solution cannot be defined by a few people,
with outside contributors merely implementing it and fixing bugs. A flexible framework is crucial,
so that different people have a way of experimenting and trying out various approaches. Developers
would write components referred to here as modules. There is a list of well-defined module types,
and there can be more than one implementation of a given module type. This will
allow the program to evolve and use those modules that prove to be effective, while discarding those
that do not work well without having to redesign the program as a whole. While it would be
prohibitively expensive for a commercial project to take this approach, the large number of Go
players who are also software developers would make this approach feasible.
This flexible framework will be implemented with the help of two design rules. First, there
will be an abstract base class which all modules are required to extend. Second, the interface for each
specific module, such as LifeAndDeath, will be standardized. This not only allows other modules
to easily use the LifeAndDeath module, but it allows for multiple versions of the LifeAndDeath
module to be written using different approaches. Developers would have the choice of enhancing an
existing module, or writing a new one from scratch as long as it corresponds to the approved interface,
neither leaving out any functionality, nor adding any new functionality. In this way, modules which
use the LifeAndDeath module do not know or even care which implementation of that module type they are using,
since they all implement the same interface. Note that the crucial assumption here is that the
definitions of the modules can be determined up front and do not require very much experimentation.
It is also useful to consider that there is a great deal of expertise in the Go playing community
that can be put to use, both software development talent, and Go playing talent. The software
developers will be of great use in developing new modules, debugging and optimizing old modules, and
reviewing the fundamental soundness of the software framework, and the modules that are running within
it. The strong Go players will be of great use in analyzing games played by the program and
analyzing the results of individual modules, as well as helping to devise the specifications
for new modules that need to be developed.
Ideally, there would be legions of very strong Go players with advanced computer skills to work
on this program. In practice, very few of the people working on this project would be very strong
at both Go and software development. Thus, it is important that the program be as easy to use as
possible, even when the user is trying to debug the internals of the program. This means that
each module will be required to produce debugging information which can be displayed graphically.
For example, a scoring module would produce output which would indicate which points are considered
black territory, which ones are considered white territory, which ones are dame points, and which
ones are considered to be partially the territory of one player or the other but not definite
territory. With the use of a graphical client program, a strong Go player can then assess the
accuracy of this analysis, and submit a bug report if necessary, without having any programming
Control over the development process would work in a distributed manner. A core person or small
group of people would control the development of the framework and integration of bug fixes and
enhancements into the framework. They would also review proposals for new modules, and finalize the
specifications for those modules. A person or group who creates a module according to the
specifications would have control over the enhancements for that module, but they would not
have control over the specifications for the module. This would allow other people to develop their
own versions of any particular module. Thus, people can choose to either cooperate on the development
of a given module, or compete
in writing the best version of the module. In either case, since the specification of the module is
the same, any of the different versions could be used interchangeably. In the case of competing
modules, they can be reviewed by the testing group, and the best one would be part of the
production release. A production release could contain multiple versions of the same module,
with the actual one being used being controlled by a configuration file. For example, the user could
be given the option of having the program make the best move, or the fastest move. A tool would
also be provided to allow the advanced user to have the ability to specify which version of each
module is to be used. Generally speaking, the higher the level of the module, the greater the
opportunity for people to write different versions of the module. For example, a module that
estimates the current score of the game would leave much more room for experimentation than a module
that determines the different groups on the board, and how many liberties they each have.
It would also be important to have a parallel testing and evaluation group, which is responsible
for ensuring that module implementations implement the specifications as intended, and to evaluate
which module of each particular type is best. It would be best to have an independent group which
is not involved in developing any modules to work on the evaluation. Note that some of these
people could be strong Go players without any programming knowledge.
It is possible to allow the interface for modules to evolve over time. That idea is explicitly
rejected. The reason is that if one of the implementers of a module wants to add new functionality,
then all of the other implementations of that same module would have to update their modules, or they
would become obsolete. The much preferred approach would be to have a new module which uses the previous
module, and adds the new functionality. Unlike most software, the requirements for the back end do not
change over time, so it should be posssible for a well implemented module to be used for many years without any changes required. This should make it clear that the most important ongoing
task facing this project is to thoroughly review module specifications before any implementations are done.
The following is a list of the features that the Moyoman server program will provide:
- Play a game of 19x19 Go
- Provide a framework for experimenting with different ideas about how to write a Go program
- Provide human readable feedback about how the program evaluates moves
- Provide options for best play, quick play, or tournament play
- Provide internationalization support
- Allow for easy automation of computer - computer play
- Provide a graphical user interface
Play a game of 19x19 Go
The purpose of this program is to play standard Go. Whenever an attempt is made to make software
more flexible, it also becomes more complicated. The design of this program will be complicated
enough without worrying about playing 9x9 or 13x13 Go. The rule set is not hard-coded, and so
the user will be able to choose among a variety of rule sets for playing the game.
Provide a framework for experimenting with different ideas about how to write a Go program
This is the main idea which distinguishes Moyoman from a program such as GNU Go, and will be
discussed in much greater detail throughout the documentation for Moyoman. The basic idea is
to spread design responsbility among a large group of developers, and make the barrier to
contributing code as low as possible.
Provide human readable feedback about how the program evaluates moves
This is used for two major purposes: first to teach the weaker Go player about how to analyze
a board position, and second to provide debugging information. The developer can then use the
graphical debugging information from a module to determine how to improve the algorithm,
and the advanced Go player who is not a software developer can critique the performance of
individual modules without having to know anything about software. Once the program has reached
a certain level of play, this user will be crucial in allowing the software to become better.
Provide options for best play, quick play, or tournament play
Since there can be multiple implementations of the same module, the criteria for comparing these
modules can be somewhat arbitrary. Two of the obvious options are select the module that produces
the best results regardless of the speed and memory resources required, and for users with
less powerful computers the module that gives the best results/resources ratio. A third option
would be tournament play, which would be used to allow Moyoman to compete in tournaments. This
option would not be important until the program is better than 10-kyu in strength.
Provide internationalization support
There is no common language among Go players. When a user requests human readable feedback
about a module, he has a right to expect that he can understand the information which he
is presented. English will be supported, since it is the only language that the original
developers speak, but Chinese, Korean, and Japanese will be the primary language for many
of the users of the system. It will be important to support major European languages as
well. The Moyoman framework supports internationalization since Unicode is used as the
underlying representation for text. Tools are provided to support internationalization.
Any language for which someone volunteers to act as translator will be supported.
Allow for easy automation of computer - computer play
Developers who are implementing learning algorithms, or testers who want to evaluate different
module implementations would like to have the program play against itself. The framework makes
it easy to automate this process, with two different configurations of the software playing
against itself, changing configurations automatically, or changing handicaps based on the
results of previous games.
Provide a graphical user interface
Although the focus of this project is on the back-end move generation algorithms, it is important
that the end user can view the results of the game in an easy to understand format. Since the
Moyoman program generates debug information in a way that is not supported by any existing client,
it is necessary to provide a client that the end user can run.
When the philosophy of incrementally computing more information about the board is considered in
conjunction with having many people involved in developing the different software modules, the
necessity for a framework for managing these modules is clear. The software framework will provide
the following features:
In order to allow the different modules to work together, a base class will be defined which each
module must extend. It will provide for things such as letting the module register with the
framework and notifying the module when it is time to start processing the next move.
- Provide a standard base class that all modules must extend.
- Provide a standard interface for each specific module type.
- Provide a multi-threaded environment in which the modules can run.
- Determine the correct order in which to run the modules based on the dependencies among them.
- Allow games to be saved and restored from disk or the network.
When loading a particular module, e.g, Endgame, the framework defines the interface that
the Endgame module must implement. The module is required to implement that interface exactly,
and not have any additional public methods.
In order to allow the different modules to run efficiently, the framework will start multiple
modules each in its own thread. Different modules may take different amounts of time to run, so new
modules can be started when others have completed their work.
Almost all modules will be dependent on the work of other modules. It will be the job of the
framework to determine the order in which the modules need to run based on their mutual dependencies.
This will also determine the extent to which multi-threading can occur at any given time.
The framework should also have the ability to save the current state of the game, and the
ability to read it back later and restart the game from that point. This can be used to implement
the taking back of moves, and also for crash recovery.
The Java Programming Language
It has been decided to implement the Moyoman server program in Java for the following reasons:
Any inefficiency caused by running Java code will be more than offset by the accessibility
of the program. It is a goal of this project that setting up and running Moyoman should be as
easy as possible for the novice computer user. This means that the program should
not require many peripheral software products to run, such as web servers, databases, etc.
Installation on a single computer should be a point and click process to encourage the use
of the program.
- The program can be distributed in a ready to run, operating system independent format.
- It is easy to support system dependent functionality such as sockets, threads, etc without
having to write platform-dependent code.
- It is easy to save objects as a serial stream and read them back in again.
A Word about the Design Philosophy
Often, when designing software using Java, the solution can become extremely complex.
Creating a distributed, fault-tolerant server using J2EE technology can involve having at
least a half dozen different middleware products to take advantage of such technologies
as Enterprise Java Beans,
Java Messaging Service, etc. For almost all users of our software, having a distributed,
fault-tolerant system is not a requirement. The typical user will be running the program on
their PC, and there will be just one human player. Our solution will be to make our software as
easy to install and configure as possible. There will be a single executable jar file which contains
the clients and a server. Installation will involve copying files
to a directory. Running the software will involve double-clicking on a jar file. This rule of
simplicity will not be violated without a compelling reason. For example, if a browser based
interface is to be implemented, then running a web server and servlet engine would be required
as part of installation. This optional installation would be more involved, but would not
make the standard installation any more complicated. This would be an option because it is valuable,
and provides useful functionality that a single executable program does not. We will not use EJB, JMS,
etc, etc unless the resulting system is no more complicated than the solution
already described, or unless they are part of an optional, advanced system in which the additional
functionality provided justifies the extra complexity.
The nuts and bolts of the software are the modules. These are small self contained units of code
that perform one Go related type of analysis. Whatever analysis has already been done is saved until
the next move is passed in as a parameter to a method, and analysis continues at that point.
Modules would mostly represent Go specific concepts, such as joseki or life and death, but they
could also represent concepts that are not Go specific, such as a geometric analysis of the board
to determine which groups are adjacent to other groups. The important points to note about modules are:
- A standard interface for a module is created and approved by the core development team,with
input from all interested members of the development community.
- The dependencies among modules are not part of the interface of a module, so one implementation
of the module that determines the score might use the results of the life and death module, and
another might not.
- The dependencies among modules are specified dynamically, and the order in which module types
are executed, and which module implementations are executed for a given module type are determined
at run-time by the framework.
- Module types are given an order, so that the subset of module types for which a given module
can use the results is defined. This prevents any circular dependencies from occurring.
By having a software framework that allows for the work of many different people to be integrated
together, the possibility of writing a high quality Go playing program is greatly enhanced. People
can contribute in the area where their talents and interests lie. People interested in low level
problems such as life and death or joseki can work on those areas. People interested in less well
defined problem areas could try to implement versions of shape or fight or kamikaze. Those with high level
interests can try their creativity by attempting to implement the strategy or move generator modules.
Still others could work on the specifications for new modules without actually implementing them.
Those who have an interest in user interface design can develop new front ends for the server.
The non-programmers can contribute by evaluating the output of each module in a given situation,
or evaluate the play as a whole and critique the results. Others can translate the output strings
into different languages. By combining the efforts of many different people,
it may be possible to generate a high level of play within a reasonable time frame.