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

["Eric Boesch" <ericboesch@xxxxxxxxxxx>]

> From: "Anders Kierulf" <anders@xxxxxxxxxxxxxxxxx>
>
>   (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).
[I will use the GnuGo terminology, where a worm is a maximal connected set 
of vertices of the same color (there are 3 colors:  white, black, and 
"empty", that is, unoccupied).]

Maintaining neighbor counts (one of which is the number of clear stones 
neighboring a white or black worm, that is, the worm's liberty count) is one 
of the few things my current program does well.

Switching the color of a single vertex while maintaining these neighbor 
counts need not take time comparable to the size of the board except in rare 
cases.  The case where the vertex belonged to a very large worm (such as an 
EMPTY worm that covers 90% of the board) does not qualify as "rare".

The trickiest problem to solve quickly is determining whether the removal of 
a vertex splits a single worm into several.  I use a wall-hugging algorithm 
(forgive my ignorance if this is not an original idea).

4 . . . .
3 . . X .
2 . a . X
1 . . O .
 A B C D

O (white) is about to play at vertex B2.  A fast, constant-space way to 
determine how many EMPTY worms will be created by this move, is to 
simultaneously send four wall-hugging turtles out in all directions from B2. 
 By "wall-hugging", I mean that every time a turtle goes forward, it turns 
90 degrees counterclockwise, and every time an edge or a vertex of the wrong 
color prevents the turtle from proceeding in the direction it is facing, it 
turns 90 degrees clockwise.  The algorithm completes as soon as 3 of the 
turtles have returned to B2; if a turtle exits in one direction, but returns 
from another, then we know that those two exits are part of a single worm.

In this example, the north turtle would follow this path:  B3 A3 A2 B2; the 
east turtle follows the path C2 B2; the west turtle follows the path A2 A1 
B1 B2; and the south turtle, if it were allowed to run that long (again, all 
4 turtles move in tandem, and the algorithm stops as soon as 3 turtles 
return), would follow the path B1 A1 A2 A3 A4 B4 C4 D4 D3 D4 C4 B4 B3 B2.

The north turtle, by returning from the west, and the west turtle, by 
returning from the south, tell us that A2, B1, and B3 are part of a single 
worm, while the east turtle tells us that C2 is part of a different worm.

The south turtle's tardiness suggests that its worm (call it W1) is probably 
the largest of the new worms created by the deletion of B2.  This is 
important, because explicitly counting the number of vertices and liberties 
in the largest worm would be too slow.

By observing that the original large empty worm had 12 vertices, 2 black 
neighbors, and 1 white neighbor, and by observing that the new empty worm at 
C2 includes 1 vertex, and all of its neighbors are also neighbors of W1, we 
can determine the number of stones in W1 (12-1-1 = 10) and its neighbors (2 
black, plus 1 white, plus 1 new white).

Code is available upon request.


_________________________________________________________________
Get your FREE download of MSN Explorer at http://explorer.msn.com