On Nov 13, 2007, at 8:35 AM, Jason House wrote:
On Nov 13, 2007 11:23 AM, Heikki Levanto <[EMAIL PROTECTED]> wrote:
There are pathological cases where this has to loop many times,
flood filling
the one liberty to a long chain of stones, but those should be rare.
This was my big turn-off. I would expect the average case in mid-
game to require several shakes (maybe 4?). Even with 64 bit
numbers, 9x9 bit boards don't fit... requiring lots of operations
per shake. With aspirations of 19x19, I figured the overhead would
be too much.
I never did any formal proof or disproof of that.
(shake == expand in my code. I've also seen this called "dilation".
Repeated dilation in a set defines Tromp-Taylor reachability.)
When I get back to my program, my next experiment would be to use
bitmaps that know their y-extent. Most operations would then not be
full-board any more.
Another idea is to cache the string bitmaps, but then the complexity
goes high enough to make a mailbox implementation attractive again.
Ian
_______________________________________________
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
