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

[David Fotland <fotland@xxxxxxxxxxxxxxx>]

At 03:48 PM 12/29/2000 -0800, you wrote:

> 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).
Many Faces does partial updates for making moves in the tactician, and full 
updates for life/death reading, and full board lookahead.  But liberty 
counts and liberty
lists are always updated, even for tactics.  I use an incremental liberty 
algorithm which is pretty fast.  I don't have a special case for 2 liberty 
tactics (ladders).
I found that there were too many cases where something went 2 liberties for 
a while, then back to 3, or with a 50-50 choice that is not forced, or some 
other
think that makes it not a simple ladder.

>   (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.
My board data structure contains group numbers, with a special value 
meaning an empty point.  The color is part of the group data structure, and 
I use
0 for Black and 1 for White.  Handtalk also has group numbers in the board 
data structure, but uses even numbers for white groups and odd group numbers
for black groups, so he can test a group's color very quickly.

>   (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 Many Faces, there is no special function for this.  It would be coded as:

point p;
group block;
bool result = inlist(p, grlbp[block]);  // grlbp is the array by 
group[block] of liberty list pointers.  inlist() tests if a value is in a list

Since almost everything is represented as lists, the set of list functions 
is used over and over again, so I don't have a bunch of
specific functions like IsLibertyOfBlock().

For speed, the core data structures are flat, one-dimensional arrays, 
rather than arrays of structs or classes.  So instead of

struct {
        int     libs;   // liberty count
        list_t  *lbp;   // liberty list pointer
        int     size;   // number of stones
        int     color;  // color of theis group
} gr[MAXGROUPS];        // the group structure

accessed using code like:  gr[block].lbp,

My code is:

int grlibs[MAXGROUPS];  // liberty count
list_t *grlbp[MAXGROUPS];       // liberty list pointer
int grsize[MAXGROUPS];  // size
int color[MAXGROUPS];   // color

accessed using code like: grlbp[block];

Since I have some discipline in my naming convention, the code reads almost 
like code using structures, but is much, much faster, since
accessing a value requires just one add rather than a multiply and an add.



> 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.
Yes!  Otherwise the code will be full of bugs, or you won't implement 
something accurately because it would require too much code.  If your
base is expressive of useful go concepts, you aren't tempted to code 
approximations rather than exact concepts.

>   (3) Efficient: There's never enough computing power. The base code is 
> not the place to squander it.
Yes!  There is always need to read more tactics :)




> 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?
Many Faces is C, not C++, and I wouldn't create new iterators in my inner 
loops, because it seems too slow.  All of the loops in the example would
just be walking linked lists, so they are very simple and fast.

I don't have any code like yours since my move generator assigns values to 
moves as it generates them, then sorts and selects at the end.  I iterate
once the liberties of the group and generate all of the moves relevant to 
that liberty, so your inner loops are intertwined with generating moves
of other types.  The code is less clear, but faster :)  I only test 
legality for moves as I try them.  That way I don't waste time testing for 
legality on
moves that are cutoff, or otherwise never tried.

If I did have such a routine, it would look like:


void ForceApproachMove(group_t block)
{
// Iterate through all the liberties of 'block.
        for (list_t lib = grlbp[block]; lib != EOL; lib = link[lib])    // 
walk block's liberty list
        {
                sqr_t liberty = list[lib];
                // Iterate through all the blocks of opposite color of 'block'
                // adjacent to 'liberty' with at most 3 liberties.
                for (list_t enemy = nbgrp[liberty][1-grcolor[g]]; enemy != 
EOL; enemy = link[enemy])    // walk liberty's adjacent group list of enemy 
color
                {
                        if(grlibs[list[enemy] > 
3)continue;                                     // make sure has 3 or less 
liberties
                        // Iterate through the liberties of those adjacent 
blocks.
                        for(list_t elib = grlbp[list[enemy]]; elib != EOL; 
elib = link[elib])   // walk the adjacent enemy's liberty list
                        {
                                sqr_t libOfAdjBlock = list[elib];
                                // Make sure 'libOfAdjBlock' is not a 
liberty of 'block'.
                                if (!inlist(libOfAdjBlock, grlbp[block]))
                                {
                                        // generate the move
                                        mvs[mvp] = libOfAdjBlock;
                                        mvval[mvp] = FORCEAPPROACH;
                                        mvcolor[mvp] = grcolor[block];
                                        mvp++:
} } } } }

I think this code is probably much faster :)  I prefer terse names, so it 
is not as readable as yours :(  I used the actual data structure
names from Many Faces here.

David Fotland




> Anders Kierulf
> www.smartgo.com
David Fotland