# 4x4x4 Programming Discussion



## unsolved (May 18, 2014)

I thought it might be a good idea to stratify the discussions about 4x4x4 programming from the discussions about the associated 4x4x4 brute force solvers. Some readers who messaged me on here mentioned they were "getting lost" in some of the technical talk. Also, if you follow the strictest interpretations of the guidelines, I found myself talking about my program in Bruce's area, and sometimes Bruce would include a reference to his program in my area, so rather than "blur the lines" I offer this mutual programming discussion area.

To start things off, let me say that I have decided to re-code my move generator completely from scratch. Sometimes when you get started on a project, by the time you make some serious progress, one of the things you come to realize is how NOT to tackle the problem. It became apparent from Bruce's Rotational Scramble example that my move generator would flounder in the attempt to come up with the optimal solution because one sequence of moves functionally turned the cube by 90 degrees. In trying to find an optimal solution for the original, un-rotated version of the cube, my program was missing some obviously shorter solutions in the rotated state. There was a "quick fix" to address this particular issue, but I preferred a holistic solution to address the more general case.

I'd like to begin here with a discussion about the true "legal position" counts as a function of depth. From one of the early posts in another area:



Jakube said:


> if there are 2 moves on the same axis, both turn in the same direction (U is the same direction as d') and one of the moves is of <D>, then ignore the case.
> if there are 3 moves on the same axis, and >=2 moves turn in the same direction, then ignore the case.
> ignore all cases with 4 moves on the same axis.
> 
> ...



The issue with using such rules (above) to create a move generator is that the move sequence *U D' u d'*would be disallowed, as would *U2 D2 u2 d2*, both of which create rotated versions of the cube. I created a move generator that *allows* those moves, since I generated every possible 36 * 33^(n-1) cube arrangement, loaded the unique positions into a RAM buffer, and scanned the buffer prior to allowing a new entry, verifying (the hard way) that no duplicates were created (including recreating the starting position). These are the numbers I get:


nExplicit Unique Counts136​21,026​328,812​4806,694​522,575,425​6631,793,942​717,681,379,137​

My move generator and turns-from-solution (TFS) databases absolutely require uniqueness in order to function properly, so it is imperative that I get these numbers right! We have already seen those "odd solutions" that older version of my program found, since essentially the index "matching" the position was, in fact, pointing to a database slot for a position that was out of synch due to duplicates occupying indices that should have been discarded.

In this new version, it should be noted that *U u *and *D' d'* create different positions, and are therefore both allowed.
If possible, I would like confirmation of these numbers before I launch the rest of my re-coding effort.


----------



## cuBerBruce (May 18, 2014)

unsolved said:


> I thought it might be a good idea to stratify the discussions about 4x4x4 programming from the discussions about the associated 4x4x4 brute force solvers. Some readers who messaged me on here mentioned they were "getting lost" in some of the technical talk. Also, if you follow the strictest interpretations of the guidelines, I found myself talking about my program in Bruce's area, and sometimes Bruce would include a reference to his program in my area, so rather than "blur the lines" I offer this mutual programming discussion area.



I agree that your other thread was kind of hijacked with more general discussions on implementing 4x4x4 solvers. I think this is good to separate such discussion from the thread that was intended to be about your own solver. I generally was avoiding talking about my own solver in that thread, but would post information about possible pruning tables not necessarily specific to my own solver. I may have mentioned it some for purposes of comparing or contrasting it with your a solver.



unsolved said:


> The issue with using such rules (above) to create a move generator is that the move sequence *U D' u d'*would be disallowed, as would *U2 D2 u2 d2*, both of which create rotated versions of the cube. I created a move generator that *allows* those moves, since I generated every possible 36 * 33^(n-1) cube arrangement, loaded the unique positions into a RAM buffer, and scanned the buffer prior to allowing a new entry, verifying (the hard way) that no duplicates were created (including recreating the starting position). These are the numbers I get:
> 
> 
> nExplicit Unique Counts136​21,026​328,812​4806,694​522,575,425​6631,793,942​717,681,379,137​



I posted the number of position at distances up to 7 moves from solved (single slice turn metric) in your other thread (currently the post numbered 148). These numbers are lower than yours, but I note my numbers are for the distances from the solved state for the regular 4x4x4. I have not computed the equivalent supercube numbers (well, I have, but only for block turn metric). The distribution of distances for a scrambled state will generally not be the same. I would assume you would be using a supercube model if you are interested in knowing how many unique sequences you need in order to generate all positions of a given number of moves away from an arbitrary scrambled state.



unsolved said:


> My move generator and turns-from-solution (TFS) databases absolutely require uniqueness in order to function properly, so it is imperative that I get these numbers right! We have already seen those "odd solutions" that older version of my program found, since essentially the index "matching" the position was, in fact, pointing to a database slot for a position that was out of synch due to duplicates occupying indices that should have been discarded.
> 
> In this new version, it should be noted that *U u *and *D' d'* create different positions, and are therefore both allowed.
> If possible, I would like confirmation of these numbers before I launch the rest of my re-coding effort.



Well, U u would be equivalent to D d (not D' d') ignoring the resulting cube orientation difference, using the old Singmaster notation standards. If you're somehow considering these different, but considering some positions differing only by orientation of the cube as the same, then I think you need to clarify what you count as to whether two positions are the same or not. I think the simplest way to compare two states is to orient the cubes so that the DLB corner cubie is properly oriented in the DLB position. (Any corner cubie could be used, but fixing DLB is consistent with speedcubers tending to prefer turning U, R, and F,) You could go further and simulate L turns (as well as D and B turns) as turning the other three layers on that same axis, so that the DLB cubie is never allowed to be out of place. This has some consequences as far as "remapping" which axis is which.

As I hope you're well aware by now, the set of sequences that yield positions n moves away from a scrambled state *depend upon the scrambled state itself*. This is due to different arrangements of indistinguishable pieces in different scrambled states.


----------



## unsolved (May 18, 2014)

cuBerBruce said:


> I posted the number of position at distances up to 7 moves from solved (single slice turn metric) in your other thread (currently the post numbered 148). These numbers are lower than yours, but I note my numbers are for the distances from the solved state for the regular 4x4x4. I have not computed the equivalent supercube numbers (well, I have, but only for block turn metric). The distribution of distances for a scrambled state will generally not be the same. I would assume you would be using a supercube model if you are interested in knowing how many unique sequences you need in order to generate all positions of a given number of moves away from an arbitrary scrambled state.



You are referring to this post I suppose...



cuBerBruce said:


> ```
> moves  positions  cumulative   positions  cumulative pos.
> positions     mod M         mod M
> 
> ...



I am calling the move generator, generating a unique index for the 4x4x4 cube, and comparing that index to every index computed thus far. If the index already exists, the position is a duplicate. If the index is not in the list, the position is unique. I created 3 verbose text files as this was in process: File 1 = all of the move sequences that created the starting position. File 2 = all of the duplicates, which also cite the prior index number that generated the collision. File 3 = the moves leading to the unique index. In this way, I can test any move sequence and see if it passed or failed or just didn't move at all. I will post some data at the end.




cuBerBruce said:


> Well, U u would be equivalent to D d (not D' d') ignoring the resulting cube orientation difference, using the old Singmaster notation standards. If you're somehow considering these different, but considering some positions differing only by orientation of the cube as the same, then I think you need to clarify what you count as to whether two positions are the same or not. I think the simplest way to compare two states is to orient the cubes so that the DLB corner cubie is properly oriented in the DLB position. (Any corner cubie could be used, but fixing DLB is consistent with speedcubers tending to prefer turning U, R, and F,) You could go further and simulate L turns (as well as D and B turns) as turning the other three layers on that same axis, so that the DLB cubie is never allowed to be out of place. This has some consequences as far as "remapping" which axis is which.



From my data:


```
U  u   @ depth 2 generates a unique cube for index 52
D  d   @ depth 2 generates a unique cube for index 153
```

*U u* pushes 2 rings of cubes front to left to back to right to front. *D d* pulls 2 rings of cubes from left to front to right to back to left. If we were to compare the front face after the application of *U u* it would look identical to the right face after *D d*. My indexing function considers them as two different cubes. To solve *U u* and create the original position, only *U' u'* or *u' U'* will work. If you solve *U u* by making the moves *D' d'*, you solve a different cube, although "the cube" is still solved. It was the only way I could reconcile the index-to-position move generator with rotated versions of the cube without having to do the *DLB cubie *hunt.



cuBerBruce said:


> As I hope you're well aware by now, the set of sequences that yield positions n moves away from a scrambled state *depend upon the scrambled state itself*. This is due to different arrangements of indistinguishable pieces in different scrambled states.



Yes, perfectly clear.

Some of my data:


```
starting cube @ depth 0 generates a unique cube for index 0
 U   @ depth 1 generates a unique cube for index 1
 R   @ depth 1 generates a unique cube for index 2
 F   @ depth 1 generates a unique cube for index 3
 D   @ depth 1 generates a unique cube for index 4
 L   @ depth 1 generates a unique cube for index 5
 B   @ depth 1 generates a unique cube for index 6
 U'  @ depth 1 generates a unique cube for index 7
 R'  @ depth 1 generates a unique cube for index 8
 F'  @ depth 1 generates a unique cube for index 9
 D'  @ depth 1 generates a unique cube for index 10
 L'  @ depth 1 generates a unique cube for index 11
 B'  @ depth 1 generates a unique cube for index 12
 U2  @ depth 1 generates a unique cube for index 13
 R2  @ depth 1 generates a unique cube for index 14
 F2  @ depth 1 generates a unique cube for index 15
 D2  @ depth 1 generates a unique cube for index 16
 L2  @ depth 1 generates a unique cube for index 17
 B2  @ depth 1 generates a unique cube for index 18
 u   @ depth 1 generates a unique cube for index 19
 r   @ depth 1 generates a unique cube for index 20
 f   @ depth 1 generates a unique cube for index 21
 d   @ depth 1 generates a unique cube for index 22
 l   @ depth 1 generates a unique cube for index 23
 b   @ depth 1 generates a unique cube for index 24
 u'  @ depth 1 generates a unique cube for index 25
 r'  @ depth 1 generates a unique cube for index 26
 f'  @ depth 1 generates a unique cube for index 27
 d'  @ depth 1 generates a unique cube for index 28
 l'  @ depth 1 generates a unique cube for index 29
 b'  @ depth 1 generates a unique cube for index 30
 u2  @ depth 1 generates a unique cube for index 31
 r2  @ depth 1 generates a unique cube for index 32
 f2  @ depth 1 generates a unique cube for index 33
 d2  @ depth 1 generates a unique cube for index 34
 l2  @ depth 1 generates a unique cube for index 35
 b2  @ depth 1 generates a unique cube for index 36
```

By generating moves in that order, it becomes easy to predict when moves collide or when they collapse to form a move generated at a prior depth.

I also annotated the duplication failures:


```
U  U   @ depth 2 generates a cube already at index 13
 U  U2  @ depth 2 generates a cube already at index 7
 R  R   @ depth 2 generates a cube already at index 14
 R  R2  @ depth 2 generates a cube already at index 8
 F  F   @ depth 2 generates a cube already at index 15
 F  F2  @ depth 2 generates a cube already at index 9
 D  U   @ depth 2 generates a cube already at index 39
 D  D   @ depth 2 generates a cube already at index 16
 D  D2  @ depth 2 generates a cube already at index 10
 L  R   @ depth 2 generates a cube already at index 73
 L  L   @ depth 2 generates a cube already at index 17
 L  L2  @ depth 2 generates a cube already at index 11
 B  F   @ depth 2 generates a cube already at index 107
 B  B   @ depth 2 generates a cube already at index 18
 B  B2  @ depth 2 generates a cube already at index 12
 U' D   @ depth 2 generates a cube already at index 140
 U' U'  @ depth 2 generates a cube already at index 13
 U' U2  @ depth 2 generates a cube already at index 1
 R' L   @ depth 2 generates a cube already at index 173
 R' R'  @ depth 2 generates a cube already at index 14
 R' R2  @ depth 2 generates a cube already at index 2
 F' B   @ depth 2 generates a cube already at index 206
 F' F'  @ depth 2 generates a cube already at index 15
 F' F2  @ depth 2 generates a cube already at index 3
 D' U   @ depth 2 generates a cube already at index 44
 D' U'  @ depth 2 generates a cube already at index 238
 D' D'  @ depth 2 generates a cube already at index 16
 D' D2  @ depth 2 generates a cube already at index 4
 L' R   @ depth 2 generates a cube already at index 78
 L' R'  @ depth 2 generates a cube already at index 271
 L' L'  @ depth 2 generates a cube already at index 17
 L' L2  @ depth 2 generates a cube already at index 5
 B' F   @ depth 2 generates a cube already at index 112
 B' F'  @ depth 2 generates a cube already at index 304
 B' B'  @ depth 2 generates a cube already at index 18
 B' B2  @ depth 2 generates a cube already at index 6
 U2 U   @ depth 2 generates a cube already at index 7
 U2 D   @ depth 2 generates a cube already at index 145
 U2 U'  @ depth 2 generates a cube already at index 1
 U2 D'  @ depth 2 generates a cube already at index 336
 R2 R   @ depth 2 generates a cube already at index 8
 R2 L   @ depth 2 generates a cube already at index 178
 R2 R'  @ depth 2 generates a cube already at index 2
 R2 L'  @ depth 2 generates a cube already at index 368
 F2 F   @ depth 2 generates a cube already at index 9
 F2 B   @ depth 2 generates a cube already at index 211
 F2 F'  @ depth 2 generates a cube already at index 3
 F2 B'  @ depth 2 generates a cube already at index 400
 D2 U   @ depth 2 generates a cube already at index 49
 D2 D   @ depth 2 generates a cube already at index 10
 D2 U'  @ depth 2 generates a cube already at index 243
 D2 D'  @ depth 2 generates a cube already at index 4
 D2 U2  @ depth 2 generates a cube already at index 431
 L2 R   @ depth 2 generates a cube already at index 83
 L2 L   @ depth 2 generates a cube already at index 11
 L2 R'  @ depth 2 generates a cube already at index 276
 L2 L'  @ depth 2 generates a cube already at index 5
 L2 R2  @ depth 2 generates a cube already at index 463
 B2 F   @ depth 2 generates a cube already at index 117
 B2 B   @ depth 2 generates a cube already at index 12
 B2 F'  @ depth 2 generates a cube already at index 309
 B2 B'  @ depth 2 generates a cube already at index 6
 B2 F2  @ depth 2 generates a cube already at index 495
 u  U   @ depth 2 generates a cube already at index 52
 u  D   @ depth 2 generates a cube already at index 150
 u  U'  @ depth 2 generates a cube already at index 246
 u  D'  @ depth 2 generates a cube already at index 341
 u  U2  @ depth 2 generates a cube already at index 434
 u  D2  @ depth 2 generates a cube already at index 526
 u  u   @ depth 2 generates a cube already at index 31
 u  u2  @ depth 2 generates a cube already at index 25
 r  R   @ depth 2 generates a cube already at index 86
 r  L   @ depth 2 generates a cube already at index 183
 r  R'  @ depth 2 generates a cube already at index 279
 r  L'  @ depth 2 generates a cube already at index 373
 r  R2  @ depth 2 generates a cube already at index 466
 r  L2  @ depth 2 generates a cube already at index 557
 r  r   @ depth 2 generates a cube already at index 32
 r  r2  @ depth 2 generates a cube already at index 26
 f  F   @ depth 2 generates a cube already at index 120
 f  B   @ depth 2 generates a cube already at index 216
 f  F'  @ depth 2 generates a cube already at index 312
 f  B'  @ depth 2 generates a cube already at index 405
 f  F2  @ depth 2 generates a cube already at index 498
 f  B2  @ depth 2 generates a cube already at index 588
 f  f   @ depth 2 generates a cube already at index 33
 f  f2  @ depth 2 generates a cube already at index 27
 d  U   @ depth 2 generates a cube already at index 55
 d  D   @ depth 2 generates a cube already at index 153
 d  U'  @ depth 2 generates a cube already at index 249
 d  D'  @ depth 2 generates a cube already at index 344
 d  U2  @ depth 2 generates a cube already at index 437
 d  D2  @ depth 2 generates a cube already at index 529
 d  u   @ depth 2 generates a cube already at index 618
 d  d   @ depth 2 generates a cube already at index 34
 d  d2  @ depth 2 generates a cube already at index 28
 l  R   @ depth 2 generates a cube already at index 89
 l  L   @ depth 2 generates a cube already at index 186
 l  R'  @ depth 2 generates a cube already at index 282
 l  L'  @ depth 2 generates a cube already at index 376
 l  R2  @ depth 2 generates a cube already at index 469
 l  L2  @ depth 2 generates a cube already at index 560
 l  r   @ depth 2 generates a cube already at index 646
 l  l   @ depth 2 generates a cube already at index 35
 l  l2  @ depth 2 generates a cube already at index 29
 b  F   @ depth 2 generates a cube already at index 123
 b  B   @ depth 2 generates a cube already at index 219
 b  F'  @ depth 2 generates a cube already at index 315
 b  B'  @ depth 2 generates a cube already at index 408
 b  F2  @ depth 2 generates a cube already at index 501
 b  B2  @ depth 2 generates a cube already at index 591
 b  f   @ depth 2 generates a cube already at index 674
 b  b   @ depth 2 generates a cube already at index 36
 b  b2  @ depth 2 generates a cube already at index 30
 u' U   @ depth 2 generates a cube already at index 58
 u' D   @ depth 2 generates a cube already at index 156
 u' U'  @ depth 2 generates a cube already at index 252
 u' D'  @ depth 2 generates a cube already at index 347
 u' U2  @ depth 2 generates a cube already at index 440
 u' D2  @ depth 2 generates a cube already at index 532
 u' d   @ depth 2 generates a cube already at index 701
 u' u'  @ depth 2 generates a cube already at index 31
 u' u2  @ depth 2 generates a cube already at index 19
 r' R   @ depth 2 generates a cube already at index 92
 r' L   @ depth 2 generates a cube already at index 189
 r' R'  @ depth 2 generates a cube already at index 285
 r' L'  @ depth 2 generates a cube already at index 379
 r' R2  @ depth 2 generates a cube already at index 472
 r' L2  @ depth 2 generates a cube already at index 563
 r' l   @ depth 2 generates a cube already at index 728
 r' r'  @ depth 2 generates a cube already at index 32
 r' r2  @ depth 2 generates a cube already at index 20
 f' F   @ depth 2 generates a cube already at index 126
 f' B   @ depth 2 generates a cube already at index 222
 f' F'  @ depth 2 generates a cube already at index 318
 f' B'  @ depth 2 generates a cube already at index 411
 f' F2  @ depth 2 generates a cube already at index 504
 f' B2  @ depth 2 generates a cube already at index 594
 f' b   @ depth 2 generates a cube already at index 755
 f' f'  @ depth 2 generates a cube already at index 33
 f' f2  @ depth 2 generates a cube already at index 21
 d' U   @ depth 2 generates a cube already at index 61
 d' D   @ depth 2 generates a cube already at index 159
 d' U'  @ depth 2 generates a cube already at index 255
 d' D'  @ depth 2 generates a cube already at index 350
 d' U2  @ depth 2 generates a cube already at index 443
 d' D2  @ depth 2 generates a cube already at index 535
 d' u   @ depth 2 generates a cube already at index 623
 d' u'  @ depth 2 generates a cube already at index 781
 d' d'  @ depth 2 generates a cube already at index 34
 d' d2  @ depth 2 generates a cube already at index 22
 l' R   @ depth 2 generates a cube already at index 95
 l' L   @ depth 2 generates a cube already at index 192
 l' R'  @ depth 2 generates a cube already at index 288
 l' L'  @ depth 2 generates a cube already at index 382
 l' R2  @ depth 2 generates a cube already at index 475
 l' L2  @ depth 2 generates a cube already at index 566
 l' r   @ depth 2 generates a cube already at index 651
 l' r'  @ depth 2 generates a cube already at index 808
 l' l'  @ depth 2 generates a cube already at index 35
 l' l2  @ depth 2 generates a cube already at index 23
 b' F   @ depth 2 generates a cube already at index 129
 b' B   @ depth 2 generates a cube already at index 225
 b' F'  @ depth 2 generates a cube already at index 321
 b' B'  @ depth 2 generates a cube already at index 414
 b' F2  @ depth 2 generates a cube already at index 507
 b' B2  @ depth 2 generates a cube already at index 597
 b' f   @ depth 2 generates a cube already at index 679
 b' f'  @ depth 2 generates a cube already at index 835
 b' b'  @ depth 2 generates a cube already at index 36
 b' b2  @ depth 2 generates a cube already at index 24
 u2 U   @ depth 2 generates a cube already at index 64
 u2 D   @ depth 2 generates a cube already at index 162
 u2 U'  @ depth 2 generates a cube already at index 258
 u2 D'  @ depth 2 generates a cube already at index 353
 u2 U2  @ depth 2 generates a cube already at index 446
 u2 D2  @ depth 2 generates a cube already at index 538
 u2 u   @ depth 2 generates a cube already at index 25
 u2 d   @ depth 2 generates a cube already at index 706
 u2 u'  @ depth 2 generates a cube already at index 19
 u2 d'  @ depth 2 generates a cube already at index 861
 r2 R   @ depth 2 generates a cube already at index 98
 r2 L   @ depth 2 generates a cube already at index 195
 r2 R'  @ depth 2 generates a cube already at index 291
 r2 L'  @ depth 2 generates a cube already at index 385
 r2 R2  @ depth 2 generates a cube already at index 478
 r2 L2  @ depth 2 generates a cube already at index 569
 r2 r   @ depth 2 generates a cube already at index 26
 r2 l   @ depth 2 generates a cube already at index 733
 r2 r'  @ depth 2 generates a cube already at index 20
 r2 l'  @ depth 2 generates a cube already at index 887
 f2 F   @ depth 2 generates a cube already at index 132
 f2 B   @ depth 2 generates a cube already at index 228
 f2 F'  @ depth 2 generates a cube already at index 324
 f2 B'  @ depth 2 generates a cube already at index 417
 f2 F2  @ depth 2 generates a cube already at index 510
 f2 B2  @ depth 2 generates a cube already at index 600
 f2 f   @ depth 2 generates a cube already at index 27
 f2 b   @ depth 2 generates a cube already at index 760
 f2 f'  @ depth 2 generates a cube already at index 21
 f2 b'  @ depth 2 generates a cube already at index 913
 d2 U   @ depth 2 generates a cube already at index 67
 d2 D   @ depth 2 generates a cube already at index 165
 d2 U'  @ depth 2 generates a cube already at index 261
 d2 D'  @ depth 2 generates a cube already at index 356
 d2 U2  @ depth 2 generates a cube already at index 449
 d2 D2  @ depth 2 generates a cube already at index 541
 d2 u   @ depth 2 generates a cube already at index 628
 d2 d   @ depth 2 generates a cube already at index 28
 d2 u'  @ depth 2 generates a cube already at index 786
 d2 d'  @ depth 2 generates a cube already at index 22
 d2 u2  @ depth 2 generates a cube already at index 938
 l2 R   @ depth 2 generates a cube already at index 101
 l2 L   @ depth 2 generates a cube already at index 198
 l2 R'  @ depth 2 generates a cube already at index 294
 l2 L'  @ depth 2 generates a cube already at index 388
 l2 R2  @ depth 2 generates a cube already at index 481
 l2 L2  @ depth 2 generates a cube already at index 572
 l2 r   @ depth 2 generates a cube already at index 656
 l2 l   @ depth 2 generates a cube already at index 29
 l2 r'  @ depth 2 generates a cube already at index 813
 l2 l'  @ depth 2 generates a cube already at index 23
 l2 r2  @ depth 2 generates a cube already at index 964
 b2 F   @ depth 2 generates a cube already at index 135
 b2 B   @ depth 2 generates a cube already at index 231
 b2 F'  @ depth 2 generates a cube already at index 327
 b2 B'  @ depth 2 generates a cube already at index 420
 b2 F2  @ depth 2 generates a cube already at index 513
 b2 B2  @ depth 2 generates a cube already at index 603
 b2 f   @ depth 2 generates a cube already at index 684
 b2 b   @ depth 2 generates a cube already at index 30
 b2 f'  @ depth 2 generates a cube already at index 840
 b2 b'  @ depth 2 generates a cube already at index 24
 b2 f2  @ depth 2 generates a cube already at index 990
 U  U  U   @ depth 3 generates a cube already at index 7
 U  U  R   @ depth 3 generates a cube already at index 421
```

This way if there is a collision that "shouldn't be here" I can look up the index in the "acceptable" list and see what the sequence happens to be.

Of note:


```
U  u  D   @ depth 3 generates a cube already at index 1141
```

That sequence fails since...


```
U  D  u   @ depth 3 generates a unique cube for index 1141
```

Also


```
U  u  D' d'  @ depth 4 generates a cube already at index 36441
```

because...


```
U  D' u  d'  @ depth 4 generates a unique cube for index 36441
```

So the program will now allow for rotations of the cube via 4 consecutive parallel face turns.

*UPDATE: I am thinking about changing my move generator from a parallel collapsed for-loop structure back to a nested move generator*

The linear move generator code with all 4-ply legal moves pre-loaded into a global structure:


```
for(i = 0; i < TOTAL_NODES_IN_TFS_4; i++)
					{
						GLOBAL_CUBE_SOLUTION[0] = GLOBAL_ALL_LEGAL_MOVES_04[i].move_list[0] + 1;
						GLOBAL_CUBE_SOLUTION[1] = GLOBAL_ALL_LEGAL_MOVES_04[i].move_list[1] + 1;
						GLOBAL_CUBE_SOLUTION[2] = GLOBAL_ALL_LEGAL_MOVES_04[i].move_list[2] + 1;
						GLOBAL_CUBE_SOLUTION[3] = GLOBAL_ALL_LEGAL_MOVES_04[i].move_list[3] + 1;

						if(time_to_update()){ BUILD_PV_STRING if(solved_in_database== 1) printf("\n"); SHOW_PV_STRING solved_in_database= 0;}

						modified_cube = cube_move_array[GLOBAL_CUBE_SOLUTION[0]-1](starting_cube);
						if(cube_cant_be_solved_by_current_search_depth(modified_cube, 3) == 0)
						{
							modified_cube = cube_move_array[GLOBAL_CUBE_SOLUTION[1]-1](modified_cube);
							if(cube_cant_be_solved_by_current_search_depth(modified_cube, 2) == 0)
							{
								modified_cube = cube_move_array[GLOBAL_CUBE_SOLUTION[2]-1](modified_cube);

								if(cube_cant_be_solved_by_current_search_depth(modified_cube, 1) == 0)
								{
									modified_cube = cube_move_array[GLOBAL_CUBE_SOLUTION[3]-1](modified_cube);
									g_total_nodes++;
									solved_in_database= probe_tfs_database(modified_cube, 4);

									if(time_to_update()){ BUILD_PV_STRING if(solved_in_database== 1) printf("\n"); SHOW_PV_STRING solved_in_database= 0;}
								}
								else {GLOBAL_LEAF_NODE_PRUNES++;}
							}
							else {GLOBAL_BRANCHES_PRUNED++;}
						}
						else {GLOBAL_BRANCHES_PRUNED++; solved_in_database= probe_tfs_database(modified_cube, 1);}
					}
```

My older code looked like this:


```
void search_tree_forever(CUBE_4x4_ARRANGEMENT which_cube, unsigned short which_depth, signed short last_move_axis, signed short last_move_group, signed short move_just_made, unsigned short unchanging_depth)
{
	CUBE_4x4_ARRANGEMENT modified_cube;

	signed short   axis_of_rotation;
	signed short   move_group;
	unsigned short move_index;
	unsigned short which_move_to_make;
	
	unsigned short result;

	if(move_just_made >= 0) GLOBAL_CUBE_SOLUTION[unchanging_depth - which_depth - 1] = move_just_made + 1;

	if(which_depth == 0)
	{
			g_total_nodes++;
			result = analyze_cube(which_cube);
	}
	else
	{
		for(axis_of_rotation = 0; axis_of_rotation < 3; axis_of_rotation++)
			for(move_group = 0; move_group < 4; move_group++)
			{
				if((axis_of_rotation != last_move_axis) || ((axis_of_rotation == last_move_axis) && (move_group > last_move_group)))
				{
					for(move_index = 0; move_index < 3; move_index++)
					{
						which_move_to_make = GLOBAL_AXIS_ROTATION[axis_of_rotation][move_group][move_index];
						modified_cube = cube_move_array[which_move_to_make](which_cube);
						search_tree_forever(modified_cube, which_depth-1, axis_of_rotation, move_group, which_move_to_make, unchanging_depth);
					}
				}
			}
	}
}
```

...which was based upon Jakube's recommendation. When I switched over to an indexing function that would ONLY generate legal moves, I thought it would be much faster. But now there is a problem! When I implement any pruning, I have "already paid the price" of generating the move! So even with massive pruning, I still have 100% of the overhead associated with move generation. If, however, I resort back to this older format, the pruning would occur PRIOR to move generation if it is evoked at any level in the tree above the move generator call. I should have thought of this before I spent 2 weeks working out the details of an index-to-position move generator!

I thought the parallel gains would more than offset the bloated game tree, but this is clearly not the case. The tree grows exponentially and the parallel gains are a linear constant == your processor core count.

So now I need to work out a modified version of Jakube's idea that will allow certain cases of 4 moves along the same axis. The old code for 3-axis turns:


```
void init_axis_move_data(void)
{
	GLOBAL_AXIS_ROTATION[0][0][0] = U___PLUS____;
	GLOBAL_AXIS_ROTATION[0][0][1] = U___MINUS___;
	GLOBAL_AXIS_ROTATION[0][0][2] = U___TWICE___;
	GLOBAL_AXIS_ROTATION[0][1][0] = u___PLUS____;
	GLOBAL_AXIS_ROTATION[0][1][1] = u___MINUS___;
	GLOBAL_AXIS_ROTATION[0][1][2] = u___TWICE___;
	GLOBAL_AXIS_ROTATION[0][2][0] = d___PLUS____;
	GLOBAL_AXIS_ROTATION[0][2][1] = d___MINUS___;
	GLOBAL_AXIS_ROTATION[0][2][2] = d___TWICE___;
	GLOBAL_AXIS_ROTATION[0][3][0] = D___PLUS____;
	GLOBAL_AXIS_ROTATION[0][3][1] = D___MINUS___;
	GLOBAL_AXIS_ROTATION[0][3][2] = D___TWICE___;
	GLOBAL_AXIS_ROTATION[1][0][0] = R___PLUS____;
	GLOBAL_AXIS_ROTATION[1][0][1] = R___MINUS___;
	GLOBAL_AXIS_ROTATION[1][0][2] = R___TWICE___;
	GLOBAL_AXIS_ROTATION[1][1][0] = r___PLUS____;
	GLOBAL_AXIS_ROTATION[1][1][1] = r___MINUS___;
	GLOBAL_AXIS_ROTATION[1][1][2] = r___TWICE___;
	GLOBAL_AXIS_ROTATION[1][2][0] = l___PLUS____;
	GLOBAL_AXIS_ROTATION[1][2][1] = l___MINUS___;
	GLOBAL_AXIS_ROTATION[1][2][2] = l___TWICE___;
	GLOBAL_AXIS_ROTATION[1][3][0] = L___PLUS____;
	GLOBAL_AXIS_ROTATION[1][3][1] = L___MINUS___;
	GLOBAL_AXIS_ROTATION[1][3][2] = L___TWICE___;
	GLOBAL_AXIS_ROTATION[2][0][0] = F___PLUS____;
	GLOBAL_AXIS_ROTATION[2][0][1] = F___MINUS___;
	GLOBAL_AXIS_ROTATION[2][0][2] = F___TWICE___;
	GLOBAL_AXIS_ROTATION[2][1][0] = f___PLUS____;
	GLOBAL_AXIS_ROTATION[2][1][1] = f___MINUS___;
	GLOBAL_AXIS_ROTATION[2][1][2] = f___TWICE___;
	GLOBAL_AXIS_ROTATION[2][2][0] = b___PLUS____;
	GLOBAL_AXIS_ROTATION[2][2][1] = b___MINUS___;
	GLOBAL_AXIS_ROTATION[2][2][2] = b___TWICE___;
	GLOBAL_AXIS_ROTATION[2][3][0] = B___PLUS____;
	GLOBAL_AXIS_ROTATION[2][3][1] = B___MINUS___;
	GLOBAL_AXIS_ROTATION[2][3][2] = B___TWICE___;
}
```


----------



## cuBerBruce (May 20, 2014)

I've now done a calculation for the number of 4x4x4 supercube positions reachable for up to 6 moves (single slice turn metric) from a starting position. The results are the same as for the regular 4x4x4 starting from the solved state for distances up to 3. At 4 moves, the supercube numbers start becoming larger.

Of course, these numbers assume the orientation of the cube doesn't matter. That is, states differing only by reorienting the cube are considered to be the same position. So, for example, U u and D d would be counted as the same position.

```
moves  positions  cumulative   positions  cumulative pos.
                   positions     mod M         mod M

  0            1           1           1              1
  1           36          37           4              5
  2          999        1036          36             41
  3        27234       28270         619            660
  4       741699      769969       15818          16478
  5     20150576    20920545      421888         438366
  6    305250472   326171017     6368087        6806453
```

If I consider the orientation to matter (that, the cube is not considered solved unless each face is a solid color and each color must be on a particular face), I get the following distance distribution for supercube positions. I note that I used a breadth-first search without any move restrictions based on previous moves (other than the fact that I am using single slice turn metric - meaning only one layer can be turned in any single move). 


```
moves  positions  cumulative
                   positions
  0            1          1
  1           36         37
  2         1026       1063
  3        28836      29899
  4       808623     838522
  5     22627004   23465526
```

Finally, if I assume a *non-supercube* model while also assuming a particular orientation for the "solved" state,
I get the following distribution of distances from the "solved" state.


```
moves  positions  cumulative
                   positions
  0            1          1
  1           36         37
  2         1026       1063
  3        28812      29875
  4       806772     836647
  5     22538576   23375223
```

I notice that that this last result agrees with Unsolved's table up to 3 moves:


> nExplicit Unique Counts136​21,026​328,812​4806,694​522,575,425​6631,793,942​717,681,379,137​



This suggests to me that Unsolved was not only still using a fixed orientation for the "solved" state, but may have also been trying to use a *non-supercube* model as the basis of his move generator, if I'm understanding him. For an arbitrary scrambled state, my numbers indicate you need to consider at least 28,836 sequences of moves for 3 moves away (although only 27,324 if you eliminated the fixed "solved" orientation of the cube), and 808,623 sequences for 4 moves away.

A simple example of 3-move sequences that look like duplicates from a turns-from-solved perspective (non-supercube), but not from a supercube perspective.

r2 b2 l2
l2 b2 r2

The above two sequences appear to have the same affect on a solved cube, but they have different actual permutation effects. Thus, while only one is needed in a "turns-from-solved" database, you need to consider applying both of these sequences from an arbitrary scrambled state.


----------



## unsolved (May 21, 2014)

cuBerBruce said:


> I've now done a calculation for the number of 4x4x4 supercube positions reachable for up to 6 moves (single slice turn metric) from a starting position. The results are the same as for the regular 4x4x4 starting from the solved state for distances up to 3. At 4 moves, the supercube numbers start becoming larger.
> 
> Of course, these numbers assume the orientation of the cube doesn't matter. That is, states differing only by reorienting the cube are considered to be the same position. So, for example, U u and D d would be counted as the same position.



Hi Bruce,

It sounds like we need some nomenclature to make this crystal clear. The enumeration of moves from the solved state can be different from the enumeration of moves from an arbitrarily scrambled state. Furthermore, each different strata can encounter move sequences that may functionally rotate the cube in place. This adds complexity to the move generation/solve state checking process. While it is possible to generate a subset of all possible moves if there is a clever solver that can detect rotations and identify a solved cube independent of its 3-space orientation, any solver that is going to access a collection of pre-solved positions from the solved state for the purpose of reducing the trunk of the game tree must also be capable of generating move sequences that would spawn any interim rotated state en route to a pre-solved database entry.

There is no way around this: it would be too computationally intensive to require the database lookup code to recognize anything but what is in the database itself. Testing for rotated versions of transient positions would create a bottleneck. It would be better to have a greater number of positions that also happen to be 90 degree or 180 degree versions of a move sequence than to pre-filter these during the distance-from-solved generation process and then to delegate the rectification to a more complex lookup procedure.

What all of this means: We need to come up with meaningful names for each of our counts!

A true Turns-From-Solved count MUST include cases where a sequence of turns re-orients a cube face, as long as no move sequence can create the identical cubies on those faces in fewer moves. The prime example:* U D' u d'* must be a legally countable position in the 4-TFS since there is no way to rotate the cube 90 degrees clockwise in fewer moves. Likewise *U2 D2 u2 d2* creates a cube arrangement that is solved but 180 degrees from the initial orientation. However, transposing moves creating a position already, as alluded to by Bruce, should be discarded.

That would seem to suggest that a TFS enumeration is really a *Solved State Transpositionless Face Rotation* (SSTFR) count.

Your first group of numbers:


```
moves  positions  cumulative   positions  cumulative pos.
                   positions     mod M         mod M

  0            1           1           1              1
  1           36          37           4              5
  2          999        1036          36             41
  3        27234       28270         619            660
  4       741699      769969       15818          16478
  5     20150576    20920545      421888         438366
  6    305250472   326171017     6368087        6806453
```

...is what I would refer to as an *Arbitrary Scramble Rotationless Transposition* (ASRT) count.

That would imply your data below would be like an *Arbitrary Scramble Preferred Orientation Transposition* (ASPOT) count.


```
moves  positions  cumulative
                   positions
  0            1          1
  1           36         37
  2         1026       1063
  3        28836      29899
  4       808623     838522
  5     22627004   23465526
```

This set of numbers below is a hybrid of the SSTFR and the ASPOT counts.


```
moves  positions  cumulative
                   positions
  0            1          1
  1           36         37
  2         1026       1063
  3        28812      29875
  4       806772     836647
  5     22538576   23375223
```



cuBerBruce said:


> This suggests to me that Unsolved was not only still using a fixed orientation for the "solved" state, but may have also been trying to use a *non-supercube* model as the basis of his move generator, if I'm understanding him. For an arbitrary scrambled state, my numbers indicate you need to consider at least 28,836 sequences of moves for 3 moves away (although only 27,324 if you eliminated the fixed "solved" orientation of the cube), and 808,623 sequences for 4 moves away.



Bingo! As was necessary, I believe, for the sake of my sanity.

I did place every move the TFS database generator will permit into separate text files sorted by depth.

http://www.lightningcloudcomputing.com/depth_01.txt

http://www.lightningcloudcomputing.com/depth_02.txt

http://www.lightningcloudcomputing.com/depth_03.txt

http://www.lightningcloudcomputing.com/depth_04.txt

I also have a 550 MB depth_05.txt file which is not online. Even the depth_04 one at 52 MB will take a while to open.

The moves that did *NOT *make the list are in a separate file, again, very large, 57 MB:

http://www.lightningcloudcomputing.com/failed_moves.txt


----------



## qqwref (May 21, 2014)

unsolved said:


> A true Turns-From-Solved count MUST include cases where a sequence of turns re-orients a cube face, as long as no move sequence can create the identical cubies on those faces in fewer moves. The prime example:* U D' u d'* must be a legally countable position in the 4-TFS since there is no way to rotate the cube 90 degrees clockwise in fewer moves. Likewise *U2 D2 u2 d2* creates a cube arrangement that is solved but 180 degrees from the initial orientation. However, transposing moves creating a position already, as alluded to by Bruce, should be discarded.


Hang on. Maybe what you're talking about is a quirk of your own approach, and something that is necessary because of the way you are keeping track of pruning tables, but for almost everyone else, they would say that U D' u d' is 0 turns from solved - rotations are free. For instance, if you load up a Cube Explorer instance and solve some cubes with slice turns enabled, you will often see a rotation or two at the end of the solving sequence. Those are not counted in the movecount, and are just there to bring the cube back to the original orientation.

Of course, even though rotations are free, solvers don't consider them as part of algs. The reason is that doing a rotation before some move sequence A is always equivalent to doing some other move sequence f(A) (of the same length as A) before the rotation. So you can always leave all rotations for the end, and as long as you accept any rotation of the solved state there, the cube will be solved.


----------



## cuBerBruce (May 21, 2014)

As I see it, Unsolved wants to use a basic model of the cube where the orientation of the solved cube matters. This differs from the normal view that the orientation of the solved cube does not matter. As a result, his solver either might have to use extra moves to get the cube "solved" to his preferred orientation, or he could try solving all 24 different possible orientations of the initial scramble. Another possibility is simply defining there to be 24 solved states, which would make his TFS databases roughly 24 times bigger than they already are. In summary, he is using a "flawed" definition of the cube being solved, and he either needs to abandon that flawed definition, compensate for it in some consistent manner, or just accept that his generated solutions may not be optimal in the manner that the cubing community would expect.

As for his files in the preceding post, I thought I would look at my 3-move examples in my prior post: r2 b2 l2 and l2 b2 r2. r2 b2 l2 is in the database with index 27067. l2 b2 r2 is in the failed_moves database, where I find:

l2 b2 r2 @ depth 3 generates a cube already at index 27138

But for index 27138, I find:

f2 D U' @ depth 3 generates a unique cube for index 27138

which is clearly not the same state that is generated by l2 b2 r2.

So it seems to me these files are flawed, regardless of whether they're intended to be a "turns from solved" database or a "turns from starting state" for a supercube.



unsolved said:


> As was necessary, I believe, for the sake of my sanity.



I am not clear what your claiming is "necessary." Are you agreeing that when applying moves to the scramble position, you must consider sequences r2 b2 l2 and l2 b2 r2 as separate unique sequences to be tried?

As for your names, I find them non-intuitive. For one thing, from your names it doesn't seem clear whether a regular cube model or a supercube model is being used, which in my view is very important. And ...



unsolved said:


> This set of numbers below is a hybrid of the SSTFR and the ASPOT counts.
> 
> 
> ```
> ...



... how is this set of numbers different from what you are calling SSTFR?


----------



## unsolved (May 22, 2014)

qqwref said:


> Hang on. Maybe what you're talking about is a quirk of your own approach



Quite possibly. I cannot disallow a move sequence to be performed if it can possibly lead to a solve though, can I? Bruce supplied a move sequence that did just that: avoided detection due to the move generator not handling the reversing process correctly. Well, if it can be generated, it must go into a turns-from-solved database. Therein lies the conundrum. 



cuBerBruce said:


> As I see it, Unsolved wants to use a basic model of the cube where the orientation of the solved cube matters. This differs from the normal view that the orientation of the solved cube does not matter. As a result, his solver either might have to use extra moves to get the cube "solved" to his preferred orientation, or he could try solving all 24 different possible orientations of the initial scramble.



My objective is to create a move generator where the orientation does not matter, but this is apparently in conflict with the Turns-From-Solved database generation process altogether. All 24 solved states are within the 4-TFS database anyway, are they not? *U D' u d'*, *U2 D2 u2 d2* are for sure, and I imagine the equivalent moves for rotating front-to-top, as well as the others, are as well. In essence, this will not impact the optimal distance for any solve anyway. The program explores all such paths, and once it finds a shorter way, it takes it, and "blocks" the display of any longer paths. What it may do is find a solution to a path to a rotated state, which at worst is just a rotated version of the preferred state, which is still solved, just rotated, with an announced distance that is "n + 4" further away than it is, with moves such as *d u' D U'* tacked on at the end. This would be preferred to not finding a solution at all because it involved 4 consecutive parallel rotations. And, if there is a shorter solve to the "preferred state," it will have smaller distances in the databases, and it will be found.



cuBerBruce said:


> Another possibility is simply defining there to be 24 solved states, which would make his TFS databases roughly 24 times bigger than they already are. In summary, he is using a "flawed" definition of the cube being solved, and he either needs to abandon that flawed definition, compensate for it in some consistent manner, or just accept that his generated solutions may not be optimal in the manner that the cubing community would expect.



I guess the question is: Are all 24 rotated states possible within the 4-ply horizon? If so, I don't think the bloating factor is 24. It would be 24 if I took all 24 solved states and generated the moves from each of them, but I don't. I just make 6 turns from a preferred solved state, and if they generate any interim rotations, so be it.



cuBerBruce said:


> As for his files in the preceding post, I thought I would look at my 3-move examples in my prior post: r2 b2 l2 and l2 b2 r2. r2 b2 l2 is in the database with index 27067. l2 b2 r2 is in the failed_moves database, where I find:
> 
> l2 b2 r2 @ depth 3 generates a cube already at index 27138
> 
> ...



Now this is good information! Clearly something is awry. I believe that is a parallel programming error of some sort. I checked all the data by having the program verify the positions. Then I experimented with the parallel code, trying to make it faster. I did not turn off the #define to stop outputting text. It must have overwritten this data many times, corrupting something. I am using omp.h for my parallelism and must have botched something. Clearly earlier versions of the program were running fine and finding solves as expected, certain rare exceptions involving rotated interim states excepted, which is what led to this recoding effort to begin with.

I will set the program back to serial-mode and regenerate the tables. Thanks for the excellent sleuthing effort!

*UPDATE: It looks like the serial version creates matching index pairs now:*


```
l2 b2 r2  @ depth 3 generates a cube already at index 27067
r2 b2 l2  @ depth 3 generates a unique cube for index 27067
```

However, the count for depth 3 == *28,702* and depth 4 == *799,020*. This used the Jakube move generator idea.



cuBerBruce said:


> I am not clear what your claiming is "necessary." Are you agreeing that when applying moves to the scramble position, you must consider sequences r2 b2 l2 and l2 b2 r2 as separate unique sequences to be tried?



Scrambled state solves and turns-from-solved database creation processes must use separate move generation routines.



cuBerBruce said:


> As for your names, I find them non-intuitive. For one thing, from your names it doesn't seem clear whether a regular cube model or a supercube model is being used, which in my view is very important. And ...



Most comp-sci names are unintuitive: Alpha-beta routine, hashing function, indexing function, minimal window principal variation search, sparsely-populated matrix, etc. After you hear them enough, they become second nature. Kind of reminds me of an Arthur Shopenhauer quote: *All truth passes through three stages. First, it is ridiculed. Second, it is violently opposed. Third, it is accepted as being self-evident.*

It looks like it is time for yet-another-move-generator attempt. I will abandon trying to make one move generator for both the forward-solving and backwards-solving code. Being able to deal with all of these orientations is going to be a problem.


----------



## cuBerBruce (May 22, 2014)

unsolved said:


> My objective is to create a move generator where the orientation does not matter, but this is apparently in conflict with the Turns-From-Solved database generation process altogether. All 24 solved states are within the 4-TFS database anyway, are they not?



No, only 9 of the 23 non-identity cube rotations are at a distance of 4. The other 14 I believe are all at a distance of 8. Basically this means what you find as an optimal solution could be as much as 8 moves more than the length of an optimal path to a solved cube.



unsolved said:


> *U D' u d'*, *U2 D2 u2 d2* are for sure, and I imagine the equivalent moves for rotating front-to-top, as well as the others, are as well. In essence, this will not impact the optimal distance for any solve anyway.



Solving to a particular orientation will always take at least as many moves as solving to any orientation, and many times it will require more moves.

By the way, in saying "optimal distance," you are being sort of redundant. Remember, the graph theory term *distance* refers to the *length of an optimal path*. The *length* of an arbitrary path is not necessarily the *distance* between the endpoints of the path. These are only equal if the path is optimal.



unsolved said:


> I guess the question is: Are all 24 rotated states possible within the 4-ply horizon? If so, I don't think the bloating factor is 24. It would be 24 if I took all 24 solved states and generated the moves from each of them, but I don't.



In saying "but I don't," you are saying that you are at least choosing not to use this method of fixing the problem of finding the true optimal path to a solved cube. But if you were to choose this option, it would mean a substantial bloating of the TFS databases. It will be less than a factor of 24 because some states will be reached from more than one of these 24 variations of the solved state. 



unsolved said:


> However, the count for depth 3 == *28,702* and depth 4 == *799,020*. This used the Jakube move generator idea.



Jakube assumed you would consider the orientation of the solved cube doesn't matter, but you seem to keep on insisting on solving to a particular orientation. You might be able to get away with this if you try all 24 orientations of the scramble, or by trying all 24 orientations of a solved cube separately. Or you might just be content with producing solutions that might be up to 8 moves longer than what we normally would consider as the optimal solution.

I think your database is leaving out certain sequences based upon an assumption that they should not matter if we don't care about the orientation of the solved cube. Hence you end up with numbers in between my numbers for "cube orientation doesn't matter" and my numbers for "cube orientation does matter."


----------



## unsolved (May 22, 2014)

cuBerBruce said:


> No, only 9 of the 23 non-identity cube rotations are at a distance of 4. The other 14 I believe are all at a distance of 8.



So the following moves should all have a distance-from-solved = 0?

U D' u d'
U2 D2 u2 d2

F B' f b'
F2 B2 f2 b2

L R' l r'
L2 R2 l2 r2


So what happens if you start out partway to a different rotated state, such as L R' l? What would its turns-from-solved distance be?




cuBerBruce said:


> Solving to a particular orientation will always take at least as many moves as solving to any orientation, and many times it will require more moves.



Theorem, postulate, lemma, fact?



cuBerBruce said:


> By the way, in saying "optimal distance," you are being sort of redundant. Remember, the graph theory term *distance* refers to the *length of an optimal path*. The *length* of an arbitrary path is not necessarily the *distance* between the endpoints of the path. These are only equal if the path is optimal.



You can say that again! 




cuBerBruce said:


> In saying "but I don't," you are saying that you are at least choosing not to use this method of fixing the problem...



It was more along the lines of stating the present condition of the code.



cuBerBruce said:


> Jakube assumed you would consider the orientation of the solved cube doesn't matter, but you seem to keep on insisting on solving to a particular orientation.



"Insisting" is probably a strong word. The solver now does not prefer an orientation. It can tell if the cube is solved without requiring a color to be on a particular face. However, having said that, the solver does "start somewhere," and that somewhere is the state of the cube initially passed to the move generation routine. Does it have to find a solution in the default orientation? No. Is all of the subsequent move generation based off of this starting arrangement? Yes.



cuBerBruce said:


> I think your database is leaving out certain sequences based upon an assumption that they should not matter if we don't care about the orientation of the solved cube. Hence you end up with numbers in between my numbers for "cube orientation doesn't matter" and my numbers for "cube orientation does matter."



It is allowing moves that rotate the cube in place, such as U D' u d', it is disallowing transpositions from the solved state, such as the second sequence of the r2 b2 l2/l2 b2 r2 example, and it disallows any sequence that recreates the starting position.

The biggest hurdle I have right now is how to deal with the U u = D d problem. I don't see how to code something from the perspective of the move generator without having to perform some kind of lookup.


----------



## rokicki (May 23, 2014)

I handle this in my solver by fixing a single corner (DLB). Then moves such as D are actually handled by Uw3 (for example).

This also means in the end I need to "clean up" my solutions, converting moves such as Uw3 to D and reorienting the
remaining moves appropriately.

My move generator then takes this into account, and all works nicely, both with respect to generating moves and pruning
the tree of redundant move sequences from the top, and looking up values in the pruning table.

Essentially, for each possible syllable (sequence of moves on one axis) you want to have a single canonical move sequence
for that and suppress all the others. And it is here that you either fix a corner, or adopt some other approach to
implicitly suppress sequences that are identical except for full-cube-rotations.

There are 63 non-trivial syllables, where non-trivial means materially affects the cube state (not just being a full-cube
rotation).


----------



## unsolved (May 23, 2014)

rokicki said:


> I handle this in my solver by fixing a single corner (DLB). Then moves such as D are actually handled by Uw3 (for example).
> 
> This also means in the end I need to "clean up" my solutions, converting moves such as Uw3 to D and reorienting the
> remaining moves appropriately.
> ...



Can you show me a concrete example?


----------



## rokicki (May 23, 2014)

Concrete example of a syllable?

U u is one. U u' is another.

The 63 number comes from the fact that if you fix a single slice,
you have 4^3=64 possibilities for the other three; one is trivial,
so don't count that, leaving 63.

This number is independent of your metric. But depending on your
metric, the actual move sequence to attain each of these syllables
differs, and in some metrics it is easier than others to figure out
the "shortest" or "best" move sequence.

For instance, one syllable is just U u2 d3. This is equivalently
Uw u d3. You pick one, and make the others illegal.

I've got a Perl script that generates a state machine based on
the next selected move that gives the legal subsequent moves
(as a bitmask). The table turns out to be pretty small in all
three of the metrics we have been working with.


----------



## qqwref (May 23, 2014)

unsolved said:


> Most comp-sci names are unintuitive: Alpha-beta routine, hashing function, indexing function, minimal window principal variation search, sparsely-populated matrix, etc. After you hear them enough, they become second nature. Kind of reminds me of an Arthur Shopenhauer quote: All truth passes through three stages. First, it is ridiculed. Second, it is violently opposed. Third, it is accepted as being self-evident.


Oh god. Don't be like this. He's just suggesting you use better names.

Incidentally, that quote seems to have very little relation to reality. I can only think of a few facts that followed those stages, and they are isolated cases; I can't even imagine violent opposition to facts like "selection sort is O(n^2)" or "7 has no positive factors other than 1 and itself". And surely it must mean something that academics and scientists never use this quote. Clearly being in the first two stages is a completely broken predictor of whether your ideas are valid.



unsolved said:


> cuBerBruce said:
> 
> 
> > Solving to a particular orientation will always take at least as many moves as solving to any orientation, and many times it will require more moves.
> ...


It can't take *more* moves to solve to any orientation than to solve to a particular orientation, because any solution to a particular orientation is already a solution to any orientation. And it's easy to exhibit positions where solving to a particular orientation can take many more moves than solving to any orientation (e.g. y x U).


----------



## unsolved (May 23, 2014)

qqwref said:


> Oh god. Don't be like this. He's just suggesting you use better names.



The names are merely a cascade of the start-to-finish types of operations the program is doing. Example:

*Solved State Transpositionless Face Rotation*

Solved State = where it starts from
Transpositionless = elimination of move sequences that transpose
Face Rotation = allow moves that functionally rotate an entire cube face from one place to another, such as front ---> left via U D' u d'

*Arbitrary Scramble Rotationless Transposition*

Arbitrary Scramble = where it starts from
Rotationless = disallowing of moves that rotate entire cube faces
Transposition = allowing transpositional move sequences, such as r2 f2 l2 and l2 f2 r2

*Arbitrary Scramble Preferred Orientation Transposition *

Yeah, this one could use a better name. Especially since it will probably be eliminated.



qqwref said:


> Incidentally, that quote seems to have very little relation to reality. I can only think of a few facts that followed those stages, and they are isolated cases;



When Galileo supposedly uttered *Eppur si muove* before The Inquisition, (Latin for "And yet it moves," which opposed the biblical phrase "the Lord set the earth on its foundations; it can never be moved." from the _Book of Psalms_ and _1 Chronicles_ and perhaps a few other places) I would have to say his supporting Copernicus's heliocentric model was being violently opposed after having been openly ridiculed. I don't think I am going out on a limb suggesting that it is now regarded as self-evident.

Copernicus himself did not publish his book* De revolutionibus orbium coelestium* until he was on his deathbed, and he even dedicated the book to Pope Paul III in an attempt to basically kiss the Catholic Church's butt. I would have to say from the words of his dedication, Copernicus was, at the very least, fearing rejection: "I can easily conceive, most Holy Father, that as soon as some people learn that in this book which I have written concerning the revolutions of the heavenly bodies, I ascribe certain motions to the Earth, they will cry out at once that I and my theory should be rejected." The fact that he waited until he was nearly dead strongly suggests he was concerned about being "violently opposed."

Jonathan Swift has a great quote on the subject as well: "When a true genius appears in this world, you may know him by this sign, that the dunces are all in confederacy against him."

Darwin's Theory of Evolution was widely criticized at the time, and still stirs controversy today. Even when he wrote to one of his close friends about his theory prior to publication, Darwin said putting such a "foolish" work in print was like "confessing [to] a murder." William Herschel had the best name for it I have heard, calling it "The law of higgledy-piggelty." Darwin's former Geology instructor, Adam Sedgwick, wrote a letter Darwin saying: "I have read your book with more pain than pleasure… you have deserted the true inductive path."

Of course there are more modern examples as well. 

After Kitty Hawk, The Wrights flew their "contraption" in fields adjoining very busy railroad lines in Dayton, Ohio for months on end. American businessmen and bankers refused to come to the demonstrations. The magazine _Scientific American_ published stories about "The Lying Brothers." The local Dayton newspapers never dispatched a single reporter to "investigate." The Wrights grew sick of the snubbings, and eventually moved to Europe where they became very successful.

It was someone named Chandrasekhar that first published the idea of what he called a "dark star" and later would be called a "Black Hole." Sir Arthur Eddington, a respectable scientist who had verified one of Einstein's predictions regarding the curvature of spacetime during a solar eclipse in 1919, was so openly critical of Chandrasekhar's papers that the idea of a Black Hole was nearly snuffed out altogether. Because Eddington was held in such high regard, even scientists who supported Chandrasekhar privately did not do so publicly.

Binning, Roher, & Ruska invented an atomic-scale resolution microscope in 1982. Demonstrations of their Scanning-Tunneling Microscope were being ridiculed through 1985, the year before they were awarded the Nobel Prize. Their instrument was ultra-sensitive, and many times they had to wait until very late at night to showcase it, since vibrations from daytime activity in the city would affect it adversely.

The problem with our own comprehension is that it is easy to conceive of "small changes," but hard to grasp really large ones. What comes to mind when you picture the automobile of 1903? A makeshift jalopy with very little horsepower that would backfire often and break down often? If so, you're pretty well on the mark. Now imagine two bicycle mechanics show up on your doorstep and tell you that they invented a "flying machine." It would be very hard to believe! Engines were heavy and weak in 1903. How could one be light enough and powerful enough to fly? Einstein suffered from the same lack of credentials prior to publication of what we now call Relativity. He was, after all, a patent clerk working in Switzerland when he basically supplanted Isaac Newton's most hallowed work. Imagine a "nobody" knocking on the door of a Physics Department chairperson and saying, "Newton is wrong," and offering nothing but "thought experiments" on paper, with no experimental data backing up his claims.



qqwref said:


> It can't take *more* moves to solve to any orientation than to solve to a particular orientation, because any solution to a particular orientation is already a solution to any orientation. And it's easy to exhibit positions where solving to a particular orientation can take many more moves than solving to any orientation (e.g. y x U).



Hmmm... interesting way to state it! Thank you.



rokicki said:


> Concrete example of a syllable?
> 
> U u is one. U u' is another.
> 
> ...



Yes, this is what I was referring to, and I was just working this out independently when I saw the new posts. 



rokicki said:


> This number is independent of your metric. But depending on your
> metric, the actual move sequence to attain each of these syllables
> differs, and in some metrics it is easier than others to figure out
> the "shortest" or "best" move sequence.



...and this is as far as I got before I was stuck!



rokicki said:


> For instance, one syllable is just U u2 d3. This is equivalently
> Uw u d3. You pick one, and make the others illegal.



Which is what I thought my new linear move generator had accomplished when I generated these moves:

http://lightningcloudcomputing.com/depth_03.txt

...but somehow someway moves were left off of the list! My mechanism for demarcating a unique cube position must be wrong.



rokicki said:


> I've got a Perl script that generates a state machine based on
> the next selected move that gives the legal subsequent moves
> (as a bitmask). The table turns out to be pretty small in all
> three of the metrics we have been working with.



I've done it for up to 5 moves, but it is clearly faulty. And not in PERL, but C. I'd be interested in seeing your script.


----------



## Lucas Garron (May 23, 2014)

unsolved said:


> I don't think I am going out on a limb suggesting that it is now regarded as self-evident.



When you look up at the sky, I don't think there's anything "self-evident" about orbiting the sun.
It may only require "basic" mechanics, but smart thinkers starting with the Greeks drew an incorrect conclusion because it is *not* self-evident. We just have better measurements, theories, and masses of data now, and it is evidently the best theory in that context.

The people trying to help you in this thread are not oligarchs who are trying to prevent you from doing usurping them. They want to help move the field of cube solvers forward, and they're patiently trying to share what they know from working at the front of this area themselves.

Until you come with a revolutionary idea that you demonstrate to work in some way, nothing about your ideas are evident (never mind the "self-"). Please try them, but don't question the merits of existing knowledge unless you have a substantial reason. Talking about paradigm shifts in astronomy just makes you *look* like a crank.

I'm sorry if I sound mean, but it saddens me to see so many posts wasted on silly stuff when we should be listening to each other.
I hope the rest of this thread is filled with cool stuff about making 4x4x4 solvers better.


----------



## DeeDubb (May 23, 2014)

Lucas Garron said:


> When you look up at the sky, I don't think there's anything "self-evident" about orbiting the sun.
> It may only require "basic" mechanics, but smart thinkers starting with the Greeks drew an incorrect conclusion because it is *not* self-evident. We just have better measurements, theories, and masses of data now, and it is evidently the best theory in that context.



Yes, actually, one reason that it became not "self-evident" (aka counter intuitive) is because they did the math. They realized we would have to be spinning at around 1000MPH and revolving around the sun at 67,000 MPH which is correct, and that seems impossible. It's still hard for me to wrap my head around when I really try to think about it.


----------



## unsolved (May 23, 2014)

Lucas Garron said:


> When you look up at the sky, I don't think there's anything "self-evident" about orbiting the sun.
> It may only require "basic" mechanics, but smart thinkers starting with the Greeks drew an incorrect conclusion because it is *not* self-evident. We just have better measurements, theories, and masses of data now, and it is evidently the best theory in that context.



I agree, it is not self-evident to the individual. It was the retrograde motion of the planets that gave the hard-core nighttime skywatchers fits. The whole concept of nested, "celestial orbs" was constructed to explain it away, with more and more concentric spheres added whenever a new object in the sky did not fit the existing mold. The Shopenhaurer quote applied to "scientific truth" in general and new discoveries in particular. In this respect, of course, the quote is perfectly applicable.



Lucas Garron said:


> The people trying to help you in this thread are not oligarchs who are trying to prevent you from doing usurping them.



Such a statement can only mean there is a complete misunderstanding of my mentioning Shopenhaurer. I was not referring to me specifically or anything like that: I was referring to the remark about not liking the names.



> Most comp-sci names are unintuitive: Alpha-beta routine, hashing function, indexing function, minimal window principal variation search, sparsely-populated matrix, etc. After you hear them enough, they become second nature. Kind of reminds me of an Arthur Shopenhauer quote...



...and by this I meant, once the idea (in this case, say the name *Arbitrary Scramble Rotationless Transposition*) is chatted about and discussed and used in context a few times, it becomes second nature. Kind of like TFS = turns-from-solved. That's all I meant. Period. In case there is any doubt, I am not proud of the sad, sorry state of my program at all. By any workable definition, it is a failure. I am not trying to align myself with any great thinker, past or present.



Lucas Garron said:


> Until you come with a revolutionary idea that you demonstrate to work in some way, nothing about your ideas are evident (never mind the "self-"). Please try them, but don't question the merits of existing knowledge unless you have a substantial reason. Talking about paradigm shifts in astronomy just makes you *look* like a crank.



Again, the Shopenhaurer quote was about the resistance to use the names/acronyms. See the above. And the astronomy references were to offer a response to the *qqwref *statement:



> Incidentally, that quote seems to have very little relation to reality.



Shopenhaurer's quote does have a basis in reality, and I offered examples of its domain of applicability. That's all. It was not meant as a slight. I think I have the right here to post a simple rebuttal to a statement such as the one I answered. It was not meant to stir a debate. I thought the only reply I would get to it would be something like, "Oh, I see."




Lucas Garron said:


> I'm sorry if I sound mean, but it saddens me to see so many posts wasted on silly stuff when we should be listening to each other.
> I hope the rest of this thread is filled with cool stuff about making 4x4x4 solvers better.



I don't take offense to any of it because I can see how what I posted could have been misunderstood. And, hopefully, you see what I was trying to convey after my explanations.


----------



## rokicki (May 23, 2014)

unsolved said:


> I'd be interested in seeing your script.



I'm happy to answer any questions and explain in more detail, but I'd prefer not to share
the code. I'm a big believer in independent implementation to cross-validate results.
Also, my script makes some implicit assumptions (such as move numbering, face numbering,
axis numbering) that are not obvious and may not apply to you.

The script actually does a *search* to find the best move sequence for a given
syllable, and it selects moves based on a set of priorities (prefer quarter turns to
half turns, prefer block moves to slice moves, things like that). Each metric simply
defines the set of moves that are allowed. Said search is straightforward and I
won't insult you by suggesting how it should be implemented.

Once the search is done, and we have a move sequence for each syllable, it combines
these into a finite state machine using a standard nondeterministic finite state machine
reduction. This is a standard algorithm that you are probably familiar with. If not,
the explanations on Wikipedia are probably superior to anything I can write in this
tiny text box.


----------



## unsolved (May 23, 2014)

rokicki said:


> I'm happy to answer any questions and explain in more detail...The script actually does a *search* to find the best move sequence for a given
> syllable



Perfectly understandable.

I was hoping there were some Meta-Rules that could be applied to avoid a search, but apparently the only alternative is to work on 24 different cube orientations in tandem.

So a few questions I have are:

1. Given that there are some transposing move sequences which can:

a) create the same position on a solved cube, 

and...

b) create a different position from a randomly scrambled cube...

...does this imply that the total number of unique moves possible as a function of depth from any given position might vary?

For example, make moves A,B,C,D on a cube. Note the position. Reset it to where it was. Make moves B,A,D,C. Either it creates the same final cube, or it doesn't. Could there be MANY positions where each of these conditions is true? And, if that is the case, can we say there is no function* n(d)* where n is the node count and d is the depth from an arbitrary position?

Or, are the only divisions the solved cube state vs. all other non-solved states?

2. This goes along with question 1 somewhat. In chess, we can list every possible legal move to a certain depth, such as 1. e4 e5 2. Nf3 and 1. e4 c5 2. d4 cxd4 3. c3 dxc3 4. Nxc3, etc. Has anyone performed any auditing of the move generator output to determine if, in fact, they are all in agreement? Or has there only been node count level verification?

3. Given that there is a linear array of legal moves to some depth, d, is it possible to extrapolate the list to the next depth via introspecting the current list? For example:

All_Depth_4_Moves[move_1][move_2][move_3][move_4] contains the moves that are legal at depth 4. [move_1] is just an index, 0...35 for U,R,F...d2,l2,b2. Ditto for the other indices.
If the moves are legal, All_Depth_4_Moves[][][][] would contain 1, otherwise it contains 0.

If I want to build a 5th-ply extension to this, can do something like this:

new_move_1_at_depth_ 5 = A
new_move_2_at_depth_ 5 = B
new_move_3_at_depth_ 5 = C
new_move_4_at_depth_ 5 = D
new_move_5_at_depth_ 5 = E

if(All_Depth_4_Moves[A]*[C][D] == 1) and (All_Depth_4_Moves[C][D][E] == 1) then the 5 moves are legal?*


----------



## rokicki (May 23, 2014)

unsolved said:


> I was hoping there were some Meta-Rules that could be applied to avoid a search, but apparently the only alternative is to work on 24 different cube orientations in tandem.



Well, we're not "combining" orientations here, or even dealing with
orientations at all (except for fixing one of the slices to *prevent*
full-cube rotations). If you don't want to prevent whole-cube
rotations in this fashion, then much of this may not apply.



unsolved said:


> So a few questions I have are:
> 
> 1. Given that there are some transposing move sequences which can:
> 
> ...



The last few messages I've written have *only* concerned themselves
with pruning the search tree of redundant move sequences, and the
only reasonable way to do this is on the supercube, which is a group,
and thus worrying about the "starting position" is not relevant.

Taking the actual position into account when pruning move sequences
is probably not going to be a win (but who knows, I might be
surprised).

It's pretty easy to evaluate, though. Just perform a search to a
particular depth using your sequence pruning, and compare the count
of sequences (equivalently, leaves in your search tree) against the
number of distinct positions found. If they are very close, then further
pruning is probably not helpful. This is assuredly the case for the 3x3x3
to extremely deep plies, and is probably the case on the 4x4x4 to the
depths we can reasonably search to.

Essentially, you define a set of canonical sequences (those generated
by your pruned tree search), and compare the count of canonical
sequences of a given length, with the count of distinct positions at a
particular distance from some particular position (typically the solved
position).



unsolved said:


> 2. This goes along with question 1 somewhat. In chess, we can list every possible legal move to a certain depth, such as 1. e4 e5 2. Nf3 and 1. e4 c5 2. d4 cxd4 3. c3 dxc3 4. Nxc3, etc. Has anyone performed any auditing of the move generator output to determine if, in fact, they are all in agreement? Or has there only been node count level verification?



In general, when writing tree pruning, you *always* compare distinct
position counts both with and without the tree pruning enabled, as
deeply as you can, to ensure you're not pruning excessively. I would
assume this is being done even by you as you add whatever pruning
you are considering.



unsolved said:


> is it possible to extrapolate the list to the next depth . . .



Absolutely; this is exactly the information
codified by the finite state machine. You can easily turn it into a matrix
that will give you the count of canonical sequences of any length.

I have two matrices:

legal_move[state][move] -> boolean

In reality, this is a single-dimension array with bitmasks.

next_state[state][move] -> state

Initial state is "0". Each move gives you a bitmask of legal
next moves; picking a legal move, you can combine it with
the current state through the next_state array to get the
subsequent state.


----------



## unsolved (May 23, 2014)

rokicki said:


> In general, when writing tree pruning, you *always* compare distinct
> position counts both with and without the tree pruning enabled, as
> deeply as you can, to ensure you're not pruning excessively. I would
> assume this is being done even by you as you add whatever pruning
> you are considering.



The method I used was rather primitive and took advantage of the 128 GB of RAM I had access to at the time. Basically, I generated the full-width 36^nth array for depths 1 through 6. I stored every "turn" made by the 36^nth move generator, one at a time, and computed a unique index for the entire cube using a large number library. The same number used to count all of the possible arrangements on the 4x4x4 cube was my formula. If the move just made by the move generator created an index not in the list, it was a "legal move" and it was stored similar to yours, using "1" to indicate legal, and "0" to indicate not legal. But, instead of 2 dimensions, it had "n" dimensions where n was the depth.

So Legal_Moves[R][F][r2][b2][u'] would contain a 1 or 0, and I defined U to be a constant == 0, R == 1, F == 2, etc.

I thought because it took at least 4 moves to do a rotation of the cube in place, such as U D' u d', that I would need at least 4 dimensions to my matrix, whereas you had managed with just 2. 

In the end, I only kept the 5-turn matrix, since the 6-turn could be generated from the 5-turn.



rokicki said:


> Absolutely; this is exactly the information
> codified by the finite state machine. You can easily turn it into a matrix
> that will give you the count of canonical sequences of any length.
> 
> ...



My thinking is this:

1. Generate all 24 solved states.
2. Store all of them in a master 1-D array with a depth of 0.
3. One by one, make one turn on each of them, generate the master 4x4x4 index, check the RAM buffer for the same index, and add it to the buffer if it is still unique.
4. Repeat the process for 2 turns, 3 turns, .... 6 turns.

In the end, I should not see moves such as D d if the move U u preceeded it, since one is a rotated version of the other.
And, once I have an "acceptable" master list through 6 plies, I can save the list to disk, and generate subsequent depths in RAM using the 6-to-7 technique,
then 7-to-8, 8-to-9, etc.

And, by the way, I found a very simple pruning idea that is 100% fully tested and known to work for plies 1, 2, and 3. With a simple statement I can tell if you are
1 move from solved, 2 moves from solved, etc., so I can do the same type of pruning as the corner prune.


----------



## Montschok (Jun 16, 2014)

There are a lot of posts in this thread (and the others) so this may already have been mentioned, but at least I haven't seen it anywhere...

One way of reducing the size of the database is to rotate the cube to a specific orientation before storing it.

The easiest way of doing this is probably to pick a specific corner piece (for example white/red/blue) and then rotate the cube until it's in a specific location (for example down/front/left).

That way you always only store each state once.

Edit : Since the database size grows exponentially, I would also recommend solving it from both the unsolved state and the target state at the same time, meeting in the middle.


----------



## unsolved (Oct 20, 2014)

Montschok said:


> There are a lot of posts in this thread (and the others) so this may already have been mentioned, but at least I haven't seen it anywhere...
> 
> One way of reducing the size of the database is to rotate the cube to a specific orientation before storing it.



Yes but there is a problem with that approach. The moves U u create a position that is identical to D' d', except the cube is rotated 90 degrees. All of the relative positions of the cubes are the same. So the question is, how do you create a move generator that "knows" D' d' is the same as U u? Well one way would be to create a database of all 24 rotated states, and flagging those that are duplicates, and pruning them from the move generator so that the game tree does not grow too fast. Then you can convert the move generator output into a run-length-encoded algorithm so that the move generator is super fast. The only problem is, you need 192 GB of RAM for this approach to be highly effective (and it is, I have an experimental version I have been working on). I managed to compress each cube position down to 28 bytes each so I have about 7,362,000,000 positions possible in my database RAM buffer.

You only need to do this once, then the move generator will produce only unique moves from the perspective of all 24 possible rotated states.

This has the added benefit of helping the brute force solver find moves that lead to solutions outside of its default orientation, something Bruce and I went on and on about for a while, mostly due to my own thick head. Take the case where you have UFr and UBr edges needing to be swapped. Holding the cube with the front facing you, apply:

l' f2 b2 U2 l U2 l' U2 r U2 r' F2 l B2 r and you have solved the cube, but it is upside down from your starting orientation. You need to be able to see this is a "distance solved = 0" condition in order to be able to announce the solution without having to check all 24 orientations every time you query the solve state. I solved this problem with 24 different "solved distance = 0" positions at the start, and letting the move generator move 1 move from each of them, labeling them "solved in 1" etc.

It was cumbersome, but it actually sped things up at the tremendous expense of RAM.

I am on the hunt for a more efficient representation of a cube position. Once I do that, the approach makes sense to release to the general public.


----------



## unsolved (Oct 20, 2014)

By the way, it would be great if we could "import" cube positions to analyze. I would like to propose a cube import/export protocol, if there is not one already.

*U*nrolled *C*ube *N*otation:

U face = 0, F = 1, R = 2, D = 3, B = 4, L = 5.

So the starting cube position would be

000000000000000011111111111111112222222222222222333333333333333344444444444444445555555555555555

The perspective of U would be F facing front and R on the right.
F is facing front with U as top R on the right and L on the left
R is facing front with U as top B on the right and F on the left
B is facing front with U as top L on the right and R on the left
L is facing front with U as top F on the right and B on the left
D is facing front with F as top R on the right and L on the left

This way we can "output" some positions, then just important them directly into our own solvers.


----------



## Lucas Garron (Oct 20, 2014)

unsolved said:


> By the way, it would be great if we could "import" cube positions to analyze. I would like to propose a cube import/export protocol, if there is not one already.
> 
> *U*nrolled *C*ube *N*otation:
> 
> ...



Suggestions:

- Just use letters for sticker colors instead of numbers.
- Use some ordering of the faces that someone else has used before.


----------



## qqwref (Oct 20, 2014)

How about this, unfold the cube as follows:

```
U
LFRB
 D
```
and then output the stickers by just reading line by line, top to bottom and left to right. For each sticker give the appropriate letter (case doesn't matter). So for a 2x2x2 the solved state is UUUULLFFRRBBLLFFRRBBDDDD.

Or, if you prefer, read faces top-to-bottom-left-to-right, and inside each face read the stickers in that way (still going by the above unfolding). So for a 2x2x2 the solved state would be UUUULLLLFFFFRRRRBBBBDDDD.


----------



## unsolved (Oct 20, 2014)

Lucas Garron said:


> Suggestions:
> 
> - Just use letters for sticker colors instead of numbers.
> - Use some ordering of the faces that someone else has used before.



That's why I am opening it up for discussion. 

So you'd rather see UUUUUUUUUUUUUUUUFFFFFFFFFFFFFFFFRRRRRRRRRRRRRRR... etc?

That makes sense, I like that idea.

I just picked Top, Front, Right to start since that is how almost everyone holds the cube. Then I just picked the opposing faces, Bottom, Back, Left.

It doesn't matter what we choose, as long as there is universal agreement in the end. Then we can test some output and the solving algos to make sure we have it all correct.


----------



## cuBerBruce (Oct 22, 2014)

qqwref said:


> How about this, unfold the cube as follows:
> 
> ```
> U
> ...



This is something my 4x4x4 solvers already support, with some minor differences.

In my solvers, delimiters (such as a '/') are required to separate the facelets for each face. (This also allows distinguishing a move sequence from a facelet string.) I also allow up to 9 facelets in succession of the same color to be specified by a number preceding the letter. Letters can be upper or lower case.

For example, the solved cube can be represented as:
8U8U/8L8L/8F8F/8R8R/8B8B/8D8D

I also allow WOGRBY instead of ULFRBD if you prefer to use color-based letters, as Lucas suggested. Standard color scheme is assumed. (That is, I don't allow using B for the face opposite W, for example.)

EDIT: I realize now that qqwref suggested doing either doing a whole layer at a time for the side faces, or doing each face separately. I use the latter approach.


----------



## unsolved (Oct 22, 2014)

cuBerBruce said:


> For example, the solved cube can be represented as:
> 8U8U/8L8L/8F8F/8R8R/8B8B/8D8D



I like this idea too. It kind of reminds me of FEN in chess for chess problem composers.

http://en.wikipedia.org/wiki/Forsyth%E2%80%93Edwards_Notation

But isn't /r a problem? That is the hard carriage return in the old C language.

Restricting it to 9 means you can have a parser that only needs to worry about reading one byte at a time.

It is always top, left, front, right, back, bottom?

My objective is to be able to feed a text file with 1 position/line to the program, have it analyze every optimal solution, output the results, and move to the next one. This way we can time how long it takes to find solutions, perhaps finding ways to optimize the code if certain positions seem to be rather difficult solves.

Do you have a 5x5x5 solver also?

If so I'd like to see an optimal solution for:

8UUR4UR4UR2UF2U/8L8L/2FU8F8F6F/R3U8R8R5R/8B8B/8D8D


----------



## cuBerBruce (Oct 22, 2014)

unsolved said:


> But isn't /r a problem? That is the hard carriage return in the old C language.



No. C/C++ source code uses '\r' (not '/r') to represent the ASCII carriage return character. When encountering a backslash character followed by an 'r' in an input stream, it will interpret the two characters as separate characters.



unsolved said:


> It is always top, left, front, right, back, bottom?


My facelet string parser always expects the faces enumerated in that particular order, so yes if I'm interpreting your question correctly.

I note that I really consider there to be 24 solved states, corresponding to orienting the solved cube 24 different ways.

So 8D8D/8F8F/8L8L/8B8B/8R8R/8U8U would also represent a solved state, for example.



unsolved said:


> Do you have a 5x5x5 solver also?


No.



unsolved said:


> If so I'd like to see an optimal solution for:
> 
> 8UUR4UR4UR2UF2U/8L8L/2FU8F8F6F/R3U8R8R5R/8B8B/8D8D



Just noting you should have 8L8L9L (or similar) in place of 8L8L, and likewise for the other solid-color faces.


----------



## unsolved (Nov 11, 2014)

Thanks Bruce. In another note, I thought I found a bug in your brute force solver.







The scramble:

http://alg.cubing.net/?puzzle=5x5x5&type=alg&view=playback&alg=R2_U2_L2_D2_R2_U2_L2_D2_R2_U2_L2_D2_r2_u2_l2_d2_r2_u2_l2_d2_r2_u2_l2_%0Ad2_

...then I realized I entered a 5x5x5 scramble into your 4x4x4 program


----------



## StachuK1992 (Nov 26, 2014)

Can we open-source this yet? Is there any reason we're holding back on this?


----------



## unsolved (Nov 26, 2014)

StachuK1992 said:


> Can we open-source this yet? Is there any reason we're holding back on this?



I posted much of the source code. I don't have a problem with it, but it's still not worthy of cranking on solves in full-width mode. For example, here is how I do the move U (I call it T+)


```
BITBOARD_4x4x4_CUBE T_PLUS(BITBOARD_4x4x4_CUBE original_4x4x4_cube)
{
		BITBOARD_4x4x4_CUBE new_cube;

		/**************************************************************************/
		/* Rotating the top will change something on every face except the bottom */
		/**************************************************************************/
		new_cube._4x4x4_bottom = original_4x4x4_cube._4x4x4_bottom;

		/******************************************************************************************/
		/* Entire row of cubes moves from right -----> front -----> left -----> back -----> right */
		/* new front = old right; new right = old back; new back = old left; new left = old front */ 
		/******************************************************************************************/
		new_cube._4x4x4_front = (original_4x4x4_cube._4x4x4_front & BITMASK_CUBE_FACE_NOT_ROW_01) | (original_4x4x4_cube._4x4x4_right & BITMASK_CUBE_FACE_ROW_01);
		new_cube._4x4x4_right = (original_4x4x4_cube._4x4x4_right & BITMASK_CUBE_FACE_NOT_ROW_01) | (original_4x4x4_cube._4x4x4_back  & BITMASK_CUBE_FACE_ROW_01);
		new_cube._4x4x4_back  = (original_4x4x4_cube._4x4x4_back  & BITMASK_CUBE_FACE_NOT_ROW_01) | (original_4x4x4_cube._4x4x4_left  & BITMASK_CUBE_FACE_ROW_01);
		new_cube._4x4x4_left  = (original_4x4x4_cube._4x4x4_left  & BITMASK_CUBE_FACE_NOT_ROW_01) | (original_4x4x4_cube._4x4x4_front & BITMASK_CUBE_FACE_ROW_01);

		/*********************************************************************************/
		/*                                 Rotate the TOP                                */
		/*********************************************************************************/
		/*                                                                               */
		/* THESE CUBE LOCATIONS BECOME....              THESE CUBE LOCATIONS             */
		/*                                                                               */
		/*                                                                               */
		/*********************************/             /*********************************/
		/*  01   *  02   *  03   *   04  */             /*  13   *  09   *  05   *   01  */
		/*********************************/             /*********************************/
		/*  05   *  06   *  07   *   08  */             /*  14   *  10   *  06   *   02  */
		/*********************************/             /*********************************/
		/*  09   *  10   *  11   *   12  */             /*  15   *  11   *  07   *   03  */
		/*********************************/             /*********************************/
		/*  13   *  14   *  15   *   16  */             /*  16   *  12   *  08   *   04  */
		/*********************************/             /*********************************/
		/*                                                                               */
		/*                                                                               */
		/*********************************************************************************/

		new_cube._4x4x4_top = ((original_4x4x4_cube._4x4x4_top & BITMASK_CUBE_FACE_SQUARE_13) << 48)  | \
							  ((original_4x4x4_cube._4x4x4_top & BITMASK_CUBE_FACE_SQUARE_09) << 28)  | \
							  ((original_4x4x4_cube._4x4x4_top & BITMASK_CUBE_FACE_SQUARE_05) << 8)   | \
							  ((original_4x4x4_cube._4x4x4_top & BITMASK_CUBE_FACE_SQUARE_01) >> 12)  | \
							  ((original_4x4x4_cube._4x4x4_top & BITMASK_CUBE_FACE_SQUARE_14) << 36)  | \
							  ((original_4x4x4_cube._4x4x4_top & BITMASK_CUBE_FACE_SQUARE_10) << 16)  | \
							  ((original_4x4x4_cube._4x4x4_top & BITMASK_CUBE_FACE_SQUARE_06) >> 4)   | \
							  ((original_4x4x4_cube._4x4x4_top & BITMASK_CUBE_FACE_SQUARE_02) >> 24)  | \
							  ((original_4x4x4_cube._4x4x4_top & BITMASK_CUBE_FACE_SQUARE_15) << 24)  | \
							  ((original_4x4x4_cube._4x4x4_top & BITMASK_CUBE_FACE_SQUARE_11) << 4)   | \
							  ((original_4x4x4_cube._4x4x4_top & BITMASK_CUBE_FACE_SQUARE_07) >> 16)  | \
							  ((original_4x4x4_cube._4x4x4_top & BITMASK_CUBE_FACE_SQUARE_03) >> 36)  | \
							  ((original_4x4x4_cube._4x4x4_top & BITMASK_CUBE_FACE_SQUARE_16) << 12)  | \
							  ((original_4x4x4_cube._4x4x4_top & BITMASK_CUBE_FACE_SQUARE_12) >> 8)   | \
							  ((original_4x4x4_cube._4x4x4_top & BITMASK_CUBE_FACE_SQUARE_08) >> 28)  | \
							  ((original_4x4x4_cube._4x4x4_top & BITMASK_CUBE_FACE_SQUARE_04) >> 48);

		return new_cube;
}
```

...and some of the supporting data types...


```
#define BITBOARD_TOP_SOLVED    0x2222222222222222
#define BITBOARD_RIGHT_SOLVED  0x3333333333333333
#define BITBOARD_FRONT_SOLVED  0x5555555555555555
#define BITBOARD_LEFT_SOLVED   0x7777777777777777
#define BITBOARD_BOTTOM_SOLVED 0xBBBBBBBBBBBBBBBB
#define BITBOARD_BACK_SOLVED   0xDDDDDDDDDDDDDDDD

#define BITMASK_CUBE_FACE_SQUARE_01 0xF000000000000000
#define BITMASK_CUBE_FACE_SQUARE_02 0x0F00000000000000
#define BITMASK_CUBE_FACE_SQUARE_03 0x00F0000000000000
#define BITMASK_CUBE_FACE_SQUARE_04 0x000F000000000000

#define BITMASK_CUBE_FACE_SQUARE_05 0x0000F00000000000
#define BITMASK_CUBE_FACE_SQUARE_06 0x00000F0000000000
#define BITMASK_CUBE_FACE_SQUARE_07 0x000000F000000000
#define BITMASK_CUBE_FACE_SQUARE_08 0x0000000F00000000

#define BITMASK_CUBE_FACE_SQUARE_09 0x00000000F0000000
#define BITMASK_CUBE_FACE_SQUARE_10 0x000000000F000000
#define BITMASK_CUBE_FACE_SQUARE_11 0x0000000000F00000
#define BITMASK_CUBE_FACE_SQUARE_12 0x00000000000F0000

#define BITMASK_CUBE_FACE_SQUARE_13 0x000000000000F000
#define BITMASK_CUBE_FACE_SQUARE_14 0x0000000000000F00
#define BITMASK_CUBE_FACE_SQUARE_15 0x00000000000000F0
#define BITMASK_CUBE_FACE_SQUARE_16 0x000000000000000F

#define BITMASK_CUBE_FACE_ROW_01 0xFFFF000000000000
#define BITMASK_CUBE_FACE_ROW_02 0x0000FFFF00000000
#define BITMASK_CUBE_FACE_ROW_03 0x00000000FFFF0000
#define BITMASK_CUBE_FACE_ROW_04 0x000000000000FFFF

#define BITMASK_CUBE_FACE_NOT_ROW_01 0x0000FFFFFFFFFFFF
#define BITMASK_CUBE_FACE_NOT_ROW_02 0xFFFF0000FFFFFFFF
#define BITMASK_CUBE_FACE_NOT_ROW_03 0xFFFFFFFF0000FFFF
#define BITMASK_CUBE_FACE_NOT_ROW_04 0xFFFFFFFFFFFF0000

#define BITMASK_CUBE_FACE_COL_01     0xF000F000F000F000
#define BITMASK_CUBE_FACE_NOT_COL_01 0x0FFF0FFF0FFF0FFF

#define BITMASK_CUBE_FACE_COL_02     0x0F000F000F000F00
#define BITMASK_CUBE_FACE_NOT_COL_02 0xF0FFF0FFF0FFF0FF

#define BITMASK_CUBE_FACE_COL_03     0x00F000F000F000F0
#define BITMASK_CUBE_FACE_NOT_COL_03 0xFF0FFF0FFF0FFF0F

#define BITMASK_CUBE_FACE_COL_04     0x000F000F000F000F
#define BITMASK_CUBE_FACE_NOT_COL_04 0xFFF0FFF0FFF0FFF0

/*****************************************/
/* Structs and their associated pointers */
/*****************************************/

typedef struct bitboard_4x4x4_cube
{
	unsigned long long _4x4x4_top;
	unsigned long long _4x4x4_right;
	unsigned long long _4x4x4_front;
	unsigned long long _4x4x4_left;
	unsigned long long _4x4x4_bottom;
	unsigned long long _4x4x4_back;
}
BITBOARD_4x4x4_CUBE, *BITBOARD_4x4x4_CUBE_PTR;

typedef BITBOARD_4x4x4_CUBE (*cube_move_ptr)(BITBOARD_4x4x4_CUBE);
cube_move_ptr cube_move_array[36];
```


----------



## StachuK1992 (Nov 26, 2014)

Posting bits of code in a forum thread isn't the same as hosting the code on a code-sharing system, where one can see the code in full, create issues, and discuss the code in a better-suited format.

Git's most common these days, but I'd live with SVN or something if you had a need to be different 

"Not done" is what alpha versions of code are for!


----------



## unsolved (Nov 26, 2014)

StachuK1992 said:


> Posting bits of code in a forum thread isn't the same as hosting the code on a code-sharing system, where one can see the code in full, create issues, and discuss the code in a better-suited format.
> 
> Git's most common these days, but I'd live with SVN or something if you had a need to be different
> 
> "Not done" is what alpha versions of code are for!



If you want a pretty kick-ass version with the (sometimes faulty) 6-turns-from-solve database loaded into a huge 12 GB RAM buffer, here is the link:






http://lightningcloudcomputing.com/OO_4x4x4.zip

It chops 6-plies of search off of the tree if it hits a database position, saving about 2 years of search time on deep searches.


----------



## cuBerBruce (Nov 27, 2014)

StachuK1992 said:


> Can we open-source this yet? Is there any reason we're holding back on this?



I assumed this was referring to my solver.

Anyway, I started doing some of the clean-up of the code (mainly removing some unused definitions and code from my 5-step solver or other obsolete/unused pieces of code). So I think it's close to a state where I might be willing to share it - maybe this weekend.

My other concern is other people "taking it over," creating bugs, and generally adding all sorts of stuff that I'm not interested in maintaining. I think I would prefer to maintain my own version privately, while others can take what I've done and update it for their own purposes.


----------



## unsolved (Nov 27, 2014)

*Cube Rotation Notation*

I added a new feature to the parser this morning: cube rotation.

I noticed that some of the solutions to solves shown on the alg website list rotations executed by the solvers. I'm not exactly sure which is which, but maybe someone can correct me if I am wrong.

Presently I use the following notation:

X+ = rotate the x-axis clockwise. This is TOP ---> RIGHT in my current implementation.
X- = rotate the x-axis counterclockwise. This is TOP ---> LEFT in my current implementation.
X2 = rotate the x-axis twice. This is TOP ---> BOTTOM in my current implementation.

Y+ = rotate the y-axis clockwise. This is FRONT ---> TOP in my current implementation.
Y- = rotate the y-axis counterclockwise. This is FRONT ---> BOTTOM in my current implementation.
Y2 = rotate the y-axis twice. This is FRONT ---> BACK in my current implementation.

Z+ = rotate the z-axis clockwise. This is RIGHT ---> FRONT in my current implementation.
Z- = rotate the z-axis counterclockwise. This is RIGHT ---> BACK in my current implementation.
Z2 = rotate the z-axis twice. This is RIGHT ---> LEFT in my current implementation.

Once such a move is parsed, the entire cube takes on the new position for all subsequent turns, until the next rotation change is encountered in the stream.
I can change the notation for the WCA notation folks out there when the time comes for a release.

This brings to mind another question: which rotations represent the set of all non-duplicating rotations?

I started with this set:

X+
X-
X2
Y+
Y-
Y2
Z+
Z-
Z2

For the 2-rotation combinations, I performed the rotation pair and checked the status of all existing prior rotations. If there was a duplicate, I exclude it from the unique set that follows. Of course, the order in which you pair the rotations will effect which ones stay and which ones remain. This is what I came up with:

X+Y+
X-Y+
X2Y+

X+Y-
X-Y-
X2Y-

X+Y2
X-Y2

X2Z+

X+Z+
X-Z+

X2Z-

X+Z-
X-Z-

So I have 14 legal 2-paired rotations, 9 legal 1-move rotation, and if you add the unmoved starting cube, this accounts for all 24 possible cube states. If someone would like to double-check me on this, I would appreciate it. I will use these rotated states to solve the TFS databases in a separate project now, so getting it correct from the start is very critical. Such an undertaking should finally put the rest the last remaining undesired feature in the old OO_4x4x4 program: finding the true distance from the solved state for any frame of reference. This should do wonders for the program.






Translating the scramble and solve:

scramble = U F [Y+][X2] r2 d2 R2 U2 [X+][Y2] U'
solve = U R2 U2 l2 f2 L' D'


----------



## cuBerBruce (Nov 27, 2014)

unsolved said:


> I added a new feature to the parser this morning: cube rotation.
> 
> I noticed that some of the solutions to solves shown on the alg website list rotations executed by the solvers. I'm not exactly sure which is which, but maybe someone can correct me if I am wrong.
> 
> ...



Well, once again you went ahead and developed your own convention instead of taking a minute to see what the speedcubing community already uses. The following table gives the correlation between the speedcubing community's notation and yours.


```
Speedcubing    unsolved's
convention     convention

    x              Y+       turns same direction as R
    x'             Y-
    x2             Y2
    y              Z+       turns same direction as U
    y'             Z-
    y2             Z2
    z              X+       turns same direction as F
    z'             X-
    z2             X2
```

I might suggest you reconsider relabeling your axes to match the speedcubing communmity. This will make it much less confusing to the entire community.

Your two-rotation combinations appear to work to provide unique states.

Your example scrambles/solves, however, don't seem to work for me.


----------



## unsolved (Nov 28, 2014)

Scramble = U F *x z2* r2 b2 *y'* R2 U2 *z x2* U'
Solution = U R2 U2 d2 f2 L' D' (and others) as shown.

The latest version, 2.0.1, but still without any TFS databases, is here:

http://lightningcloudcomputing.com/OO_4x4x4_bitboard.zip

Improvements since yesterday:

1. This is a great deal faster. I noticed my compiler was set to use the lowest levels of optimizations in prior versions. I selected "optimize for speed" when compiling the latest version. 
2. I also hand crafted some assembly code into areas where the profiler said there were some bottlenecks.
3. I added two pruning heuristics, nothing major, but it reduces the 36^n search tree significantly. 
4. Standard notation for moves and rotations is now supported.








cuBerBruce said:


> Well, once again you went ahead and developed your own convention instead of taking a minute to see what the speedcubing community already uses.



Well it was about 3 O'clock in the morning when I started coding and I knew it would be easy enough to change if it wasn't as the WCA used. It took all of 45 seconds to adjust the code. I was just too curious about which of the pairs of rotations were not duplicates. I used your post above to alter the code and I am pretty sure it is working now. Search time dropped from 1:41 to under a second also, very big speed improvement.


----------



## qqwref (Nov 29, 2014)

unsolved said:


> 3. I added two pruning heuristics, nothing major, but it reduces the 36^n search tree significantly.


Could you do a timing with and without this pruning stuff? From my work with ksolve I know that pruning can make a HUGE difference in time. If your search time dropped 100x it's quite possible that a lot of that was due to pruning.


----------



## unsolved (Dec 4, 2014)

There is a new, greatly improved version of OO_4x4x4 available:







You can download version 2.0.3 from here:

http://lightningcloudcomputing.com/OO_4x4x4_203.zip

New for this version:

1. The 3-Turns-From-Solved Databases, featuring up to 3-moves from all 24 rotated states, is included, debugged, and appears to be working fine. Total size is about 35 MB.
2. The TFS-databases are no longer computed in RAM every time you start the program. This version reads the databases from 3 small files included in the download. Keep them in the same directory as the program if you want to use them.
3. Up to 6 different pruning mechanisms are in place to reduce the size of the game tree. The TFS databases are used as both leaf-node pruners AND to prune the trunk. Previously OO_4x4x4 would only use these databases for pruning the trunk.
4. You can specify rotated states at any time, as often as you like, embedded within the scramble.
5. The move generator speed is reduced to around 15,000,000 nodes/second on my machine (down from 35 million) as a result of probing the databases in RAM during the search. But... ply 11 can be reached in this version without a struggle.
*6. As you can see from the screen shot enclosed, sometimes a TFS database entry merely reversed the last move made by the move generator.* This is due to where the code is executed for the db lookup. I am working on removing this anomaly.


----------



## qqwref (Dec 4, 2014)

That's kind of odd, how come it found the 10 move solution at depth 10, but not the 8+2 move solution at depth 8?

Oh, and how big is the turns-from-solved database compared to the old version, for a given size of moves? 35 MB sounds like a lot for just 3 TFS. Is it still practical for you to have 6 TFS on your own computer? If you are storing the same position for all 24 solved orientations, have you thought about ways to remove that problem, e.g. by 'normalizing' the color scheme (so doing a given 2 moves from solved gives the same database entry no matter what orientation the puzzle was in)? It may slow down computation of which database entry a position would correspond to, but I'm sure with some bit-twiddling cleverness you can make it pretty quick. I can't find the post, but I think I remember you storing every face as 16 4-bit sequences; would it be useful to store them as 0010, 0011, 0100, 0101, 1000, and 1001 (with the xxx0 and xxx1 being opposite)?


----------



## unsolved (Dec 4, 2014)

qqwref said:


> That's kind of odd, how come it found the 10 move solution at depth 10, but not the 8+2 move solution at depth 8?



Because it pruned a candidate leaf node before passing it recursively on to (depth == 0) where the TFS databases "look ahead" beyond the current depth. It is very frustrating, but if I figure this out, the "depth" of the databases will functionally double. Here is what is going on:


```
void search_forever(BITBOARD_4x4x4_CUBE which_cube, unsigned short which_depth, signed short last_move_axis, signed short last_move_group, signed short move_just_made, unsigned short unchanging_depth)
{

	if(move_just_made >= 0) GLOBAL_CUBE_SOLUTION[unchanging_depth - which_depth - 1] = move_just_made + 1;

	if(which_depth == 0)
	{
		g_total_nodes++;

                // if this is the "time to update" you get the full principal variation shown because all moves at the present depth have been generated
		if(time_to_update()) {BUILD_PV_STRING SHOW_PV_STRING g_last_update = clock();}

		if(bitboard_4x4x4_cube_is_solved_from_any_orientation(which_cube))
		{
			show_this_solution(unchanging_depth);
		}
		else
		{
				tfs_result = tfs_1_database_lookup(which_cube);
				if(tfs_result >= 0)
				{
					show_this_solution_from_TFS_1_at_which_depth(unchanging_depth, tfs_result);
				}
				else
				{
						tfs_result = tfs_2_database_lookup(which_cube);
						if(tfs_result >= 0)
						{
							show_this_solution_from_TFS_2_at_which_depth(unchanging_depth, tfs_result);
						}
						else
						{
								tfs_result = tfs_3_database_lookup(which_cube);
								if(tfs_result >= 0)
								{
									show_this_solution_from_TFS_3_at_which_depth(unchanging_depth, tfs_result);
								}
						}
				}
		}
	}
	else
	{
                // if this is the "time to update" you will see ?? since the entire principal variation cant be drawn
		if(time_to_update()) {BUILD_PV_STRING SHOW_PV_STRING g_last_update = clock();}

		if(---PRUNING CONDITIONS---)
		{
					return;
		}
		  
                //The Jakube Move Generator Move Ordering...
		for(axis_of_rotation = 0; axis_of_rotation < 3; axis_of_rotation++)
		{
			for(move_group = 0; move_group < 4; move_group++)
			{
				if((axis_of_rotation != last_move_axis) || ((axis_of_rotation == last_move_axis) && (move_group > last_move_group)))
				{
					for(move_index = 0; move_index < 3; move_index++)
					{
						which_move_to_make = GLOBAL_AXIS_ROTATION[axis_of_rotation][move_group][move_index];
						modified_cube = cube_move_array[which_move_to_make](which_cube);
						search_forever(modified_cube, which_depth-1, axis_of_rotation, move_group, which_move_to_make, unchanging_depth);
					}
				}
			}
		}
	}
}
```

So basically if pruning occurs down towards the bottom, it means a database query (like 3 moves left in the search tree, but the 3-turns database showed a miss, so that means no matter what 3 turns are left, the cube is not solved) rejects a node. Somehow, my depth count is off by 1, or, worse, a scramble entry can be optimized, so an 8-move scramble can be solved in 7 or less, so I am pruning GOOD SOLUTIONS from another rotated state before they have a chance to be tested when depth == 0. I think all I need to do is add 1 to my pruning depth condition, or maybe 2 for safety, and I should be able to prune 3 plies worth during move generation, and still see 3 moves "into the future" when depth ==0! If I am correct, this means *the 4-TFS could be used as a functional 8-TFS database*, the 5-TFS could be used as a 10-TFS database, etc. 



qqwref said:


> Oh, and how big is the turns-from-solved database compared to the old version, for a given size of moves? 35 MB sounds like a lot for just 3 TFS.



It is a lot, indeed. Just computing the counts for a given depth was a huge undertaking. I had to verify there were no duplicate positions in any one of 24 different cube orientations before I could add a single node to the count. I did it the hard way, with a 36^n move generator, and storing EVERY POSITION that passed the test of being unique, then adding that to the scan list for the next run of tests. Here are the position counts per depth:


```
#define TOTAL_POSITIONS_TFS_DEPTH_00 24
#define TOTAL_POSITIONS_TFS_DEPTH_01 864
#define TOTAL_POSITIONS_TFS_DEPTH_02 23976
#define TOTAL_POSITIONS_TFS_DEPTH_03 652464
#define TOTAL_POSITIONS_TFS_DEPTH_04 17917200
#define TOTAL_POSITIONS_TFS_DEPTH_05 490105728
#define TOTAL_POSITIONS_TFS_DEPTH_06 13406521248
#define TOTAL_POSITIONS_TFS_DEPTH_07 366726051072
```

Every position in the database is 48 bytes plus 1 byte per move in the solution plus 1 byte for the turncount (I might merge the data into one huge database some day) plus one byte for the rotation index. So 51 bytes per position in the 1-TFS, 52 bytes per 2-TFS position, 53 for 3-TFS, 54 for 4-TFS etc. Multiply this by the corresponding number above, and you the number of bytes of RAM you need.

The old code took too many shortcuts. Case in point: I did not store the positions, I stored a 64-bit hash number, only 8 bytes, per position. When I had "hash collisions" you saw weird moves in the "[inside TFS] --->" output. It worked in 99.999% of the cases, but when it failed, it was pretty bad. I also did not store rotated states, so it would only find positions that would arise from the original solving orientation. A vast majority of the solutions are of such a nature, but still, not the way to do it. So the old 6-TFS was something like 12 GB. The new scheme would be 699 GB  Slight difference.



qqwref said:


> Is it still practical for you to have 6 TFS on your own computer?



When 699 GB becomes commonplace, yes. You laugh, but in 1989, when I was working as a Mac software developer, we had 5 MB of RAM on our systems, and we laughed at the thought of ever having 1 GB of RAM someday.



qqwref said:


> If you are storing the same position for all 24 solved orientations, have you thought about ways to remove that problem, e.g. by 'normalizing' the color scheme (so doing a given 2 moves from solved gives the same database entry no matter what orientation the puzzle was in)? It may slow down computation of which database entry a position would correspond to, but I'm sure with some bit-twiddling cleverness you can make it pretty quick. I can't find the post, but I think I remember you storing every face as 16 4-bit sequences; would it be useful to store them as 0010, 0011, 0100, 0101, 1000, and 1001 (with the xxx0 and xxx1 being opposite)?



I only store the positions that are unique. For example, I solve all moves at depth 1 for an unrotated cube. Next, I do rotation #1 of 23. I start generating moves. I query the database as it is being built. If the same position already exists, even though coming from a different rotated state, I do not enter the position into the TFS database. Only unique positions are in there, so the databases have 0 wasted space. That is why it took so long for me to build them this time around. Lots of computation before allowing them in.

*EDIT: Looks like Version 2.0.4 is finally handling the pruning properly.*






http://lightningcloudcomputing.com/OO_4x4x4_204.zip


----------

