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

[Tapani Raiko <praiko@xxxxxxxxx>]

> > 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.
I implemented a crude version of this, where I add a column at a time. The 
memory requirement is still around 3^n but the time recuirement is around 
3^(2n). I got exactly the known results up to 4 by 5. I can send the 
Matlab code if you are interested.

For 5 by 5 boards, 414294790771 out of 847288609443 are legal (48.8965%).
(6 by 6 is still running)

> 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.
For 5x5 board, the number of different columns was 827. 
(for comparison 3^5 = 243, 5^5 = 3125)

Regards,
--
 Tapani Raiko, <tapani.raiko@xxxxxxxxxxxxxxxxx>, +358 9 451 4468, +358 50 522 5750
 http://www.cis.hut.fi/praiko/
_______________________________________________
computer-go mailing list
computer-go@xxxxxxxxxxxxxxxxx
http://www.computer-go.org/mailman/listinfo/computer-go/