Re: [computer-go] Groups, liberties, and such

["Eric Boesch" <ericboesch@xxxxxxxxxxx>]

"Harri Salakoski" <harri.salakoski@xxxxxxxxxxxxxxxxx> wrote:
> O(?) is little unknown, but that kind of AI
> I think goal is to get as much info from one board situation than you can 
> and not focusing "how much boards you can evaluate per second".
> In GoGame where alfatree grows like factor of 100? or something I dont see 
> small peformance improvements in board evaluation important. Like average 
> human sees about 90% of one board situation in average when making move :)?
The "merge smaller group into larger one and incrementally update liberties" 
algorithm that Remi mentioned is O(log2 s) amortized cost over the course of 
a game, where s is the size of the largest group in the game, so s is 
bounded by both the size of the board and the duration of the game.  The 
O(log2 s) average is not guaranteed for pathological tree searches instead 
of linear games, but I doubt that would ever make a real difference.  Better 
performance is much more likely than worse performance, I think.

In contrast, incremental merges performed with a disregard to which group is 
larger has big-O performance no better than recomputing from scratch -- 
recomputing may be faster than that, because it's simpler.  Put it this way: 
 merging in random order (or recomputing from scratch) is O(log s) if the 
merged groups have similar size or up to O(s) if they are very different, 
while merging the smaller into the larger is O(log s) or as little as O(1) 
in those two respective cases.  So as Remi pointed out, you need to get the 
order right.

The algorithm is simpler than the math.  Just move stones one at a time from 
the smaller group to the larger one, and as you add each stone, update the 
larger group's liberty count appropriately.  You have to check each of the 
stone's liberties to see if they are already liberties of the larger group, 
so it's not something you can do in a few CPU cycles -- but it's not that 
bad.  (At least that's what I do; I'm guessing that's what Remi and many 
others do also.)

I also agree that the disjoint-set data structure is probably not worth it 
if you compute liberties this way.  Reassigning all stones to the new group 
at the same time you assign their liberties to it is natural and only 
marginally increases the time cost.

The "merge bitmaps of liberties" approach that Heiki mentioned is an 
O(boardsize/wordsize) algorithm.  I wouldn't equate that with O(1), but it's 
still fast.  If you're going to store liberty bitmasks to begin with, it is 
a natural way to go.  One might implement it something like this, to 
minimize time spent doing bitcounts (untested Java pseudocode).

class Worm {
   void absorb(Worm other) {
       // stone-merge code goes here...
       ...
       // Liberty-counting code goes here.
       for (int i = 0; i < other.libertyMasks.length; i++) {
           long newLibertiesMask = other.libertyMasks[i] & 
~libertyMasks[i];
           if (newLibertiesMask != 0) {
               libertyMasks[i] |= newLibertiesMask;
               libertyCount += Long.bitCount(newLibertiesMask);
           }
       }
   }
}

For choices when rolling your own bitCount, see

http://groups.google.com/group/sci.crypt/msg/23104e0c36f96e7d

Tangent:  what clever tricks can you do with liberty lists or liberty 
bitmaps?  Okay, first off, if two worms' liberty bitmasks intersect once, 
they're at least half-connected, and if they intersect twice, they're 
connected.  Second, you can use liberty lists to compute second- and 
higher-order liberties.  What else?

The cost of doing liberty updates would be swamped by the cost of other 
evaluations in many situations, but maybe not all.  For quick local 
searches, liberty counts might be as compute-intensive as the node 
evaluation gets.  You could skip the liberty count too, but liberty counts 
are good for presorting move candidates to improve performance of 
alpha-beta, for short-circuiting branches that are guaranteed to exceed 
preset limits (e.g. you can't kill a 4-liberty group in less than 7 plies), 
etc.

_________________________________________________________________
On the road to retirement? Check out MSN Life Events for advice on how to 
get there! http://lifeevents.msn.com/category.aspx?cid=Retirement

_______________________________________________
computer-go mailing list
computer-go@xxxxxxxxxxxxxxxxx
http://www.computer-go.org/mailman/listinfo/computer-go/