[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

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

At 11:58 PM 12/29/2000 -0800, you wrote:

> >   (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

Note that this implementation is linear in the number of liberties of the
block. The current implementation in SmartGo looks at the (at most) four
adjacent points and checks whether any of them contain the block in
question. No doubt the same could easily be done in Many Faces.
You are right. I wasn't thinking :) It should be

bool result = inlist(block, nbgrp[p][grcolor[block]]); // nbgrp is an array of lists of adjacent groups to a point, by color

The list of neighboring blocks by color usually has only 1 or two entries, so
this much faster. My original code seems a more natural expression of the notion
of if a point is a liberty of a group, so this is a good example of the expressiveness
of a library leading to faster or slower implementations. I'll check my tactics code, but
I'm sure I have several examples of the grlbp[block] code rather the faster nbgrp version.

(Turns out I coded it the slow way 3 times :) When I wrote the tactician, I didn't maintain
the lists of adjacent groups by color, because I thought it would be too slow. But it
turned out to be worth it. I didn't go back and rewrite all of the old working code :)

I should add a macro or inline function to express this concept more directly.


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

The iterators are mostly syntactic sugar that gets inlined without loss of
efficiency. The LibertyIterator essentially boils down to iteration through
an array; the NeighborBlockIterator has to call a function to compute the
neighboring blocks first, eliminating duplicates. One advantage of using
iterator classes is that I can change the implementation (e.g. from list to
array) without having to change any of the client code.
So there is no call to new() in each for loop to allocate memory for the iterator object?


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

Right, that's the way to do it.

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

Thanks for replying with actual code, David. One slight issue: the legality
tests in the routine are not primarily to test whether the generated move is
legal, but to make sure that the played move is not in atari after the move
and that the opponent can't approach without getting into atari. Can you
please let us know how that would look in Many Faces?
My tests for self-atari tend to be rather approximate and simpleminded, I'm
afraid :) You can't just eliminate self-atari moves of course, or you will miss
good throwins that lead to shortage of liberties or snapbacks.

My code for generating attacking moves is organized like (highly simplified). The full
code is about 600 lines:

to attack group g, where g is not in atari already:

for(list_t lbp = grlbp[g]; lbp != EOL; lpb = link[lbp])//walk g's liberty list
{
sqr_t s = link[lbp]; // a liberty

// lots of code for general value of playing here

if(lnbn[s] == 0){ // no empty points next to this liberty
// check if there are adjacent friendly stones with enough liberties to avoid self-atari or illegal self-capture
// if so, generate the move
// else generate approach moves
// check to see if there could be a good throwin here.
// if so, generate it
}
else if(lnbn[s] == 1){ // one empty point next to this liberty
// check to see if there are adjacent friendly stones with enough liberties to avoid self atari
// if so, generate the move
// else generate approach moves
// check to see if there is a good throwin here
// if so, generate the move
}
else
// generate the move

// lots of code for other cases
}

code to check if the adjacent stones have enough liberties looks like:

// s is a liberty of the group g being attacked

list_t sumptr = EOL;
int sumlibs = 0; // number of liberties of group containing the move played at s, assuming no enemy captures

for(list_t ptr = nbgrp[s][1-grcolor[g]]; ptr != EOL; ptr = link[ptr]){
sumlibs += mrglist(grlbp[list[ptr]], &sumptr);
}
killist(&sumptr);
sumlibs--;

If(sumlibs > 1){ // can play here without self-atari
}

// mrglist merges one linked list into another, returning the number of elements added.
// these linked lists are all kept sorted, with each element unique. Merging sorted lists
// is pretty fast.

// I'm just building the new liberty list for the group that will be formed, without making the move,
// since making the move updates many other lists.



> David Fotland

Anders Kierulf
www.smartgo.com

David Fotland