-
Notifications
You must be signed in to change notification settings - Fork 0
/
phase1prunesm.w
executable file
·378 lines (342 loc) · 11.6 KB
/
phase1prunesm.w
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
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
\def\mod{\mathop{mod}}
@s cubepos int
@s moveseq int
@s kocsymm int
@s permcube int
@s lookup_type int
@* Introduction.
Phase one of Kociemba's two-phase algorithm involves finding a
sequence of moves that takes an arbitrary position into the $H$ group,
generated by $\{U,F2,R2,D,B2,L2\}$.
The Schreier coset graph, as implemented in the |kocsymm| class, has
size $3^7\cdot 2^{11}\cdot{12\choose 4}$ which is 2,217,093,120
entries. This coset has 16-way symmetry, so we reduce the size of the
pruning table to about 170,000,000 entries; the remapping of |kocsymm|
is reasonably fast requiring only small tables. (This is a bit more
than what you would expect, because we only do an approximate
reduction by symmetry for speed, and thus have a few more table
entries.)
Our basic API is straightforward. We have an initialization routine,
and a lookup method that takes the position to look up, the current
number of moves remaining for the current search, and by reference a
variable to return a bitmask of which moves to consider for the next
level of search. Everything in this class is static; there are no
instance methods or fields.
@(phase1prunesm.h@>=
#ifndef PHASE1PRUNE_H
#define PHASE1PRUNE_H
#include "kocsymm.h"
const int BEDGEPERM = 512 ;
class phase1prunesm {
public: @/
static void init(int maxdep=255, int suppress_writing=0) ;
static int lookup(const kocsymm &kc, int &mask) ;
@<Method declarations@> @;
@<Data declarations@> @;
} ;
#endif
@ Our initialization routine is the first component of our C++ file.
It is protected against multiple invocation by a method-local static.
@(phase1prunesm.cpp@>=
#include "phase1prunesm.h"
#include <cstdio>
using namespace std ;
@<Data instantiations@> @;
@<Utility functions@> @;
@<Method bodies@> @;
void phase1prunesm::init(int maxdep, int suppress_writing) {
static int initialized = 0 ;
if (initialized)
return ;
initialized = 1 ;
@<Initialize the instance@> @;
dep3 = maxdep + 1 ;
}
@ We need a memory array to store the result, a static variable to
hold the size of the array, and another static variable to hold
the checksum of the array. We also need a filename for the file.
@<Data decl...@>=
static unsigned int memsize ;
static unsigned int *mem ;
static int file_checksum ;
static const char *const filename ;
static int dep3 ;
@ All these must be instantiated. For the filename, we use the
name given below to indicate phase 1 pruning data, halfturn metric.
@<Data inst...@>=
unsigned int phase1prunesm::memsize ;
unsigned int *phase1prunesm::mem ;
int phase1prunesm::file_checksum ;
int phase1prunesm::dep3 ;
#ifdef HALF
const char *const phase1prunesm::filename = "p1p3h.dat" ;
#endif
#ifdef QUARTER
const char *const phase1prunesm::filename = "p1p3q.dat" ;
#endif
#ifdef SLICE
const char *const phase1prunesm::filename = "p1p3s.dat" ;
#endif
@ We need a routine to do a checksum of the file, to verify integrity.
We use a simplistic hash function. Note that this function expects an
array pointing to |unsigned int|, not |unsigned char| like our |mem|
array; we use a bit of coercion to make this work. These data files
are not interchangeable across different endian architectures; the
checksums will be different. We make it file static in case we
use a different one somewhere else.
@<Utility...@>=
static int datahash(unsigned int *dat, int sz, int seed) {
while (sz > 0) {
sz -= 4 ;
seed = 37 * seed + *dat++ ;
}
return seed ;
}
@ Our initialization routine calculates the memory size and allocates
the array. We use a single contiguous array; even on 32-bit
architectures it should be straightforward to get about 700MB of
contiguous memory---at least early in the program's lifetime.
@<Initial...@>=
memsize = CORNERRSYMM * EDGEOSYMM * BEDGEPERM / 4 ;
mem = (unsigned int *)malloc(memsize) ;
if (mem == 0)
error("! no memory") ;
@ We need methods to generate the table, read it, write it, and check
it for integrity.
@<Method decl...@>=
static int quick_pop(kocsymm kc, int togo, int v, int canon, int mm) ;
static void gen_table(int maxdep) ;
static int read_table() ;
static void write_table() ;
static void check_integrity() ;
@ Our generate table routine is next. We iterate over the distances,
finding each position at the current depth, and extending it by one move.
@<Method bodies...@>=
int phase1prunesm::quick_pop(kocsymm kc, int togo, int v, int canon, int mm) {
if (togo == 0) {
corner_mapinfo &cm = kocsymm::cornersymm[kc.csymm] ;
int m = cm.minmap ;
int at = (cm.csymm * BEDGEPERM +
kocsymm::edgepmap[kc.epsymm][m]) * EDGEOSYMM +
kocsymm::edgeomap[kocsymm::edgepxor[kc.epsymm][m>>3]^kc.eosymm][m] ;
int bits = 2 * (at & 15) ;
at >>= 4 ;
int r = (mem[at] >> bits) & 3 ;
if (r == 3) {
int rv = 1 ;
mem[at] -= (3 - v) << bits ;
if (cm.minbits & (cm.minbits - 1)) {
for (int m=cm.minmap + 1; (1<<m) <= cm.minbits; m++)
if ((cm.minbits >> m) & 1) {
at = (cm.csymm * BEDGEPERM +
kocsymm::edgepmap[kc.epsymm][m]) * EDGEOSYMM +
kocsymm::edgeomap[kocsymm::edgepxor[kc.epsymm][m>>3]^kc.eosymm][m] ;
bits = 2 * (at & 15) ;
at >>= 4 ;
r = (mem[at]>>bits) & 3 ;
if (r == 3) {
mem[at] -= (3 - v) << bits ;
rv++ ;
}
}
}
return rv ;
}
return 0 ;
}
int mvmask = cubepos::cs_mask(canon) & mm ;
kocsymm kc2 ;
togo-- ;
int r = 0 ;
for (int mv=0; mv<NMOVES; mv++) {
if (((mvmask >> mv) & 1) == 0)
continue ;
kc2 = kc ;
kc2.move(mv) ;
r += quick_pop(kc2, togo, v, cubepos::next_cs(canon, mv), -1) ;
}
return r ;
}
void phase1prunesm::gen_table(int maxdep) {
memset(mem, -1, memsize) ;
mem[0] = 0xfffffffc ;
int seen = 1 ;
printf("Gen phase1 so far %g\n", duration()) ;
fflush(stdout) ;
for (int d=1; d <= maxdep; d++) {
int backwards = (d >= 10) ;
int seek = (d - 1) % 3 ;
int target = d % 3 ;
if (d <= 8) {
kocsymm kc ;
seen += quick_pop(kc, d, target, CANONSEQSTART, 0x8) ;
} else {
for (int cs=0; cs<CORNERRSYMM; cs++) {
int csymm = kocsymm::cornersymm_expand[cs] ;
for (int mv=0; mv<NMOVES; mv++) {
int cs2 = kocsymm::cornermove[csymm][mv] ;
corner_mapinfo &cm = kocsymm::cornersymm[cs2] ;
for (int m=cm.minmap; cm.minbits>>m; m++)
if ((cm.minbits >> m) & 1) {
@<Handle edge bits@> ;
}
}
}
}
printf(" %d %d %g\n", d, seen, duration()) ;
fflush(stdout) ;
if (seen == CORNERRSYMM * EDGEOSYMM * EDGEPERM)
break ;
}
dep3 = maxdep + 1 ;
printf(" done.\n") ;
fflush(stdout) ;
}
@ For each position, we consider all possible moves.
@<Handle edge bits@>=
int dat1 = cm.csymm * EDGEOSYMM * BEDGEPERM ;
for (int epsymm=0; epsymm<EDGEPERM; epsymm++) {
int ep2 = kocsymm::edgepmove[epsymm][mv] ;
int ep3 = kocsymm::edgepmap[ep2][m] ;
int ex = kocsymm::edgepxor[ep2][m>>3] ;
int at = cs * BEDGEPERM * EDGEOSYMM + epsymm * EDGEOSYMM ;
unsigned int *p = mem + (at >> 4) ;
if (backwards) {
for (int o=0; o<EDGEOSYMM; o += 16, p++) {
if ((*p & (*p >> 1)) & 0x55555555) {
for (int ieo=0; ieo<16; ieo++) {
if (((*p >> (2*ieo)) & 3) == 3) {
int eosymm = o + ieo ;
int eo2 = kocsymm::edgeomove[eosymm][mv] ;
int eo3 = kocsymm::edgeomap[ex^eo2][m] ;
int dat3 = dat1 + eo3 + ep3 * EDGEOSYMM ;
if (((mem[dat3>>4] >> (2*(dat3&15))) & 3) == seek) {
*p -= (3 - target) << (2 * ieo) ;
seen++ ;
}
}
}
}
}
} else {
for (int o=0; o<EDGEOSYMM; o += 16, p++) {
if (*p != 0xffffffff) {
for (int ieo=0; ieo<16; ieo++) {
if (((*p >> (2*ieo)) & 3) == seek) {
int eosymm = o + ieo ;
int eo2 = kocsymm::edgeomove[eosymm][mv] ;
int eo3 = kocsymm::edgeomap[ex^eo2][m] ;
int dat3 = dat1 + eo3 + ep3 * EDGEOSYMM ;
if (((mem[dat3>>4] >> (2*(dat3&15))) & 3) == 3) {
mem[dat3>>4] -= (3 - target) << (2 * (dat3 & 15)) ;
seen++ ;
}
}
}
}
}
}
}
@ We now finish our initialization with the routines that read
and/or generate the file.
@<Initial...@>=
gen_table(maxdep) ;
@ Lookup routines, and a solve routine.
@<Method decl...@>=
static int lookup(const kocsymm &kc) ;
static moveseq solve(kocsymm kc) ;
static int solve(kocsymm kc, moveseq &ms, int togo, int d, int canon) ;
@ Looking up the distance is quick, based on the code we've already
seen.
@<Method bodies...@>=
int phase1prunesm::lookup(const kocsymm &kc) {
corner_mapinfo &cm = kocsymm::cornersymm[kc.csymm] ;
int m = cm.minmap ;
int at = (cm.csymm * BEDGEPERM +
kocsymm::edgepmap[kc.epsymm][m]) * EDGEOSYMM +
kocsymm::edgeomap[kocsymm::edgepxor[kc.epsymm][m>>3]^kc.eosymm][m] ;
return (mem[at>>4] >> (2*(at & 15))) & 3 ;
}
@ We also provide a quick and dirty solve routine.
@(phase1prunesm.cpp@>=
int phase1prunesm::solve(kocsymm kc, moveseq &r, int togo, int d, int canon) {
kocsymm kc2 ;
if (d == 3) {
if (togo == 0)
return 0 ;
int msk = cubepos::cs_mask(canon) ;
for (int mv=0; mv<NMOVES; mv++) {
if (((msk >> mv) & 1) == 0)
continue ;
kc2 = kc ;
kc2.move(mv) ;
r.push_back(mv) ;
if (solve(kc2, r, togo-1, phase1prunesm::lookup(kc2),
cubepos::next_cs(canon, mv)))
return 1 ;
r.pop_back() ;
}
return 0 ;
} else {
while (kc.eosymm != 0 || kc.epsymm != 0 || kc.csymm != 0) {
int goal = (d + 2) % 3 ;
int msk = cubepos::cs_mask(canon) ;
for (int mv=0; mv<NMOVES; mv++) {
if (((msk >> mv) & 1) == 0)
continue ;
kc2 = kc ;
kc2.move(mv) ;
if (phase1prunesm::lookup(kc2) == goal) {
r.push_back(mv) ;
kc = kc2 ;
canon = cubepos::next_cs(canon, mv) ;
d = goal ;
break ;
}
}
}
return 1 ;
}
}
moveseq phase1prunesm::solve(kocsymm kc) {
moveseq r ;
int d = phase1prunesm::lookup(kc) ;
for (int togo=1; ; togo++)
if (solve(kc, r, togo, d, CANONSEQSTART))
return r ;
}
@ Our test routines.
@(phase1prunesm_test.cpp@>=
#include "phase1prunesm.h"
#include <iostream>
using namespace std ;
int main(int argc, char *argv[]) {
int maxdep = 15 ;
if (argc > 1)
maxdep = atol(argv[1]) ;
phase1prunesm::init(maxdep) ;
int t[10000] ;
for (int i=0; i<10000; i++)
t[i] = random_move() ;
kocsymm kc ;
@<Check basic lookup performance@> @;
@<Check solution performance@> @;
}
@ Check how fast we can look up.
@<Check basic lookup performance@>=
int sum = 0 ;
duration() ;
for (int i=0; i<1; i++)
for (int j=0; j<10000; j++) {
kc.move(t[j]) ;
sum += phase1prunesm::lookup(kc) ;
}
cout << "Did 100M basic lookups in " << duration() << " sum " << sum << endl ;
@ Check how fast we can solve.
@<Check solution performance@>=
for (int i=0; i<100; i++)
for (int j=0; j<10000; j++) {
kc.move(t[j]) ;
phase1prunesm::solve(kc) ;
}
cout << "Did 1M solves in " << duration() << " sum " << sum << endl ;