Moyoman: a Go playing program

Introduction

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.

Philosophy

The design for the Moyoman Go playing program described here is based on five major assumptions:
  1. Writing a Go playing program is a very large problem.
  2. The problem can be broken up into well-defined components
  3. Analysis can be done incrementally
  4. We understand what needs to be done much better than how to do it.
  5. 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.

Organization

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

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.

Features

The following is a list of the features that the Moyoman server program will provide:

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.

Framework

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.

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:
  1. The program can be distributed in a ready to run, operating system independent format.
  2. It is easy to support system dependent functionality such as sockets, threads, etc without having to write platform-dependent code.
  3. It is easy to save objects as a serial stream and read them back in again.
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.

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.

Modules

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:

Conclusion

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.