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

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

"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


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