The requirements for and the architecture of a programming environment that facilitates the research and development of a strong Go playing program are described. The environment has been successfully developed and is in use.

1. Requirements *

2. Highest Level Classes *

Figure 1 - Top Level Classes *

Figure 2 : Board, Piece, String, and Related Classes *

Figure 3 - Portability Classes *

This paper describes the software organization, class hierarchies, of an environment that facilitates the development of and research in a program capable of playing the game of Go.

1. Requirements


The program must be able to communicate with both programs and people, located locally and remotely.

The program must be able to play a game of go with a person at superior strength.

The program is to be used as a vehicle for experimenting with techniques to play go well. Such techniques as machine learning, genetic programming and other techniques are to be easily facilitated. This work should not interfere with the rest of the program, and much effort should be spent to make available components of one part of the program to another: such things as game display code, scoring code, go game format code, etc.

It should be capable of running completely automated against other programs or remote users. This will be done through support of the Go-Modem protocol, the Internet Go Server protocol (IGS), and the No Name Go Server protocol (NNGS).

The code should be portable to UNIX AIX, UNIX Solaris, Windows NT and Windows 95.

The code should be extensible to any operating system that supports threads.

The code should be capable of using different user interfaces or GUIs with little or no work.

2. Highest Level Classes


To meet these requirements, the program is put together in a way that operating system dependencies are encapsulated in a set of generic service classes, such as a Thread class. These operating system primitives are combined with a set of sized types (signed 8 bit = S8BIT, unsigned 16 bit = U16BIT), instead of the C++ sizeless native types (short, long, char, int, etc) that help give portability over the compiler and hardware. Together these provide a high level of portability.

From these building blocks is built the following high level abstraction that address the different kinds of player support that are required:
 


Figure 1 - Top Level Classes

1. Referees and Players


The environment is composed of a single Referee object. A Referee can create players that play each other. The players can be people playing on the same computer, or players that are remote – playing via the Internet or via a modem connection. Players can be a person or a program. To accomplish all these different kinds of connections, the Referee creates two PlayerProxy classes, each of which mediates the connections between the actual players, wherever and whatever they may be. The Referee then monitors the game and can interrupt it and record it as necessary.

It would be possible to have multiple Referees each with a pair of Players. For some kinds of experimentation, such as Genetic Programming, it is beneficial to support multiple, simultaneous games especially on computers with multiple CPUs as a way to more efficiently evolve populations. The point being that this architecture could be easily elaborated to support this.

Both PlayerProxys and the Referee are (subclassed from) AsyncMsgHandlers, meaning that they can rapidly be posted a message containing a command or a response, and then, sometime later, they will run and process that message. This allows for each player to operate seemingly at the same time. The AsyncMsgHandler class uses portable thread and semaphore classes in its implementation.

This design allows adding different kinds of clients as they come along… For example, a Player that interfaced with a Java or Netscape browser plug-in could be added simply. Or a database client that could look up moves in databases could be added.

2. User Interfaces and GUIs
The Referee provides a console or GUI interface, depending on the platform that the program is running on. (Currently only a console interface is implemented.) The Referee user interface controls which kind of competitor will play against each other. Each type of competitor then provides it’s own interface. Note that Players are interface specific: there is a console type interface and a GUI type of interface.

It would be best to de-couple the interface from the Referee as it is from the Player. This is not yet done.

3. The Referee and Players
1. Referee Class

1. PlayerProxy - Each of these front-ends a player. Any two can play each other.
1. GameDisplay - The view of the game from the referee’s perspective.
1. DataBoard - The state of the game and board.

The Referee class creates and uses PlayerProxy classes, and encapsulates the DataBoard and GameDisplay classes. There are only two PlayerProxys at any one time, one for each opponent. For the convenience of the Players, a read-only instance of the DataBoard, which contains the rules and state of the game, is made available to them. Each may make a copy of the DataBoard for their particular purpose. In this way, a formal division is made between the rules and procedure of the game, and the strategic and tactical knowledge developed in the computer opponent to win.

1. PlayerProxy Class


This class is the base-class of all players. Each player is assumed to be operating asynchronously from each other; this is the general case. A player on the Internet playing someone linked via a modem. Each player is operating independent of the other. The actions of each player are transmitted via the common functions of the PlayerProxy class to the Referee class. In this way, different kinds of players can be implemented and can all play against each other as a measure of each opponent’s progress. This class provides a uniform interface between the Referee and a particular player.

2. GameDisplay


This is an abstract representation of a displayable board that represents the referees view of the game including the history of moves and current status.

3. DataBoard


The DataBoard provides enough basic information to play and track the state of the game. The referee uses it to do it’s job. All the information necessary to obey the rules of the game including setting the board size, detecting and preventing Ko, allowing or preventing suicide, removing killed stones, scoring a game, and determining when the score is final (game over) are stored in the DataBoard and in the classes it uses. The DataBoard provides the means to add, examine, remove and takeback pieces from the board.

Super Ko checking is provided via a hashing scheme.

Fully Enclosed areas are detected. Ponuki’s are detected and used to estimate controlled space. No influence function is provided. The DataBoard can detect if the game is over by determining that all the board space is occupied or contained by ponuki. This means that the game must be played out to the very end, if such automatic game scoring is to be used. Humans will not stand for it, but for some computer go algorithms, this is sufficient.

A copy of the board is available to players as a way for them to work the game.



Figure 2 : Board, Piece, String, and Related Classes

The board and the related important classes are noted below.

1. BoardCell


A board is composed of an array of BoardCells. The non-empty ones point to the GoStrings which contain them. A BoardCell also contains a Piece, which contains the color of the cell and it’s location. Thus the Piece can locate the BoardCell it’s in and vica-versa.

2. GoStrings


Are a collection of contiguous BoardCells. The GoString can report the number of stones in it, the number of liberties around those stones. GoStrings can be used to store lists of liberties as well. GoStrings suport invisible marks on the board to faciliate liberty counting and other operations. GoStrings can be added to GoStrings as is the case when they are joined.

3. GoStringCollections


There are collections of white and black GoStrings. GoStrings can be added or removed from a GoStringCollection. These collections can be used to store related GoStrings, such as armies or blocks. They can report the number of strings in them and the total liberties of the collection. GoStrings can remove dead GoStrings in it..

4. HistoryElement


Each move and pieces killed by the move are stored here. This is used by the DataBoard to support taking back a move.

5. History


A collection of HistoryElements comprising the moves of the game in order. This is used by the DataBoard to support recording the entire game and in taking back moves. In addition, this can be used to support pushing and popping moves when searching.

6. Enclosure


A contiguous chain of empty BoardCells. Includes information about the enclosing GoStrings. In other words liberties and potential eyes.

7. Enclosures

1. Supported Player Classes


Each of these is a (subclass of) PlayerProxy class. The PlayerProxy class provides a uniform, asynchronous, message based, callback interface between a player and the referee.

Players are specialized versions (subclasses) of a PlayerProxy. Each player implements a different kind of Go opponent. Some are merely interfaces to the human player at the computer, others might interface to people playing over the Internet or by modem, and others might interface to a local or remote computer opponent.

1. Computer Go Prototype: Circlet.


This encapsulates the computer Go program that is the heart of the project. The results of this class are detailed in [Greenberg 97].

2. Human: Console Interface


This is a command-line style interface. It is completely scrolling, lacking even a UNIX "curses" style interface. A "curses" style interface could be implemented in a similar class.

3. Modem: Go Modem Protocol


This protocol is commonly implemented by Go programs and is used in Go program competitions. The standard is publicly available. [Ref].

4. Wally Public Domain Go Program


This is an interface to the public domain Go playing program, Wally. Wally plays very poorly but better than randomly. [Ref]

5. Human: Windows Interface(*)


This is a Microsoft Foundation Class (MFC) based Windows interface for playing Go. ((This is planned - not implemented yet))

6. Random


Plays randomly. The Referee rejects all illegal moves. Thus if Random makes a bad move, it is rejected by the Referee and then solicited to make another move. After a fixed consecutive number of failed attempts, it passes.

7. IGS/Internet Go Server and the No Name Go Server (*)


These are two related interfaces for playing Go on the Internet. Both humans and programs can play here with players world-wide, their scores maintained, and rankings made available. ((This is planned - not implemented yet))

8. Go Database(*)

1. ISHI
1. Smart Go Format (SGF) [Muller]
1. (etc.)

1. Portability Classes


There are classes providing portability across various operating systems. The system is currently runs on Sun Solaris, UNIX AIX, and Windows NT.

Classes have not yet been provided to abstract the GUI, yet.



Figure 3 - Portability Classes

1. Operating System (OS) Portability


These are classes that provide an abstract OS capability. For a given operating system, there is a particular implementation of these classes that provide the concrete capability. For example, there is an abstract Modem class that applications can use, and for Windows NT an NT_Modem class that implements the interface. The abstract classes are described below.

The build environment and makefiles control the operating system target, compiling the concrete classes that are specific to a given operating system.

This approach assumes that the number of such targets, and thus class implementation, is small.

1. AsyncMsgHandler Pattern


This operating system pattern provides a kind of messaging interface. The application can post a command to another thread of execution and continue on its way. Meanwhile, a separate thread will receive the command via a callback and handle it. This operation is portably provided across operating systems. The pattern is built on other abstract classes that follow.

2. Sized, Base Types


These are set of sized types that provide hardware level characterization of memory in terms of sized types: signed 8 bit, unsigned 16 bit, etc.

3. Standard Template (STL) and Standard C Library


These are a standard ANSI set of container classes, algorithms, iterators, file access capabilities, math functions and other primitives.

4. Abstract Thread and Synchronization Classes


An OS independent thread class is provided. Synchronization of the threads and control over sharing of resources is provided through abstract Semapahore, Mutex, and Trigger classes (OSThread, OSSemaphore, OSMutex, OSTrigger).

5. Abstract Modem, Abstract Go Modem Protocol
These classes provide a standardized modem interface and Go Modem Protocol that runs over a modem. The Go Modem Protocol allows go programs and go players to compete over phone lines.
2. GUI Portability

• Assume simple dialog functions can be called to present and set related data. These interfaces look procedural, while a given dialog box is event driven.
• Some Display Classes will be re-written for a given GUI and controlled as part of the build environment.
• Consolidation of different kinds of IO into different IOSTREAMS. In a windowing implementation, these streams can be associated with a particular window.

Much work remains to be done here, or a 3^rd party solution adopted. The current implementation is not windows based.

1. Conclusions

It successfully encapsulates interfaces to all the current Go game playing interfaces, local or remote, human or program, GUI or not.