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

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

From: "Jeffrey Rainy" <jrainy@xxxxxxxxxxxxxxxxx>

Reply-To: computer-go <computer-go@xxxxxxxxxxxxxxxxx>
To: "computer-go" <computer-go@xxxxxxxxxxxxxxxxx>
Subject: [computer-go] Exact number of goban configurations.
Date: Thu, 20 Jan 2005 17:44:29 -0500

Hi,

Is there any published articles or websites stating the exact number of
legal goban configurations that are possible for a given goban size ?

The best I found, from Sensei's Library is :

1x1: 1 legal, 2 illegal, prob 0.333333
2x2: 57 legal, 24 illegal, prob 0.703704
3x3: 12675 legal, 7008 illegal, prob 0.643957
4x4: 24318165 legal, 18728556 illegal, prob 0.564925
4x5: 1840058693 legal, 1646725708 illegal, prob 0.527724

I realise this is of no interest except from a purely
theoretical/combinatorial viewpoint. However, I think I could come up with
the exact values up to at least 9x9. Was this done before ?
I have no idea, but just because asking around in forums like Sensei's, this one, and Usenet fails to locate an existing answer to a go problem, does not mean that one isn't known! (A handfull of us found that out the hard way where terminal sekis with many mutual liberties were concerned...)

Would anyone find it useful or at least somehow interesting ?
Yes, I think the answer would be interesting, and the method used to arrive at numbers for such large boards would be even more interesting. At first I thought you were crazy to think the computation was practical for 9x9, but after considerable thought, I'm not so sure. I think I've finally worked out an angle. In any case, it sounds like not only did you find an angle first, but you also had the insight to realize an answer might be possible in the first place, which I did not. Considering where you say Sensei's left off (5x4), I bet they used brute force, which isn't very interesting.

Here are my thoughts on the problem. I have not actually worked out the solution -- I figure you have dibs on this problem anyway :) Possible spoiler?

Bisection and divide-and-conquer, while (I think) straightforward enough for 1-dimensional boards, seemed very difficult to do for 2-dimensional ones. Hmm...

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.

In sum, when you're adding a new intersection to the region, you iterate through all of the old border states, and through all of the possible colors for that new intersection (black, white, empty). For each old border state, you compute the new border state that results from adding the given stone to the old border, and you add the number of positions having the old border state to the number of positions having the new border state. Once you have added all 81 stones, the single (null) border state number will equal the total number of valid positions -- make sure to use either floating point or bignums.

_________________________________________________________________
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/