Computer Go Source Code
revertable code and all test files (see instructions
below for building under WinNT).
You will also need the boehm
Send questions or comments to firstname.lastname@example.org.
Revertable object system
A major design issue in go programming is how to deal with maintaining
the state during search. From-scratch recomputation has the advantage that
it adds no complexity to the program, and requires no thought to design
or implement. It has the disadvantage that it subsequently puts constant
(and to my mind insidious) pressure on you not to try any computationally
expensive algorithms as part of your state update because you have to throw
away and redo all that work every time you read or backtrack a move.
Incremental update implemented by copying the changed structure adds
substantial complexity to the program, and requires a great deal of effort
to design and implement. It has the advantage that, if done well, it is
nearly transparent and puts no pressure on the go programer to steer clear
of complex or expensive algorithms, allowing her to concentrate on generating
whatever information she thinks best for playing a move.
The following code from our go program provides a C++ implementation
of a revertable class mechanism. Each revertable object knows how to store
a copy of itself, and does so just before it's changed (but at most once
each turn). To backtrack a move we just copy back the saved versions for
More detailed information
is available about how the revertable system works and how to use it.
Sample Revertable Code
What you really need to make this system most useful is a revertable container
class library - revertable versions of standard data structures like lists,
maps, etc. Here is a toy revertable list example:
And here's a simple example of a revertable board structure:
Note: Unfortunately STL wasn't around when we started, and the library
we modified to be revertable isn't free, so we can't post it. If somone
wants to work on modifying (part of) STL to be garbage collected and revertable,
I think it would be a huge benefit to starting go programmers (and probably
not very difficult to do). If anyone's interested in working on this send
The code was developed under NT using MSVC++ 5.0, but should be easily
portable to any modern OS/C++ compiler environment.
This version of the revertable system uses the boehm
garbage collector. GC makes the revertable system particularly easy
to use, elegant, and maybe even more efficient. And of course GC is in
general a great thing and an excellent idea in a complex prototyping project
like developing a go program.
Here's how I got it to work under my development
The Garbage Collector
The Revertable Test Project
Download and unpack the gc source in a directory.
Open the file cord/de_win.RC in a text editor and change the last line
from "DE ICON cord/de_win.ICO" to "DE ICON de_win.ICO". Or make a subdirectory
in cord called cord and copy the .ICO file in there.
Open the file "gc.mak" in the IDE.
Define OPERATOR_NEW_ARRAY in the precompiler options.
Save the workspace and make the projects.
If this isn't the best way of doing it, if there's a better way of configuring
the GC system for NT (I get some thread related error when GC programs
exit that I haven't bothered to track down), or if you have specific info
on getting the system to work on other platforms, please let me know and
I'll make the information available here.
Make a another directory, download the revertable files, and create a 32
bit console project including the two .cpp source files.
Make sure the preprocessor can find the gc header files gc.h and gc_cpp.h
to include in the revertable project (copy them or add the gc directory
to the include path of the revertable projects.)
Add the gc library gc.lib to the libraries to link into the revertable
project. Make sure the linker can find gc.lib.
Make sure that gc file gc.dll is someplace in your DLL path (I just copied
it into the target directory of the revertable project).
Build the revertable project.