a*****g
发帖数: 19398 | 1 【 以下文字转载自 Programming 讨论区 】
发信人: ananpig (●○ 围棋数学一把抓的安安猪), 信区: Programming
标 题: 围棋18路棋盘的可能棋局数量算出来了
发信站: BBS 未名空间站 (Mon Mar 9 19:33:10 2015, 美东)
一大堆的 server 算了９个多月——
http://tromp.github.io/go/legal.html
Number of legal 18x18 Go positions
Following 9 months of computation and 4 petabyte of disk IO on a Dell
PowerEdge R820 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) =
6697231142888292128927401888417065435099377806401787328103183376969456244285
4721810521432601277437139718484889097011183628347046881282790714992650234763
3 which factorizes as 7176527950749135946361 *
9332132737237076489000151144700353729763797704278405915612698329348183333522
6774708913094831974704397065455646983337368444156410553
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 | a*****g
发帖数: 19398 | 2 正在仔细读这个paper
我在胡思乱想，也许可以和我前几天提出的“一串子最多的气”有关联
因为这个paper是基于合法局面，讨论的是一串子最少要有一气
by
【在 a*****g 的大作中提到】
: 【 以下文字转载自 Programming 讨论区 】
: 发信人: ananpig (●○ 围棋数学一把抓的安安猪), 信区: Programming
: 标 题: 围棋18路棋盘的可能棋局数量算出来了
: 发信站: BBS 未名空间站 (Mon Mar 9 19:33:10 2015, 美东)
: 一大堆的 server 算了９个多月——
: http://tromp.github.io/go/legal.html
: Number of legal 18x18 Go positions
: Following 9 months of computation and 4 petabyte of disk IO on a Dell
: PowerEdge R820 server, generously provided by Piet Hut, and administered by
: Lee Colbert, at the IAS School of Natural Sciences in Princeton, we
|
|
