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

[Gunnar Farnebäck <gunnar@xxxxxxxxxxxxxx>]

I wrote:
> 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.

Ok, it is the same basic idea, but with the aim to derive matrix
recursions for the number of configurations corresponding to each
border state, which complicates the presentation and to some extent
the algorithm.

My implementation of the algorithm Eric outlined is now available at
http://www.lysator.liu.se/~gunnar/legal.pike.txt
(Save it as legal.pike. The extra .txt is only a workaround.)

I think the code should be clear enough to follow.

The result for 10x10 is, by the way,
96498428501909654589630887978835098088148177857.

Extrapolation of the computing times suggests that 11x11 can be done
in about 24 hours, 12x12 in a week and 13x13 in less than two months,
in case someone should happen to find enough computer time.

It should be possible to reduce these numbers by some smallish factor
with a more efficient implementation. For people with clusters on
their hands parallelization of the loop over the previous border
states should work well. The algorithm can also likely gain some speed
at the cost of higher code complexity by traversing the board
diagonally, i.e.

.
6.
358
1247

and so on instead of columnwise. This reduces the length of the border
most of the time and thus the number of border states. Unfortunately
the same maximum border length is reached when passing the main
diagonal(s) so it probably doesn't have a really drastic effect but
still it might reduce the time for 13x13 by a factor 3 or 4.

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