Re: [computer-go] Exact number of goban configurations.

[Antti Huima <antti.huima@xxxxxxxxxxxxx>]

Eric Boesch wrote:

> Instead of divide-and-conquer, I think you should work out from the 
> corner, adding stones one at a time, column by column, keeping an 
> array mapping all possible border states to the number of different 
> overall region states that share that same border state.  The border 
> is the set of intersections that are inside the region that are 
> adjacent to intersections outside the region.  The border state is not 
> only the color of the border intersections, but also whether those 
> stones already have liberties, or whether they need to connect to 
> outside liberties, and also whether those stones are connected to each 
> other.  For example:
>
> -----
> | #
> | # O
> | # #
> | # O
> | O .
> -----
>
> If this is our region, then the border consists of the four rightmost 
> intersections (the rightmost ones in each row).  The border colors are 
> #,O,#,O, and "." (empty), but the border state is more than just the 
> colors of the border stones.  It's also important to know that the 
> topmost O stone needs to connect (directly or indirectly) to an 
> outside liberty.  The two # stones on the border also need to connect 
> to a liberty, but since they are already connected to each other, a 
> single liberty at either end suffices.
>
> So the number of possible border configurations is strictly greater 
> than 3^(# of border intersections).  I have no idea what the exact 
> number would be, but as long as the effective exponent base isn't too 
> big, the space demands for 9x9 should be manageable.  For example, 4^9 
> is just a quarter million.
This seems like a clever and working idea.

The number of board configurations should be, I guess, for 9 x 9 board, 
5^9 = 1953125. For 19 x 19 board the same number would be around 2^44, 
not manageable any more. But for 9 x 9 this should work.

The number five is obtained as: empty intersection, black stone with an 
unseen liberty behind (live stone), black stone without liberties 
behind, whit estone with a liberty behind, white stone without a liberty 
behind.

Will you implement it?

--
Antti Huima (Mr.)
Director, Conformiq Tools
mobile: +358 40 528 8667
email: antti.huima@xxxxxxxxxxxxxxxxx

Conformiq Software Ltd.
Stella Terra, Lars Sonckin kaari 16
FIN-02600 Espoo, Finland
tel: +358 10 286 6300
fax: +358 10 286 6309 
http://www.conformiq.com/

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