Announcing: New 4x4x4 Brute Force Solver

[cuBerBruce]

If someone could check that out and let me know.

Looks like ply-1 is working...

It looks wrong to me. You should only have 4 new configurations at depth 1.

From solved, R and R' produce the same orientation configuration. Cubicles URB and DRF will each contain a cubie that is twisted clockwise, and cubicles UFR and DBR will contain counter-clockwise twisted cubies.

If you're using (DLB),UFR,ULF,URB,DRF,ULB,DFL,DBR cublicle ordering, the base 3 number should look like (0)2011002. This should give 1568 decimal. Your value of 84 (for R) would correspond to a base 3 number of (?)0010001, and it doesn't have any 2's (well, one if the "(?)" is a 2, but it actually needs to be 1 for the digits to add to 0 modulo 3) for the counterclockwise-twisted cubicles, so it doesn't make sense to me.

EDIT (appending):
I've now finished analyzing the distance distribution for the 3x3x1 block pruning table in single slice turn metric and block turn metric.

3x3x1 block:
Single slice turn metric:
dist  0: count =          1 total          1
dist  1: count =         18 total         19
dist  2: count =        348 total        367
dist  3: count =       6969 total       7336
dist  4: count =     127662 total     134998
dist  5: count =    2183800 total    2318798
dist  6: count =   31940635 total   34259433
dist  7: count =  328348722 total  362608155
dist  8: count = 1463547678 total 1826155833
dist  9: count =  879470589 total 2705626422
dist 10: count =    4258602 total 2709885024

Block turn metric:
dist  0: count =          1 total          1
dist  1: count =         18 total         19
dist  2: count =        455 total        474
dist  3: count =      11271 total      11745
dist  4: count =     266161 total     277906
dist  5: count =    5722833 total    6000739
dist  6: count =   96340321 total  102341060
dist  7: count =  882894514 total  985235574
dist  8: count = 1638637904 total 2623873478
dist  9: count =   86011474 total 2709884952
dist 10: count =         72 total 2709885024

 

[unsolved]

I've now finished analyzing the distance distribution for the 3x3x1 block pruning table in single slice turn metric and block turn metric.

3x3x1 block:
Single slice turn metric:
dist  0: count =          1 total          1
dist  1: count =         18 total         19
dist  2: count =        348 total        367
dist  3: count =       6969 total       7336
dist  4: count =     127662 total     134998
dist  5: count =    2183800 total    2318798
dist  6: count =   31940635 total   34259433
dist  7: count =  328348722 total  362608155
dist  8: count = 1463547678 total 1826155833
dist  9: count =  879470589 total 2705626422
dist 10: count =    4258602 total 2709885024

Block turn metric:
dist  0: count =          1 total          1
dist  1: count =         18 total         19
dist  2: count =        455 total        474
dist  3: count =      11271 total      11745
dist  4: count =     266161 total     277906
dist  5: count =    5722833 total    6000739
dist  6: count =   96340321 total  102341060
dist  7: count =  882894514 total  985235574
dist  8: count = 1638637904 total 2623873478
dist  9: count =   86011474 total 2709884952
dist 10: count =         72 total 2709885024

So there are no depth == 11 entries?

 

[rokicki]

Wow. So on average corners-only distance returns a higher value than this metric, which uses
9 cubies and 2.7B entries.

Of course this metric can be applied in 24 different ways, which bumps it up a move or two.
And then there's the addition of one you can perform in many cases because a given move only
changes a subset of the solved blocks. This is easy to figure out, I think; there are only a few
moves that disturb a solved block, and you can make a bitmask for each, and "and" together all
the ones at the greatest distance, and if you end up with zero, you get a free addition of 1
move to the distance.

Next is to consider other subspaces than just defined by cubies, and see if there's a good
pruning table that works well. Probably edge pairing is something to consider.

 

[unsolved]

Next is to consider other subspaces than just defined by cubies, and see if there's a good
pruning table that works well. Probably edge pairing is something to consider.

I have given this idea some thought, when I have not been pulling what's left of my hair out of my head from the orientation perplexity.

How about this for an idea...

Of course, pruning based on the location of ALL CENTERS is never going to happen, but... we can get the functional "distance-usable" equivalent with a trick.

A chain is only as strong as its weakest link, and so, the distance-from-solved for any of the center arrangements cannot be any faster than the slowest solution for two adjacent faces.

Why not index every possible U vs. F center face configuration, obtain strong solutions for distance-from-solved for each, and use them as a center pruning table?

There should be all kinds of symmetry reductions, and the state space is small enough that it can be handled via distributed computing in a reasonable amount of time.
The table will be small, RAM resident, and should provide for some very deep pruning. Using the corner-pruning table during the database generation will be of tremendous help.

 

[cuBerBruce]

So there are no depth == 11 entries?

Correct. Although this table is different from the one you're working on, which does have distance 11 positions. By the way the numbers I get for corners considering only orientation are { 1, 4, 34, 186, 816, 1018, 128 } for distances 0 through 6, with 6 being the maximum depth.

Wow. So on average corners-only distance returns a higher value than this metric, which uses
9 cubies and 2.7B entries.

Of course this metric can be applied in 24 different ways, which bumps it up a move or two.
And then there's the addition of one you can perform in many cases because a given move only
changes a subset of the solved blocks. This is easy to figure out, I think; there are only a few
moves that disturb a solved block, and you can make a bitmask for each, and "and" together all
the ones at the greatest distance, and if you end up with zero, you get a free addition of 1
move to the distance.

Next is to consider other subspaces than just defined by cubies, and see if there's a good
pruning table that works well. Probably edge pairing is something to consider.

Yes, the corners pruning table has the branching factor limited due to several 4x4x4 moves having no effect on them. Another thing about corners pruning, is that if the pruning table distance is exactly the distance-to-goal depth, you can skip applying any moves that don't involve outer layers.

One could try 8 corners and 2 edges. (Of course, that's a superset of just the 8 corners, so it doesn't complement that pruning table.)

 

[rokicki]

Why not index every possible U vs. F center face configuration, obtain strong solutions for distance-from-solved for each, and use them as a center pruning table?

There should be all kinds of symmetry reductions, and the state space is small enough that it can be handled via distributed computing in a reasonable amount of time.
The table will be small, RAM resident, and should provide for some very deep pruning. Using the corner-pruning table during the database generation will be of tremendous help.

This isn't that big a space; (24 choose 4) * (20 choose 4) for which I get 51M entries. No need
for distributed computing. Probably worth investigating.

Indeed, for any pruning table that fits in memory, it's pretty fast and easy to just do breadth-first
by scanning; you can even multithread this pretty easily if you're careful. If you have a big-memory
machine, consider doing relatively large scans. You can use some of the tricks on Jaap's site to
push things a bit further (for instance, four values in a byte by storing values mod 3 is a very classic
trick).

 

[cuBerBruce]

This isn't that big a space; (24 choose 4) * (20 choose 4) for which I get 51M entries. No need
for distributed computing. Probably worth investigating.

I've done this for the center pieces of 2 opposite faces (with respect to a corner piece) instead of 2 adjacent faces (post 83). It should be rather easy to change it to adjacent faces. I'll probably try it in the next day or so, but I would guess the results will be similar.

 

[unsolved]

It looks wrong to me. You should only have 4 new configurations at depth 1.

From solved, R and R' produce the same orientation configuration. Cubicles URB and DRF will each contain a cubie that is twisted clockwise, and cubicles UFR and DBR will contain counter-clockwise twisted cubies.

If you're using (DLB),UFR,ULF,URB,DRF,ULB,DFL,DBR cublicle ordering, the base 3 number should look like (0)2011002. This should give 1568 decimal. Your value of 84 (for R) would correspond to a base 3 number of (?)0010001, and it doesn't have any 2's (well, one if the "(?)" is a 2, but it actually needs to be 1 for the digits to add to 0 modulo 3) for the counterclockwise-twisted cubicles, so it doesn't make sense to me.

I changed the order of the cubicles for the place-value assignments in the power-of-3 section of the code that generates the orientation sub-index.

Here is ply 1 with the 1st two entries @ ply-2.

I still get R and R' tossing out different orientation indices from the solved state.

  Node 1 == orientation # 0  [(base-3 number = 0000000) order UFR UFL UBL UBR DFR DFL DBL] @ depth 0 after --- 1 found, 2186 remain.

TOP                     FRONT                   RIGHT
---------------------   ---------------------   ---------------------
|####|####|####|####|   |OOOO|OOOO|OOOO|OOOO|   |XXXX|XXXX|XXXX|XXXX|
---------------------   ---------------------   ---------------------
|####|####|####|####|   |OOOO|OOOO|OOOO|OOOO|   |XXXX|XXXX|XXXX|XXXX|
---------------------   ---------------------   ---------------------
|####|####|####|####|   |OOOO|OOOO|OOOO|OOOO|   |XXXX|XXXX|XXXX|XXXX|
---------------------   ---------------------   ---------------------
|####|####|####|####|   |OOOO|OOOO|OOOO|OOOO|   |XXXX|XXXX|XXXX|XXXX|
---------------------   ---------------------   ---------------------


BOTTOM                  BACK                    LEFT
---------------------   ---------------------   ---------------------
|~~~~|~~~~|~~~~|~~~~|   |&&&&|&&&&|&&&&|&&&&|   |^^^^|^^^^|^^^^|^^^^|
---------------------   ---------------------   ---------------------
|~~~~|~~~~|~~~~|~~~~|   |&&&&|&&&&|&&&&|&&&&|   |^^^^|^^^^|^^^^|^^^^|
---------------------   ---------------------   ---------------------
|~~~~|~~~~|~~~~|~~~~|   |&&&&|&&&&|&&&&|&&&&|   |^^^^|^^^^|^^^^|^^^^|
---------------------   ---------------------   ---------------------
|~~~~|~~~~|~~~~|~~~~|   |&&&&|&&&&|&&&&|&&&&|   |^^^^|^^^^|^^^^|^^^^|
---------------------   ---------------------   ---------------------



  Node 7 == orientation # 756  [(base-3 number = 1001000) order UFR UFL UBL UBR DFR DFL DBL] @ depth 1 after  R. 2 found, 2185 remain.

TOP                     FRONT                   RIGHT
---------------------   ---------------------   ---------------------
|####|####|####|OOOO|   |OOOO|OOOO|OOOO|~~~~|   |XXXX|XXXX|XXXX|XXXX|
---------------------   ---------------------   ---------------------
|####|####|####|OOOO|   |OOOO|OOOO|OOOO|~~~~|   |XXXX|XXXX|XXXX|XXXX|
---------------------   ---------------------   ---------------------
|####|####|####|OOOO|   |OOOO|OOOO|OOOO|~~~~|   |XXXX|XXXX|XXXX|XXXX|
---------------------   ---------------------   ---------------------
|####|####|####|OOOO|   |OOOO|OOOO|OOOO|~~~~|   |XXXX|XXXX|XXXX|XXXX|
---------------------   ---------------------   ---------------------


BOTTOM                  BACK                    LEFT
---------------------   ---------------------   ---------------------
|~~~~|~~~~|~~~~|&&&&|   |####|&&&&|&&&&|&&&&|   |^^^^|^^^^|^^^^|^^^^|
---------------------   ---------------------   ---------------------
|~~~~|~~~~|~~~~|&&&&|   |####|&&&&|&&&&|&&&&|   |^^^^|^^^^|^^^^|^^^^|
---------------------   ---------------------   ---------------------
|~~~~|~~~~|~~~~|&&&&|   |####|&&&&|&&&&|&&&&|   |^^^^|^^^^|^^^^|^^^^|
---------------------   ---------------------   ---------------------
|~~~~|~~~~|~~~~|&&&&|   |####|&&&&|&&&&|&&&&|   |^^^^|^^^^|^^^^|^^^^|
---------------------   ---------------------   ---------------------



  Node 8 == orientation # 738  [(base-3 number = 1000100) order UFR UFL UBL UBR DFR DFL DBL] @ depth 1 after  R'. 3 found, 2184 remain.

TOP                     FRONT                   RIGHT
---------------------   ---------------------   ---------------------
|####|####|####|&&&&|   |OOOO|OOOO|OOOO|####|   |XXXX|XXXX|XXXX|XXXX|
---------------------   ---------------------   ---------------------
|####|####|####|&&&&|   |OOOO|OOOO|OOOO|####|   |XXXX|XXXX|XXXX|XXXX|
---------------------   ---------------------   ---------------------
|####|####|####|&&&&|   |OOOO|OOOO|OOOO|####|   |XXXX|XXXX|XXXX|XXXX|
---------------------   ---------------------   ---------------------
|####|####|####|&&&&|   |OOOO|OOOO|OOOO|####|   |XXXX|XXXX|XXXX|XXXX|
---------------------   ---------------------   ---------------------


BOTTOM                  BACK                    LEFT
---------------------   ---------------------   ---------------------
|~~~~|~~~~|~~~~|OOOO|   |~~~~|&&&&|&&&&|&&&&|   |^^^^|^^^^|^^^^|^^^^|
---------------------   ---------------------   ---------------------
|~~~~|~~~~|~~~~|OOOO|   |~~~~|&&&&|&&&&|&&&&|   |^^^^|^^^^|^^^^|^^^^|
---------------------   ---------------------   ---------------------
|~~~~|~~~~|~~~~|OOOO|   |~~~~|&&&&|&&&&|&&&&|   |^^^^|^^^^|^^^^|^^^^|
---------------------   ---------------------   ---------------------
|~~~~|~~~~|~~~~|OOOO|   |~~~~|&&&&|&&&&|&&&&|   |^^^^|^^^^|^^^^|^^^^|
---------------------   ---------------------   ---------------------



  Node 10 == orientation # 328  [(base-3 number = 0110011) order UFR UFL UBL UBR DFR DFL DBL] @ depth 1 after  L'. 4 found, 2183 remain.

TOP                     FRONT                   RIGHT
---------------------   ---------------------   ---------------------
|OOOO|####|####|####|   |~~~~|OOOO|OOOO|OOOO|   |XXXX|XXXX|XXXX|XXXX|
---------------------   ---------------------   ---------------------
|OOOO|####|####|####|   |~~~~|OOOO|OOOO|OOOO|   |XXXX|XXXX|XXXX|XXXX|
---------------------   ---------------------   ---------------------
|OOOO|####|####|####|   |~~~~|OOOO|OOOO|OOOO|   |XXXX|XXXX|XXXX|XXXX|
---------------------   ---------------------   ---------------------
|OOOO|####|####|####|   |~~~~|OOOO|OOOO|OOOO|   |XXXX|XXXX|XXXX|XXXX|
---------------------   ---------------------   ---------------------


BOTTOM                  BACK                    LEFT
---------------------   ---------------------   ---------------------
|&&&&|~~~~|~~~~|~~~~|   |&&&&|&&&&|&&&&|####|   |^^^^|^^^^|^^^^|^^^^|
---------------------   ---------------------   ---------------------
|&&&&|~~~~|~~~~|~~~~|   |&&&&|&&&&|&&&&|####|   |^^^^|^^^^|^^^^|^^^^|
---------------------   ---------------------   ---------------------
|&&&&|~~~~|~~~~|~~~~|   |&&&&|&&&&|&&&&|####|   |^^^^|^^^^|^^^^|^^^^|
---------------------   ---------------------   ---------------------
|&&&&|~~~~|~~~~|~~~~|   |&&&&|&&&&|&&&&|####|   |^^^^|^^^^|^^^^|^^^^|
---------------------   ---------------------   ---------------------



  Node 13 == orientation # 1968  [(base-3 number = 2200220) order UFR UFL UBL UBR DFR DFL DBL] @ depth 1 after  F. 5 found, 2182 remain.

TOP                     FRONT                   RIGHT
---------------------   ---------------------   ---------------------
|####|####|####|####|   |OOOO|OOOO|OOOO|OOOO|   |####|XXXX|XXXX|XXXX|
---------------------   ---------------------   ---------------------
|####|####|####|####|   |OOOO|OOOO|OOOO|OOOO|   |####|XXXX|XXXX|XXXX|
---------------------   ---------------------   ---------------------
|####|####|####|####|   |OOOO|OOOO|OOOO|OOOO|   |####|XXXX|XXXX|XXXX|
---------------------   ---------------------   ---------------------
|^^^^|^^^^|^^^^|^^^^|   |OOOO|OOOO|OOOO|OOOO|   |####|XXXX|XXXX|XXXX|
---------------------   ---------------------   ---------------------


BOTTOM                  BACK                    LEFT
---------------------   ---------------------   ---------------------
|XXXX|XXXX|XXXX|XXXX|   |&&&&|&&&&|&&&&|&&&&|   |^^^^|^^^^|^^^^|~~~~|
---------------------   ---------------------   ---------------------
|~~~~|~~~~|~~~~|~~~~|   |&&&&|&&&&|&&&&|&&&&|   |^^^^|^^^^|^^^^|~~~~|
---------------------   ---------------------   ---------------------
|~~~~|~~~~|~~~~|~~~~|   |&&&&|&&&&|&&&&|&&&&|   |^^^^|^^^^|^^^^|~~~~|
---------------------   ---------------------   ---------------------
|~~~~|~~~~|~~~~|~~~~|   |&&&&|&&&&|&&&&|&&&&|   |^^^^|^^^^|^^^^|~~~~|
---------------------   ---------------------   ---------------------



  Node 16 == orientation # 216  [(base-3 number = 0022000) order UFR UFL UBL UBR DFR DFL DBL] @ depth 1 after  B'. 6 found, 2181 remain.

TOP                     FRONT                   RIGHT
---------------------   ---------------------   ---------------------
|^^^^|^^^^|^^^^|^^^^|   |OOOO|OOOO|OOOO|OOOO|   |XXXX|XXXX|XXXX|####|
---------------------   ---------------------   ---------------------
|####|####|####|####|   |OOOO|OOOO|OOOO|OOOO|   |XXXX|XXXX|XXXX|####|
---------------------   ---------------------   ---------------------
|####|####|####|####|   |OOOO|OOOO|OOOO|OOOO|   |XXXX|XXXX|XXXX|####|
---------------------   ---------------------   ---------------------
|####|####|####|####|   |OOOO|OOOO|OOOO|OOOO|   |XXXX|XXXX|XXXX|####|
---------------------   ---------------------   ---------------------


BOTTOM                  BACK                    LEFT
---------------------   ---------------------   ---------------------
|~~~~|~~~~|~~~~|~~~~|   |&&&&|&&&&|&&&&|&&&&|   |~~~~|^^^^|^^^^|^^^^|
---------------------   ---------------------   ---------------------
|~~~~|~~~~|~~~~|~~~~|   |&&&&|&&&&|&&&&|&&&&|   |~~~~|^^^^|^^^^|^^^^|
---------------------   ---------------------   ---------------------
|~~~~|~~~~|~~~~|~~~~|   |&&&&|&&&&|&&&&|&&&&|   |~~~~|^^^^|^^^^|^^^^|
---------------------   ---------------------   ---------------------
|XXXX|XXXX|XXXX|XXXX|   |&&&&|&&&&|&&&&|&&&&|   |~~~~|^^^^|^^^^|^^^^|
---------------------   ---------------------   ---------------------



  Node 17 == orientation # 164  [(base-3 number = 0020002) order UFR UFL UBL UBR DFR DFL DBL] @ depth 1 after  B. 7 found, 2180 remain.

TOP                     FRONT                   RIGHT
---------------------   ---------------------   ---------------------
|XXXX|XXXX|XXXX|XXXX|   |OOOO|OOOO|OOOO|OOOO|   |XXXX|XXXX|XXXX|~~~~|
---------------------   ---------------------   ---------------------
|####|####|####|####|   |OOOO|OOOO|OOOO|OOOO|   |XXXX|XXXX|XXXX|~~~~|
---------------------   ---------------------   ---------------------
|####|####|####|####|   |OOOO|OOOO|OOOO|OOOO|   |XXXX|XXXX|XXXX|~~~~|
---------------------   ---------------------   ---------------------
|####|####|####|####|   |OOOO|OOOO|OOOO|OOOO|   |XXXX|XXXX|XXXX|~~~~|
---------------------   ---------------------   ---------------------


BOTTOM                  BACK                    LEFT
---------------------   ---------------------   ---------------------
|~~~~|~~~~|~~~~|~~~~|   |&&&&|&&&&|&&&&|&&&&|   |####|^^^^|^^^^|^^^^|
---------------------   ---------------------   ---------------------
|~~~~|~~~~|~~~~|~~~~|   |&&&&|&&&&|&&&&|&&&&|   |####|^^^^|^^^^|^^^^|
---------------------   ---------------------   ---------------------
|~~~~|~~~~|~~~~|~~~~|   |&&&&|&&&&|&&&&|&&&&|   |####|^^^^|^^^^|^^^^|
---------------------   ---------------------   ---------------------
|^^^^|^^^^|^^^^|^^^^|   |&&&&|&&&&|&&&&|&&&&|   |####|^^^^|^^^^|^^^^|
---------------------   ---------------------   ---------------------



  Node 4 == orientation # 783  [(base-3 number = 1002000) order UFR UFL UBL UBR DFR DFL DBL] @ depth 2 after  U R. 8 found, 2179 remain.

TOP                     FRONT                   RIGHT
---------------------   ---------------------   ---------------------
|####|####|####|XXXX|   |XXXX|XXXX|XXXX|~~~~|   |XXXX|XXXX|XXXX|&&&&|
---------------------   ---------------------   ---------------------
|####|####|####|OOOO|   |OOOO|OOOO|OOOO|~~~~|   |XXXX|XXXX|XXXX|&&&&|
---------------------   ---------------------   ---------------------
|####|####|####|OOOO|   |OOOO|OOOO|OOOO|~~~~|   |XXXX|XXXX|XXXX|&&&&|
---------------------   ---------------------   ---------------------
|####|####|####|OOOO|   |OOOO|OOOO|OOOO|~~~~|   |XXXX|XXXX|XXXX|&&&&|
---------------------   ---------------------   ---------------------


BOTTOM                  BACK                    LEFT
---------------------   ---------------------   ---------------------
|~~~~|~~~~|~~~~|&&&&|   |####|^^^^|^^^^|^^^^|   |OOOO|OOOO|OOOO|OOOO|
---------------------   ---------------------   ---------------------
|~~~~|~~~~|~~~~|&&&&|   |####|&&&&|&&&&|&&&&|   |^^^^|^^^^|^^^^|^^^^|
---------------------   ---------------------   ---------------------
|~~~~|~~~~|~~~~|&&&&|   |####|&&&&|&&&&|&&&&|   |^^^^|^^^^|^^^^|^^^^|
---------------------   ---------------------   ---------------------
|~~~~|~~~~|~~~~|^^^^|   |####|&&&&|&&&&|&&&&|   |^^^^|^^^^|^^^^|^^^^|
---------------------   ---------------------   ---------------------



  Node 5 == orientation # 1476  [(base-3 number = 2000200) order UFR UFL UBL UBR DFR DFL DBL] @ depth 2 after  U R'. 9 found, 2178 remain.

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


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

This isn't that big a space; (24 choose 4) * (20 choose 4) for which I get 51M entries. No need
for distributed computing. Probably worth investigating.

Well you'd have to solve 51M entries via searching from scratch, and not via just move generation + hoping to run into a permutation * orientation as in the case of the corners table. With a distance-from-solved == 8 plies just for 1 center unsolved vs. 1 center unsolved, I imagine the longest to swap say 3 splattered on 1 face and 3 splattered on another could take 24 plies or longer. Might be a tough solve! And, you'd need data for every entry to make the table fully useful.

You can use some of the tricks on Jaap's site to
push things a bit further (for instance, four values in a byte by storing values mod 3 is a very classic
trick).

Oh, you can do waaaay better than 2 per byte if you use run-length encoding. When I solved the 440 billion positions in the 8-piece checkers endgame database, we averaged over 30 positions per byte by examining the runs of the same data and compressing it with data bytes that indicate how many were in a row.

Example in our case. Say you have indices where the results are (in turns from solved) 1,1,1,1,1,1,2,2,2,2,3,2,2,2,1,2,3,2,2,2,2,2,2,2,4,4,4,4,4,4,4,4,4,4,4,4

You represent the bytes as 1x6, 2x4, (3 + 2 as 4-bits each stuffed into a byte since they break up a run), (2 + 2 as 4-bits each since we don't run-length encode runs of 2 values in a row), (1 + 2, same reason), (3 + 2, same reason), 2x6, 4x12.

There is no reason to adhere to a standard where 1 represents the number 1, 2 represents the number 2, etc. I can encode "2" to mean "when I have 12 values in a row, each == 4."

In such a scheme, you have 1 byte per run of entries, and 1 byte per pair (as you suggested @ 4 bits each).

You create a lookup table as you compress the data, storing them in blocks with the last global index stored per block of data.

-----------------------------------------------------------------------------------------------------
| 205 | 206 |  50 |  34 |  18 |  50 |  207 |  208 |XXXX| store that index 36 is last entry in block |
-----------------------------------------------------------------------------------------------------

You can store up to 12 + 12 in one byte and only use 204 of the 255 values in a byte.
So you can make 205 to 255 mean anything you want!

1x6 = 205
2x4 = 206

(3 + 2 = 0011 0010) = 50 
(2 + 2 = 0010 0010) = 34
(1 + 2 = 0001 0010) = 18
(3 + 2 = 0011 0010) = 50 

2x6  = 207 
4x12 = 208

This way, you have 36 entries encoded using only 8 bytes + a "last index in block" value that can store the largest index in your set, in this case, 4 bytes.

This means 36 entries in 12 bytes = 3 positions per byte.

So what you have is a cluster of fixed-size blocks in RAM, each of which you know the largest index contained therein. So to find the value of your position, here is what you do:

1. Generate the index.
2. Binary search among the blocks to find the block that contains the index.
3. Go to the start of that block, read the bytes sequentially, decoding the "skip" value for the entry, and keeping track until you encounter or surpass your index.
4. Once you are at such a location, the value of the byte tells you the value of your distance.

There is a "penalty" for decompression, so you want to only use this for very large databases that would not otherwise fit into RAM.

 

[cuBerBruce]

  Node 7 == orientation # 756  [(base-3 number = 1001000) order UFR UFL UBL UBR DFR DFL DBL] @ depth 1 after  R. 2 found, 2185 remain.

First, I want to say that you should list the facelets/stickers consistently in either clockwise order or counterclockwise order. For this post, I will use clockwise order. Then UFL is OK, but UFR is not - it should be URF (or RFU or FUR). Then after the move F' (starting from solved), we can say that the cubie at UFL is RFU. The U facelet of the UFL cubicle has an R-color sticker, the F facelet is the F-color, and the L-facelet is the U-color. Similarly, after U, we could say the UFL cubicle contains cubie URF. In this manner we not only specify what what cubie is at a particular cublcle, but also how its oriented.

We then list our cubicles, as (DRB) URF UFL ULB UBR DFR DLF DBL. The state after the move R (starting from solved) can be specified by listing the cubicles and the cubie at each of them.

cubicles: (DRB) URF UFL ULB UBR DFR DLF DBL
cubies:   (BRU) FRD UFL ULB FUR BDR DLF DBL
base 3 #: (  2)   2 0   0    1   1  0   0

So for R, we should get the base-3 number 2001100 (ignoring the DRB cubicle) or 1494 decimal.

For F, we should get:

cubicles: (DRB) URF UFL ULB UBR DFR DLF DBL
cubies:   (DRB) LUF LFD ULB UBR RFU RDF DBL
base 3 #  (0  )  1    2 0   0     2  1  0

Base-3 1200210 is decimal 1236.

Note I label the cubicles starting with a U or D, and then the position of the U or D for the cubies determines the base-3 digit.

 

[qqwref]

Just a little pruning table idea: suppose we have a table for corners, so we know our position needs at least (say) 8 moves to solve. But none of those 8 moves are slice moves, since slice moves don't affect corners. Perhaps we could add on a second pruning table for centers or edges, and then by looking at that, determine that our position also requires at least (say) 4 slice moves. Because the second pruning table counts slice moves only, we can add the results! Then our position requires at least 12 moves to solve.

 

[cuBerBruce]

Just a little pruning table idea: suppose we have a table for corners, so we know our position needs at least (say) 8 moves to solve. But none of those 8 moves are slice moves, since slice moves don't affect corners. Perhaps we could add on a second pruning table for centers or edges, and then by looking at that, determine that our position also requires at least (say) 4 slice moves. Because the second pruning table counts slice moves only, we can add the results! Then our position requires at least 12 moves to solve.

Good suggestion! This should be very useful at least for single slice turn metric. It's probably not going to be helpful for block turn metric or outer block turn metric.

Inner layer turns are needed to pair up edges, and if you have 3 or fewer dedges formed, we know it takes at least 3 inner layer turns to form the rest. Similarly, inner layer moves are needed to move center pieces to a different face. If you know at least 17 center pieces must move to a different face, at least 3 inner layer turns are required. Determining the number of centers needing to move to a different face may not be so simple, though. A table based on a subset might be more useful.

 

[unsolved]

I have not had much success with the orientation bug, so I took a "time out" from that and worked on something else as a distraction. I probed my 2-turns-from-solved database of 1,026 positions and saw that there were only 73 different "patterns" for the first row on the top face. I decided to see if it was possible to do a Karnaugh Map Reduction of the entire database into a series of instructions. As it turns out, it is possible, and I recoded the positions (remember there are 98,496 data elements total that describe every possible arrangement 2 turns away from a solved cube, if you count each cube's location as 1 item) with one set of case statements, one matrix, and one for-loop that determines what range of the matrix to parse over.

UPDATE: Added a feature to automatically turn off any turns-from-solved (tfs) database that could not possibly improve upon the fastest solution found so far.

It is a relatively small chunk of code when you consider what it does and how it can be used.

Recall, my previous 2-tfs database was not in any kind of "order," so I had a lazy implementation where I had to scan every element in the database to see if there was a match. My "justification" of this lazy approach was that it was a small database and the performance hit was not that great when you consider it chops off 2 entire plies of search from the tree.

But now, it is much quicker, though clearly not as elegant as a hashing function with a bitboard. (My bitboard code is too buggy for now, I am back to the old matrix code).

I am not sure if this code is of interest to the group or not. The bigger question is, to what extent can this be applied to larger tfs databases.

Solution to 4x4x4 Cube scrambled with ----> d'  u2  l2  F'  b'  f2  L2  

TOP                     FRONT                   RIGHT
---------------------   ---------------------   ---------------------
|^^^^|~~~~|####|####|   |&&&&|&&&&|XXXX|OOOO|   |~~~~|^^^^|####|XXXX|
---------------------   ---------------------   ---------------------
|####|OOOO|XXXX|^^^^|   |^^^^|&&&&|XXXX|OOOO|   |~~~~|OOOO|~~~~|^^^^|
---------------------   ---------------------   ---------------------
|XXXX|~~~~|####|~~~~|   |OOOO|^^^^|OOOO|&&&&|   |####|XXXX|####|&&&&|
---------------------   ---------------------   ---------------------
|~~~~|^^^^|&&&&|XXXX|   |&&&&|&&&&|XXXX|OOOO|   |~~~~|^^^^|####|XXXX|
---------------------   ---------------------   ---------------------


BOTTOM                  BACK                    LEFT
---------------------   ---------------------   ---------------------
|####|XXXX|OOOO|^^^^|   |&&&&|&&&&|OOOO|OOOO|   |####|XXXX|~~~~|^^^^|
---------------------   ---------------------   ---------------------
|^^^^|####|~~~~|####|   |OOOO|OOOO|XXXX|&&&&|   |~~~~|^^^^|~~~~|OOOO|
---------------------   ---------------------   ---------------------
|~~~~|&&&&|^^^^|XXXX|   |^^^^|^^^^|&&&&|OOOO|   |####|&&&&|####|XXXX|
---------------------   ---------------------   ---------------------
|XXXX|####|~~~~|~~~~|   |&&&&|&&&&|OOOO|OOOO|   |####|XXXX|~~~~|^^^^|
---------------------   ---------------------   ---------------------



Solution [1] =  L2 F f2 b l2  [INSIDE 2-turn database]
Solution [2] =  L2 F f2 b l2 u  [INSIDE 2-turn database]
Solution [3] =  L2 F f2 b l2 u'  [INSIDE 2-turn database]
Solution [4] =  L2 F f2 b l2 u2  [INSIDE 1-turn database]
Solution [5] =  L2 F f2 b l2 d'  [INSIDE 2-turn database]
Solution [6] =  L2 F f2 b l2 d  [INSIDE 1-turn database]
Solution [7] =  L2 F f2 b l2 d2  [INSIDE 2-turn database]
Solution [8] =  L2 F b l2 f2 u2  [INSIDE 1-turn database]
Solution [9] =  L2 F b l2 f2 d  [INSIDE 1-turn database]

Update: Karnaugh Map Reduction for 3-TFS Database

Believe it or not, there are only 216 unique patterns possible for the topmost row of the Top face of the 4x4x4 after every possible 3-turn path is taken. I was able to perform a Karnaugh Map Reduction on the entire database, mapping every position possible from 3 moves away from a solution using just a case statement, a matrix, and a for loop. Well, the matrix is much bigger, but only a small section of it ever needs to be queried to find a position.

If you turn the top row of the top face into a 4-digit number, where 1 = top color, 2 = front color, 3 = right color, 4 = bottom color, 5 = back color, 6 = left color, these are the only combinations that are present 3 moves from a solution. The cube's orientation is UFR facing you for the assignment of row numerals.

        TFS_03_ARRAY_INDEX = 0;
	current_cube_row_data = cube_row_to_4_digit_number(your_cube.cube_top[0], your_cube.cube_top[1], your_cube.cube_top[2], your_cube.cube_top[3]);

	switch(current_cube_row_data)
	{
		case 1111: index_start = 0; index_stop = 184656; break;
		case 1121: index_start = 184680; index_stop = 211824; break;
		case 1131: index_start = 211848; index_stop = 218160; break;
		case 1141: index_start = 218184; index_stop = 246384; break;
		case 1151: index_start = 246408; index_stop = 273384; break;
		case 1161: index_start = 273408; index_stop = 279720; break;
		case 1211: index_start = 279744; index_stop = 306888; break;
		case 1221: index_start = 306912; index_stop = 308808; break;
		case 1231: index_start = 308832; index_stop = 308904; break;
		case 1241: index_start = 308928; index_stop = 310680; break;
		case 1251: index_start = 310704; index_stop = 312456; break;
		case 1261: index_start = 312480; index_stop = 312552; break;
		case 1311: index_start = 312576; index_stop = 318888; break;
		case 1321: index_start = 318912; index_stop = 318984; break;
		case 1331: index_start = 319008; index_stop = 319392; break;
		case 1341: index_start = 319416; index_stop = 319608; break;
		case 1351: index_start = 319632; index_stop = 319752; break;
		case 1361: index_start = 319776; index_stop = 319848; break;
		case 1411: index_start = 319872; index_stop = 348072; break;
		case 1421: index_start = 348096; index_stop = 349848; break;
		case 1431: index_start = 349872; index_stop = 350064; break;
		case 1441: index_start = 350088; index_stop = 353496; break;
		case 1451: index_start = 353520; index_stop = 355296; break;
		case 1461: index_start = 355320; index_stop = 355512; break;
		case 1511: index_start = 355536; index_stop = 382512; break;
		case 1521: index_start = 382536; index_stop = 384288; break;
		case 1531: index_start = 384312; index_stop = 384432; break;
		case 1541: index_start = 384456; index_stop = 386232; break;
		case 1551: index_start = 386256; index_stop = 388080; break;
		case 1561: index_start = 388104; index_stop = 388224; break;
		case 1611: index_start = 388248; index_stop = 394560; break;
		case 1621: index_start = 394584; index_stop = 394656; break;
		case 1631: index_start = 394680; index_stop = 394752; break;
		case 1641: index_start = 394776; index_stop = 394968; break;
		case 1651: index_start = 394992; index_stop = 395112; break;
		case 1661: index_start = 395136; index_stop = 395544; break;
		case 2112: index_start = 395568; index_stop = 422568; break;
		case 2122: index_start = 422592; index_stop = 424488; break;
		case 2132: index_start = 424512; index_stop = 424584; break;
		case 2142: index_start = 424608; index_stop = 426384; break;
		case 2152: index_start = 426408; index_stop = 428160; break;
		case 2162: index_start = 428184; index_stop = 428256; break;
		case 2212: index_start = 428280; index_stop = 430176; break;
		case 2222: index_start = 430200; index_stop = 432648; break;
		case 2232: index_start = 432672; index_stop = 432840; break;
		case 2242: index_start = 432864; index_stop = 433056; break;
		case 2252: index_start = 433080; index_stop = 433176; break;
		case 2262: index_start = 433200; index_stop = 433392; break;
		case 2312: index_start = 433416; index_stop = 433488; break;
		case 2322: index_start = 433512; index_stop = 433680; break;
		case 2332: index_start = 433704; index_stop = 436368; break;
		case 2342: index_start = 436392; index_stop = 436416; break;
		case 2352: index_start = 436440; index_stop = 436512; break;
		case 2362: index_start = 436536; index_stop = 436632; break;
		case 2412: index_start = 436656; index_stop = 438432; break;
		case 2422: index_start = 438456; index_stop = 438648; break;
		case 2432: index_start = 438672; index_stop = 438696; break;
		case 2442: index_start = 438720; index_stop = 441528; break;
		case 2452: index_start = 441552; index_stop = 441648; break;
		case 2462: index_start = 441672; index_stop = 441696; break;
		case 2512: index_start = 441720; index_stop = 443472; break;
		case 2522: index_start = 443496; index_stop = 443592; break;
		case 2532: index_start = 443616; index_stop = 443688; break;
		case 2542: index_start = 443712; index_stop = 443808; break;
		case 2552: index_start = 443832; index_stop = 443904; break;
		case 2562: index_start = 443928; index_stop = 444000; break;
		case 2612: index_start = 444024; index_stop = 444096; break;
		case 2622: index_start = 444120; index_stop = 444312; break;
		case 2632: index_start = 444336; index_stop = 444432; break;
		case 2642: index_start = 444456; index_stop = 444480; break;
		case 2652: index_start = 444504; index_stop = 444576; break;
		case 2662: index_start = 444600; index_stop = 447264; break;
		case 3113: index_start = 447288; index_stop = 453672; break;
		case 3123: index_start = 453696; index_stop = 453768; break;
		case 3133: index_start = 453792; index_stop = 454176; break;
		case 3143: index_start = 454200; index_stop = 454368; break;
		case 3153: index_start = 454392; index_stop = 454512; break;
		case 3163: index_start = 454536; index_stop = 454632; break;
		case 3213: index_start = 454656; index_stop = 454728; break;
		case 3223: index_start = 454752; index_stop = 454944; break;
		case 3233: index_start = 454968; index_stop = 457704; break;
		case 3243: index_start = 457728; index_stop = 457752; break;
		case 3253: index_start = 457776; index_stop = 457848; break;
		case 3263: index_start = 457872; index_stop = 457944; break;
		case 3313: index_start = 457968; index_stop = 458352; break;
		case 3323: index_start = 458376; index_stop = 461112; break;
		case 3333: index_start = 461136; index_stop = 484896; break;
		case 3343: index_start = 484920; index_stop = 486288; break;
		case 3353: index_start = 486312; index_stop = 488904; break;
		case 3363: index_start = 488928; index_stop = 490368; break;
		case 3413: index_start = 490392; index_stop = 490560; break;
		case 3423: index_start = 490584; index_stop = 490608; break;
		case 3433: index_start = 490632; index_stop = 492000; break;
		case 3443: index_start = 492024; index_stop = 492360; break;
		case 3453: index_start = 492384; index_stop = 492408; break;
		case 3463: index_start = 492432; index_stop = 492456; break;
		case 3513: index_start = 492480; index_stop = 492600; break;
		case 3523: index_start = 492624; index_stop = 492696; break;
		case 3533: index_start = 492720; index_stop = 495312; break;
		case 3543: index_start = 495336; index_stop = 495360; break;
		case 3553: index_start = 495384; index_stop = 495576; break;
		case 3563: index_start = 495600; index_stop = 495672; break;
		case 3613: index_start = 495696; index_stop = 495792; break;
		case 3623: index_start = 495816; index_stop = 495888; break;
		case 3633: index_start = 495912; index_stop = 497352; break;
		case 3643: index_start = 497376; index_stop = 497400; break;
		case 3653: index_start = 497424; index_stop = 497496; break;
		case 3663: index_start = 497520; index_stop = 498984; break;
		case 4114: index_start = 499008; index_stop = 527256; break;
		case 4124: index_start = 527280; index_stop = 529032; break;
		case 4134: index_start = 529056; index_stop = 529248; break;
		case 4144: index_start = 529272; index_stop = 532560; break;
		case 4154: index_start = 532584; index_stop = 534408; break;
		case 4164: index_start = 534432; index_stop = 534624; break;
		case 4214: index_start = 534648; index_stop = 536400; break;
		case 4224: index_start = 536424; index_stop = 536592; break;
		case 4234: index_start = 536616; index_stop = 536640; break;
		case 4244: index_start = 536664; index_stop = 539472; break;
		case 4254: index_start = 539496; index_stop = 539568; break;
		case 4264: index_start = 539592; index_stop = 539616; break;
		case 4314: index_start = 539640; index_stop = 539832; break;
		case 4324: index_start = 539856; index_stop = 539880; break;
		case 4334: index_start = 539904; index_stop = 541272; break;
		case 4344: index_start = 541296; index_stop = 541656; break;
		case 4354: index_start = 541680; index_stop = 541704; break;
		case 4364: index_start = 541728; index_stop = 541752; break;
		case 4414: index_start = 541776; index_stop = 545064; break;
		case 4424: index_start = 545088; index_stop = 547896; break;
		case 4434: index_start = 547920; index_stop = 548280; break;
		case 4444: index_start = 548304; index_stop = 578280; break;
		case 4454: index_start = 578304; index_stop = 581040; break;
		case 4464: index_start = 581064; index_stop = 581424; break;
		case 4514: index_start = 581448; index_stop = 583272; break;
		case 4524: index_start = 583296; index_stop = 583368; break;
		case 4534: index_start = 583392; index_stop = 583416; break;
		case 4544: index_start = 583440; index_stop = 586176; break;
		case 4554: index_start = 586200; index_stop = 586440; break;
		case 4564: index_start = 586464; index_stop = 586488; break;
		case 4614: index_start = 586512; index_stop = 586704; break;
		case 4624: index_start = 586728; index_stop = 586752; break;
		case 4634: index_start = 586776; index_stop = 586800; break;
		case 4644: index_start = 586824; index_stop = 587184; break;
		case 4654: index_start = 587208; index_stop = 587232; break;
		case 4664: index_start = 587256; index_stop = 588600; break;
		case 5115: index_start = 588624; index_stop = 615768; break;
		case 5125: index_start = 615792; index_stop = 617520; break;
		case 5135: index_start = 617544; index_stop = 617664; break;
		case 5145: index_start = 617688; index_stop = 619440; break;
		case 5155: index_start = 619464; index_stop = 621288; break;
		case 5165: index_start = 621312; index_stop = 621432; break;
		case 5215: index_start = 621456; index_stop = 623184; break;
		case 5225: index_start = 623208; index_stop = 623304; break;
		case 5235: index_start = 623328; index_stop = 623376; break;
		case 5245: index_start = 623400; index_stop = 623496; break;
		case 5255: index_start = 623520; index_stop = 623568; break;
		case 5265: index_start = 623592; index_stop = 623664; break;
		case 5315: index_start = 623688; index_stop = 623808; break;
		case 5325: index_start = 623832; index_stop = 623880; break;
		case 5335: index_start = 623904; index_stop = 626568; break;
		case 5345: index_start = 626592; index_stop = 626616; break;
		case 5355: index_start = 626640; index_stop = 626832; break;
		case 5365: index_start = 626856; index_stop = 626928; break;
		case 5415: index_start = 626952; index_stop = 628704; break;
		case 5425: index_start = 628728; index_stop = 628824; break;
		case 5435: index_start = 628848; index_stop = 628872; break;
		case 5445: index_start = 628896; index_stop = 631656; break;
		case 5455: index_start = 631680; index_stop = 631872; break;
		case 5465: index_start = 631896; index_stop = 631920; break;
		case 5515: index_start = 631944; index_stop = 633768; break;
		case 5525: index_start = 633792; index_stop = 633840; break;
		case 5535: index_start = 633864; index_stop = 634056; break;
		case 5545: index_start = 634080; index_stop = 634272; break;
		case 5555: index_start = 634296; index_stop = 636864; break;
		case 5565: index_start = 636888; index_stop = 637080; break;
		case 5615: index_start = 637104; index_stop = 637224; break;
		case 5625: index_start = 637248; index_stop = 637320; break;
		case 5635: index_start = 637344; index_stop = 637416; break;
		case 5645: index_start = 637440; index_stop = 637464; break;
		case 5655: index_start = 637488; index_stop = 637680; break;
		case 5665: index_start = 637704; index_stop = 640320; break;
		case 6116: index_start = 640344; index_stop = 646632; break;
		case 6126: index_start = 646656; index_stop = 646728; break;
		case 6136: index_start = 646752; index_stop = 646848; break;
		case 6146: index_start = 646872; index_stop = 647040; break;
		case 6156: index_start = 647064; index_stop = 647184; break;
		case 6166: index_start = 647208; index_stop = 647592; break;
		case 6216: index_start = 647616; index_stop = 647688; break;
		case 6226: index_start = 647712; index_stop = 647904; break;
		case 6236: index_start = 647928; index_stop = 647976; break;
		case 6246: index_start = 648000; index_stop = 648024; break;
		case 6256: index_start = 648048; index_stop = 648120; break;
		case 6266: index_start = 648144; index_stop = 650808; break;
		case 6316: index_start = 650832; index_stop = 650928; break;
		case 6326: index_start = 650952; index_stop = 651000; break;
		case 6336: index_start = 651024; index_stop = 652512; break;
		case 6346: index_start = 652536; index_stop = 652560; break;
		case 6356: index_start = 652584; index_stop = 652680; break;
		case 6366: index_start = 652704; index_stop = 654168; break;
		case 6416: index_start = 654192; index_stop = 654360; break;
		case 6426: index_start = 654384; index_stop = 654408; break;
		case 6436: index_start = 654432; index_stop = 654456; break;
		case 6446: index_start = 654480; index_stop = 654864; break;
		case 6456: index_start = 654888; index_stop = 654912; break;
		case 6466: index_start = 654936; index_stop = 656304; break;
		case 6516: index_start = 656328; index_stop = 656448; break;
		case 6526: index_start = 656472; index_stop = 656544; break;
		case 6536: index_start = 656568; index_stop = 656664; break;
		case 6546: index_start = 656688; index_stop = 656712; break;
		case 6556: index_start = 656736; index_stop = 656928; break;
		case 6566: index_start = 656952; index_stop = 659568; break;
		case 6616: index_start = 659592; index_stop = 659976; break;
		case 6626: index_start = 660000; index_stop = 662664; break;
		case 6636: index_start = 662688; index_stop = 664152; break;
		case 6646: index_start = 664176; index_stop = 665544; break;
		case 6656: index_start = 665568; index_stop = 668184; break;
		case 6666: index_start = 668208; index_stop = 692040; break;
		default: goto test_tfs_02; break;
	}

The start and stop indices are the only ranges within the matrix that need to be scanned in order to identify a position that matches the rest of the cube.

So now all you have to do is...

for(TFS_03_ARRAY_INDEX = index_start; TFS_03_ARRAY_INDEX <= index_stop; TFS_03_ARRAY_INDEX+= 24)
	{
		GLOBAL_TFS_3_DATABASE_PROBES++;

		index_offset = 0;

		/*********************************/
		/* TOP face match existing cube? */
		/*********************************/
		current_database_row_data = GLOBAL_TFS_03_DATABASE[TFS_03_ARRAY_INDEX + index_offset];
		current_cube_row_data = cube_row_to_4_digit_number(your_cube.cube_top[0], your_cube.cube_top[1], your_cube.cube_top[2], your_cube.cube_top[3]);
		if(current_database_row_data != current_cube_row_data) continue;

		index_offset++;
		current_database_row_data = GLOBAL_TFS_03_DATABASE[TFS_03_ARRAY_INDEX + index_offset];
		current_cube_row_data = cube_row_to_4_digit_number(your_cube.cube_top[4], your_cube.cube_top[5], your_cube.cube_top[6], your_cube.cube_top[7]);
		if(current_database_row_data != current_cube_row_data) continue;

		index_offset++;
		current_database_row_data = GLOBAL_TFS_03_DATABASE[TFS_03_ARRAY_INDEX + index_offset];
		current_cube_row_data = cube_row_to_4_digit_number(your_cube.cube_top[8], your_cube.cube_top[9], your_cube.cube_top[10], your_cube.cube_top[11]);
		if(current_database_row_data != current_cube_row_data) continue;

		index_offset++;
		current_database_row_data = GLOBAL_TFS_03_DATABASE[TFS_03_ARRAY_INDEX + index_offset];
		current_cube_row_data = cube_row_to_4_digit_number(your_cube.cube_top[12], your_cube.cube_top[13], your_cube.cube_top[14], your_cube.cube_top[15]);
		if(current_database_row_data != current_cube_row_data) continue;

		/***********************************/
		/* FRONT face match existing cube? */
		/***********************************/
		index_offset++;
		current_database_row_data = GLOBAL_TFS_03_DATABASE[TFS_03_ARRAY_INDEX + index_offset];
		current_cube_row_data = cube_row_to_4_digit_number(your_cube.cube_front[0], your_cube.cube_front[1], your_cube.cube_front[2], your_cube.cube_front[3]);
		if(current_database_row_data != current_cube_row_data) continue;

ETC. ETC. ETC.

...and the GLOBAL_TFS_03_DATABASE matrix finds the matching positions.

Nice way to shave off 3-ply from any search.

 

[rokicki]

Just a little pruning table idea: suppose we have a table for corners, so we know our position needs at least (say) 8 moves to solve. But none of those 8 moves are slice moves, since slice moves don't affect corners. Perhaps we could add on a second pruning table for centers or edges, and then by looking at that, determine that our position also requires at least (say) 4 slice moves. Because the second pruning table counts slice moves only, we can add the results! Then our position requires at least 12 moves to solve.

I don't think you can add here, unfortunately, since
the face turns alone change the edges and corners
sufficiently that you have a different position.

If you could generalize things, so you build a table
that somehow says "for this particular edge
pairing, and this particular corner quads" (neither
of which are affected by face turns) you might be
able to do something, but even if it is only slice
turns I'm still a little leery.

Additive pruning tables are excellent; if there's a
way to apply them to the 4x4x4, that's almost
certainly the best direction to go---but I'm not
yet convinced it is possible.

 

[cuBerBruce]

I don't think you can add here, unfortunately, since
the face turns alone change the edges and corners
sufficiently that you have a different position.

In the breadth-first search for inner layer turns, after each inner-layer turn, you need to find all positions reachable using only face turns (not including wide turns, we need to assume single-slice turn metric) and mark those positions as being of the same depth. Likewise the "solved" states have to include all positions reachable from only face turns from the actual solved state. Then we'll have a count of the minimum number of inner layer turns needed indpendent of how many outer layer turns are needed. Then for a given position, we can have a minimum number of inner turns independent of how many outer layer turns are used, and (from the corner table) a minimum number of outer layer turns independent of how many inner layer turns are used. Then the minimum number of moves from solved has to be at least the sum of these two bounds.

A simple bound for edge pairing bound can be obtained using the following table:

dedges already    inner layer
   formed         turns needed
     0                3
     1                3
     2                3
     3                3
     4                2
     5                2
     6                2
     7                2
     8                1
     9                2
    10                2
    11            (impossible)
    12                0

 

[unsolved]

In the breadth-first search for inner layer turns, after each inner-layer turn,

Hi Bruce,

Sorry that this post is unrelated I just ran a solve for the case of 2 centers missing from 2 adjacent faces. It hit my new 3-TFS database and found a solution, but I don't have a cube with me here at work to test it out. Can you supply the last 3 turns for me if your solver is not otherwise engaged right now? Thanks if you can. And, is there an algo for doing 2 simultaneous center swaps?

Solution to 4x4x4 cube center scenario U1,2:F1,2 

TOP                     FRONT                   RIGHT
---------------------   ---------------------   ---------------------
|####|####|####|####|   |OOOO|OOOO|OOOO|OOOO|   |XXXX|XXXX|XXXX|XXXX|
---------------------   ---------------------   ---------------------
|####|OOOO|OOOO|####|   |OOOO|####|####|OOOO|   |XXXX|XXXX|XXXX|XXXX|
---------------------   ---------------------   ---------------------
|####|####|####|####|   |OOOO|OOOO|OOOO|OOOO|   |XXXX|XXXX|XXXX|XXXX|
---------------------   ---------------------   ---------------------
|####|####|####|####|   |OOOO|OOOO|OOOO|OOOO|   |XXXX|XXXX|XXXX|XXXX|
---------------------   ---------------------   ---------------------


BOTTOM                  BACK                    LEFT
---------------------   ---------------------   ---------------------
|~~~~|~~~~|~~~~|~~~~|   |&&&&|&&&&|&&&&|&&&&|   |^^^^|^^^^|^^^^|^^^^|
---------------------   ---------------------   ---------------------
|~~~~|~~~~|~~~~|~~~~|   |&&&&|&&&&|&&&&|&&&&|   |^^^^|^^^^|^^^^|^^^^|
---------------------   ---------------------   ---------------------
|~~~~|~~~~|~~~~|~~~~|   |&&&&|&&&&|&&&&|&&&&|   |^^^^|^^^^|^^^^|^^^^|
---------------------   ---------------------   ---------------------
|~~~~|~~~~|~~~~|~~~~|   |&&&&|&&&&|&&&&|&&&&|   |^^^^|^^^^|^^^^|^^^^|
---------------------   ---------------------   ---------------------



Solution [1] =  U  F' D2 B2 l' B2 D2 F2  [INSIDE 3-turn database] @ 11076427485 nodes                                                           
Solution [2] =  U  F' l' F2 D2 B2 r' B2  [INSIDE 3-turn database] @ 11205157254 nodes

 

[cuBerBruce]

Hi Bruce,

Sorry that this post is unrelated I just ran a solve for the case of 2 centers missing from 2 adjacent faces. It hit my new 3-TFS database and found a solution, but I don't have a cube with me here at work to test it out. Can you supply the last 3 turns for me if your solver is not otherwise engaged right now?

Enter: F b' u' d b U2 b' u d' b U2 F' U F' D2 B2 l' B2 D2 F2
scramble: [20] F b' u' d b U2 b' u d' b U2 F' U F' D2 B2 l' B2 D2 F2
Found solution: [ 3] r' F' U'
distance 3 node count 177 solved state checks 54
Enter: F b' u' d b U2 b' u d' b U2 F' U F' l' F2 D2 B2 r' B2
scramble: [20] F b' u' d b U2 b' u d' b U2 F' U F' l' F2 D2 B2 r' B2
Found solution: [ 3] D2 F' U'
distance 3 node count 99 solved state checks 54

 

[unsolved]

Found solution: [ 3] r' F' U'
Found solution: [ 3] D2 F' U'

Thanks! I will check it out when I get home.

So now we have an 11-move algo for swapping two adjacent centers.

 

[rokicki]

Ahh, if your metric is such that turning a two-depth block counts as two moves,
yes, then this works. Is "slice turn metric" such a metric? I guess I was confused
by what was meant by "slice turn metric".

 

[cuBerBruce]

Ahh, if your metric is such that turning a two-depth block counts as two moves,
yes, then this works. Is "slice turn metric" such a metric? I guess I was confused
by what was meant by "slice turn metric".

That's why I don't call it "slice turn metric," but rather "single slice turn metric" - to emphasize that you're only allowed to turn a single slice (layer) at a time as a move.

 

[qqwref]

The first alg is a setup to F2 D2 B2 l' B2 D2 F2 r'. I didn't know about that one but it's interesting.