# 4x4x4 God's Number Position Hunt



## unsolved (Feb 19, 2015)

So far, I believe the lower bound for God's Number for the 4x4x4 is set at 32 moves. That should mean we can solve every tough scramble in that many moves if we put our collective minds to the task. 

I have a 37-move scramble that creates this position:







Can anyone solve this faster than 37 moves (not using OBTM)?

If it can be solved faster, maybe we can post positions here that are believed to be of "God's Number Length" and the rest of us can take a shot at solving them faster.

The person who solves the position fastest is the one who can post the next attempt.


----------



## supercavitation (Feb 19, 2015)

L' F' L R' Rw U2 Rw' U2' Rw U2 Rw U2 Lw' U2 Rw U2' Rw' U2 x' U2' Rw2 U2 R L' F L

26 moves, 34 when outer slice moves count as two moves.


----------



## Stefan (Feb 19, 2015)

L' F' L R' r' U2 r' U2 l U2 r' U2 r U2 x U2 r2 U2 r' U2 r U2 R L' F L

Edit: Darn ninjas... I should have just posted instead of double-check. Oh well, at least it shows how obvious this was.


----------



## supercavitation (Feb 19, 2015)

Stefan said:


> L' F' L R' r' U2 r' U2 l U2 r' U2 r U2 x U2 r2 U2 r' U2 r U2 R L' F L
> 
> Edit: Darn ninjas... I should have just posted instead of double-check. Oh well, at least it shows how obvious this was.



Did you find it by hand too?


----------



## Stefan (Feb 19, 2015)

Not sure what you mean. I grabbed the double parity alg from the wiki and then conjugated it as needed.


----------



## supercavitation (Feb 19, 2015)

Stefan said:


> Not sure what you mean. I grabbed the double parity alg from the wiki and then conjugated it as needed.



That's exactly what I meant. I did the same thing, except that's my normal OLL Parity alg.


----------



## TDM (Feb 19, 2015)

L' F' L R' U2 Rw2 F2 Rw U2 Rw U2 x U2 Rw U2 Rw' U2 Rw U2 Rw2 U2 R L' U L

24 moves, different double parity alg.

E: wait, what metric are we using? If we're counting wide moves as 2, then this is 31 moves.


----------



## Stefan (Feb 19, 2015)

TDM said:


> what metric are we using?



As this is about simply "4x4x4 God's Number", it ought to be the one corresponding to God's Number for 3x3x3. That is, OBTM.


----------



## unsolved (Feb 19, 2015)

TDM said:


> L' F' L R' U2 Rw2 F2 Rw U2 Rw U2 x U2 Rw U2 Rw' U2 Rw U2 Rw2 U2 R L' U L
> 
> 24 moves, different double parity alg.
> 
> E: wait, what metric are we using? If we're counting wide moves as 2, then this is 31 moves.



I was politely requesting *not *using OBTM. I have an OBTM solution already. I was interested in seeing other solutions.


----------



## supercavitation (Feb 19, 2015)

unsolved said:


> I was politely requesting *not *using OBTM. I have an OBTM solution already. I was interested in seeing other solutions.



Stefan's is 25 moves without OBTM.


----------



## TDM (Feb 19, 2015)

unsolved said:


> I was politely requesting *not *using OBTM. I have an OBTM solution already. I was interested in seeing other solutions.


I gave you a movecount without using OBTM too...? In the metric I think we're using which you haven't explained, my alg is 31 moves.


----------



## Jokern (Feb 19, 2015)

unsolved said:


> I was politely requesting *not *using OBTM. I have an OBTM solution already. I was interested in seeing other solutions.



When you say _not OBTM_, there is still several other metrics to choose from. Could you be more precise?


----------



## Stefan (Feb 19, 2015)

TDM said:


> I gave you a movecount without using OBTM too...? In the metric I think we're using which you haven't explained, my alg is 31 moves.



Actually, I also get 24 for your alg without using OBTM. Using BTM  (and rewriting to 22 is possible)


----------



## unsolved (Feb 19, 2015)

Jokern said:


> When you say _not OBTM_, there is still several other metrics to choose from. Could you be more precise?



I forget the name of the metric where you don't use block moves such as F f and U u. I think it's just one of the half turn metrics?

However you would describe something like this:


```
Solution [001] =  U2 l2 U2 F2 l  F2 l' F2 l2 [inside 6-TFS] ---> U2 r  U2 r' F2 l   @ 0000406465872 nodes with 0006985517899 6-TFS probes   
Solution [002] =  D2 r2 F2 r  F2 r' F2 D2 r2 [inside 6-TFS] ---> D2 r' F2 l  D2 l'  @ 0001824428262 nodes with 0013045561714 6-TFS probes   
Solution [003] =  D2 l2 F2 l' F2 l  F2 D2 l2 [inside 6-TFS] ---> D2 l  F2 r' D2 r   @ 0001844715291 nodes with 0013132289376 6-TFS probes   
Solution [004] =  r  F2 r' F2 l  B2 r2 B2 D2 [inside 6-TFS] ---> l  B2 r' B2 l2 D2  @ 0002432573235 nodes with 0015644898845 6-TFS probes   
Solution [005] =  r  F2 l' U2 l  U2 r2 F2 r' [inside 6-TFS] ---> F2 r  F2 U2 r2 U2  @ 0002433795581 nodes with 0015650127901 6-TFS probes   
Solution [006] =  r  B2 r' U2 r  U2 l2 B2 r' [inside 6-TFS] ---> U2 l  U2 F2 l2 F2  @ 0002506684772 nodes with 0015961661391 6-TFS probes
```


----------



## TDM (Feb 19, 2015)

unsolved said:


> I forget the name of the metric where you don't use block moves such as F f and U u. I think it's just one of the half turn metrics?


I can't understand your code; can you describe the metric you're using?


----------



## qqwref (Feb 19, 2015)

I believe unsolved's metric is just a 4x4x4 version of STM, so the only thing that counts as 1 move is a turn of a single layer by any amount.


----------



## TDM (Feb 19, 2015)

qqwref said:


> I believe unsolved's metric is just a 4x4x4 version of STM, so the only thing that counts as 1 move is a turn of a single layer by any amount.


Oh... is there a name for that?

Also, L' F' L R r2 B2 Rw' U2 Rw' U2 B2 Rw' B2 Rw B2 Rw' B2 Rw2 B2 U2 R L' U L is 30 moves for the case posted in the OP.


----------



## unsolved (Feb 20, 2015)

qqwref said:


> I believe unsolved's metric is just a 4x4x4 version of STM, so the only thing that counts as 1 move is a turn of a single layer by any amount.



Couldn't have said it better myself.

For some reason I was thinking Single Turn Metric was counting a move such as U2 as 2 moves, which, of course, is not correct.

I created the original position by just fusing together the 22 move (STM) for the corner swap with the 15 move (STM) single dedge flip for 37 moves total.

Based on the responses, are the outer block turn solutions the shortest ones for this position if you count moves using STM enumeration?

I am genuinely impressed by the low move counts I have seen. I have no idea how you guys worked them out!


----------



## TDM (Feb 20, 2015)

unsolved said:


> I have no idea how you guys worked them out!


Rw2 B2 Rw' U2 Rw' U2 B2 Rw' B2 Rw B2 Rw' B2 Rw2 B2 (U2) is usually used as an OLL parity alg. However, it also swaps two corners; the first four moves are setting up the corners to be swapped to the right place, and the last four moves are undoing the setup moves.


----------



## Stefan (Feb 20, 2015)

unsolved said:


> For some reason I was thinking Single Turn Metric was counting a move such as U2 as 2 moves, which, of course, is not correct.



STM is slice turn metric, not single turn metric.

Now that this has been cleared up, I suggest you either add "STM" to the thread title or change it to say "God's Number*s*" or switch the content to OBTM (I'd say "the" 4x4 God's Number should correspond to "the" (3x3) God's Number").



unsolved said:


> I am genuinely impressed by the low move counts I have seen. I have no idea how you guys worked them out!



Did you skip the posts where we explained it?


----------



## rokicki (Feb 20, 2015)

The subject of the original post asked for candidates for antipodal positions.

I hereby nominate the 10 positions presented in the 4x4x4 fewest moves challenge run earlier.

I doubt the sort of mostly-solved positions we've seen will be antipodal.

I also doubt any of the 10 positions I nominate are antipodal, but I think those positions are much
more challenging than the ones I've seen posted. And I think they serve as a good benchmark
for how effective solvers of any sort are getting.

And I'm interested in three metrics (I call them OBT = Outer Block Turn, SST = Single Slice Turn,
and BT for Block Turn).


----------



## Mike Hughey (Feb 20, 2015)

rokicki said:


> The subject of the original post asked for candidates for antipodal positions.
> 
> I hereby nominate the 10 positions presented in the 4x4x4 fewest moves challenge run earlier.
> 
> ...



To record this hopefully permanently, here are the second set of 5 (from your website:
1) U L F D B2 F2 U2 R' F2 R2 B2 D2 R' D2 L B R D' U' R2 L' F L2 D F2 Uw2 B Uw2 F' R' Fw2 F' Rw2 R' B' R2 Fw2 L' Uw L2 D' B2 U Rw' Fw Uw' F' Uw' U' R B R U
2) F U R U B' D R U2 R B U2 L D' F' U2 L R B2 D2 R D2 R' B2 Uw2 Rw2 R' D L D2 L2 R Fw2 U L2 B' U Fw' L D2 F2 Rw' Fw2 Rw' Uw' Fw2 Rw D' F U F D
3) F D B D L' U2 F U2 D' B2 F L B F U2 L' F2 R' U2 F2 L B2 R2 B2 Fw2 Uw2 D' B F' Uw2 B R2 Fw2 Uw2 D' U2 Rw U L B U2 Uw' F' Rw2 R2 Fw F2 Uw' B' L B U L
4) R F D L D2 F D U B2 F2 L' B2 U F2 L D2 U2 L U2 R B2 L B2 Uw2 Rw2 F U2 R' B' Uw2 F2 R Uw2 F' Uw' L2 D2 L B2 R' Uw' D2 Fw' Rw R Uw' L2 B D F D
5) F U F U F2 R2 D' R2 B2 D B2 D2 B2 R2 U' F R F' B' D' R2 D' L' Uw2 F' Uw2 U2 Rw2 Fw2 B D F' B D' L2 B2 Rw' Fw2 R' U B U' Rw' Uw R' Fw B U L D R

I can't find the first set - do you have them somewhere?


----------



## ch_ts (Feb 20, 2015)

There were only 5 scrambles not 10.


----------



## Mike Hughey (Feb 20, 2015)

Sorry, I thought those were a new set, since he mentioned 10.


----------



## rokicki (Feb 20, 2015)

Mike Hughey said:


> Sorry, I thought those were a new set, since he mentioned 10.



Oops; sorry. Yes, just those five. Thanks! (I just misremembered the number of positions.)


----------



## unsolved (Feb 21, 2015)

Mike Hughey said:


> To record this hopefully permanently, here are the second set of 5 (from your website:
> 1) U L F D B2 F2 U2 R' F2 R2 B2 D2 R' D2 L B R D' U' R2 L' F L2 D F2 Uw2 B Uw2 F' R' Fw2 F' Rw2 R' B' R2 Fw2 L' Uw L2 D' B2 U Rw' Fw Uw' F' Uw' U' R B R U
> 2) F U R U B' D R U2 R B U2 L D' F' U2 L R B2 D2 R D2 R' B2 Uw2 Rw2 R' D L D2 L2 R Fw2 U L2 B' U Fw' L D2 F2 Rw' Fw2 Rw' Uw' Fw2 Rw D' F U F D
> 3) F D B D L' U2 F U2 D' B2 F L B F U2 L' F2 R' U2 F2 L B2 R2 B2 Fw2 Uw2 D' B F' Uw2 B R2 Fw2 Uw2 D' U2 Rw U L B U2 Uw' F' Rw2 R2 Fw F2 Uw' B' L B U L
> ...



So we are trying to find faster solutions to the positions created from the scrambles above?


----------



## rokicki (Feb 21, 2015)

unsolved said:


> So we are trying to find faster solutions to the positions created from the scrambles above?



Oh, absolutely! Ideally at some point our software will
reach the point where we can find near-optimal solutions
(I don't think we are quite there yet) and start finding
some actual candidates for antipodal positions.

Probably symmetric positions may be more fruitful, as
well as being easier to "prove hard" (less search
required).

It's early days yet. But let's see how good our solvers
can get.


----------



## unsolved (Feb 21, 2015)

rokicki said:


> Oh, absolutely! Ideally at some point our software will
> reach the point where we can find near-optimal solutions
> (I don't think we are quite there yet) and start finding
> some actual candidates for antipodal positions.
> ...



My solver is just a brute-force, "zero-elegance" solver. It just generates moves, no goals in mind, no intermediate evaluation function, and it hunts for any-and-all solutions at the current depth. It does store every position 5 moves from the solved state (and fewer) into a RAM buffer, so it can trim up to 5 plies from the game tree. Here is what I have so far for the first attempt:







Obviously it will not carve too much further into this one.

It does have another specialized database of "centers only" which are solved through 7 turns. That is, if you have everything solved but the centers, it can make an announcement when you are 7 turns from the solved state.


----------



## rokicki (Feb 21, 2015)

unsolved said:


> Here is what I have so far for the first attempt:



Excellent, so now we have a position that we know is at least 13 moves from
the start (if I interpret your screenshot correctly). Do you agree? This is a
start.

Can we find positions that we know are at least 14 moves from start? 15?
(I think we have some from an earlier investigation, but it would be nice
to give them here.)

While these are clearly not proof of antipodal positions, the fact that we've
actually proved a concrete position to be at least a particular distance away
is progress.

If we find a symmetric position and use symmetry to reduce the search, we
can probably get another ply deeper (maybe even two plys).

Long term, in order to raise the lower bound, we need to prove a particular
position to be deeper than the simple pigeonhole argument (or else use
another technique). For instance, some of the subgroup DP approaches
(to calculate counts of canonical move sequences for cosets of subgroups)
may be able to increase the lower bound without finding a concrete position.

Some may argue we are so far from being able to solve a random position
optimally, that this is a fool's errand. But I think there is a lot to be
learned from the attempt.


----------



## unsolved (Feb 21, 2015)

rokicki said:


> Excellent, so now we have a position that we know is at least 13 moves from
> the start (if I interpret your screenshot correctly). Do you agree? This is a
> start.



The program is still searching the 13th ply. So we can say with certainty it is at least 12 moves from a solved state. You can see* (08/36)* right before the PV. That means it is on move number 8 of 36 in the current depth.



rokicki said:


> Can we find positions that we know are at least 14 moves from start? 15?
> (I think we have some from an earlier investigation, but it would be nice
> to give them here.)



Do you mean other positions, or "play into the line" one ply at a time and do 13-ply searches to functionally test for a depth of "13 + d" where d is the number of plies we advance manually?

For example, from the scrambled position, if I play the move *F*, then search 13-ply, we have functionally searched 1 out of the 36 moves to a depth of 14. 
If we recreate the scramble, then play the move* F'*, then repeat the 13-ply search, we have no searched 2 out of the 36 moves to a depth of 14. Etc., Etc.



rokicki said:


> While these are clearly not proof of antipodal positions, the fact that we've
> actually proved a concrete position to be at least a particular distance away
> is progress.



Yes but that branching factor of 36 is a real killer.



rokicki said:


> If we find a symmetric position and use symmetry to reduce the search, we
> can probably get another ply deeper (maybe even two plys).



I am on a 16-core machine but I have parallel searching off. My earlier parallel implementations were very fast, but ultimately flawed, as the intrepid Bruce Norskog was able to demonstrate. I disabled all of the parallel code and stripped out a great deal of the dead wood. If someone wants to take a crack at parallelizing the code, I'm willing to donate the code.

By the way, my move generator only executes 6 lines of C-code to generate a legal 4x4x4 move. It is slowed down by probing the 16 GB hash tables and generating 64-bit hash numbers and resolving hash conflicts. Otherwise it's speed is in the 50 million moves per second range using a single CPU core.



rokicki said:


> Long term, in order to raise the lower bound, we need to prove a particular
> position to be deeper than the simple pigeonhole argument (or else use
> another technique). For instance, some of the subgroup DP approaches
> (to calculate counts of canonical move sequences for cosets of subgroups)
> ...



I have a few ideas regarding optimal solutions as well. Are you familiar with so-called "Dropout Expansion" by Thomas Lincke? Programmers Martin Fierz and Edward Gilbert used this technique to develop automated opening books for their checkers programs using this technique. Their implementation was very effective, making their programs virtually bullet proof in the opening.

http://www.fierz.ch/strategy4.htm

I am convinced this approach would work well for scrolling into a solution-attack line, then backing up as needed. All that is required is an evaluation function, which can be as simple as an enumeration of correct colors per cube side, maybe with goal-directed bonuses for centers to be prefered over edges, and so on. Fixed depth searches with conspiracy numbers to guide the way will insure that positions with color counts improving get searched more deeply than those positions where there is little to no progress, or worse, lost progress.


----------



## cuBerBruce (Feb 21, 2015)

rokicki said:


> Can we find positions that we know are at least 14 moves from start? 15?
> (I think we have some from an earlier investigation, but it would be nice
> to give them here.)



Has the pure dedge flip been proven to require 15 BTM?

Of course, we know of over 86.5 quintillion positions that are at least 13 BTM from solved. In fact, we know a set of over 86.5 quintillion positions that are known to be at least 13 BTM from another set of positions of the same size (and that contains the solved state).

(By "from start" I assume you meant "from solved," since the 4x4x4 positions form a coset space, not a group. So the "start" position can not be any arbitrarily chosen position.)


----------



## unsolved (Feb 22, 2015)

cuBerBruce said:


> Has the pure dedge flip been proven to require 15 BTM?
> 
> Of course, we know of over 86.5 quintillion positions that are at least 13 BTM from solved. In fact, we know a set of over 86.5 quintillion positions that are known to be at least 13 BTM from another set of positions of the same size (and that contains the solved state).
> 
> (By "from start" I assume you meant "from solved," since the 4x4x4 positions form a coset space, not a group. So the "start" position can not be any arbitrarily chosen position.)



It requires 15 moves using STM I am sure of that. 

I compiled a list of positions as a function of depth up to move 32. Here are the counts through depth 16, I have not added the other numbers yet:

http://lightningcloudcomputing.com/OO_4x4x4/info_05.shtml


----------



## Christopher Mowla (Feb 22, 2015)

unsolved said:


> It requires 15 moves using STM I am sure of that.


How are you sure?

I'm sure many thought that the adjacent double parity case (y' 2R2 F r' F') 2R2 U2 2R' U2 2R' U2 2R' U2 (F r F' 2R2 y) could be solved in no fewer than 18 BTM, but this (my) solution is 16 BTM. It uses two wide (double) turns, which each still count as a single block turn each.

Moreover, it probably wasn't imagined that the 2-cycle case r2 u' b 2R' b' u b r' u' 2R' u r 2R b' r2 could be solved in 15 BTM, but I found five 15 BTM length solutions (there are probably more). This algorithm, for example, is 27 turns in your solver's metric but is 15 BTM.


----------



## unsolved (Feb 22, 2015)

cmowla said:


> How are you sure?



Are we talking about the single dedge flip?


----------



## Christopher Mowla (Feb 22, 2015)

unsolved said:


> Are we talking about the single dedge flip?


Yes. The examples I gave are illustrations of when the presence of wide (double) turns lessens the number of BTM an algorithm has. Who's to say that there isn't some single dedge flip algorithm of this category? Sure I researched this particular position for 9 months, but I can't say I'm positive I explored every possible path.


----------



## unsolved (Feb 22, 2015)

cmowla said:


> Yes. The examples I gave are illustrations of when the presence of wide (double) turns lessens the number of BTM an algorithm has. Who's to say that there isn't some single dedge flip algorithm of this category? Sure I researched this particular position for 9 months, but I can't say I'm positive I explored every possible path.



I have searched it to completion. Recall I have the 5-Turns-From-Solution database now, so I only need to explore every 10-ply node in order to see 15 plies distant.

*r2 D2 r' F2 r F2 D2 r D2 l' F2 l F2 D2 r2* is one of the solutions.


----------



## Christopher Mowla (Feb 22, 2015)

unsolved said:


> I have searched it to completion. Recall I have the 5-Turns-From-Solution database now, so I only need to explore every 10-ply node in order to see 15 plies distant.
> 
> *r2 D2 r' F2 r F2 D2 r D2 l' F2 l F2 D2 r2* is one of the solutions.


BTM means "Block Turn Moves", not single slice turn (which you call ply) moves. Bruce specifically mentioned BTM.

Reread this portion of my post.


cmowla said:


> Moreover, it probably wasn't imagined that the 2-cycle case r2 u' b 2R' b' u b r' u' 2R' u r 2R b' r2 could be solved in 15 BTM, but I found five 15 BTM length solutions (there are probably more). *This algorithm, for example, is 27 turns in your solver's metric but is 15 BTM.*


----------



## unsolved (Feb 22, 2015)

cmowla said:


> BTM means "Block Turn Moves", not single slice turn (which you call ply) moves.



Ok, understood.

Then disregard my remark, my program does not use this metric at all.


----------



## rokicki (Feb 26, 2015)

cuBerBruce said:


> Has the pure dedge flip been proven to require 15 BTM?



I've been reviewing the earlier runs of my OBTM optimal solver.

The position:

2L 2R U' 2R2 F2 2R2 U 2R2 U' F2 U 2L' 2R 

(I'm using 2L here instead of l to mean a slice turn)

has been searched through 16 moves in the OBTM without a solution.

So here's a concrete position that requires at least 17 moves in the OBTM.

I've got a few more positions proved to require at least 17 moves.
(They were when I was trying to solve some top edge cases.)

Proving these positions took a great deal of CPU time. I should
probably start with some more-random positions.


----------



## ch_ts (Feb 26, 2015)

rokicki said:


> I've got a few more positions proved to require at least 17 moves.
> (They were when I was trying to solve some top edge cases.)
> 
> Proving these positions took a great deal of CPU time. I should
> probably start with some more-random positions.



How much CPU time to search through depth 16?


----------



## rokicki (Feb 26, 2015)

ch_ts said:


> How much CPU time to search through depth 16?



Days and days (but just one thread). Since the patterns were "nearly" solved,
my pruning tables didn't help too much though, and I also don't think I used the
best pruning tables. I think if I use multiple threads and start with more random
positions, I can probably get a few more plies.

I may even be able to contrive a position that is as deep as my pruning tables
go, specifically to try to get an easy position to prove deep.

And if I can ensure the position has enough symmetry, I can probably get a bit
deeper yet.

But my 4x4 code is probably not nearly as advanced or mature as other
posters on this site.


----------



## unsolved (Feb 27, 2015)

rokicki said:


> But my 4x4 code is probably not nearly as advanced or mature as other
> posters on this site.



I use a 6 separate 64-bit variables to represent the 4x4x4 cube. That way, I can use very fast bit-operations to generate moves, rather than more expensive matrix updates. Example:


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

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

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

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

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

return new_cube;
}
```

The above executes the move U. It is only 6 lines of code (though the last one is long, it still executes quickly).

I have also been experimenting with the concept of the *Compound Move*. There is nothing that says you can't code how move pairs, triplets (or more) change the cube in one fell swoop. I am writing a bit monitoring routine that will write the C-code for me so that I can handle U R, U R', U R2, U F, U F', U F2.... U B, U B', U B2 etc as one move generator call. It complicates the dispatch function and the list of Procedure Pointers grows in proportion to the node count at the equivalent search depth, but in the case of move pairing you are guaranteed to double the speed of the move generator.

*Edit:*

Here are the numbers I get for the 4x4x4 "canonical sequences" possible as a function of depth.


----------



## Christopher Mowla (Jul 5, 2015)

Can someone run this position through his solver? I'm curious what the upperbound is for this 4x4x4 position.

_Note that the generating scramble is in old WCA notation!_
L2 F r2 B2 U l2 U' l2 U l2 U' B2 r2 F' x l2 U F L U R2 F r2 F' R2 U' L' F' U' l2 x F2 U' l' r' U F' L U' F l r F' U L' F' x2 L2 x L' F d2 F' L U2 L' F d2 F' L U2 x' F2 d B2 R' f' R B2 R' f R d' F2


----------



## rokicki (Jul 5, 2015)

Christopher Mowla said:


> Can someone run this position through his solver? I'm curious what the upperbound is for this 4x4x4 position.
> 
> _Note that the generating scramble is in old WCA notation!_
> L2 F r2 B2 U l2 U' l2 U l2 U' B2 r2 F' x l2 U F L U R2 F r2 F' R2 U' L' F' U' l2 x F2 U' l' r' U F' L U' F l r F' U L' F' x2 L2 x L' F d2 F' L U2 L' F d2 F' L U2 x' F2 d B2 R' f' R B2 R' f R d' F2



What metric would you like? I can do outer block turn, single slice turn, or block turn.


----------



## Christopher Mowla (Jul 5, 2015)

rokicki said:


> What metric would you like? I can do outer block turn, single slice turn, or block turn.


OBTM (since this is the metric you all are first shooting for with god's number). Thank you very much!


----------



## rokicki (Jul 9, 2015)

Christopher Mowla said:


> Can someone run this position through his solver? I'm curious what the upperbound is for this 4x4x4 position.
> 
> _Note that the generating scramble is in old WCA notation!_
> L2 F r2 B2 U l2 U' l2 U l2 U' B2 r2 F' x l2 U F L U R2 F r2 F' R2 U' L' F' U' l2 x F2 U' l' r' U F' L U' F l r F' U L' F' x2 L2 x L' F d2 F' L U2 L' F d2 F' L U2 x' F2 d B2 R' f' R B2 R' f R d' F2



Did I transcribe this correctly? Is this what it looks like in SiGN notation?

2L2 2F 2R2 B2 U 2L2 U' 2L2 U 2L2 U' B2 2R2 2F' x 2L2 U 2F 2L U 2R2 2F 2R2 2F' 2R2 U' 2L' 2F' U' 2L2 x 2F2 U' 2L' 2R' U 2F' 2L U' 2F 2L 2R 2F' U 2L' 2F' x2 2L2 x 2L' 2F 2D2 2F' 2L U2 2L' 2F 2D2 2F' 2L U2 x' 2F2 2D B2 2R' 2F' 2R B2 2R' 2F 2R 2D' 2F2

I notice the corners and four edges are fully solved.


----------



## Christopher Mowla (Jul 9, 2015)

rokicki said:


> Did I transcribe this correctly? Is this what it looks like in SiGN notation?
> 
> 2L2 2F 2R2 B2 U 2L2 U' 2L2 U 2L2 U' B2 2R2 2F' x 2L2 U 2F 2L U 2R2 2F 2R2 2F' 2R2 U' 2L' 2F' U' 2L2 x 2F2 U' 2L' 2R' U 2F' 2L U' 2F 2L 2R 2F' U 2L' 2F' x2 2L2 x 2L' 2F 2D2 2F' 2L U2 2L' 2F 2D2 2F' 2L U2 x' 2F2 2D B2 2R' 2F' 2R B2 2R' 2F 2R 2D' 2F2
> 
> I notice the corners and four edges are fully solved.


The corners and centers are fully solved. It's just a scramble of wings. Here is the correct translation:
L2 F 2R2 B2 U 2L2 U' 2L2 U 2L2 U' B2 2R2 F' x 2L2 U F L U R2 F 2R2 F' R2 U' L' F' U' 2L2 x F2 U' 2L' 2R' U F' L U' F 2L 2R F' U L' F' x2 L2 x L' F 2D2 F' L U2 L' F 2D2 F' L U2 x' F2 2D B2 R' 2F' R B2 R' 2F R 2D' F2

I got this translation immediately with a translator I wrote in Mathematica (I used this subroutine to convert all algorithms on the 4x4x4 parity algorithms page to SiGN to avoid human error), just in case you want to code it for future use. 


Spoiler: 4x4x4 WCAToSiGN Translator


----------



## rokicki (Jul 10, 2015)

Christopher Mowla said:


> The corners and centers are fully solved. It's just a scramble of wings. Here is the correct translation:
> L2 F 2R2 B2 U 2L2 U' 2L2 U 2L2 U' B2 2R2 F' x 2L2 U F L U R2 F 2R2 F' R2 U' L' F' U' 2L2 x F2 U' 2L' 2R' U F' L U' F 2L 2R F' U L' F' x2 L2 x L' F 2D2 F' L U2 L' F 2D2 F' L U2 x' F2 2D B2 R' 2F' R B2 R' 2F R 2D' F2



I've run this through my OBTM reduction solver, and the shortest reduction is 14 moves. I've completed
searching through depths 14 and 15 without a total solution, which means it is at least 16 moves from
solved.

I've found solutions (by completing a reduction solve) of length 30. So the true distance is somewhere
between 16 and 30, inclusive.

This position gives my reduction solver a *bit* more difficulty than random positions do, because with
the middle solved in the starting position, my deepest table (the one for the middle cubies) is
made largely impotent.

Are you interested in the actual length-30 solves I have?


----------



## Christopher Mowla (Jul 10, 2015)

rokicki said:


> Are you interested in the actual length-30 solves I have?


No, that's okay. Knowing that it is <=30 moves is sufficient. Thanks for your time.


----------



## ch_ts (Jul 10, 2015)

Is there something special about this position? Is it for your method that you previously alluded to? Anything you can share with us about that?


----------



## Waran (Jul 13, 2015)

rokicki said:


> Oh, absolutely! Ideally at some point our software will
> reach the point where we can find near-optimal solutions
> (I don't think we are quite there yet) and start finding
> some actual candidates for antipodal positions.
> ...



I have a database with more then 670 symmetric positions. 
They might be useful to get one or maybe two plys deeper. 

All these positions are generated in 39 or less moves (btm). 
Currently only about 80 positions require more then 29 moves. 
So this makes them all potential candidates for antipodal positions.

Maybe someone can run the two hardest positions below through the solver?


Here are the original algorithms in SSE notation. 

Deep Edge Hexagon
D B D' F2 SD WF U2 R' F' B2 D' F' U2 WR F' WR
TR2 F' TD2 L' F' MR2 TF2 R' TU2 F2 R
TU' L2 D L TU2 B SD'
TB' TU2 TR' TU2 TR' (39 btm)

2 Dual-Color Rings
L B' R' WF2 R' D2 WF2 L WF D2 R WF2 D' R' B' L'
TF2 TD2 D L U' TR2 U2 F2 L D2 U
B' U TB' D2 F' TU2 TB U
TU B' F' R2 (39 btm)


Translated in SiGN, the algorithms look like this:

Deep Edge Hexagon
D B D' F2 e' y' s U2 R' F' B2 D' F' U2 m' F' m'
Rw2 F' Dw2 L' F' 2R2 Fw2 R' Uw2 F2 R
Uw' L2 D L Uw2 B e y
Bw' Uw2 Rw' Uw2 Rw' (39 btm)

2 Dual-Color Rings
L B' R' s2 R' D2 s2 L s D2 R s2 D' R' B' L'
Fw2 Dw2 D L U' Rw2 U2 F2 L D2 U
B' U Bw' D2 F' Uw2 Bw U
Uw B' F' R2 (39 btm)


----------

