[math-fun] Number of legal 18x18 Go positions
FYI -- https://tromp.github.io/go/legal.html Following 9 months of computation and 4 petabyte of disk IO on a Dell PowerEdge R280 server, generously provided by Piet Hut, and administered by Lee Colbert, at the IAS School of Natural Sciences in Princeton, we determined L(18,18) = 669723114288829212892740188841706543509937780640178732810318337696945624428547218105214326012774371397184848890970111836283470468812827907149926502347633 which factorizes as 7176527950749135946361 * 93321327372370764890001511447003537297637977042784059156126983293481833335226774708913094831974704397065455646983337368444156410553 The computation uses dynamic programming to count the number of paths through a graph consisting of 18^2=324 layers with up to 81 billion nodes each. Each node corresponds to a set of partial board (e.g. the top 7 rows plus 6 points on the 8th row) positions that are equivalent in their set of valid completions. Our paper explains the algorithm in detail, and also explains how the resulting exact counts allow derivation of the approximation formula L(m,n) ~ 0.850639925845714538 * 0.96553505933837387^{m+n} * 2.97573419204335724938^{m*n} which gives us the approximate number of legal positions on a standard board size L(19,19) ~ 2.08168199381982*10^170 https://tromp.github.io/go/gostate.ps
A quick analysis of the sequence shows that the second differences of the log(a(n)) is constant : 2.1809815915841... which I can't identify now, being away from my tables and programs. The sequence is : [1, 57, 12675, 24318165, 414295148741, 62567386502084877, 83677847847984287628595, 990966953618170260281935463385, 103919148791293834318983090438798793469, 96498428501909654589630887978835098088148177857, 793474866816582266820936671790189132321673383112185151899, 57774258489513238998237970307483999327287210756991189655942651331169, 372497923\ 07686396442294904767024517674249157948208717533254799550970595875237705, 212667\ 7329003662242497893576504405980988058610832691271966238722132281963524554475750\ 29701325, 107514643083613831187684137548661238097337888203278444027646016628708\ 83601711298309339239868998337801509491, 481306696382275541642905602248429964648\ 6874100967249263944719599975607459850502222039591149331431805524655467453067042\ 377, 19079388919628199204605726181850465220151058338147922243967269231944059187\ 214767997105992341735209230667288462179090073659712583262087437, 66972311428882\ 9212892740188841706543509937780640178732810318337696945624428547218105214326012\ 774371397184848890970111836283470468812827907149926502347633] A094777 (not updated yet). Best regards, Simon Plouffe
RIES didn't find anything convincing in the appropriate region, for either that constant or its exponential (or, for that matter, the constant I get by Aitken extrapolation). Charles Greathouse Analyst/Programmer Case Western Reserve University On Mon, Mar 9, 2015 at 8:48 AM, Simon Plouffe <simon.plouffe@gmail.com> wrote:
A quick analysis of the sequence shows that the second differences of the log(a(n)) is constant : 2.1809815915841... which I can't identify now, being away from my tables and programs.
The sequence is : [1, 57, 12675, 24318165, 414295148741, 62567386502084877, 83677847847984287628595, 990966953618170260281935463385, 103919148791293834318983090438798793469, 96498428501909654589630887978835098088148177857, 793474866816582266820936671790189132321673383112185151899, 57774258489513238998237970307483999327287210756991189655942651331169, 372497923\ 07686396442294904767024517674249157948208717533254799550970595875237705, 212667\
7329003662242497893576504405980988058610832691271966238722132281963524554475750\ 29701325, 107514643083613831187684137548661238097337888203278444027646016628708\ 83601711298309339239868998337801509491, 481306696382275541642905602248429964648\
6874100967249263944719599975607459850502222039591149331431805524655467453067042\ 377, 19079388919628199204605726181850465220151058338147922243967269231944059187\ 214767997105992341735209230667288462179090073659712583262087437, 66972311428882\
9212892740188841706543509937780640178732810318337696945624428547218105214326012\ 774371397184848890970111836283470468812827907149926502347633]
A094777 (not updated yet).
Best regards, Simon Plouffe _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
participants (3)
-
Charles Greathouse -
Henry Baker -
Simon Plouffe