Announcing: New 4x4x4 Brute Force Solver

Status
Not open for further replies.
qqwref said:
I'm not completely sure what you're talking about, as the example you posted doesn't quite do what I mean. You have solutions beginning with both F2 f2 and b2 B2, whereas I'm suggesting that since those positions are the same (up to a rotation) you only allow one of the two sequences.
Click to expand...

Well I decided to shelve the forward pruning stuff for a while and see if I could come up with a way to do the TFS in RAM only, like I did before.

Good News: I cranked out up to TFS-05 from all 24 cube orientations in only 4:26 (and that's minutes and seconds).

The Bad News: You need slightly more than 14 GB of RAM to have near collision-free hashtable performance.

TFS_05.jpg


The numbers need a little explaining. The Nodes are cumulative, the other numbers are the per-ply totals. Remember, there is 24 times as much of everything, and I used a 36^n move generator. I only tested the position after it was generated. So if the program made U u' U U it quereied the hashtable for uniqueness, obviously seeing that was a duplicate of U' u', so it was not added. It did count as a duplicate for depth 4.

The node count @ depth 1 = 888 - 24 = 864. And that = 864 unique + 0 duplicates. 864/24 = 36.
The node count @ depth 2 = 31992 - 888 = 31104. And that = 23976 unique + 7128 duplicates. 31104/24 = 1296 = 36 * 36. Notice you don't calculate 31992 - 888 - 24 because the 24 is already accumulated in the 888.

So the numbers all add up to their 36^n proper counts.

Also the unique counts divided by 24 match some other published node counts.

23976/24 = 999.
652464/24 = 27186.
17714304/24 = 738096.

EDIT

And now it looks like TFS-05 with all of the forward pruning stripped away is behaving as expected. It found all of the solutions, and I double-checked with Bruce's program.

11_ply_agreement.jpg
 
Last edited:
Related to what qqwref was saying, Dan Hoey used the term syllable to refer to different possible combinations of moves among parallel layers that have distinct effects. For the 4x4x4, assuming you consider that the resulting orientation of the cube doesn't matter, there are 63 possible syllables for each axis. Below (in the spoiler), I will list a possible way to generate the 63 syllables for one axis. Converting to a different axis should be straightforward. This is for the single-slice turn metric.

1-move cases (12 total): U U' U2 u u' u2 D D' D2 d d' d2

2-move cases (45 total):
if first move is U, U' or U2:
then second move can be one of: u u' u2 D D' D2 d d' d2

if first move is u:
then second move can be one of: D D2 d d2

if first move is u':
then second move can be one of: D' D2 d' d2

if first move is u2:
then second move can be one of: D D' d d'

if first move is D:
then second move can be one of: d' d2

if first move is D':
then second move can be one of: d d2

if first move is D2:
then second move can be one of: d d'

if first move is d, d', or d2:
then no second move is allowed for this axis.

3-move cases (6 total):
if first 2 moves are U u':
then third move must be: D2

if first 2 moves are U u2:
then third move must be: D

if first 2 moves are U' u:
then third move must be: D2

if first 2 moves are U' u2:
then third move must be: D'

if first 2 moves are U2 u:
then third move must be: D

if first 2 moves are U2 u':
then third move must be: D'

A third move is not used for any other first 2 moves.
 
cuBerBruce said:
Related to what qqwref was saying, Dan Hoey used the term syllable to refer to different possible combinations of moves among parallel layers that have distinct effects. For the 4x4x4, assuming you consider that the resulting orientation of the cube doesn't matter, there are 63 possible syllables for each axis. Below (in the spoiler), I will list a possible way to generate the 63 syllables for one axis. Converting to a different axis should be straightforward. This is for the single-slice turn metric.
Click to expand...

Thanks Bruce. Good information. So is your move generator rule-based? Is all that is needed is a history check backwards for 3 plies, with a table-lookup for the legality of the next move series?

I have been cleaning up code, and placing #define statements strategically throughout, so all I have to do is specify the largest TFS-database the user wants, and it will build automatically and all the code handles the proper distance info returned by the search. It's a little more difficult than it sounds.

Running some more tests now... I may release TFS-4 early, was planning on December 13th.

Memory requirements for TFS-4 looks like 560 MB minimum for acceptable hashtable lookup speeds.
For TFS-5 it's still large, 14 GB :)

RLFBx3_in_progress.jpg


EDIT: Holy cow! This thing is cranking out tons of solutions! This is what my older versions were trying to suppress.

Code: 
Omnia Obtorquebantur 4x4x4 Version 2.1.1, December 13, 2014. Copyright 2014 by Ed Trice.

                          TOP
                          ---------------------
                          |####|####|####|####|
                          ---------------------
                          |####|####|####|####|
                          ---------------------
                          |####|####|####|####|
                          ---------------------
                          |####|####|####|####|
                          ---------------------

  LEFT                    FRONT                   RIGHT                   BACK
  ---------------------   ---------------------   ---------------------   ---------------------
  |XXXX|XXXX|XXXX|&&&&|   |OOOO|^^^^|^^^^|^^^^|   |&&&&|&&&&|&&&&|XXXX|   |^^^^|OOOO|OOOO|OOOO|
  ---------------------   ---------------------   ---------------------   ---------------------
  |XXXX|&&&&|&&&&|XXXX|   |^^^^|OOOO|OOOO|^^^^|   |&&&&|XXXX|XXXX|&&&&|   |OOOO|^^^^|^^^^|OOOO|
  ---------------------   ---------------------   ---------------------   ---------------------
  |XXXX|&&&&|&&&&|XXXX|   |^^^^|OOOO|OOOO|^^^^|   |&&&&|XXXX|XXXX|&&&&|   |OOOO|^^^^|^^^^|OOOO|
  ---------------------   ---------------------   ---------------------   ---------------------
  |&&&&|XXXX|XXXX|XXXX|   |^^^^|^^^^|^^^^|OOOO|   |XXXX|&&&&|&&&&|&&&&|   |OOOO|OOOO|OOOO|^^^^|
  ---------------------   ---------------------   ---------------------   ---------------------

                          BOTTOM
                          ---------------------
                          |~~~~|~~~~|~~~~|~~~~|
                          ---------------------
                          |~~~~|~~~~|~~~~|~~~~|
                          ---------------------
                          |~~~~|~~~~|~~~~|~~~~|
                          ---------------------
                          |~~~~|~~~~|~~~~|~~~~|
                          ---------------------


 
  Solutions To Scramble = R L F B R L F B R L F B 
 
  Solution [0001] =  R  L  U2 F2 U2 B2 R   [inside 05-TFS] --->  L  F2 D2 B2 D2  @ 000000788411812 nodes [time = 03:41]
  Solution [0002] =  R  L  U2 F2 U2 B2 L   [inside 05-TFS] --->  R  F2 D2 B2 D2  @ 000000788411822 nodes [time = 03:41]
  Solution [0003] =  R  L  U2 B2 U2 F2 R   [inside 05-TFS] --->  L  B2 D2 F2 D2  @ 000000788610523 nodes [time = 03:41]
  Solution [0004] =  R  L  U2 B2 U2 F2 L   [inside 05-TFS] --->  R  B2 D2 F2 D2  @ 000000788610533 nodes [time = 03:41]
  Solution [0005] =  R  L  D2 F2 D2 B2 R   [inside 05-TFS] --->  L  F2 U2 B2 U2  @ 000000793821505 nodes [time = 03:42]
  Solution [0006] =  R  L  D2 F2 D2 B2 L   [inside 05-TFS] --->  R  F2 U2 B2 U2  @ 000000793821515 nodes [time = 03:42]
  Solution [0007] =  R  L  D2 B2 D2 F2 R   [inside 05-TFS] --->  L  B2 U2 F2 U2  @ 000000794020216 nodes [time = 03:42]
  Solution [0008] =  R  L  D2 B2 D2 F2 L   [inside 05-TFS] --->  R  B2 U2 F2 U2  @ 000000794020226 nodes [time = 03:42]
  Solution [0009] =  R  L  F  B  R  L  F   [inside 05-TFS] --->  B  L  R  B  F   @ 000000794714977 nodes [time = 03:43]
  Solution [0010] =  R  L  F  B  R  L  B   [inside 05-TFS] --->  F  L  R  B  F   @ 000000794714987 nodes [time = 03:43]
  Solution [0011] =  R2 U2 L2 F  B  R2 D2  [inside 05-TFS] --->  L2 D2 B  F  U2  @ 000002024251152 nodes [time = 09:28]
  Solution [0012] =  R2 D2 L2 F  B  R2 U2  [inside 05-TFS] --->  L2 U2 B  F  D2  @ 000002181587811 nodes [time = 10:12]
  Solution [0013] =  R2 F2 U  D  F2 L2 F2  [inside 05-TFS] --->  L2 D  U  L2 B2  @ 000002238681087 nodes [time = 10:28]
  Solution [0014] =  R2 B2 U  D  B2 L2 B2  [inside 05-TFS] --->  L2 D  U  L2 F2  @ 000002396024838 nodes [time = 11:11]
  Solution [0015] =  L2 U2 R2 F  B  L2 D2  [inside 05-TFS] --->  R2 D2 B  F  U2  @ 000006291376107 nodes [time = 29:25]
  Solution [0016] =  L2 D2 R2 F  B  L2 U2  [inside 05-TFS] --->  R2 U2 B  F  D2  @ 000006448712766 nodes [time = 30:10]
  Solution [0017] =  L2 F2 U  D  F2 R2 F2  [inside 05-TFS] --->  R2 D  U  R2 B2  @ 000006511208418 nodes [time = 30:27]
  Solution [0018] =  L2 B  R2 f2 U' B2 L   [inside 05-TFS] --->  L2 F  r2 b2 u'  @ 000006647371016 nodes [time = 31:05]
  Solution [0019] =  L2 B2 U  D  B2 R2 B2  [inside 05-TFS] --->  R2 D  U  R2 F2  @ 000006668552169 nodes [time = 31:10]
  Solution [0020] =  U  R' L' D2 F  B  U2  [inside 05-TFS] --->  B' F' L  R  U   @ 000006700358190 nodes [time = 31:19]
  Solution [0021] =  U  R' L' F  B  U2 F'  [inside 05-TFS] --->  B' D2 L  R  U   @ 000006700392026 nodes [time = 31:19]
  Solution [0022] =  U  R' L' F  B  U2 B'  [inside 05-TFS] --->  F' D2 L  R  U   @ 000006700392034 nodes [time = 31:19]
  Solution [0023] =  U  R2 U' D  L2 D2 R2  [inside 05-TFS] --->  F2 D2 B2 L2 D   @ 000006723489291 nodes [time = 31:26]
  Solution [0024] =  U  R2 U' D  L2 D2 L2  [inside 05-TFS] --->  B2 U2 F2 R2 D   @ 000006723489300 nodes [time = 31:26]
  Solution [0025] =  U  R2 u  d' B2 D2 F2  [inside 05-TFS] --->  L2 D2 R2 B2 D   @ 000006724813077 nodes [time = 31:26]
  Solution [0026] =  U  R2 u  d' B2 D2 B2  [inside 05-TFS] --->  R2 U2 L2 F2 D   @ 000006724813086 nodes [time = 31:26]
  Solution [0027] =  U  R2 u  B2 D2 B2 d'  [inside 05-TFS] --->  R2 U2 L2 F2 D   @ 000006725183602 nodes [time = 31:26]
  Solution [0028] =  U  R2 d' B2 D2 B2 u   [inside 05-TFS] --->  R2 U2 L2 F2 D   @ 000006727106053 nodes [time = 31:27]
  Solution [0029] =  U  R2 F  R2 L2 F2 R2  [inside 05-TFS] --->  L2 F' R2 D2 U   @ 000006729983043 nodes [time = 31:27]
  Solution [0030] =  U  R2 F  R2 L2 F2 r2  [inside 05-TFS] --->  l2 B' R2 D  U2  @ 000006729983046 nodes [time = 31:27]
  Solution [0031] =  U  R2 F  R2 L2 F2 l2  [inside 05-TFS] --->  r2 B' R2 D  U2  @ 000006729983049 nodes [time = 31:27]
  Solution [0032] =  U  R2 F  R2 L2 F2 L2  [inside 05-TFS] --->  R2 F' R2 D2 U   @ 000006729983052 nodes [time = 31:27]
  Solution [0033] =  U  R2 F  r2 l2 B2 R2  [inside 05-TFS] --->  L2 B' R2 D  U2  @ 000006730051875 nodes [time = 31:27]
  Solution [0034] =  U  R2 F  r2 l2 B2 r2  [inside 05-TFS] --->  l2 F' R2 D2 U   @ 000006730051878 nodes [time = 31:27]
  Solution [0035] =  U  R2 F  r2 l2 B2 l2  [inside 05-TFS] --->  r2 F' R2 D2 U   @ 000006730051881 nodes [time = 31:27]
  Solution [0036] =  U  R2 F  r2 l2 B2 L2  [inside 05-TFS] --->  R2 B' R2 D  U2  @ 000006730051884 nodes [time = 31:27]
  Solution [0037] =  U  R2 F' R2 L2 F2 R2  [inside 05-TFS] --->  L2 F  R2 D2 U   @ 000006730715769 nodes [time = 31:28]
  Solution [0038] =  U  R2 F' R2 L2 F2 r2  [inside 05-TFS] --->  l2 B  R2 D  U2  @ 000006730715772 nodes [time = 31:28]
  Solution [0039] =  U  R2 F' R2 L2 F2 l2  [inside 05-TFS] --->  r2 B  R2 D  U2  @ 000006730715775 nodes [time = 31:28]
  Solution [0040] =  U  R2 F' R2 L2 F2 L2  [inside 05-TFS] --->  R2 F  R2 D2 U   @ 000006730715778 nodes [time = 31:28]
  Solution [0041] =  U  R2 F' r2 l2 B2 R2  [inside 05-TFS] --->  L2 B  R2 D  U2  @ 000006730784601 nodes [time = 31:28]
  Solution [0042] =  U  R2 F' r2 l2 B2 r2  [inside 05-TFS] --->  l2 F  R2 D2 U   @ 000006730784604 nodes [time = 31:28]
  Solution [0043] =  U  R2 F' r2 l2 B2 l2  [inside 05-TFS] --->  r2 F  R2 D2 U   @ 000006730784607 nodes [time = 31:28]
  Solution [0044] =  U  R2 F' r2 l2 B2 L2  [inside 05-TFS] --->  R2 B  R2 D  U2  @ 000006730784610 nodes [time = 31:28]
  Solution [0045] =  U  R2 B' U2 D2 F2 U2  [inside 05-TFS] --->  D2 B  R2 D2 U   @ 000006736242222 nodes [time = 31:29]
  Solution [0046] =  U  R2 B' U2 D2 F2 u2  [inside 05-TFS] --->  d2 F  L2 D2 U   @ 000006736242225 nodes [time = 31:29]
  Solution [0047] =  U  R2 B' U2 D2 F2 d2  [inside 05-TFS] --->  u2 F  L2 D2 U   @ 000006736242228 nodes [time = 31:29]
  Solution [0048] =  U  R2 B' U2 D2 F2 D2  [inside 05-TFS] --->  U2 B  R2 D2 U   @ 000006736242231 nodes [time = 31:29]
  Solution [0049] =  U  R2 B' u2 d2 B2 U2  [inside 05-TFS] --->  D2 F  L2 D2 U   @ 000006736311054 nodes [time = 31:29]
  Solution [0050] =  U  R2 B' u2 d2 B2 u2  [inside 05-TFS] --->  d2 B  R2 D2 U   @ 000006736311057 nodes [time = 31:29]

...

  Solution [0497] =  U2 D' F2 L' f2 b2 R2  [inside 05-TFS] --->  b2 f2 L  F2 D'  @ 000008163942852 nodes [time = 38:09]
  Solution [0498] =  U2 D' F2 L  F2 B2 L2  [inside 05-TFS] --->  B2 F2 L' F2 D'  @ 000008163959649 nodes [time = 38:09]
  Solution [0499] =  U2 D' F2 L  f2 b2 R2  [inside 05-TFS] --->  b2 f2 L' F2 D'  @ 000008163962076 nodes [time = 38:09]
  Solution [0500] =  U2 D' B2 R  F2 B2 R2  [inside 05-TFS] --->  B2 F2 R' B2 D'  @ 000008169329616 nodes [time = 38:11]
  Solution [0501] =  U2 D' B2 R  f2 b2 L2  [inside 05-TFS] --->  b2 f2 R' B2 D'  @ 000008169332061 nodes [time = 38:11]
  Solution [0502] =  U2 D' B2 R' F2 B2 R2  [inside 05-TFS] --->  B2 F2 R  B2 D'  @ 000008169355671 nodes [time = 38:11]
  Solution [0503] =  U2 D' B2 R' f2 b2 L2  [inside 05-TFS] --->  b2 f2 R  B2 D'  @ 000008169358116 nodes [time = 38:11]
  Solution [0504] =  U2 D' B2 L' U2 D2 R2  [inside 05-TFS] --->  D2 U2 L  B2 D'  @ 000008169525456 nodes [time = 38:11]
  Solution [0505] =  U2 D' B2 L' u2 d2 L2  [inside 05-TFS] --->  d2 u2 L  B2 D'  @ 000008169527901 nodes [time = 38:11]
  Solution [0506] =  U2 D' B2 L  U2 D2 R2  [inside 05-TFS] --->  D2 U2 L' B2 D'  @ 000008169544680 nodes [time = 38:11]
  Solution [0507] =  U2 D' B2 L  u2 d2 L2  [inside 05-TFS] --->  d2 u2 L' B2 D'  @ 000008169547125 nodes [time = 38:11]
  Solution [0508] =  U2 D  R2 F  U2 D2 B2  [inside 05-TFS] --->  D2 U2 F' R2 D   @ 000008171790939 nodes [time = 38:11]
  Solution [0509] =  U2 D  R2 F  u2 d2 F2  [inside 05-TFS] --->  d2 u2 F' R2 D   @ 000008171793369 nodes [time = 38:11]
  Solution [0510] =  U2 D  R2 F' U2 D2 B2  [inside 05-TFS] --->  D2 U2 F  R2 D   @ 000008171816994 nodes [time = 38:11]
  Solution [0511] =  U2 D  R2 F' u2 d2 F2  [inside 05-TFS] --->  d2 u2 F  R2 D   @ 000008171819424 nodes [time = 38:11]
  Solution [0512] =  U2 D  R2 B' R2 L2 B2  [inside 05-TFS] --->  L2 R2 B  R2 D   @ 000008171993610 nodes [time = 38:11]
  Solution [0513] =  U2 D  R2 B' r2 l2 F2  [inside 05-TFS] --->  l2 r2 B  R2 D   @ 000008171996040 nodes [time = 38:11]
  Solution [0514] =  U2 D  R2 B  R2 L2 B2  [inside 05-TFS] --->  L2 R2 B' R2 D   @ 000008172012834 nodes [time = 38:11]
  Solution [0515] =  U2 D  R2 B  r2 l2 F2  [inside 05-TFS] --->  l2 r2 B' R2 D   @ 000008172015264 nodes [time = 38:11]
  Solution [0516] =  U2 D  L2 F  R2 L2 F2  [inside 05-TFS] --->  L2 R2 F' L2 D   @ 000008177183838 nodes [time = 38:13]
  Solution [0517] =  U2 D  L2 F  r2 l2 B2  [inside 05-TFS] --->  l2 r2 F' L2 D   @ 000008177186286 nodes [time = 38:13]
  Solution [0518] =  U2 D  L2 F' R2 L2 F2  [inside 05-TFS] --->  L2 R2 F  L2 D   @ 000008177209893 nodes [time = 38:13]
  Solution [0519] =  U2 D  L2 F' r2 l2 B2  [inside 05-TFS] --->  l2 r2 F  L2 D   @ 000008177212341 nodes [time = 38:13]
  Solution [0520] =  U2 D  L2 B' U2 D2 F2  [inside 05-TFS] --->  D2 U2 B  L2 D   @ 000008177406417 nodes [time = 38:13]
  Solution [0521] =  U2 D  L2 B' u2 d2 B2  [inside 05-TFS] --->  d2 u2 B  L2 D   @ 000008177408865 nodes [time = 38:13]
  Solution [0522] =  U2 D  L2 B  U2 D2 F2  [inside 05-TFS] --->  D2 U2 B' L2 D   @ 000008177425641 nodes [time = 38:13]
  Solution [0523] =  U2 D  L2 B  u2 d2 B2  [inside 05-TFS] --->  d2 u2 B' L2 D   @ 000008177428089 nodes [time = 38:13]
  Solution [0524] =  U2 D  F2 R  U2 D2 L2  [inside 05-TFS] --->  D2 U2 R' F2 D   @ 000008178926757 nodes [time = 38:13]
  Solution [0525] =  U2 D  F2 R  u2 d2 R2  [inside 05-TFS] --->  d2 u2 R' F2 D   @ 000008178929184 nodes [time = 38:13]
  Solution [0526] =  U2 D  F2 R' U2 D2 L2  [inside 05-TFS] --->  D2 U2 R  F2 D   @ 000008178952812 nodes [time = 38:13]
  Solution [0527] =  U2 D  F2 R' u2 d2 R2  [inside 05-TFS] --->  d2 u2 R  F2 D   @ 000008178955239 nodes [time = 38:13]
  Solution [0528] =  U2 D  F2 L' F2 B2 L2  [inside 05-TFS] --->  B2 F2 L  F2 D   @ 000008179142505 nodes [time = 38:13]
  Solution [0529] =  U2 D  F2 L' f2 b2 R2  [inside 05-TFS] --->  b2 f2 L  F2 D   @ 000008179144932 nodes [time = 38:13]
  Solution [0530] =  U2 D  F2 L  F2 B2 L2  [inside 05-TFS] --->  B2 F2 L' F2 D   @ 000008179161729 nodes [time = 38:13]
  Solution [0531] =  U2 D  F2 L  f2 b2 R2  [inside 05-TFS] --->  b2 f2 L' F2 D   @ 000008179164156 nodes [time = 38:13]
  Solution [0532] =  U2 D  B2 R  F2 B2 R2  [inside 05-TFS] --->  B2 F2 R' B2 D   @ 000008184531696 nodes [time = 38:15]
  Solution [0533] =  U2 D  B2 R  f2 b2 L2  [inside 05-TFS] --->  b2 f2 R' B2 D   @ 000008184534141 nodes [time = 38:15]
  Solution [0534] =  U2 D  B2 R' F2 B2 R2  [inside 05-TFS] --->  B2 F2 R  B2 D   @ 000008184557751 nodes [time = 38:15]
  Solution [0535] =  U2 D  B2 R' f2 b2 L2  [inside 05-TFS] --->  b2 f2 R  B2 D   @ 000008184560196 nodes [time = 38:15]
  Solution [0536] =  U2 D  B2 L' U2 D2 R2  [inside 05-TFS] --->  D2 U2 L  B2 D   @ 000008184727536 nodes [time = 38:15]
  Solution [0537] =  U2 D  B2 L' u2 d2 L2  [inside 05-TFS] --->  d2 u2 L  B2 D   @ 000008184729981 nodes [time = 38:15]
  Solution [0538] =  U2 D  B2 L  U2 D2 R2  [inside 05-TFS] --->  D2 U2 L' B2 D   @ 000008184746760 nodes [time = 38:15]
  Solution [0539] =  U2 D  B2 L  u2 d2 L2  [inside 05-TFS] --->  d2 u2 L' B2 D   @ 000008184749205 nodes [time = 38:15]
  Solution [0540] =  U2 F' B' D2 R2 D2 L2  [inside 05-TFS] --->  B' F' R2 U2 L2  @ 000008240367066 nodes [time = 38:30]
  Solution [0541] =  U2 F' B' D2 L2 D2 R2  [inside 05-TFS] --->  B' F' L2 U2 R2  @ 000008240373888 nodes [time = 38:30]
  Solution [0542] =  U2 F2 U2 B2 R' L' F2  [inside 05-TFS] --->  D2 B2 D2 L' R'  @ 000008251246158 nodes [time = 38:33]
  Solution [0543] =  U2 B2 U2 F2 R' L' B2  [inside 05-TFS] --->  D2 F2 D2 L' R'  @ 000008408383872 nodes [time = 39:16]
 
Last edited:
unsolved said:
Thanks Bruce. Good information. So is your move generator rule-based? Is all that is needed is a history check backwards for 3 plies, with a table-lookup for the legality of the next move series?
Click to expand...

Basically, my code currently uses a state machine to look up a bitmap value that indicates which layers can be turned. I am working on updating my single-slice turn version to use the 63-syllables per axis method I described. So basically the current state machine state is used along with the current move to look up the next state of the state machine following the current move. So I don't actually have to look at what the previous moves actually were.
 
cuBerBruce said:
Basically, my code currently uses a state machine to look up a bitmap value that indicates which layers can be turned.
Click to expand...

Is that how you were able to determine that on the non-supercube some moves are duplicates whereas on a supercube they are not? Can you program produce a short list of some of those 3-turn transpositions?

cuBerBruce said:
I am working on updating my single-slice turn version to use the 63-syllables per axis method I described. So basically the current state machine state is used along with the current move to look up the next state of the state machine following the current move. So I don't actually have to look at what the previous moves actually were.
Click to expand...

Are you talking about a predictive index function? I was thinking about using a reverse indexing function to do something similar, but I could not get it to work. Feed in any index (1, 2, 3, 35, 36 37, .... 947 .... 2376518, whatever) and from the index telescopes out a move list. It treats each index as the sum of up to three enumerations from the perpendicular axes, and you work backwards to determine how many predecessor positions there must have been on each axis, which in turn can tell you the coefficients that must go before the expansion equation, and from these you can determine the smallest coefficients (0...35 or 1...36 depending on your preference) and these translate into moves.

It sounds like moving forward from the syllable set is the way to do it. I will experiment with it.

In other news, I am releasing version 2.11 for both 3- and 4-Turns From Solved today. Both programs are in the same folder. Launch whichever one you have RAM for.

TFS-03 = 152 MB required for 10,000,019 hash table entries.
TFS-04 = 561 MB required for 36,721,073 hash table entries.

The hash tables are so large for performance reasons. They are nearly collision-free for very fast lookup. Beats the pants off of Binary Search, averaging 1.002 probes per lookup for TFS-03 and about 1.094 probes per lookup for TFS-04. Practically indexing function speeds!

lightningcloudcomputing.com/OO_4x4x4_211.zip

There is a big difference in performance between the 3- and 4-TFS databases. A picture is worth 1,000 words here.

TFS-03

Here is a 12-ply position, all slice moves, which has a 10-ply solution:

12_ply_improved_to_10_TFS_03.jpg


It finds the first solution after 6 minutes, and completes ply 10 @ 47 minutes on a 3.1 GHz computer. Note: Almost certainly your times will be even faster than this.

Compare that result to...

TFS-04

12_ply_improved_to_10_TFS_04.jpg


Ply 10 finishes in less than 2.5 minutes!

EDIT: Afterthought. Should I be concerned that neither of these solution sets features the move b' at the start?
 
Last edited:
Here is something worthy of its own post and raises an interesting question. Can two solvers both have different solution counts for the same position, and both of them be correct?

rlfb_differences.jpg


I only checked a few of these solutions out, and I am going down the list, but the thought occurred to me, maybe the count is a function of the move generator used. There might not be a "universal count" of solutions unless you use a 36^n move generator and report every permutation.
 
unsolved said:
EDIT: Afterthought. Should I be concerned that neither of these solution sets features the move b' at the start?
Click to expand...

The scramble is not optimal (12 moves instead of 10). Therefore, there is no particular reason to assume optimal solutions should start with the same moves as the inverse of the scramble. I also note that the last 2 moves of the scramble commute, so if the scramble were optimal, you would expect solutions starting f' b' or b' f'.

unsolved said:
Here is something worthy of its own post and raises an interesting question. Can two solvers both have different solution counts for the same position, and both of them be correct?
Click to expand...

I see what's happening. You are producing solutions that are the same except for two moves being u' d' and d' u'. Since these commute, my program only shows one of the two solutions. In your program, these moves are appear across the boundary between the search tree and the TFS database generated moves. I'm not sure if it's worth trying to remove such "redundancies" from your solver.
 
cuBerBruce said:
The scramble is not optimal (12 moves instead of 10). Therefore, there is no particular reason to assume optimal solutions should start with the same moves as the inverse of the scramble. I also note that the last 2 moves of the scramble commute, so if the scramble were optimal, you would expect solutions starting f' b' or b' f'.



I see what's happening. You are producing solutions that are the same except for two moves being u' d' and d' u'. Since these commute, my program only shows one of the two solutions. In your program, these moves are appear across the boundary between the search tree and the TFS database generated moves. I'm not sure if it's worth trying to remove such "redundancies" from your solver.
Click to expand...

I just spent a great deal of time tearing out all such code from the solver, see some of the earlier posts. :)

So now we have your solver, and 3 of my solvers (each differing only by the databases loaded) and they all report different solution counts after exhaustively searching the same exact scramble.
This 4x4x4 puzzle is much more subtle than it appears to be on the surface!

I would like to make 2 requests,for the next version of your solver.

1. Use 64-bit data types for your counters. You are overflowing the "node count" and "state check" variables on some of my longer solving runs with your program.
2. Perhaps number your solutions instead of repeating the depth at which you find each one. After the first find, the depth is known, but in the case of a scramble with many solutions, it might be nice to see them and identify them by solution # if we ever run into the need for it in the future.
 
Last edited:
Are you trying all possible ways to solve the last 5-or-so moves of the solution? If you want to print all solutions, that would certainly be worthwhile. Once you've found a position in the TFS database you're already at a solution, and very few of the positions will be solutions, so it doesn't hurt the overall computing time to spend a little extra time checking all possible ways through the TFS database. For instance, r u r' d and d r u r' give the same position, so you could have two solutions that end in these 4 moves, but your program would currently only print one.

I assume you have an ordering of moves on each axis - for instance, U before u before D before d. I suggest that any series of moves on the same axis that does not follow this order should be invalid - even if one move comes before the TFS lookup and one doesn't. So in your above image with 20 solutions where Bruce's program only gives 16:
- Solution 13, f b R2 L2 u' continues with d' l' r' d u
- Solution 14, f b R2 L2 d' is in the 5-TFS, but the d' means you can't continue with another move on the same axis. The 5-TFS solution is u' l' r' d u so you must throw it out. This is not a new solution at all!
Using this method you would throw out solutions 2, 4, 14, and 16 as being valid, but equivalent to other solutions that should already have been found.
 
qqwref said:
Are you trying all possible ways to solve the last 5-or-so moves of the solution?
Click to expand...

By "trying" do you mean verifying the moves listed in the 05-TFS will solve the cube if applied to it? Yes and no. I did so much up-front verification during the build process, and after testing over 5 billion random probes with no mismatches, I turned off that code with a #define statement. It slowed things down. However, I see I have a misfire with a false-positive: a cube position created a hash code that was in the hash table but not the same cube. It took over 190 billion probes to find one mismatch. Considering there are 64-bits of randomness (a 20-digit number beginning with 18...) I am surprised that it happened so soon. So it looks like I will be forced to perform the additional verification procedure after all (Deja Vu).

qqwref said:
If you want to print all solutions, that would certainly be worthwhile.
Click to expand...

I am thinking about refactoring in my old solve_termination options: Halt on first solution, Halt on completion of ply of first solution (its present mode), Search forever (even after finding solutions, to see if other crazy moves still solve it).

qqwref said:
So in your above image with 20 solutions where Bruce's program only gives 16:

- Solution 13, f b R2 L2 u' continues with d' l' r' d u
- Solution 14, f b R2 L2 d' is in the 5-TFS, but the d' means you can't continue with another move on the same axis. The 5-TFS solution is u' l' r' d u so you must throw it out. This is not a new solution at all!
Using this method you would throw out solutions 2, 4, 14, and 16 as being valid, but equivalent to other solutions that should already have been found.
Click to expand...

Well...

Solution [0014] = f b R2 L2 d' [inside 05-TFS] ---> u' l' r' d u @ 000000018804997 nodes [time = 00:05]

...certainly does solve the cube!

And, if you remember from just a little while ago, we talked about removing all of the code I added to do the very same thing you are now suggesting!

Obtaining all possible solutions should do just that... so I am rethinking some of this now.

===================================


I don't know why I didn't think of this sooner. I used a full-width move generator (36^n, no move ordering intelligence) to solve the TFS-05 from every possible orientation (all 24; 1 starting cube + 23 possible rotated states). Independent of what crazy moves create a cube position, if it is not in the hash table of visited/solved positions, it will add it, along with the solution. This is effectively the same as coming up with the ideal move generation sequence, at the price of having to visit every possible position, even the absurd ones.

So I hooked up the full-width generator to the scramble solver now, instead of using the move-order-by-3-axes technique suggested by Jackube. It now finds 80 solutions.

rlfb_full_width_80_solutions.jpg


Code: 
Omnia Obtorquebantur 4x4x4 Version 2.1.1, December 13, 2014. Copyright 2014 by Ed Trice.

                          TOP
                          ---------------------
                          |####|OOOO|^^^^|####|
                          ---------------------
                          |&&&&|####|####|&&&&|
                          ---------------------
                          |XXXX|####|####|XXXX|
                          ---------------------
                          |####|OOOO|^^^^|####|
                          ---------------------

  LEFT                    FRONT                   RIGHT                   BACK
  ---------------------   ---------------------   ---------------------   ---------------------
  |&&&&|~~~~|####|&&&&|   |OOOO|~~~~|####|OOOO|   |XXXX|~~~~|####|XXXX|   |^^^^|~~~~|####|^^^^|
  ---------------------   ---------------------   ---------------------   ---------------------
  |&&&&|XXXX|XXXX|&&&&|   |OOOO|^^^^|^^^^|OOOO|   |XXXX|&&&&|&&&&|XXXX|   |^^^^|OOOO|OOOO|^^^^|
  ---------------------   ---------------------   ---------------------   ---------------------
  |&&&&|XXXX|XXXX|&&&&|   |OOOO|^^^^|^^^^|OOOO|   |XXXX|&&&&|&&&&|XXXX|   |^^^^|OOOO|OOOO|^^^^|
  ---------------------   ---------------------   ---------------------   ---------------------
  |&&&&|~~~~|####|&&&&|   |OOOO|~~~~|####|OOOO|   |XXXX|~~~~|####|XXXX|   |^^^^|~~~~|####|^^^^|
  ---------------------   ---------------------   ---------------------   ---------------------

                          BOTTOM
                          ---------------------
                          |~~~~|^^^^|OOOO|~~~~|
                          ---------------------
                          |&&&&|~~~~|~~~~|&&&&|
                          ---------------------
                          |XXXX|~~~~|~~~~|XXXX|
                          ---------------------
                          |~~~~|^^^^|OOOO|~~~~|
                          ---------------------


 
  Solutions To Scramble = r l f b r l f b r l f b 
 
  Solution [0001] =  r  l  F2 B2 u'  [inside 05-TFS] --->  d' b' f' d  u   @ 000000007081361 nodes [time = 00:02]
  Solution [0002] =  r  l  F2 B2 d'  [inside 05-TFS] --->  u' b' f' d  u   @ 000000007081364 nodes [time = 00:02]
  Solution [0003] =  r  l  f2 b2 u'  [inside 05-TFS] --->  d' b' f' d  u   @ 000000007085141 nodes [time = 00:02]
  Solution [0004] =  r  l  f2 b2 d'  [inside 05-TFS] --->  u' b' f' d  u   @ 000000007085144 nodes [time = 00:02]
  Solution [0005] =  r  l  b2 f2 u'  [inside 05-TFS] --->  d' b' f' d  u   @ 000000007088921 nodes [time = 00:02]
  Solution [0006] =  r  l  b2 f2 d'  [inside 05-TFS] --->  u' b' f' d  u   @ 000000007088924 nodes [time = 00:02]
  Solution [0007] =  r  l  B2 F2 u'  [inside 05-TFS] --->  d' b' f' d  u   @ 000000007092701 nodes [time = 00:02]
  Solution [0008] =  r  l  B2 F2 d'  [inside 05-TFS] --->  u' b' f' d  u   @ 000000007092704 nodes [time = 00:02]
  Solution [0009] =  r2 u  d  r' l'  [inside 05-TFS] --->  d' u' b  f  l2  @ 000000010849004 nodes [time = 00:03]
  Solution [0010] =  r2 u  d  l' r'  [inside 05-TFS] --->  d' u' b  f  l2  @ 000000010849109 nodes [time = 00:03]
  Solution [0011] =  r2 d  u  r' l'  [inside 05-TFS] --->  d' u' b  f  l2  @ 000000010985084 nodes [time = 00:03]
  Solution [0012] =  r2 d  u  l' r'  [inside 05-TFS] --->  d' u' b  f  l2  @ 000000010985189 nodes [time = 00:03]
  Solution [0013] =  r2 f  b  u' d'  [inside 05-TFS] --->  l' r' d  u  l2  @ 000000011424872 nodes [time = 00:03]
  Solution [0014] =  r2 f  b  d' u'  [inside 05-TFS] --->  l' r' d  u  l2  @ 000000011424977 nodes [time = 00:03]
  Solution [0015] =  r2 b  f  u' d'  [inside 05-TFS] --->  l' r' d  u  l2  @ 000000011560952 nodes [time = 00:03]
  Solution [0016] =  r2 b  f  d' u'  [inside 05-TFS] --->  l' r' d  u  l2  @ 000000011561057 nodes [time = 00:03]
  Solution [0017] =  l  r  F2 B2 u'  [inside 05-TFS] --->  d' b' f' d  u   @ 000000011980241 nodes [time = 00:03]
  Solution [0018] =  l  r  F2 B2 d'  [inside 05-TFS] --->  u' b' f' d  u   @ 000000011980244 nodes [time = 00:03]
  Solution [0019] =  l  r  f2 b2 u'  [inside 05-TFS] --->  d' b' f' d  u   @ 000000011984021 nodes [time = 00:03]
  Solution [0020] =  l  r  f2 b2 d'  [inside 05-TFS] --->  u' b' f' d  u   @ 000000011984024 nodes [time = 00:03]
  Solution [0021] =  l  r  b2 f2 u'  [inside 05-TFS] --->  d' b' f' d  u   @ 000000011987801 nodes [time = 00:03]
  Solution [0022] =  l  r  b2 f2 d'  [inside 05-TFS] --->  u' b' f' d  u   @ 000000011987804 nodes [time = 00:03]
  Solution [0023] =  l  r  B2 F2 u'  [inside 05-TFS] --->  d' b' f' d  u   @ 000000011991581 nodes [time = 00:03]
  Solution [0024] =  l  r  B2 F2 d'  [inside 05-TFS] --->  u' b' f' d  u   @ 000000011991584 nodes [time = 00:03]
  Solution [0025] =  l2 u  d  r' l'  [inside 05-TFS] --->  d' u' b  f  r2  @ 000000015887852 nodes [time = 00:04]
  Solution [0026] =  l2 u  d  l' r'  [inside 05-TFS] --->  d' u' b  f  r2  @ 000000015887957 nodes [time = 00:04]
  Solution [0027] =  l2 d  u  r' l'  [inside 05-TFS] --->  d' u' b  f  r2  @ 000000016023932 nodes [time = 00:04]
  Solution [0028] =  l2 d  u  l' r'  [inside 05-TFS] --->  d' u' b  f  r2  @ 000000016024037 nodes [time = 00:04]
  Solution [0029] =  l2 f  b  u' d'  [inside 05-TFS] --->  l' r' d  u  r2  @ 000000016463720 nodes [time = 00:04]
  Solution [0030] =  l2 f  b  d' u'  [inside 05-TFS] --->  l' r' d  u  r2  @ 000000016463825 nodes [time = 00:04]
  Solution [0031] =  l2 b  f  u' d'  [inside 05-TFS] --->  l' r' d  u  r2  @ 000000016599800 nodes [time = 00:04]
  Solution [0032] =  l2 b  f  d' u'  [inside 05-TFS] --->  l' r' d  u  r2  @ 000000016599905 nodes [time = 00:04]
  Solution [0033] =  u  d  r' l' u'  [inside 05-TFS] --->  d' l2 r2 b  f   @ 000000027767105 nodes [time = 00:07]
  Solution [0034] =  u  d  r' l' d'  [inside 05-TFS] --->  u' l2 r2 b  f   @ 000000027767108 nodes [time = 00:07]
  Solution [0035] =  u  d  l' r' u'  [inside 05-TFS] --->  d' l2 r2 b  f   @ 000000027770885 nodes [time = 00:07]
  Solution [0036] =  u  d  l' r' d'  [inside 05-TFS] --->  u' l2 r2 b  f   @ 000000027770888 nodes [time = 00:07]
  Solution [0037] =  u  d  f' b' u'  [inside 05-TFS] --->  d' b2 f2 l  r   @ 000000027799073 nodes [time = 00:07]
  Solution [0038] =  u  d  f' b' d'  [inside 05-TFS] --->  u' b2 f2 l  r   @ 000000027799076 nodes [time = 00:07]
  Solution [0039] =  u  d  b' f' u'  [inside 05-TFS] --->  d' b2 f2 l  r   @ 000000027802853 nodes [time = 00:07]
  Solution [0040] =  u  d  b' f' d'  [inside 05-TFS] --->  u' b2 f2 l  r   @ 000000027802856 nodes [time = 00:07]
  Solution [0041] =  d  u  r' l' u'  [inside 05-TFS] --->  d' l2 r2 b  f   @ 000000032665985 nodes [time = 00:08]
  Solution [0042] =  d  u  r' l' d'  [inside 05-TFS] --->  u' l2 r2 b  f   @ 000000032665988 nodes [time = 00:08]
  Solution [0043] =  d  u  l' r' u'  [inside 05-TFS] --->  d' l2 r2 b  f   @ 000000032669765 nodes [time = 00:08]
  Solution [0044] =  d  u  l' r' d'  [inside 05-TFS] --->  u' l2 r2 b  f   @ 000000032669768 nodes [time = 00:08]
  Solution [0045] =  d  u  f' b' u'  [inside 05-TFS] --->  d' b2 f2 l  r   @ 000000032697953 nodes [time = 00:08]
  Solution [0046] =  d  u  f' b' d'  [inside 05-TFS] --->  u' b2 f2 l  r   @ 000000032697956 nodes [time = 00:08]
  Solution [0047] =  d  u  b' f' u'  [inside 05-TFS] --->  d' b2 f2 l  r   @ 000000032701733 nodes [time = 00:08]
  Solution [0048] =  d  u  b' f' d'  [inside 05-TFS] --->  u' b2 f2 l  r   @ 000000032701736 nodes [time = 00:08]
  Solution [0049] =  f  b  R2 L2 u'  [inside 05-TFS] --->  d' l' r' d  u   @ 000000048479921 nodes [time = 00:12]
  Solution [0050] =  f  b  R2 L2 d'  [inside 05-TFS] --->  u' l' r' d  u   @ 000000048479924 nodes [time = 00:12]
  Solution [0051] =  f  b  r2 l2 u'  [inside 05-TFS] --->  d' l' r' d  u   @ 000000048483701 nodes [time = 00:12]
  Solution [0052] =  f  b  r2 l2 d'  [inside 05-TFS] --->  u' l' r' d  u   @ 000000048483704 nodes [time = 00:12]
  Solution [0053] =  f  b  l2 r2 u'  [inside 05-TFS] --->  d' l' r' d  u   @ 000000048487481 nodes [time = 00:12]
  Solution [0054] =  f  b  l2 r2 d'  [inside 05-TFS] --->  u' l' r' d  u   @ 000000048487484 nodes [time = 00:12]
  Solution [0055] =  f  b  L2 R2 u'  [inside 05-TFS] --->  d' l' r' d  u   @ 000000048491261 nodes [time = 00:12]
  Solution [0056] =  f  b  L2 R2 d'  [inside 05-TFS] --->  u' l' r' d  u   @ 000000048491264 nodes [time = 00:12]
  Solution [0057] =  f2 r  l  u' d'  [inside 05-TFS] --->  b' f' d  u  b2  @ 000000050584808 nodes [time = 00:13]
  Solution [0058] =  f2 r  l  d' u'  [inside 05-TFS] --->  b' f' d  u  b2  @ 000000050584913 nodes [time = 00:13]
  Solution [0059] =  f2 l  r  u' d'  [inside 05-TFS] --->  b' f' d  u  b2  @ 000000050720888 nodes [time = 00:13]
  Solution [0060] =  f2 l  r  d' u'  [inside 05-TFS] --->  b' f' d  u  b2  @ 000000050720993 nodes [time = 00:13]
  Solution [0061] =  f2 u  d  f' b'  [inside 05-TFS] --->  d' u' l  r  b2  @ 000000051160676 nodes [time = 00:13]
  Solution [0062] =  f2 u  d  b' f'  [inside 05-TFS] --->  d' u' l  r  b2  @ 000000051160781 nodes [time = 00:13]
  Solution [0063] =  f2 d  u  f' b'  [inside 05-TFS] --->  d' u' l  r  b2  @ 000000051296756 nodes [time = 00:13]
  Solution [0064] =  f2 d  u  b' f'  [inside 05-TFS] --->  d' u' l  r  b2  @ 000000051296861 nodes [time = 00:13]
  Solution [0065] =  b  f  R2 L2 u'  [inside 05-TFS] --->  d' l' r' d  u   @ 000000053378801 nodes [time = 00:13]
  Solution [0066] =  b  f  R2 L2 d'  [inside 05-TFS] --->  u' l' r' d  u   @ 000000053378804 nodes [time = 00:13]
  Solution [0067] =  b  f  r2 l2 u'  [inside 05-TFS] --->  d' l' r' d  u   @ 000000053382581 nodes [time = 00:13]
  Solution [0068] =  b  f  r2 l2 d'  [inside 05-TFS] --->  u' l' r' d  u   @ 000000053382584 nodes [time = 00:13]
  Solution [0069] =  b  f  l2 r2 u'  [inside 05-TFS] --->  d' l' r' d  u   @ 000000053386361 nodes [time = 00:13]
  Solution [0070] =  b  f  l2 r2 d'  [inside 05-TFS] --->  u' l' r' d  u   @ 000000053386364 nodes [time = 00:13]
  Solution [0071] =  b  f  L2 R2 u'  [inside 05-TFS] --->  d' l' r' d  u   @ 000000053390141 nodes [time = 00:13]
  Solution [0072] =  b  f  L2 R2 d'  [inside 05-TFS] --->  u' l' r' d  u   @ 000000053390144 nodes [time = 00:13]
  Solution [0073] =  b2 r  l  u' d'  [inside 05-TFS] --->  b' f' d  u  f2  @ 000000055623656 nodes [time = 00:14]
  Solution [0074] =  b2 r  l  d' u'  [inside 05-TFS] --->  b' f' d  u  f2  @ 000000055623761 nodes [time = 00:14]
  Solution [0075] =  b2 l  r  u' d'  [inside 05-TFS] --->  b' f' d  u  f2  @ 000000055759736 nodes [time = 00:14]
  Solution [0076] =  b2 l  r  d' u'  [inside 05-TFS] --->  b' f' d  u  f2  @ 000000055759841 nodes [time = 00:14]
  Solution [0077] =  b2 u  d  f' b'  [inside 05-TFS] --->  d' u' l  r  f2  @ 000000056199524 nodes [time = 00:14]
  Solution [0078] =  b2 u  d  b' f'  [inside 05-TFS] --->  d' u' l  r  f2  @ 000000056199629 nodes [time = 00:14]
  Solution [0079] =  b2 d  u  f' b'  [inside 05-TFS] --->  d' u' l  r  f2  @ 000000056335604 nodes [time = 00:14]
  Solution [0080] =  b2 d  u  b' f'  [inside 05-TFS] --->  d' u' l  r  f2  @ 000000056335709 nodes [time = 00:14]
 
Last edited:
unsolved said:
By "trying" do you mean verifying the moves listed in the 05-TFS will solve the cube if applied to it?
Click to expand...
Nah, I mean computing all solutions to that position in the 5-TFS database, rather than just printing one solution. So a given way to get to the 5-TFS database may not necessarily lead to exactly one solution.

unsolved said:
Well...

Solution [0014] = f b R2 L2 d' [inside 05-TFS] ---> u' l' r' d u @ 000000018804997 nodes [time = 00:05]

...certainly does solve the cube!
Click to expand...
Yeah, but it's equivalent to solution 13 (and you can see it just by looking at the d' u' sequence), so it is not a new solution and it would be better to not print it.

unsolved said:
Independent of what crazy moves create a cube position, if it is not in the hash table of visited/solved positions, it will add it, along with the solution.
Click to expand...
Wait wait, you're storing the solution too? I guess that makes sense if you only keep a hash of the position - not much else you can do. But then you can't guarantee you will be able to find every solution. You could probably store the actual position in not much more space with a little data compression. If you can fit 3 stickers into one byte, you could put the cube state into 4 64-bit ints.

unsolved said:
So I hooked up the full-width generator to the scramble solver now, instead of using the move-order-by-3-axes technique suggested by Jackube. It now finds 80 solutions.
Click to expand...
Sorry, I don't understand what you mean. I do see a ton of duplicates though (as in, solutions that are exactly the same, just with moves on the same axis transposed or rewritten). Solutions 1-8 and 17-24 are actually only 2 solutions - and only one if you would consider F2 B2 and f2 b2 to be the same (they are equivalent up to a rotation).
 
Last edited:
qqwref said:
Nah, I mean computing all solutions to that position in the 5-TFS database, rather than just printing one solution. So a given way to get to the 5-TFS database may not necessarily lead to exactly one solution.
Click to expand...

Here is what is solved, in the order of solving, and why all solutions in the database represent a complete set.

1. Starting cube, no turns, no rotations. Is it in the database? No, add it.
2. Rotate 23 permutations of it. Check the database. None match, they are all added. (Now any move sequence that produces a rotated, solved cube won't be added, i.e. all the "ridiculous" moves).
3. Loop from 1 to 24. 1 == the unrotated solved cube ... 24 == the last version of a rotated cube that does not produce another rotated cube.
3.A. Inside loop 1, generate every one of the 36 available moves. Check for being in the database already. If not, add the "unmove" to solve the move made to the database.
3.B. Inside loop 2, generate every one of the 36 available moves. Check for being in the database already...
...
3.X. Inside loop 24, generate every one of the 36 available moves. Check for being in the database already...

4. Same, only for every 2-move sequence, including such winners as U U, R R', L L2, etc. U U will hit a match against U2 so it will never make it in. R R' recreates solved cubes, no chance of getting in there, etc.
5. Same, only for every 3-move sequence...
6. Same, only for every 4-move sequence...
7. Same, only for every 5-move sequence...

So I delegate the legitimacy of the entry to the explicit uniqueness of the cube position, with blatant disregard for whatever sequence produced it. The beauty of it is, the result is exactly the same as if I spent a tremendous amount of thought, time, and energy into coming up with the world's most awesome uniqueness algorithm on my own, but I had to do 0% of that :)


qqwref said:
Yeah, but it's equivalent to solution 13 (and you can see it just by looking at the d' u' sequence), so it is not a new solution and it would be better to not print it.
Click to expand...

Equivalency is a function of move generation "bias." As you saw from earlier versions of the program, it filtered "too many" when trying to adhere to a symmetry heuristic. In removing all such code from the program, this is the result. I have decided too much is better than too little. Thanks to you :)

qqwref said:
Wait wait, you're storing the solution too? I guess that makes sense if you only keep a hash of the position - not much else you can do.
Click to expand...

Yes, the solution is embedded within the database. Download the program, enter a scramble of 4 moves or fewer. The program prints info from RAM without executing a search. It shows the cube data (6 separate 64-bit integers), the hash code, and the hash index that precipitates out of the modulo divide with the large prime number. Earlier versions of the program also stored the rotation index number (0-23) along with it. I no longer do this.

There's a great deal more than can be done, though. For one, I can work on implementing a BMZ Minimal Perfect Hashing Function to save memory, or implement Quadratic probing to alleviate primary clustering within the hash table. I'm also trying to come up with an algorithm to avoid having to enter the entire cube into the hash table as well in order to guarantee a 100% match. All fun stuff that I enjoy. It will only improve future versions. Right now, I think 179 GB is needed for 6-TFS. That is awfully tempting to someone like me :)

qqwref said:
But then you can't guarantee you will be able to find every solution. You could probably store the actual position in not much more space with a little data compression. If you can fit 3 stickers into one byte, you could put the cube state into 4 64-bit ints.
Click to expand...

The two primary objectives of hashing are fast retrieval and not storing the position. I do store some cubies that are from splattered random parts of the cube (but the same parts in each case) for match testing in case of two 64-bit hash numbers being the same. If the bit patterns of the cubies match, the odds of 2 different positions still matching go way down.

Since 6^3 = 216 and 216 < 255 I could use a power series to store 3 stickers into one byte.

compressed_value = (sticker_1)*(6^2) + (sticker_2)*(6^1) + (sticker_3). I already have 2 in one byte (4 bits each) which turns out to be perfect for move generation on the 4x4x4.

qqwref said:
Sorry, I don't understand what you mean. I do see a ton of duplicates though (as in, solutions that are exactly the same, just with moves on the same axis transposed or rewritten). Solutions 1-8 and 17-24 are actually only 2 solutions - and only one if you would consider F2 B2 and f2 b2 to be the same (they are equivalent up to a rotation).
Click to expand...

Yes, but the whole point was, this is the only way to test 100% if 2 programs have both correctly returned every possible move generation path that leads to a solution. Each version of my program (3-TFS, 4-TFS, 5-TFS) had a different solution count (different move boundaries separate entry into the TFS databases) and Bruce's program also produced a number different from all 3 of them! In the event one program is suspected to be incorrect, how can you determine which one is "correct" based on move count alone? This exercise demonstrates the only real way using solution count as the metric is to go full-width with the move generation. I think it would be very improbable for 2 different full-width programs to produce different solution counts, but I am in the process of seeking verification of this.

Previously, when Bruce's program showed more solutions than mine, it was easy to hunt for a bug in my own program. Now, we can't be so quick to judge on that qualification alone. QED.
 
Last edited:
I have implemented new hash table loading/searching configurations, and introduced user-configurable Full Width and Normal search modes.

Hash Tables: Explicit or Implicit

Previously, all incarnations of the program featured Implicit hashing. If a hash position matched, the implicit assumption was so did the position. But, roughly 1 out of 100 billion cubes will generate an identical 64-bit hash number, due to the nature of the hashing function, not to impune the nature of random numbers which would suggest that 18,446,744,073,709,551,615 nodes should be perused before a duplicate match would be encountered. And so, whenever one of those random cubes would be encountered during the search, you would see a move sequence being reported as a "solve" that had no chance to solve the scrambled cube.

The solution was to also store the entire cube (48 bytes per cube for my bitboard move generator) in the hash table as well. For each matching hash code, a cube comparison is made (very fast since each cube is 6 different 64-bit numbers, if all 6 match the cubes ARE identical). If the cubes do not match, the hash table result is ignore and the search for a match continues. This is what I call the Explicit Hash Table version. The down side to using the EHT is that 48 additional bytes, times all of the 24 rotated cube states, times all of node counts per depth, will put even the 04-TFS-EHT at 5.4 GB of RAM.

The good news is, if you have the RAM, you'll always get a known, good solution, and the verification is fast. But, if you don't have the RAM, you can always use the new, verification-in-place version of the Implicit Hash Table.

As before, the IHT does not store each cube in the TFS databases in RAM. But, the new versions of OO_4x4x4 can resolve hash-match cube-disparities. Whenever a matching hash table entry is found, the stored solution is applied to the cube generated during the search. If the hash table solution does indeed solve the cube, the result is displayed. If the solution does not work, it must be a hash-match disparity, and the hash table data is ignored and the search continues.

The only down side to this is that these hash tables take much longer to generate when the program starts up. That's because the hash tables exclude duplicates, and this process must now evoke the move generator while a great deal of move generation is already happening. The lower RAM requirement makes it worth it for those who do not have enough memory to load the corresponding EHT.

Move Generation: Normal or Full Width

As a result of looking at the rlfb rlfb rlfb scrambles on 4 different brute force cube solving apps (Bruce's program and the 03-TFS, 04-TFS, and 05-TFS versions of OO_4x4x4), the discovery was made that the total solution count for any given cube is a function of move generator bias. While it was debated as to which solutions "should count" and which were "obvious duplicates," what remained unresolved was the answer to the question:

"Can you know if a solving program is working correctly just by observing the reported solution count for a given scrambled cube?"

The answer is: No.

This will no doubt spawn arguments such as, "Well if you examine each solution and look for transposing parallel plane rotations made in succession..." but that only serves to prove my point. Examining each solution is not the same as merely enumerating all reported solutions.

The only valid solution count for a given scrambled state must be done via Full Width Searching, which does not exclude transposing moves (but which does exclude moves such as R R or F F', or U2 U', etc.) Any other reported solution count must accept the fact that it incorporated Move Generator Bias.

rlfb_12_search_TSF_04e_full_width_in_progress.jpg


As shown above, typing search full width at the scramble prompt now directs OO_4x4x4 to use its 36 * 33^n-1 move generation mode.

To resume the reduced tree move generation mode, type search normal at the scramble prompt.

So now there are 6 different versions of OO_4x4x4, each using the same set of source code and only #define directives to determine what code to execute. Each version can be run in Full Width search or Normal search mode as well.

03-TFS-e = 3-Turns-From-Solved using Explicit Hash Table probing.
03-TFS-i = 3-Turns-From-Solved using Implicit Hash Table probing.

04-TFS-e = 4-Turns-From-Solved using Explicit Hash Table probing.
04-TFS-i = 4-Turns-From-Solved using Implicit Hash Table probing.

05-TFS-e = 5-Turns-From-Solved using Explicit Hash Table probing.
05-TFS-i = 5-Turns-From-Solved using Implicit Hash Table probing.

Since RAM requirements and performance options vary widely (since 05-TFS-i solves the rlfb-12 move scramble in normal search mode in 8 seconds while 04-TFS-e solves the same scramble in 03:28) I will be putting up a web page to help add to the confusion :)

rlfb_12_TFS_05i_search_normal.jpg
 
Last edited:
unsolved said:
The two primary objectives of hashing are fast retrieval and not storing the position. I do store some cubies that are from splattered random parts of the cube (but the same parts in each case) for match testing in case of two 64-bit hash numbers being the same. If the bit patterns of the cubies match, the odds of 2 different positions still matching go way down.

Since 6^3 = 216 and 216 < 255 I could use a power series to store 3 stickers into one byte.
Click to expand...

You appear to be referring to stickers (or facelets) when you (mis)use the word cubies here. The 4x4x4 has 96 stickers (facelets), but only 56 cubies. There are 8 corner cubies, 24 edge cubies, and 24 center cubies. A cubie can have up to 3 stickers (corner cubies). That's also why your representation of the cube is called a facelet level (or sticker level) representation, not a cubie representation.

unsolved said:
"Can you know if a solving program is working correctly just by observing the reported solution count for a given scrambled cube?"

The answer is: No.
Click to expand...
I agree that different solvers can output different number of solutions simply because of what you refer to as move generator bias. But in restricting the combinations of moves that the move generator makes, a very significant savings in search time can be achieved. In addition, the user may find it a nuisance being presented with many solutions that are doing essentially the same thing to the cube.

I would say all good solvers at least "canonicalize" solutions so that consecutive moves that commute are generated in a specific order only. Two solvers that both "canonicalize" the order of commuting moves will generate exactly the same number of solutions if no other move generation shortcuts are used.

In the sequence U u' d2, all the moves commute, so you can apply the three moves in any of the six possible ways. Producing all six variants is a basically a waste since someone should easily recognize that the moves commute, and should realize the order of the three moves doesn't matter. These sequence can be thought of as being trivially equivalent.

If several such commuting-move sequences occur in a solution, the number of trivially equivalent solution can grow quite large. A solution having three such 3-move sub-sequences would generate 216 different (but only "trivially" different) solutions.

Another example of sequences that are in some way equivalent is U u R and D d B. As qqwref mentioned, U u and D d have the same affect on the state of the cube except for the resulting orientation of the cube. Because they put the cube into different orientations, the rest of the moves in the solutions will look different. The remaining moves for the first one need to be translated to different moves for the other. For example, in the above sequences U u R and D d B, the R in the first one needs to be translated (mapped) to B for the other. This perhaps may be thought of as semi-trivially equivalent. It may be not so easy to recognize such solutions as being essentially the same just from eyeballing them. Some users might prefer that all these solutions as some may be more fingertrick friendly than others.

There are other sequences that can be thought of as being non-trivially equivalent. We can think of such sequences as being related by a non-trivial identity. For example, consider these two sequences.

F R' F' R U F'
U F' L' U L U'

These two move sequence have exactly the same effect on the cube. However, there is no obvious reason that these should be the same. A user who wants "all" solutions will typically want to see both of these solutions.

Another way solutions can be related is through what I will call "virtual" identities.

For example, consider these two sequences:

Code: 
r2 b2 r2
l2 b2 l2

These two sequences have different effects on the cube, but they both will solve the same position (unless we are talking about the supercube rather than the regular cube).

Using GAP, we can see exactly how these affect the cube:

[CODE]
gap> r2 := (3,83)(7,87)(11,91)(15,95)(35,78)(39,74)(43,70)(47,66);
(3,83)(7,87)(11,91)(15,95)(35,78)(39,74)(43,70)(47,66)
gap> l2 := (2,82)(6,86)(10,90)(14,94)(34,79)(38,75)(42,71)(46,67);
(2,82)(6,86)(10,90)(14,94)(34,79)(38,75)(42,71)(46,67)
gap> b2 := (5,92)(6,91)(7,90)(8,89)(18,63)(22,59)(26,55)(30,51);
(5,92)(6,91)(7,90)(8,89)(18,63)(22,59)(26,55)(30,51)

gap> r2*b2*r2;
(5,92)(6,11)(8,89)(18,63)(22,59)(26,55)(30,51)(87,90)
gap> l2*b2*l2;
(5,92)(7,10)(8,89)(18,63)(22,59)(26,55)(30,51)(86,91)
gap> r2*b2*r2 = l2*b2*l2;
false

In the above, 6, 7, 10, and 11 represent the U centers, and 86, 87, 90, and 91 represent the D centers. The first maneuver swaps U centers 6 and 11, and D centers 87 and 90. The 2nd maneuver swaps U centers 7 and 10, and D centers 86 and 91. The two sequences also swap some other pieces, but these other swaps are identical for the two sequences.

If the TFS databases in OO_4x4x4 stores only one sequence for each position, and only uses that sequence to generate a solution, it will (in general) miss some solutions that are "non-trivially" different. This may be fine for people who simply are interested in finding solutions as quickly as possible, but may be disappointing to some users that may want to get all essentially different solutions.
 
Last edited:
cuBerBruce said:
There are other sequences that can be thought of as being non-trivially equivalent. We can think of such sequences as being related by a non-trivial identity. For example, consider these two sequences.

F R' F' R U F'
U F' L' U L U'

These two move sequence have exactly the same effect on the cube. However, there is no obvious reason that these should be the same.
Click to expand...
Not to be super nitpicky (your post was really good otherwise), but isn't this the case for *all* pairs of non-equivalent solutions of a given position? They're all related through SOME nontrivial identity, just usually one nobody has explicitly generated or looked at. I would say that if you want to generate all solutions to a position, you should never take non-trivial identities into account, even well-known 10- or 12-move ones.
 
qqwref said:
Not to be super nitpicky (your post was really good otherwise), but isn't this the case for *all* pairs of non-equivalent solutions of a given position? They're all related through SOME nontrivial identity, just usually one nobody has explicitly generated or looked at. I would say that if you want to generate all solutions to a position, you should never take non-trivial identities into account, even well-known 10- or 12-move ones.
Click to expand...

Well, the 4x4x4 has indistinguishable pieces, so solutions may be related to what I called a "virtual" identity rather than a true identity. Also, unless you're doing something like converting all moves to a fixed DLB model, if the non-equivalent solutions are P and Q, the expression P Q' will not necessarily be an identity. Cube rotations might need to be included to make it an identity. But I suppose you can define what it means for two solutions to be "related to an identity" so that any two sequences can be related to a trivial or a non-trivial identity (perhaps a lengthy one).
 
cuBerBruce said:
You appear to be referring to stickers (or facelets) when you (mis)use the word cubies here. The 4x4x4 has 96 stickers (facelets), but only 56 cubies. There are 8 corner cubies, 24 edge cubies, and 24 center cubies. A cubie can have up to 3 stickers (corner cubies). That's also why your representation of the cube is called a facelet level (or sticker level) representation, not a cubie representation.
Click to expand...

Yes, I keep falling into the same hole. But I think I wrote the first Bitboard Facelet representation, have I not? I only use 6 variables to represent my cube, each one a 64-bit int. My original implementation was an Array Facelet, actually swapping matrix elements on the face[6][16] level. Even the Multithreaded Array Facelet was slower than the unencumbered Single-Threaded Bitboard version.

cuBerBruce said:
I agree that different solvers can output different number of solutions simply because of what you refer to as move generator bias. But in restricting the combinations of moves that the move generator makes, a very significant savings in search time can be achieved. In addition, the user may find it a nuisance being presented with many solutions that are doing essentially the same thing to the cube.
Click to expand...

I agree, and never disagreed on this point. I just gave the user the option to select how they want to see the solutions now, given the most recent discovery regarding the Solution Count Paradox.

cuBerBruce said:
I would say all good solvers at least "canonicalize" solutions so that consecutive moves that commute are generated in a specific order only. Two solvers that both "canonicalize" the order of commuting moves will generate exactly the same number of solutions if no other move generation shortcuts are used.
Click to expand...

What is the name of Jakube's canonicalization? The one with the 3-axes and move groups? Does it have a formalized term associated with it?

cuBerBruce said:
If the TFS databases in OO_4x4x4 stores only one sequence for each position, and only uses that sequence to generate a solution, it will (in general) miss some solutions that are "non-trivially" different. This may be fine for people who simply are interested in finding solutions as quickly as possible, but may be disappointing to some users that may want to get all essentially different solutions.
Click to expand...

You can type a move sequence with <= the number of moves of your largest loaded TFS database, and the hash table will display what it finds immediately. Download a copy and bang away at it. Let me know if any such sequence escapes detection. I've done it with a full-width 36^n move generator and encountered no gaps, so I believe the probe-before-add-to-the-hash-table approach has worked. Remember, I solve each depth 24 times, once for each possible starting orientation of the cube. That's why the hash tables are so large now.

My Cube Solved routine examines 24 states, but my hash probing code makes no rotation state queries. If it is in the hashtable, it's one of 24 rotated states. A huge cost in memory, and huge performance gain not to make so many rotation tests.
 
Last edited:
unsolved said:
You can type a move sequence with <= the number of moves of your largest loaded TFS database, and the hash table will display what it finds immediately. Download a copy and bang away at it. Let me know if any such sequence escapes detection. I've done it with a full-width 36^n move generator and encountered no gaps, so I believe the probe-before-add-to-the-hash-table approach has worked. Remember, I solve each depth 24 times, once for each possible starting orientation of the cube. That's why the hash tables are so large now.

My Cube Solved routine examines 24 states, but my hash probing code makes no rotation state queries. If it is in the hashtable, it's one of 24 rotated states. A huge cost in memory, and huge performance gain not to make so many rotation tests.
Click to expand...

In Version 2.1.1 if I enter r2 b2 r2, I only get one solution displayed (r2 b2 r2). It does not display l2 b2 l2, which I would consider a non-trivially different solution. That's why only one maneuver per TFS database entry is not sufficient if you want to display *all* non-trivially different solutions. If you want to merely guarantee that the program will produce at least one optimal solution, then one maneuver per TFS entry will suffice.
 
cuBerBruce said:
In Version 2.1.1 if I enter r2 b2 r2, I only get one solution displayed (r2 b2 r2). It does not display l2 b2 l2, which I would consider a non-trivially different solution. That's why only one maneuver per TFS database entry is not sufficient if you want to display *all* non-trivially different solutions. If you want to merely guarantee that the program will produce at least one optimal solution, then one maneuver per TFS entry will suffice.
Click to expand...

And what happens when you enter l2 b2 l2?

For both r2 b2 r2 and l2 b2 r2 I get the same solution, l2 b2 r2. My move generator makes l2 before r2, so you should not see r2 b2 r2 at all.

r2b2r2.jpg


They both map to the same index and hashcode.

l2b2l2.jpg


I think this is the exact behavior that is desired. At each and every depth, you want a 1:1 relationship between a scramble and a database entry. There are many, many paths to any particular solution. As an example, how many solutions should be reported for the scramble R L F B R L F B R L F B?

Code: 
                          TOP
                          ---------------------
                          |####|####|####|####|
                          ---------------------
                          |####|####|####|####|
                          ---------------------
                          |####|####|####|####|
                          ---------------------
                          |####|####|####|####|
                          ---------------------

  LEFT                    FRONT                   RIGHT                   BACK
  ---------------------   ---------------------   ---------------------   ---------------------
  |XXXX|XXXX|XXXX|&&&&|   |OOOO|^^^^|^^^^|^^^^|   |&&&&|&&&&|&&&&|XXXX|   |^^^^|OOOO|OOOO|OOOO|
  ---------------------   ---------------------   ---------------------   ---------------------
  |XXXX|&&&&|&&&&|XXXX|   |^^^^|OOOO|OOOO|^^^^|   |&&&&|XXXX|XXXX|&&&&|   |OOOO|^^^^|^^^^|OOOO|
  ---------------------   ---------------------   ---------------------   ---------------------
  |XXXX|&&&&|&&&&|XXXX|   |^^^^|OOOO|OOOO|^^^^|   |&&&&|XXXX|XXXX|&&&&|   |OOOO|^^^^|^^^^|OOOO|
  ---------------------   ---------------------   ---------------------   ---------------------
  |&&&&|XXXX|XXXX|XXXX|   |^^^^|^^^^|^^^^|OOOO|   |XXXX|&&&&|&&&&|&&&&|   |OOOO|OOOO|OOOO|^^^^|
  ---------------------   ---------------------   ---------------------   ---------------------

                          BOTTOM
                          ---------------------
                          |~~~~|~~~~|~~~~|~~~~|
                          ---------------------
                          |~~~~|~~~~|~~~~|~~~~|
                          ---------------------
                          |~~~~|~~~~|~~~~|~~~~|
                          ---------------------
                          |~~~~|~~~~|~~~~|~~~~|
                          ---------------------

You can see what a can of worms this would open up if at every depth in the tree multiple solutions @ depth were stored. There are 957 solutions @ 1 database node per scramble per ply.

http://lightningcloudcomputing.com/957.txt
 
Last edited:
I just solved up to and including the 7-TFS database for only centers :)

CENTERS_7_tfs.jpg


And here is an interesting entry:

upside_down_solve_center_7.jpg


If you reverse and prime the scramble with F2 u' f2 u' b2 u2 B2 you don't create the position shown. It rotates the position upside down. However, if you apply the rotation z2 to a solved cube first, then F2 u' f2 u' b2 u2 B2 you will create the position shown. The solution is correct. That is the power of rotating the cube 23 times and looking for the shortest entry into the database. The database probe only cares if the solution works with no preference to the rotated state to start with, and this is a clear-cut example.

_____________________________________________________________________________________________________________________

EDIT: Now if I could only start calling the access code at the correct location, this thing might actually be powerful :)

centers_frustrating.jpg


_____________________________________________________________________________________________________________________

EDIT #2: OK now I think I tracked this one down, so I am releasing an experimental version for testing. This one loads the 4-TFS and probes up to 7-TFS if only centers need solving in the resulting position. And, it probes it in RAM, so it can extend the search by up to 7-plies from the position being generated.

center_probe_sucess.jpg


And here is the download link, about 40 MB compressed with the Centers-4,5,6, and 7 included.

http://lightningcloudcomputing.com/OO_experimental.zip

Try adding some of these into the mix of your scrambles at the tail end. (These should all be optimal solutions as well, no way faster to create the scrambled position that results.)

Code: 
r2 f  d' r2 d' f' d2  @ 000000042288954891 nodes [time = 33:07]
l2 b  d  l2 d  b' d2  @ 000000046279685877 nodes [time = 35:56]
u2 b  u2 b2 d  b  d'  @ 000000057902469587 nodes [time = 44:00]
u2 b  u2 b2 d' b  d   @ 000000057902470675 nodes [time = 44:00]
u2 b' r  u' b  u' r'  @ 000000057924436517 nodes [time = 44:01]
u2 b' r  u2 r  b  r2  @ 000000057924446682 nodes [time = 44:01]
u2 b' r  u2 r2 b  r   @ 000000057924448858 nodes [time = 44:01]
u2 b' r  u2 b' r' b2  @ 000000057924473172 nodes [time = 44:01]
u2 b' r  b  u' r' u'  @ 000000057924927269 nodes [time = 44:01]
u2 b' r  b' r' u2 b2  @ 000000057924950484 nodes [time = 44:01]
u2 b' r  b' u2 r' b2  @ 000000057924964311 nodes [time = 44:01]

Maybe something like this:

centers_07_during_solve.jpg
 
Last edited:
Status
Not open for further replies.

Similar threads

P
Announcing: Competition Cubes - A Ranked Speedcubing Website
Replies
4
Views
1,281
Phantom37
P
E
Announcing the United States School Cubing League (USSCL) Season 3!
Replies
4
Views
792
ea99
E
Calode
Announcing LetsCube! A real-time racing website
Replies
6
Views
3,119
abunickabhi
abunickabhi
M
Announcing: Vintage Cube Sale/Store
Replies
3
Views
1,102
herbs1685
H
penguinz7
Announcing our new Canadian collab channel, Cubing Province
Replies
1
Views
944
penguinz7
penguinz7
Back
Top