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

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

Gunnar Farnebäck <gunnar@xxxxxxxxxxxxxxxxx> wrote:

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

There is an r.g.g. article from 2000 that tries to describe a method
that is supposed to work for the kind of board sizes we handle now.
The idea seems to be somewhat related to the one suggested by Eric
Boesch in this thread (which in turn may or may not be similar to what
you have in mind) but at least the description is vastly more complex.
See

http://groups-beta.google.com/group/rec.games.go/msg/7dea58f58cfe601a

Unfortunately I find the article close to unreadable.
I didn't get much out of scanning it either, but I agree that it seems to say everything I did and more. I can't say I'm terribly surprised, though I might have expected John Tromp to point this out himself.

I wasn't in a hurry to write a program because I thought Jeffrey deserved time to finish his first -- not that I'm criticizing anybody, given the contents of my previous message. I don't think there's any doubt that, left alone, he soon would have found the 9x9 figures (actually, since I might expect a row-by-row approach to be a little slower than stone-by-stone, I wouldn't be surprised if he's doing the computation right now).

I did write a program, though (after you did), and I got the same numbers you did. My running times were also pretty comparable. Then I tried to fix the sharp upturn in running times above 7x7. I figured this was the problem:

XOXOXOXOX

There must be many thousands of ways a set of nine edge stones like the above can have liberties or not or be interconnected, and they were all being searched and inserted linearly in an array. So I switched from arrays to HashMaps. After the switch, 9x19 (3.07...71 * 10^80) took only 15 minutes, but since 10x10 ran out of heap space, the time savings were pretty moot. It might not take much to fit 10x10 in, but finding space for 13x13 just by shaving bytes is out of the question. That's not much of a surprise either -- I figured you'd need several gigabytes minimum (I have 384MB), but now I think it would be hard to get by even with that much memory.

From: Gunnar Farnebäck <gunnar@xxxxxxxxxxxxxxxxx>
Reply-To: computer-go <computer-go@xxxxxxxxxxxxxxxxx>
To: computer-go <computer-go@xxxxxxxxxxxxxxxxx>
Subject: Re: [computer-go] Exact number of goban configurations. Date: Wed, 26 Jan 2005 03:22:02 +0100

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

There is an r.g.g. article from 2000 that tries to describe a method
that is supposed to work for the kind of board sizes we handle now.
The idea seems to be somewhat related to the one suggested by Eric
Boesch in this thread (which in turn may or may not be similar to what
you have in mind) but at least the description is vastly more complex.
See

http://groups-beta.google.com/group/rec.games.go/msg/7dea58f58cfe601a

Unfortunately I find the article close to unreadable.

If you can read German there's also some discussions on recursive
formulas for 1xN and 2xN boards and how those may be extended to
larger boards at

http://groups-beta.google.com/group/de.rec.spiele.brett+karten/browse_thread/thread/1214afa5c374c593/17a3d39b58f72e96?q=24318165&_done=%2Fgroups%3Fq%3D+24318165%26&_doneTitle=Back+to+Search&&d#17a3d39b58f72e96

My German is rather weak but the ideas seem very similar to what I
just derived myself before reading it.

Btw, the tesuji to finding these was to let google search for
"24318165" on the web and in the newsgroups. But neither of
414295148741, 62567386502084877, and 139304759213 show up in google
yet (but obviously will soon) so it doesn't seem likely that the
results for anything larger than 4x5 have actually been computed and
published on the web previously. Alternatively these numbers are
wrong. :-)

/Gunnar
_______________________________________________
computer-go mailing list
computer-go@xxxxxxxxxxxxxxxxx
http://www.computer-go.org/mailman/listinfo/computer-go/
_________________________________________________________________
Express yourself instantly with MSN Messenger! Download today - it's FREE! http://messenger.msn.click-url.com/go/onm00200471ave/direct/01/

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