[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[research report] Equation Derived -- Re: On Game Space Size (Monte Carlo)
Ladies & Gentlemen,
Instead of waiting for Professor Pieter's result, I wrote a java program
which does the calculation. The data reveal some astoninshing results.
After the program finished calculation for a 10 x 10 board (now it's
working for 16 x 16), I hacked the data (see below) and derived the
following relationship.
Given p -- % of illegal position
n -- square board dimension size (i.e., a n x n board)
s -- percentage of board coverage ( # of B/W stones / n^2)
We have:
log(p/(1 - p)) ~= 4.8 * s + 0.009 * n^2 - 3.8 or
p = 10^(4.8s + 0.009n^2 - 3.8)/[1 + 10^(4.8s + 0.009n^2 - 3.8)]
Or approximately
log(p/(1 - p)) ~= 5s + 0.01n^2 - 4,
p = 10^(5s + 0.01n^2 - 4)
(Copy Right, Mousheng Xu, 1999 :) )
Statistics shows that for the above regression,
R squre = 94.1%
the residual plot show no obvious patterns, which implies the unexplained
5.9% can be explained by random errors.
Chemists should know the formula is similar to "Hill plot" equation.
Back to Dave Dyer's question: what the hell does it matter? :)
It at least can give us a relatively accurate estimation about the real
complexity of a board instead of saying "I guess" or "approximately" ...
Before we do any calculation, check below for the result for 9 x 9. When
the board is half full, about 1/4 configurations are illegal, when the
board is about 90% full, almost every configurtion is illegal. Which means,
the complexity would be less than that of a 72 stone board, a save of 3(81
- 72) = 20000 times of calculation.
Thanks.
-- Mousheng Xu
------------------------------------------------------------------------------
For every entry below, 100 random samples are drawn.
n #stone %illegal
2 1 0.0
2 2 0.0
2 3 0.17
2 4 1.0
3 1 0.0
3 2 0.0
3 3 0.0
3 4 0.04
3 5 0.02
3 6 0.16
3 7 0.26
3 8 0.74
3 9 1.0
4 1 0.0
4 2 0.0
4 3 0.0
4 4 0.0
4 5 0.0
4 6 0.03
4 7 0.01
4 8 0.06
4 9 0.1
4 10 0.15
4 11 0.21
4 12 0.3
4 13 0.5
4 14 0.65
4 15 0.9
4 16 1.0
5 1 0.0
5 2 0.0
5 3 0.0
5 4 0.0
5 5 0.0
5 6 0.02
5 7 0.0
5 8 0.0
5 9 0.04
5 10 0.06
5 11 0.02
5 12 0.04
5 13 0.06
5 14 0.14
5 15 0.19
5 16 0.3
5 17 0.27
5 18 0.32
5 19 0.44
5 20 0.55
5 21 0.59
5 22 0.77
5 23 0.89
5 24 0.99
5 25 1.0
6 1 0.0
6 2 0.0
6 3 0.0
6 4 0.0
6 5 0.02
6 6 0.0
6 7 0.0
6 8 0.0
6 9 0.0
6 10 0.0
6 11 0.0
6 12 0.02
6 13 0.04
6 14 0.04
6 15 0.02
6 16 0.09
6 17 0.1
6 18 0.12
6 19 0.11
6 20 0.14
6 21 0.3
6 22 0.3
6 23 0.25
6 24 0.31
6 25 0.38
6 26 0.45
6 27 0.46
6 28 0.48
6 29 0.64
6 30 0.76
6 31 0.82
6 32 0.89
6 33 0.96
6 34 0.98
6 35 1.0
6 36 1.0
7 1 0.0
7 2 0.0
7 3 0.0
7 4 0.0
7 5 0.0
7 6 0.0
7 7 0.01
7 8 0.0
7 9 0.0
7 10 0.0
7 11 0.0
7 12 0.01
7 13 0.01
7 14 0.02
7 15 0.0
7 16 0.05
7 17 0.02
7 18 0.03
7 19 0.02
7 20 0.11
7 21 0.11
7 22 0.04
7 23 0.1
7 24 0.19
7 25 0.14
7 26 0.21
7 27 0.22
7 28 0.23
7 29 0.27
7 30 0.26
7 31 0.29
7 32 0.3
7 33 0.4
7 34 0.51
7 35 0.59
7 36 0.62
7 37 0.64
7 38 0.61
7 39 0.72
7 40 0.71
7 41 0.78
7 42 0.85
7 43 0.95
7 44 0.97
7 45 0.97
7 46 0.98
7 47 0.99
7 48 1.0
7 49 1.0
8 1 0.0
8 2 0.0
8 3 0.0
8 4 0.0
8 5 0.0
8 6 0.0
8 7 0.0
8 8 0.0
8 9 0.0
8 10 0.0
8 11 0.0
8 12 0.0
8 13 0.02
8 14 0.03
8 15 0.0
8 16 0.0
8 17 0.0
8 18 0.02
8 19 0.01
8 20 0.01
8 21 0.01
8 22 0.03
8 23 0.03
8 24 0.06
8 25 0.08
8 26 0.1
8 27 0.06
8 28 0.13
8 29 0.15
8 30 0.09
8 31 0.1
8 32 0.15
8 33 0.22
8 34 0.24
8 35 0.27
8 36 0.3
8 37 0.3
8 38 0.31
8 39 0.34
8 40 0.45
8 41 0.46
8 42 0.48
8 43 0.46
8 44 0.54
8 45 0.58
8 46 0.57
8 47 0.68
8 48 0.75
8 49 0.76
8 50 0.72
8 51 0.83
8 52 0.8
8 53 0.84
8 54 0.87
8 55 0.94
8 56 0.95
8 57 0.98
8 58 0.97
8 59 0.98
8 60 1.0
8 61 1.0
8 62 1.0
8 63 1.0
8 64 1.0
9 1 0.0
9 2 0.0
9 3 0.0
9 4 0.0
9 5 0.0
9 6 0.0
9 7 0.0
9 8 0.0
9 9 0.0
9 10 0.0
9 11 0.0
9 12 0.0
9 13 0.0
9 14 0.01
9 15 0.0
9 16 0.02
9 17 0.01
9 18 0.01
9 19 0.0
9 20 0.02
9 21 0.01
9 22 0.0
9 23 0.02
9 24 0.02
9 25 0.03
9 26 0.08
9 27 0.02
9 28 0.05
9 29 0.03
9 30 0.02
9 31 0.07
9 32 0.03
9 33 0.1
9 34 0.05
9 35 0.11
9 36 0.1
9 37 0.14
9 38 0.21
9 39 0.16
9 40 0.26
9 41 0.21
9 42 0.25
9 43 0.18
9 44 0.16
9 45 0.34
9 46 0.35
9 47 0.36
9 48 0.41
9 49 0.47
9 50 0.44
9 51 0.47
9 52 0.5
9 53 0.64
9 54 0.65
9 55 0.52
9 56 0.63
9 57 0.76
9 58 0.76
9 59 0.72
9 60 0.77
9 61 0.81
9 62 0.84
9 63 0.86
9 64 0.86
9 65 0.95
9 66 0.91
9 67 0.92
9 68 0.93
9 69 0.95
9 70 0.98
9 71 0.96
9 72 1.0
9 73 1.0
9 74 0.99
9 75 0.98
9 76 1.0
9 77 1.0
9 78 1.0
9 79 1.0
9 80 1.0
9 81 1.0
10 1 0.0
10 2 0.0
10 3 0.0
10 4 0.0
10 5 0.0
10 6 0.0
10 7 0.0
10 8 0.0
10 9 0.0
10 10 0.0
10 11 0.0
10 12 0.0
10 13 0.0
10 14 0.01
10 15 0.01
10 16 0.0
10 17 0.0
10 18 0.0
10 19 0.0
10 20 0.02
10 21 0.0
10 22 0.0
10 23 0.01
10 24 0.02
10 25 0.03
10 26 0.02
10 27 0.01
10 28 0.03
10 29 0.03
10 30 0.05
10 31 0.06
10 32 0.04
10 33 0.02
10 34 0.06
10 35 0.05
10 36 0.07
10 37 0.08
10 38 0.05
10 39 0.1
10 40 0.07
10 41 0.12
10 42 0.1
10 43 0.17
10 44 0.14
10 45 0.13
10 46 0.17
10 47 0.11
10 48 0.18
10 49 0.25
10 50 0.24
10 51 0.24
10 52 0.31
10 53 0.23
10 54 0.31
10 55 0.36
10 56 0.33
10 57 0.39
10 58 0.36
10 59 0.44
10 60 0.43
10 61 0.45
10 62 0.5
10 63 0.6
10 64 0.58
10 65 0.56
10 66 0.59
10 67 0.66
10 68 0.67
10 69 0.76
10 70 0.72
10 71 0.73
10 72 0.82
10 73 0.77
10 74 0.83
10 75 0.89
10 76 0.9
10 77 0.89
10 78 0.94
10 79 0.92
10 80 0.92
10 81 0.95
10 82 0.98
10 83 0.94
10 84 0.94
10 85 0.95
10 86 0.96
10 87 0.99
10 88 1.0
10 89 1.0
10 90 1.0
10 91 1.0
10 92 1.0
10 93 1.0
10 94 1.0
10 95 1.0
10 96 1.0
10 97 1.0
10 98 1.0
10 99 1.0
10 100 1.0