RE: computer-go: Languages for programming go are?

["Anders Kierulf" <anders@xxxxxxxxxxx>]

> 2) If one were to imagine a new language, invented solely for
> the purpose of writing a great computer go system, what would
> its characteristics likely be?  (Or would there be multiple
> new languages, for different parts of the problem?)
> ...
> Bob Myers
> Intelligent Go Foundation

In a sense, everybody developing a Go program is designing their own language for computer Go. The base code of a Go program provides types and functions that implement board management (such as blocks, liberties, playing and taking back a move), bitboards, pattern matching, hash tables, and more, and higher-level code (such as groups and tactical search) is based on those functions. Whether that base code is provided as a toolkit or as a language is not a crucial issue, as long as the desired higher-level Go concepts can be expressed in terms of the base code.

The problem with designing a computer language specifically for computer Go is that few Go programmer would agree on what the base code for a strong Go program should be. We don't yet know how to write a strong Go program, and the choices made at a low level are partly dependent on choices made at higher levels in the code. It might be possible to reach some agreement on basic board management, but even there I see a lot of room for different choices. Some examples:
  (a) In SmartGo, the stones and liberties of a block are always updated when playing and taking back a move. For most tactics, that's the right choice. However, that's not the most efficient way to implement an efficient ladder algorithm, and thus SmartGo has special code to handle that case (without slowing down the normal case).
  (b) Many programs use zero to represent an empty point, 1 for a black stone, and 2 or -1 for a white stone. SmartGo uses 1 for black, 2 for white, and 4 for empty. This makes it efficient to test e.g. the neighbors of a point for black OR empty, and to use other bits for other flags that can be tested in a single operation with the color. Another choice would be a bitboard representation of the board, making some higher-level operations more and others less efficient.
  (c) What would you provide as primitives of the language? E.g. the GoBoard class in SmartGo provides a function IsLibertyOfBlock(Point p, Point block) that returns whether the empty point 'p' is a liberty of 'block'. This could easily be coded in terms of more basic functions, but inside the GoBoard class this can be implemented more efficiently.

In my opinion, base code for a Go program has to be:
  (1) Extensible: It must be possible for each Go programmer to add additional functions, and to attach additional data to base types.
  (2) Expressive: It must be possible to express high-level concepts in a way that's easy to read and understand.
  (3) Efficient: There's never enough computing power. The base code is not the place to squander it.
  In addition, if the base code were directly embodied as a language, that language would need to have the power of a general-purpose programming language, as there are always plenty of non-Go issues to program (e.g. modem protocol and user interface).

SmartGo is written in C++, and while C++ is far from ideal, it lets us efficiently express the concepts we want to express. Our web site explains how C++ is used in SmartGo, see http://www.smartgo.com/t_use_of_cpp.htm. That web page also shows the method ForceApproachMove exactly as written in SmartGo. It would be very interesting to see how other Go programs express that algorithm, not in pseudo-code, but in real code that will actually work as written, and is efficient enough to generate moves during a tactical search that examines thousands of positions per second. Concrete examples like this is where the rubber hits the road. How would this look in Lisp? In GNU Go? In Many Faces of Go?

Anders Kierulf
www.smartgo.com