-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathNOTES.txt
129 lines (94 loc) · 4.98 KB
/
NOTES.txt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
Board representation
--------------------
abcdefgh
4 .OX.. 4
3 ...oxY.. 3
2 ..Oox... 2
1 ..OX. 1
abcdefgh
o = white mover
O = white pusher
x = black mover
X = black pusher without anchor
Y = black pusher with anchor
Some example positions:
Started: .OX.....oxX....Oox.....OX.
In-progress: ..OoO..X......oxY..XO..x..
Finished: ..OoO..X.......oxX..Y..x..
401567166000 permutations
401567166000 = 2^4 × 3^3 × 5^3 × 7 × 11 × 13 × 17 × 19 × 23
401567166000 = 7429 × 54054000
401,567,166,000 = 7429 × 54,054,000
The number of permutations could be reduced using two observations:
1. Some positions are unreachable. In a reachable position, the anchor is on a
piece that has a free space in one direction (e.g., left, top, right, bottom)
and an occupied space in the opposite direction (right, bottom, left, top,
respectively). Taking this into account reduces the total number of
permutations to 172416263040.
172,416,263,040 = 2^7 × 3^4 × 5 × 7 × 17 × 19 × 1471
2. The board has rotational symmetry. The presence of the unique anchor piece
quarantees that each permutation is different from its rotation. We can
use this to cut the number of permutations in half again by normalizing the
permutation. For two rotations, we can take either the lexicographically
smallest one, or the one where the anchor is on the top half (or the bottom,
left, or right half.) This would reduce the total number of permutations
to 86208131520.
86,208,131,520 = 2^6 × 3^4 × 5 × 7 × 17 × 19 × 1471
Note the current solvers don't use the above optimizations. For simplicity, they
operate on the full 401,567,166,000 permutations including rotations and
unreachable positions.
At 54054000 permutations per chunk, and 10,000 permutations/second, each chunk takes 1.5 hours to process.
For r0, it looks chunks can be computed in ~1 minute or 7429/60/24 = ~5 days wall clock time.
Total size at 1 bit per permutation: ~50.2 GB (6.8 MB/chunk)
Total size at 1.6 bit per permutation: ~80.3 GB (10.8 MB/chunk)
Total size at 4 bits per permutation: ~321.3 GB (27.0 MB/chunk)
Total size at 1 byte per permutation: ~401.5 GB
File formats:
chunk-r0-0000: 1 bit per position (0=TIE/LOSS, 1=WIN)
chunk-rN-0000: 1.6 bits per position (0=TIE, 1=LOSS, 2=WIN)
A state is:
- WIN, if the state is WIN in r(N - 1), or there is at least one successor in
r(N - 1) that is LOSS for the opponent
- LOSS, if the state is LOSS in r(N - 1), or all successors in r(N - 1) are
WON for the opponent (including the case where there are no successors,
though it's not clear if that happens)
Note that between chunk-r(N - 1) and chunk-rN the only values that can change
are TIEs, because WIN and LOSS will be copied unmodified. After several phases
fewer and fewer TIEs will remain, until chunks no longer change, at which point
the assessment is final.
Test vectors:
$ sha256sum results/chunk-r0-010?.bin
0deb3a32f8190784a47912ddabd6b8d36b9a734f3d345c30b9fdda21955e3507 results/chunk-r0-0100.bin
ebd0e118cef4887bd46d1430436437d53e8eb434583d2847e59c41de7764c36e results/chunk-r0-0101.bin
e0e2c0cbbdafc17a663fe3decbae699c89cfcee99343abecba272ddff84c6b01 results/chunk-r0-0102.bin
25aed7790a7426c018f70496d1c8e7c35b88f9060e12a6a05d32ddd25a436dde results/chunk-r0-0103.bin
d75b7a9efe5412b2ed7dfaaf154fc94f1d9a652c801840b9c4996ac9c5066558 results/chunk-r0-0104.bin
a3851ff3df8d45f97cc36c9a5a815cc853a89a6a7ca48113f5da6ad0b238ca47 results/chunk-r0-0105.bin
77a233275f6f5f05774b6b656f8fe7e16b965f4cb3e034d479d5b007f44cbb26 results/chunk-r0-0106.bin
a3f3c0396fac84127925e78cc27a215a9a00189da3801a8b74bdd5df82a13ea5 results/chunk-r0-0107.bin
107f972750452f85a1a358ac50ae7fddc3e77f75a2fbb46f1990d7255cb781a9 results/chunk-r0-0108.bin
73fb27946f306151e47c4e0c7f83021fa1b2ae3afa92398eb8235d3b18a3bd62 results/chunk-r0-0109.bin
$ ./count-bits results/chunk-r0-010?.bin
Zero bits: 175671731
One bits: 364868269
Total bits: 540540000
Fraction of ones: 0.675007
Compressed file formats
-----------------------
lookup-min and pushfight-standalone-server can use minimized.bin.xz directly,
without having to unzip it! This is quite a bit slower than accessing the
bytes in the uncompressed file, but it's good enough for local use.
minimized.bin.xz is generated as follows:
xz --block-size=65536 --check=crc32 -0 --extreme --keep input/minimized.bin
Options used:
--block-size=65536 splits input into 64 KiB blocks (this is what enables
efficient random access)
-0 selects a smaller dictionary size (256 KiB) which reduces decoder memory
use. A small dictionary should be sufficient since our blocks are only
64 KiB in size.
-e selects extreme compression, to maximize compression rate (otherwise, -0
would be very fast but not compress very well)
--check=crc32 changes the CRC64 to CRC32 which saves 4 bytes per block
and should be sufficient to detect errors considering each block is
very small.
--keep prevents the input file from being deleted