a*****g
发帖数: 19398 | 1 【 以下文字转载自 Programming 讨论区 】
发信人: ananpig (●○ 围棋数学一把抓的安安猪), 信区: Programming
标 题: 19路围棋的所有合法图案终于出来了 Number of legal Go positi
发信站: BBS 未名空间站 (Fri Jan 22 10:38:03 2016, 美东)
Number of legal Go positions
The 361 points on a 19x19 Go board can be colored empty, black, or white.
Only some of the 3^361 possible positions are legal, namely those where
every group of connected stones of the same color has an empty point
adjacent to it. In the position above, black stones at E18 and N9 lack such
``liberties'', making the position illegal. Due to its capture rule, the
positions that can arise in a game of Go are exactly the legal positions. On
Jan 20, 2016, the number of legal positions on a standard size Go board was
determined to be
L19 =
2081681993819799846994786333448627702865224538845305484256394568209274196127
3801537852564845169851964390725991601562812854608988831442712971531931755773
6620397247064840935
or in more compact form
2081681993819799846
9947863334486277028
6522453884530548425
6394568209274196127
3801537852564845169
8519643907259916015
6281285460898883144
2712971531931755773
6620397247064840935
weighing in at 9*19=171 digits. We can write this more naturally in base 3
as the 19*19 ternary digits
0 0 0 0 2 2 2 0 1 1 0 0 2 0 1 1 1 0 1
2 1 1 2 1 2 0 0 2 1 2 1 0 0 0 2 2 0 2
2 1 0 0 2 1 0 1 1 1 1 1 0 1 1 1 1 1 2
0 0 2 2 0 1 1 0 2 0 0 1 2 1 0 2 0 1 0
1 0 2 0 2 0 1 2 0 1 1 2 2 1 0 0 1 2 1
1 0 0 0 1 1 1 2 0 2 2 0 0 0 2 0 1 2 2
0 0 2 1 2 0 0 2 0 0 1 1 1 0 2 0 2 0 0
0 0 2 2 0 2 2 2 0 0 0 2 1 0 1 0 0 0 2
2 1 0 0 2 0 2 2 2 2 1 0 0 2 1 1 1 2 1
2 0 0 1 0 2 2 1 2 1 1 2 2 0 2 0 1 2 0
2 1 1 1 0 0 2 1 0 0 2 2 1 2 2 2 0 1 1
2 2 1 2 0 1 1 1 0 2 0 1 2 0 2 2 2 0 2
2 0 1 0 1 2 1 1 0 1 1 0 2 1 2 0 0 2 1
2 0 0 0 1 2 2 1 1 2 0 2 2 0 0 1 0 1 0
1 1 2 2 0 0 1 2 2 0 2 0 2 0 1 2 2 1 0
2 0 1 0 0 1 1 0 2 1 2 1 2 1 1 0 2 2 0
2 2 1 1 2 0 1 0 2 0 1 2 0 2 1 2 1 0 0
0 0 0 1 1 2 2 1 0 2 1 0 1 0 2 1 1 2 0
2 2 0 2 1 0 2 2 0 0 2 1 1 1 1 1 2 2 2
which bears a striking resemblance to the image above.
It should come as no surprise that L19, viewed as a position, is itself
illegal. The initial ternary digits show that the probability of a random
position being legal is about 0.0000222 in ternary, close to 3^-4, or 1 in
81. This 1.2% chance was already computed by random sampling back in 1992.
The approximation
L19 ~ 2.081681994 * 10^170
has been known since 2006. So what took us 10 years to nail it down to the
last digit?
A Computational Challenge
Consider the problem of factoring. How do we find the prime factors of L19?
Repeated trial division, the dumbest possible approach, takes time
exponential in the number of digits, so it's utterly infeasible. Instead one
should use an advanced algorithm, like the General Number Field Sieve, or
the Elliptic Curve Method (ECM). These still take exponential time, but not
in the number of digits itself, but rather (roughly) in the cube root or
square root thereof, thereby vastly extending the range of inputs on which
they're feasible in practice.
Using an ECM implementation courtesy of Dario Alejandro Alpern, I was able
to factorize L19 in mere hours on my laptop, yielding 8 prime factors:
5 *
401 *
4821637 *
964261621 *
2824211368611548437 *
2198466965002376001759613307922757 *
65948646836807567941440434317404197 *
54536540603346595211722061421378072820459376985314707345317470047
of 1,3,7,9,19,34,35, and 65 digits respectively. The challenge of
constructing (rather than deconstructing) L19 is surprisingly similar.
Individually testing 3^361 positions for legality is as insane as doing
trial divisions. Detecting illegalities early during position generation, as
this small program for legal probability approximation does, offers only
the slightest improvement. Just as with factoring, we need an advanced
algorithm that is exponential not in the number of points, but rather in the
square root thereof, the board dimension.
Such an algorithm was developed in the early 2000s, and is described in
detail in our paper Combinatorics of Go. It essentially reduces computing
L19 to taking the 361st power of a very sparse matrix of 363 billion rows
and columns. The computational power required for this only became available
to me last year.
363 billion what?
The matrix rows and columns represent so called border states, which
describe all pertinent information about a cross section of the board, such
as the presence of stones still needing liberties and how they are connected
. Matrix powers represent counts of the number of paths from one border
state to another. Each legal position uniquely corresponds to a path from
the edge border state to one without libertyless stones, as illustrated for
this 3x3 position:
Chinese jobs
Clever use of the Chinese Remainder Theorem allows for splitting the
computation into 9 independent parts, each computing L19 modulo 2^64 minus
some small number, contributing 64 bits of the 566 bit result. Starting from
March 6 2015, running on big servers at
the IAS School of Natural Sciences in Princeton, where the L18 computation
was recently performed, generously provided by Piet Hut and administered by
Lee Colbert,
the IDA Center for Communications Research, on the other side of Princeton,
generously offered by Michael Di Domenico, who spent many hours setting up,
monitoring, streamlining, and patching the jobs, as well as helping improve
the jobflow scripts,
and the HP Helion Cloud, generously provided by HP courtesy of Eric Moore,
suffering many hiccups and a few catastrophes, after generating an estimated
30 petabyes of disk IO, the last of these jobs finished on December 26,
2015. It then took a few weeks to get the needed log files into my hands. A
huge thanks to all these people who made the computation possible!
Verifiability
The software used for these computations is available at my github
repository. Running "make" should compute L(3,3) in about a second. For
running an L19 job, a beefy server with 15TB of fast scratch diskspace, 8 to
16 cores, and 192GB of RAM, is recommended. Expect a few months of running
time. Please use a modulus index outside the set {0,1,2,3,4,5,6,11,19} that
we used. The computation has many built-in checks to guard against memory
and disk corruption. Values L(m,n) where n
) (computed in a very different way), while all values L(m,n) have to
closely match the approximation formula
L(m,n) ~ 0.8506399258457 * 0.965535059338374^{m+n} * 2.9757341920433572493^{
m*n}
derived from earlier results. Finally, application of the Chinese Remainder
Theorem provide an important safeguard in that a tiny change in any of the
inputs results in a huge change of output.
A big number game
Large numbers have a way of popping up in the game of Go. Few people believe
that a tiny 2x2 Go board allows for more than a few hundred games. Yet 2x2
games number not in the hundreds, nor in the thousands, nor even in the
millions. They number in the hundreds of billions! 386356909593 to be
precise. Things only get crazier as you go up in boardsize. A lower bound of
10^{10^48} on the number of 19x19 games, as proved in our paper, was
recently improved to a googolplex.
Server benchmark, anyone?
Go counting could make a decent server benchmark:
The task is well defined, easily understood, and non-artificial.
The program code is small and self-contained.
The generated data sets are huge.
The problem is a typical instance of map-reduce, and thus representative of
a wide class of popular problems.
The computation requires a good balance of multi-core processing power,
memory for sorting, and disk-IO.
The board size parameter gives an entire family of benchmarks, where each
increment corresponds to a factor of about 5 in effort.
Legal counts for all boardsizes
This is sequence A094777 in the fabulous On-Line Encyclopedia of Integer
Sequences.
Click on the left links to find tables for m by n boards.
n number of legal n*n positions
1 1
2 57
3 12675
4 24318165
5 414295148741
6 62567386502084877
7 83677847847984287628595
8 990966953618170260281935463385
9 103919148791293834318983090438798793469
10 96498428501909654589630887978835098088148177857
11 793474866816582266820936671790189132321673383112185151899
12 57774258489513238998237970307483999327287210756991189655942651331169
13
3724979230768639644229490476702451767424915794820871753325479955097059587523
7705
14
2126677329003662242497893576504405980988058610832691271966238722132281963524
55447575029701325
15
1075146430836138311876841375486612380973378882032784440276460166287088360171
1298309339239868998337801509491
16
4813066963822755416429056022484299646486874100967249263944719599975607459850
502222039591149331431805524655467453067042377
17
1907938891962819920460572618185046522015105833814792224396726923194405918721
4767997105992341735209230667288462179090073659712583262087437
18
6697231142888292128927401888417065435099377806401787328103183376969456244285
4721810521432601277437139718484889097011183628347046881282790714992650234763
3
19
2081681993819799846994786333448627702865224538845305484256394568209274196127
3801537852564845169851964390725991601562812854608988831442712971531931755773
6620397247064840935
The results for n=14,15,16 and 17 were obtained in a joint effort between
Michal Koucky and John Tromp.
Many thanks to Gunnar Farneb?ck and Michal Koucky for their contributions.
Gunnar wrote a legal counting program in pike, while Michal suggested the
use of Chinese Remaindering and implemented a file based program. |
|
