GoLib

Computer Go Source Code

Download revertable code and all test files (see instructions below for building under WinNT).
You will also need  the boehm garbage collector.

Send questions or comments to klinger@cs.nyu.edu.

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 that turn.

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 me email.

Development notes

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 environment:

 The Garbage Collector

  1. Download and unpack the gc source in a directory.
  2. 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.
  3. Open the file "gc.mak" in the IDE.
  4. Define OPERATOR_NEW_ARRAY in the precompiler options.
  5. Save the workspace and make the projects.
The Revertable Test Project
  1. Make a another directory, download the revertable files, and create a 32 bit console project including the two .cpp source files.
  2. 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.)
  3. Add the gc library gc.lib to the libraries to link into the revertable project. Make sure the linker can find gc.lib.
  4. 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).
  5. Build the revertable project.
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.