# What is God's number on a 4x4 Rubik's cube?



## rubiksarlen (Mar 16, 2012)

http://cube20.org/

We all know that God's number for a 3x3x3 Rubik's cube is 20 moves. But I have been wondering lately what is God's number for a 4x4x4 Rubik's cube? :confused:


----------



## qqwref (Mar 16, 2012)

Nobody knows, and it's way too difficult to calculate. The best estimates are somewhere in the 30s. /thread


----------



## Lucas Garron (Mar 16, 2012)

Quick, someone register cube21.org to cube50.org


----------



## Dacuba (Mar 16, 2012)

Remembers me of the surprise challenge thread. When I clicked this one, I first was like "oh no, not again"


----------



## cubernya (Mar 16, 2012)

It's been proven to be at least 33 (according to multiple sites), but as far as I know we don't even have an upper bound. What I want to know is how they got the lower bound


----------



## cuBerBruce (Mar 16, 2012)

theZcuber said:


> but as far as I know we don't even have an upper bound


 
67 block turns
77 single-layer turns
82 twists (face turns)

http://cubezzz.duckdns.org/drupal/?q=node/view/93


----------



## Christopher Mowla (Mar 16, 2012)

cuBerBruce said:


> 67 block turns
> 77 single-layer turns
> 82 twists (face turns)
> 
> http://cubezzz.dyndns.org/drupal/?q=node/view/93


Hey Bruce, could you list some scrambles which generate the worst positions (it doesn't matter how long the scrambles are).


----------



## AbstractAlg (Mar 16, 2012)

theZcuber said:


> It's been proven to be at least 33 (according to multiple sites), but as far as I know we don't even have an upper bound. What I want to know is how they got the lower bound


 
prove that you can't select all four aces in the deck of cards with only three selections.
now imagine that after you have selected one card from deck you return it and remove few non-aces cards from the deck depnding on last selected card... all the way to be left with only 4 cards, which are, of course 4 aces.
similar principle.

waiting to super-uber-computers to calculate all the states of 4x4 and fewest move solve for each one.
one can't simply calculate the 4God's number, but dozens can.


----------



## SenileGenXer (Mar 16, 2012)

We seem to have a lot of computing power now. I think it should be calculable. 

How much computing power was needed to prove 20 on a 3x3 and how much time has gone by?


----------



## StachuK1992 (Mar 16, 2012)

It was just 2 years ago, and read up.


----------



## AbstractAlg (Mar 16, 2012)

I thinks it's still incalculable. Those are real big numbers, much more positions. :/


----------



## Owen (Mar 16, 2012)

I don't think we can even calculate optimal solutions yet...


----------



## StachuK1992 (Mar 16, 2012)

Of course we can find optimal solutions, just not as efficiently as we'd like.
Making a solver for any puzzle isn't hard - doing it efficiently /is/.


----------



## SenileGenXer (Mar 17, 2012)

That was 35 years of CPU time. That's a rounding error to projects like SETI at home. 

Nonetheless a 4x4 would require an astronomical amont more. Probably more than all the distributed computing projects put together.
Plus interested qualified people doing the coding.

I would be interesting to know god's answers.


----------



## Christopher Mowla (Mar 17, 2012)

SenileGenXer said:


> We seem to have a lot of computing power now. I think it should be calculable.





rokicki said:


> Will the diameter of the 4x4x4 be known in my lifetime? I suspect it will be, despite the fact that *just solving a single random 4x4x4 position optimally probably requires more CPU time* using current techniques than were used to determine the diameter of the 3x3x3


Link.


----------



## qqwref (Mar 17, 2012)

Indeed... and there are about 10^26 million times as many 4x4 positions as there are 3x3 positions (that's a hundred million million million million). So even if it was as easy to solve a 4x4 scramble optimally as it is to solve a 3x3 scramble optimally, we'd still need a hundred million million million million times as long to get God's Algorithm as we took to do it for the 3x3...

Considering we're only a few orders of magnitude from the atomic computing limit, I feel like I can predict that this computation cannot be done using our current knowledge of optimal-solving techniques.


----------



## ben1996123 (Mar 17, 2012)

qqwref said:


> Indeed... and there are about 10^26 million times as many 4x4 positions as there are 3x3 positions (that's a hundred million million million million). So even if it was as easy to solve a 4x4 scramble optimally as it is to solve a 3x3 scramble optimally, we'd still need a hundred million million million million times as long to get God's Algorithm as we took to do it for the 3x3...
> 
> Considering we're only a few orders of magnitude from the atomic computing limit, I feel like I can predict that this computation cannot be done using our current knowledge of optimal-solving techniques.



How do we actually know that Kociemba generates optimal solutions? I'm guessing some (probably confusing) group theory stuff.


----------



## Kirjava (Mar 17, 2012)

ben1996123 said:


> How do we actually know that Kociemba generates optimal solutions? I'm guessing some (probably confusing) group theory stuff.


 
Kociemba isn't used for generating optimal solutions - that is done by brute force. Simple to understand why they must be optimal.

IIRC when proving god's alg they didn't optimally solve every position, 20 moves is all they needed.


----------



## ben1996123 (Mar 17, 2012)

Kirjava said:


> Kociemba isn't used for generating optimal solutions - that is done by brute force. Simple to understand why they must be optimal.



oh ok.



Kirjava said:


> IIRC when proving god's alg they didn't optimally solve every position, 20 moves is all they needed.



yeah, I read this on cube20.org. It says the computers they used could solve 0.36 positions/sec optimally, but 3900 positions/sec in <=20 moves.


----------



## Cool Frog (Mar 17, 2012)

AbstractAlg said:


> *prove that you can't select all four aces in the deck of cards with only three selections*.
> now imagine that after you have selected one card from deck you return it and remove few non-aces cards from the deck depnding on last selected card... all the way to be left with only 4 cards, which are, of course 4 aces.
> similar principle.
> 
> ...


 
Is it because you are only taking 3 cards total?

SURPRISE CHALLENGE IN THE MIDDLE OF A THREAD.

Do a 4x4 Linear FMC and post movecount (Don't have to type out all the moves)


----------



## aronpm (Mar 17, 2012)

here's a 4x4 solve

Scramble: U R L2 u' f' F L F2 L2 u' D R' L U' R2 f' u' r2 L2 f' F' r' F2 B2 U' r2 R' D2 f' F' r2 U2 F R' B u F u2 R2 r'

F r u B2 r' F2 u2 L' U' D2 r' U u2 B D' r2 U2 F r2 D' f2 u2 // reduction (22 moves)
D2 R' B U2 D' F2 U R2 B' U L F L U R B R2 // 3x3 (17 moves)


----------



## cubecraze1 (Mar 17, 2012)

aronpm said:


> here's a 4x4 solve
> 
> Scramble: U R L2 u' f' F L F2 L2 u' D R' L U' R2 f' u' r2 L2 f' F' r' F2 B2 U' r2 R' D2 f' F' r2 U2 F R' B u F u2 R2 r'
> 
> ...


did that really happen?


----------



## aronpm (Mar 17, 2012)

cubecraze1 said:


> did that really happen?


 
yeah but i didn't come up with that solution computer did


----------



## cubecraze1 (Mar 17, 2012)

aronpm said:


> yeah but i didn't come up with that solution computer did


 
who did?


----------



## Stefan (Mar 17, 2012)

qqwref said:


> Indeed... and there are about 10^26 million times as many 4x4 positions as there are 3x3 positions (that's a hundred million million million million). So even if it was as easy to solve a 4x4 scramble optimally as it is to solve a 3x3 scramble optimally, we'd still need a hundred million million million million times as long to get God's Algorithm as we took to do it for the 3x3...
> 
> Considering we're only a few orders of magnitude from the atomic computing limit, I feel like I can predict that this computation cannot be done using our current knowledge of optimal-solving techniques.



We're not just making computers faster, we're also making their memory bigger. IIRC, Tom told me a while ago that search speed scales about proportional to memory size. So if you take a computer "only" a million million times faster and memory "only" a million million times bigger, that could suffice.


----------



## tx789 (Mar 17, 2012)

Woul there be a pattern of gods number between 2x2 3x3 4x4 5x5. So you could possibly find out gods number for 6x6- yxyxy


----------



## RNewms27 (Mar 17, 2012)

cubecraze1 said:


> who did?


 
Mister roboto. But I would like to know what was used to get the solution.


----------



## TheAwesomeAlex (Mar 17, 2012)

the number of moves to solve anything is the number of moves it takes to scramble it or less


----------



## aronpm (Mar 17, 2012)

TheAwesomeAlex said:


> the number of moves to solve anything is the number of moves it takes to scramble it or less


 
Thank you for this insightful information. We now know God's number for the 4x4.


----------



## AbstractAlg (Mar 17, 2012)

aronpm said:


> Thank you for this insightful information. We now know God's number for the 4x4.


 


But, some of the solving-all-the-permutations programs used approach not to solve each permutation, but to scramble the cube to each permutation.
I mean, you don't scramble the cube and then try to solve it optimally, but force a scramble to get to each and every permutation of the cube.
All the previous permutation pattern being stored into some array and checked whether or not the previous best (shortest) scramble for the given pattern has lower move count than the current one.


----------



## guusrs (Mar 18, 2012)

Back in the 80's I once made some statistic calculations on the number of moves for God's algorithm. This was based on the number of independent and identically distributed (iid) scrambles you need to make 90% sure to cover all possible scrambles. For the 3x3x3 I estimated 21 moves and for 4x4x4 at was something like *35* or so (I don't remember exactly anymore). I have to dig up some old papers. 

Note that if you choose x^n iid scrambles out of x possible scrambles your covering precentage is (100% x (1 – ((1/_e_)^n))). Where _e_ is the mathematical constant, approximately equal to 2.71828 

So for n=1 the precentage is about 63%.


----------



## rokicki (Mar 19, 2012)

*God's Number for 4x4x4*



ben1996123 said:


> yeah, I read this on cube20.org. It says the computers they used could solve 0.36 positions/sec optimally, but 3900 positions/sec in <=20 moves.


 
This is for single random positions. For cosets of Kociemba's subgroup, we could solve about a billion positions a second in <= 20 moves.

It does seem inconceivable to brute-force God's Number for the 4x4x4, but I think we are learning new and better techniques all the time. As long as all we care about is the diameter, I think optimally solving positions with significant symmetry will most likely give us at least one of the antipodes. From there we can plan how to prove all positions can be solved in that number of moves. And as Stefan points out, optimally solving single positions speeds up as the product of memory size and CPU speed. And optimally solving all highly symmetrical positions is much easier than n * solving one highly symmetrical position (using coset techniques).

I mean, if you think about it, it was only a few short years ago that Kunkle and Cooperman proved 26 was an upper bound in the half-turn metric; progress has been surprisingly (and unexpectingly) rapid since then, much more so than simple technology would dictate.


----------



## spyr0th3dr4g0n (Apr 2, 2012)

Presuming that a supercomputer was rented, approximately how long would it take to brute force it?


----------



## Stefan (Apr 2, 2012)

spyr0th3dr4g0n said:


> Presuming that a supercomputer was rented, approximately how long would it take to brute force it?


 
Today's technology? I'm guessing a couple sextillion years, give or take a few orders of magnitude.

edit: oh cool, it wasn't censored


----------



## whauk (Apr 2, 2012)

a 4x4 has no group-structure because of the same colored centers. i dont know much about the theory behind finding god's number but i assume this could be a problem.


----------



## qqwref (Apr 2, 2012)

Yeah, that could definitely be a potential problem with a coset approach... but seeing as we still can't even optimally solve a random scramble, I think we'd have to get around much bigger problems than that.


----------



## AbstractAlg (Apr 4, 2012)

are 4x4 centers same?
I mean, do we talk about regular 4x4 or a 4x4 super cube? super cube could be somehow managed by group theory, I think.


----------



## Florian (Apr 4, 2012)

I don't know anything about optimal solving but I say God's number is 56. 
Who knows why?


----------



## Stefan (Apr 6, 2012)

Florian said:


> I don't know anything about optimal solving but I say God's number is 56.
> Who knows why?


 
Because it's the number of pieces and you think God's 3x3 number also equalled its number of pieces (I'd say it really has 21 pieces).


----------



## tx789 (Apr 6, 2012)

Well it's at least 40 I wonder if there's a pattern between god number for 2x2-3x3 3x3-4x4 ect


----------



## Dacuba (Apr 6, 2012)

I doubt that there is any pattern for God's numbers. Just because the 2x2 and 3x3 and 4x4 are very different compared to each other (3x3 has no center pieces, 2x2 has no edges nor centerpieces). I don't think they fit in a scheme in that way.


----------



## Chrisalead (Apr 6, 2012)

I never say I had any justification for this ! I said "I Think" that's all. It's simply my personal feeling about this. One thing is sure : that kind of maths are really hard for human beings. This reminds me of the Syracuse conjecture.


----------



## asportking (Apr 6, 2012)

I imagine if you tried hard enough, and you already knew God's number for three or four cubes, you could find a pattern. However, I doubt it would be anything as simple as "multiply the cube size by seven," and you'd probably have to figure out a few more Gods' numbers in order to confirm the pattern.


----------



## AbstractAlg (Apr 6, 2012)

again me, with crazy examples.
find next number in row:
1, 2, 4, ...?

It could be 8 if you look this as powers of 2.
It could be 7 if you look this that increment between every two numbers rises for 1.
It can be any number actually, unless you give some rule or function to follow (it depends on previous number, it's arithmetic array, it's geometrical array, it depends on previous two numbers...)

Meaning, the pattern could exist, but as we know, even the simplest math arrays like Fibonachi (don't know how to spell) row have very big formulas, complicated with imaginary parts and square and cubic roots.
So even if pattern does exist, I believe we could never calculate it.


----------



## LNZ (Apr 7, 2012)

For the Fibonacci numbers at least, there is an easy and very accurate approximation expression:

F(n)=(1/sqrt(5))*G^n where G = Golden ratio = (1 + sqrt(5))/2

Example #1: n=5, F(5)=4.95967...... , exact value of F(5)=5 

Example #2: n=2, F(2)=1.17082......, exact value of F(2)=1


----------



## AbstractAlg (Apr 7, 2012)

LNZ said:


> For the Fibonacci numbers at least, there is an easy and very accurate approximation expression:
> 
> F(n)=(1/sqrt(5))*G^n where G = Golden ratio = (1 + sqrt(5))/2
> 
> ...


 
To be precise: Fibonacci - Wolfram|Alpha


----------



## Marco Aurelio (Dec 1, 2012)

Well, an n x n x n cube can be optimally solved with Θ(n2 / log(n)) moves. [by Wikipedia]
But I don't know how to do this calculation


----------



## bobthegiraffemonkey (Dec 1, 2012)

Marco Aurelio said:


> Well, an n x n x n cube can be optimally solved with Θ(n2 / log(n)) moves. [by Wikipedia]
> But I don't know how to do this calculation



Don't trust Wikipedia to get everything correct. As far as I know, a method of solving an nxnxn cube which was of Θ(n^2 / log(n)) was found. That provides an upper bound of how fast God's number grows, it doesn't say how fast it grows or what the formula for God's number actually is (assuming such a formula can ever be found).

Basically, for every n, it is possible to solve a fully scrambled nxnxn cube using no more than x((n^2)/log(n)) moves, for some constant x which is the same for all n. I can't bothered checking if (n^2)/log(n) is actually correct, but it looks roughly like what I remember it being.


----------



## tx789 (Dec 1, 2012)

31 is my estimate now since if you only turn two layers it reduced to a 2x2 and gods number for a 2x2 is 11 and if you only turn the outer layers it reduced to a 3x3 which gods number is 20 abd 20+11=31


----------



## tim (Dec 1, 2012)

tx789 said:


> 31 is my estimate now since if you only turn two layers it reduced to a 2x2 and gods number for a 2x2 is 11 and if you only turn the outer layers it reduced to a 3x3 which gods number is 20 abd 20+11=31



You need to pair up edges and put them in the right spot relative to your centers as well.


----------



## tx789 (Dec 1, 2012)

tim said:


> You need to pair up edges and put them in the right spot relative to your centers as well.


opitmal reduction isn't the shortest 4x4 solution. Still finding this out will be hard what about the 13ish quintillion solutions that look like a 3x3 but have parity can't that be solved in 11 moves 

finding this out will take a while there's 
7,401,196,841,564,901,869,874,093,974,498,574,336,000,000,000 
7.4 quattuordecillion
7.401196841564901869874093974498574366e+45 


7.4 quintillion quintillion quintillion i think


----------



## TMOY (Dec 1, 2012)

tx789 said:


> opitmal reduction is the shortest 4x4 solution.


Well, no. Here is a counterexample: apply the following 6-move scramble:
Lw' U R' U' Lw R2
Now perform optimal reduction:
x' Rw'' D R' D' Rw (5 moves)
If optimal reduction yielded the shortest solution, you should be able to finish the solve in 1 move or less by now. This is obviously not the case.


----------



## Stefan (Dec 1, 2012)

bobthegiraffemonkey said:


> Don't trust Wikipedia to get everything correct. As far as I know, a method of solving an nxnxn cube which was of Θ(n^2 / log(n)) was found. That provides an upper bound of how fast God's number grows, it doesn't say how fast it grows or what the formula for God's number actually is (assuming such a formula can ever be found).



Please don't illegitimately badmouth Wikipedia, especially when it's you who doesn't know the difference between O and Θ.


----------



## CarlBrannen (Dec 2, 2012)

Hmmm. I've a 4x4x4 in my hand. If I keep the TFL corner unmoved, there are 36 possible moves. Assuming I want to eliminate repeated moves like RR = R2, I get 33 moves. But I also have to eliminate stuff like R 2R R' so let's call it about 30 available moves per turn.

The number of positions is 7.40E+45, according to wikipedia, so this gives a lower bound estimate (using Shannon information theory) of around log_30(7.40E+45) = 31.05 moves, so I'm going to guess 32 or 33.


----------



## tx789 (Dec 2, 2012)

TMOY said:


> Well, no. Here is a counterexample: apply the following 6-move scramble:
> Lw' U R' U' Lw R2
> Now perform optimal reduction:
> x' Rw'' D R' D' Rw (5 moves)
> If optimal reduction yielded the shortest solution, you should be able to finish the solve in 1 move or less by now. This is obviously not the case.



I meant isn't


----------



## Swordsman Kirby (Dec 3, 2012)

Stefan said:


> Please don't illegitimately badmouth Wikipedia, especially when it's you who doesn't know the difference between O and Θ.



Blah, Stefan beat me to it again.


----------



## uberCuber (Dec 3, 2012)

tx789 said:


> 31 is my estimate now since if you only turn two layers it reduced to a 2x2 and gods number for a 2x2 is 11 and if you only turn the outer layers it reduced to a 3x3 which gods number is 20 abd 20+11=31



I'm not sure how much sense it makes to separate wide turns and outer-layer turns like this because, for example, you can't even solve the centers of any scramble with only wide turns.


----------



## userman (Dec 19, 2012)

http://www.wolframalpha.com/input/?i=gods+number

Look at the description. Oh god.


----------



## Ickathu (Dec 19, 2012)

*cringe*
Really, "minimum" number?! :fp


----------



## Noahaha (Dec 19, 2012)

Ickathu said:


> *cringe*
> Really, "minimum" number?! :fp



I guess the FMC WR will be 20 forever 


EDIT: looking at it again, it does say the right thing, just in a poorly worded way.


----------



## KottenCube (Dec 20, 2012)

Now please don't go asking for bigger cube god numbers. It took day with Google computers for a 3x3, imagine how long it would take them with a 4x4.


----------



## Lucas Garron (Dec 20, 2012)

userman said:


> http://www.wolframalpha.com/input/?i=gods+number
> 
> Look at the description. Oh god.



Then leave feedback with an improved description. They listen.
(The description is based on MathWorld.)


----------



## CubeRoots (Dec 20, 2012)

I don't see what's wrong with this description, it's correct.


----------



## Stefan (Dec 20, 2012)

The number involves both a maximum and a minimum, and "minimum" and "required" both cover the minimum aspect while the maximum aspect is missing. Should be "maximum number of turns required" or "minimum number of turns sufficient".


----------



## tx789 (Dec 20, 2012)

There's 7.4x10^45 and a 3x3 has 4.3x10^18 so if it takes one day to do 43 quintillion(4.3x10^18) it would take approx years (no calulator likes you putting in the 7.4x10^45 or at least true iOS one)


----------



## Ickathu (Dec 20, 2012)

but when you add in the increased speed and strength and power of technology and computers, I estimate that Google could crack it in about 2 years. I wonder how fast it could be calculated if you used all the supercomputers and processing power that the US government uses... Not that that would happen, of course, but I bet that could do it in 6 months to a year.


----------



## RNewms27 (Dec 20, 2012)

tx789 said:


> There's 7.4x10^45 and a 3x3 has 4.3x10^18 so if it takes one day to do 43 quintillion(4.3x10^18) it would take approx years (no calulator likes you putting in the 7.4x10^45 or at least true iOS one)



From cube20.org about the 3x3:

"We partitioned the positions into 2,217,093,120 sets of 19,508,428,800 positions each.
We reduced the count of sets we needed to solve to 55,882,296 using symmetry and set covering.
We did not find optimal solutions to each position, but instead only solutions of length 20 or less.
We wrote a program that solved a single set in about 20 seconds.
We used about 35 CPU years to find solutions to all of the positions in each of the 55,882,296 sets."

Symmetry will make the numbers smaller, but 4x4 solutions are also much longer.


----------



## Stefan (Dec 20, 2012)

Ickathu said:


> but when you add in the increased speed and strength and power of technology and computers, I estimate that Google could crack it in about 2 years. I wonder how fast it could be calculated if you used all the supercomputers and processing power that the US government uses... Not that that would happen, of course, but I bet that could do it in 6 months to a year.



I'd like to see how you calculated those times.


----------



## Ickathu (Dec 20, 2012)

Stefan said:


> I'd like to see how you calculated those times.



computerz get fazters, not uber fazt, I like the number 2, yearz seems like a good unit. Government haz bunches of cpus, probably 4 or more times cpu power than goooogle. 6 monfz.

i.e., I didn't.


----------



## qqwref (Dec 21, 2012)

Uh, the problem is 1.7 * 10^26 times harder just in terms of the number of positions alone. That is about a sixth of a billion billion billion. To crack it in 170 million days (which is about 465,000 years) we would need a billion billion times as much computing power as Google used for the cube20 experiment. And oh yeah, we also have to factor in that solving each position takes longer (have we even solved ONE random 4x4x4 position optimally yet?), that we would need much more storage space (an exabyte is far far too small), and that dividing the search space into cosets is much harder for 4x4x4 (since it's not a group).

I think it's absolutely fair to say that this won't be computed in the lifetime of anyone on this forum now.


----------



## Owen (Dec 21, 2012)

qqwref said:


> I think it's absolutely fair to say that this won't be computed in the lifetime of anyone on this forum now.



Bummer, I am really curious about this.


----------



## tx789 (Dec 21, 2012)

qqwref said:


> I think it's absolutely fair to say that this won't be computed in the lifetime of anyone on this forum now.


You never know still


----------



## athena (Mar 28, 2013)

i'm going to make a wild guess that it's 77 single layer turns.
i found the pattern below which holds for n=1 to 3.

1^3 - 1^2 + 1^1 - 1^0 = 0
2^3 + 2^2 - 2^1 + 2^0 = 11
3^3 - 3^2 + 3^1 - 3^0 = 20
4^3 + 4^2 - 4^1 + 4^0 = 77
5^3 - 5^2 + 5^1 - 5^0 = 104
etc.

i doubt it's correct but i thought i would share.
i saw the current upper bound on n=4 is 77 here: http://cubezzz.dyndns.org/drupal/?q=node/view/93
so we just need to get it lower than 77 to throw away this pattern.


----------



## ben1996123 (Mar 28, 2013)

athena said:


> 1^3 - 1^2 + 1^2 - 1^0 = 0
> 2^3 + 2^2 - 2^2 + 2^0 = 11
> 3^3 - 3^2 + 3^1 - 3^0 = 20
> 4^3 + 4^2 - 4^2 + 4^0 = 77
> 5^3 - 5^2 + 5^5 - 5^0 = 104



yeah you're bad at maff, I also doubt its correct.


----------



## cuBerBruce (Mar 28, 2013)

athena said:


> i'm going to make a wild guess that it's 77 single layer turns.
> i found the pattern below which holds for n=1 to 3.
> 
> 1^3 - 1^2 + 1^2 - 1^0 = 0
> ...



The number 20 for 3x3x3 restricts turns to face layers only. Allowing central layer turns, it's likely to be 18 or 19 (although I'm not aware 20 has been ruled out with certainty).

I also presume 77 to be a rather weak upper bound on 4x4x4. A similar technique on 3x3x3 resulted in a 29-move upper bound (face turns).


----------



## qqwref (Mar 28, 2013)

That, plus:
- you can't do unique cubic interpolation on only two or three data points
- God's number isn't O(n^3), it's O(n^2/log n) (iirc).


----------



## Christopher Mowla (Mar 28, 2013)

athena said:


> i'm going to make a wild guess that it's 77 single layer turns.
> i found the pattern below which holds for n=1 to 3.
> 
> 1^3 - 1^2 + 1^1 - 1^0 = 0
> ...


Obviously you made a few typos (I fixed them in the quote above), but writing this pattern as a formula, it gives a value of 8381 slice half turns for the 20x20x20. I attempted to make a formula myself for this while back, and it seemed to give values larger than what God's number probably is for very large cubes. Based on my formula, GN for the 20x20x20 cannot be more than 867 slice half turns, and Mr. Rokicki claims that it must be at least 682. Even if GN for n = 20 is 1500 slice half turns, 8381 is a lot more (which also supports qqwref's comment). So 77 is most likely too high (based on my formula, it's going to be at most 63...it's most likely in the mid 40s).

EDIT: And I'm just playing here, but when I mentioned that GN for 4x4x4 is most likely in the mid 40s, extrapolating those calculations to the 100x100x100 gives about 15,000. (Just to make even more stupid guesses, based on my formula, GN for the 105^3 should be no more than 18k...just because someone is solving that one right now).


----------



## IAssemble (Jun 21, 2013)

*How many turns does it take you to solve a 4x4x4 cube?*

Can you solve a 4x4x4 cube in fewer turns than MultiCuber 3? 






Enjoy!


----------



## ben1996123 (Jun 21, 2013)

50 moves wat !

I was expecting it to take about 80

also, no


----------



## AvGalen (Jun 21, 2013)

I have never been a big fan of 444fmc because I can really only do a very optimized reduction+avoidparity+333fmc. But I think my lowest ever was around 65 and most were much more like 80


----------



## IAssemble (Jun 21, 2013)

To be fair it averages about 51...


----------



## KongShou (Jun 21, 2013)

nice PLL skip there!

y u no rite can u solve faster than this thingy cos i can


----------



## IAssemble (Jun 21, 2013)

AvGalen said:


> I have never been a big fan of 444fmc because I can really only do a very optimized reduction+avoidparity+333fmc. But I think my lowest ever was around 65 and most were much more like 80



I'm impressed! 65 is amazing! And I believe an average of 80 is much better than most.

The algorithm I developed for MultiCuber is an "optimized reduction" (as you describe) which can solve the middles and pair edges (including correct parity) in about 30 moves and then uses the 3x3x3 algorithm I developed for my earlier robots and CubeStormer II to solve the rest in about another 20 moves.


----------



## IAssemble (Jun 21, 2013)

KongShou said:


> nice PLL skip there!
> 
> y u no rite can u solve faster than this thingy cos i can



Thanks but the 3x3x3 algorithm is not CFOP so there is no such thing as a PLL skip for MultiCuber 3


----------



## IAssemble (Jun 21, 2013)

KongShou said:


> y u no rite can u solve faster than this thingy cos i can



Yes, I realise that many people can solve the 4x4x4 much faster than this robot. Even my average time is about the same as MultiCuber 3 and I do not consider myself to be a speedcuber!

I have been working on the software algorithm on and off for about the last year... and this is the first robot to use it.

Perhaps I should focus on making the mechanics faster now too?!?


----------



## ben1996123 (Jun 21, 2013)

IAssemble said:


> Yes, I realise that many people can solve the 4x4x4 much faster than this robot. Even my average time is about the same as MultiCuber 3 and I do not consider myself to be a speedcuber!
> 
> I have been working on the software algorithm on and off for about the last year... and this is the first robot to use it.
> 
> Perhaps I should focus on making the mechanics faster now too?!?



multicubestormer pls


----------



## IAssemble (Jun 21, 2013)

ben1996123 said:


> multicubestormer pls



Perhaps I should chat to Mike about this?!? 

Oh - and I like your suggestion for the name!


----------



## Kirjava (Jun 21, 2013)

you could write an insane solving program for people to use if you wanted to...


----------



## IAssemble (Jun 21, 2013)

Kirjava said:


> you could write an insane solving program for people to use if you wanted to...



I'm not sure I understand what you mean exactly...?


----------



## Kirjava (Jun 21, 2013)

I'm talking about an application similar to acube for NxNxN cubes.

I feel rude just throwing this request at you, I should also say that I did enjoy the video


----------



## IAssemble (Jun 21, 2013)

Kirjava said:


> I'm talking about an application similar to acube for NxNxN cubes.
> 
> I feel rude just throwing this request at you, I should also say that I did enjoy the video



Ah, I see what you mean.

Thanks for the request. I hope you won't consider me rude if I decline as I am not ready to share the algorithm just yet... 

And thanks, I'm glad you enjoyed the video


----------



## IAssemble (Jun 23, 2013)

And if anybody is interested, there is an interview where I talk a little about MultiCuber 3


----------



## Ross The Boss (Jun 23, 2013)

if the cube were to lock up, would the machene break or would it stop turning?

also, the title of this thread reminded me of those tootsie pop commercials.


----------



## IAssemble (Jun 23, 2013)

Ross The Boss said:


> if the cube were to lock up, would the machene break or would it stop turning?
> 
> also, the title of this thread reminded me of those tootsie pop commercials.



This mechanical design is geared down more than some of the others in order to be able to turn stiffer cubes (it has been used to solve some give-away cubes that typically are not as smooth to turn). However, it can still probably not apply enough torque to damage the cube or itself.

As with most of my designs, if the NXT senses that the motors have stalled for a short time while turning, it is programmed to try and recover by turning in the opposite direction by an appropriate amount. If that fails and it stalls again it will simply shut down the motors and report the failure. However, this is probably my most reliable design so far and has not jammed while turning the cube at all since I got it working. 

Sorry about the title... but at least some of you decided it might be worth a look at the thread anyway!?! ;-)


----------



## Ross The Boss (Jun 23, 2013)

IAssemble said:


> This mechanical design is geared down more than some of the others in order to be able to turn stiffer cubes (it has been used to solve some give-away cubes that typically are not as smooth to turn). However, it can still probably not apply enough torque to damage the cube or itself.
> 
> As with most of my designs, if the NXT senses that the motors have stalled for a short time while turning, it is programmed to try and recover by turning in the opposite direction by an appropriate amount. If that fails and it stalls again it will simply shut down the motors and report the failure. However, this is probably my most reliable design so far and has not jammed while turning the cube at all since I got it working.
> 
> Sorry about the title... but at least some of you decided it might be worth a look at the thread anyway!?! ;-)



the title is actually why i looked at it


----------



## IAssemble (Jun 23, 2013)

Ross The Boss said:


> the title is actually why i looked at it



Thanks. Sorry, but I have to ask now.... how many moves does it take you Ross?


----------



## Ross The Boss (Jun 23, 2013)

i just counted 157. that is how i would do it in a speed solve. i didnt try to optimize.


----------



## IAssemble (Jun 23, 2013)

Ross The Boss said:


> i just counted 157. that is how i would do it in a speed solve. i didnt try to optimize.



Thanks for the info. That seems to be around the level I expected for speed solves.

I was extremely impressed when AvGalen mentioned an average of about 80 and personal best of about 65 for 444fmc!


----------



## ben1996123 (Jun 23, 2013)

126 while trying to use fewer moves than in a speedsolve
no parity


----------



## MorrisKid101 (Jun 23, 2013)

Is there an app or something that can tell you you're move count or is it that you have to do it manually?


----------



## Username (Jun 23, 2013)

MorrisKid101 said:


> Is there an app or something that can tell you you're move count or is it that you have to do it manually?



The app wouldn't work if you didn't type your solution, and when typing it you might make a mistake and not get the correct movecount. Counting by hand is the safest (I count in tens, ....Thirty, one, two, three, four, five, six, seven, eight, nine, fourty, one, two....)

I was at about 90 after reduction was finished, that + about 50 moves speedsolve + parity goes to about 150-170


----------



## IAssemble (Jun 23, 2013)

Username said:


> The app wouldn't work if you didn't type your solution, and when typing it you might make a mistake and not get the correct movecount. Counting by hand is the safest (I count in tens, ....Thirty, one, two, three, four, five, six, seven, eight, nine, fourty, one, two....)
> 
> I was at about 90 after reduction was finished, that + about 50 moves speedsolve + parity goes to about 150-170



That sounds pretty reasonable. I think I already mentioned that MultiCuber 3 manages to solve middles, pair edges and avoid parity in about 30 turns and then solves the 3x3x3 in about a further 20 

Last time I counted, about the time I started working on the efficient software algorithm, I recall it took me well over 200!


----------



## LNZ (Jun 23, 2013)

Out of interest I did a 4x4 solve and counted the moves. I used a black Eastsheen cube.

I got 159 moves and that included both OLL and PLL parities.

I used keyhole F3L, which is my preffered method and reduction with 2-look OLL and 2-look PLL with some full PLL.


----------



## IAssemble (Jun 23, 2013)

ben1996123 said:


> 126 while trying to use fewer moves than in a speedsolve
> no parity



That's very good! Far better than me


----------



## Ninja Storm (Jun 23, 2013)

125 with no parity whatsoever.


----------



## qq280833822 (Jun 26, 2013)

30 moves' reduction is cool. Would you mind telling us how the algorithm works?


----------



## IAssemble (Jun 26, 2013)

qq280833822 said:


> 30 moves' reduction is cool. Would you mind telling us how the algorithm works?



Thanks. Sorry, I am not sharing the precise details at the moment but I will summarize it:

The algorithm is lookup table driven (as you would expect). There is about 600MB of data in total in the lookup tables. There is a significant amount of searching done to find a good solution. For example, in 2s x 4 CPUs, MultiCuber 3 attempts about 100,000 solutions and picks the shortest.

The order in which it solves the cube is fairly standard:

1) simultaneously solve two opposite middles
2) simultaneously solve remaining four middles
3) pair all edges (in arbitrary positions) checking parity. This may require several passes but typically only 2 and often just 1
4+5) solve 3x3x3 using my own 2-phase algorithm that I used on CubeStormer II etc.

So overall it is really a 5-phase solver I guess.

Phases 1) and 4) can find an arbitrary numbers of solutions, shortest first. Phase 3) can usually solve in a number of different ways

The solver keeps trying different solutions in phases 1), 3) (ignoring cases with incorrect 3x3x3 parity) and 4) until it finds a complete solution that is "good enough" based on a move count or time-out etc.


----------



## tx789 (Jun 26, 2013)

50 moves is so few on 4x4


----------



## Username (Jun 26, 2013)

Tried a solve with a bit of FMC in it, but it was linear and basically pure reduction

122 moves no parity


----------



## IAssemble (Jun 26, 2013)

tx789 said:


> 50 moves is so few on 4x4







Username said:


> Tried a solve with a bit of FMC in it, but it was linear and basically pure reduction
> 
> 122 moves no parity



Thanks for the information. I think that is pretty good.


----------



## Mike Hughey (Jun 26, 2013)

For a little while we had 4x4x4 fewest moves as an event in our speedsolving.com weekly competition. It became evident quite quickly that 100 moves on 4x4x4 was equivalent to 35-40 moves on 3x3x3, and 80 moves on 4x4x4 was more like the 30-move target that people often shoot for with 3x3x3 fewest moves. I did it most weeks, and averaged around 95 moves. So I guess the typical proportion of human to computer moves is roughly similar on 4x4x4 and 3x3x3, with humans being about half as efficient as computers, on a move count basis.


----------



## ben1996123 (Jun 27, 2013)

find gods number pls !!!


----------



## kcl (Jun 27, 2013)

I got a 104 move solution with easy centers, an edge done, and a PLL skip


----------



## IAssemble (Jun 27, 2013)

ben1996123 said:


> find gods number pls !!!



Is that a serious question? 

I have not researched this extensively so please forgive me if anything below is incorrect...

There is a huge difference between developing an algorithm that discovers efficient solutions and one which has finds provably optimal solutions or has a provable upper bound.

Either or both those properties might be useful, but not sufficient by themselves to help find "God's number" for the 4x4x4.

If a similar style of proof was used as for the 3x3x3, it would have to include some reasoning about the solution space to break it down into a small enough subset of problems to "brute force" using an efficient algorithm. It would also be need a provable lower bound (that happened to also be the upper bound).

My understanding from what I've seen, is that the current lower bound for the 4x4x4 is probably very weak (probably lower than the actual upper bound) and there has not yet been a breakthrough in being able to reason about sub-dividing the solution space to make a proof anywhere near practical.


----------



## Kirjava (Jun 27, 2013)

What *are* the current lower and upper bounds for 4x4x4?


----------



## windhero (Jun 27, 2013)

I averaged around 130 moves with regular Yau-duction and just a tad better lookahead (which I dont count as FMC since I could still do a solve like that in way under 2 minutes easy). Basically intuitive Yau-solves with 130ish moves on average, a solve like the ones I do when I speedsolve.

None of the cases had any parity at all, so thats like +10-27 moves on average give or take (10 for only PLL, 17 for only OLL, 27 for both)

EDIT: Now I know whats stopping me from a sub 1 solve. Even at only 3TPS average I'd be a 50 second solver ,_,


----------



## whauk (Jun 27, 2013)

@IAssemble:
could you look up the longest solution for every phase of your algorithm? that should give us a reasonable upper bound.


----------



## IAssemble (Jun 27, 2013)

whauk said:


> @IAssemble:
> could you look up the longest solution for every phase of your algorithm? that should give us a reasonable upper bound.



You make an assumption that each phase of my algorithm is an exhaustive lookup table for all possible positions with a sequence of moves associated with it... it doesn't! ;-)

I cannot easily bound phases 1) or 4) this way and it would need some work for 3) to determine the worst case number of passes... (and there is a trick I use between 1) and 2) that would need to be considered)

Although actually I would use 20 for a combination of 4) and 5) as they could be replaced by an optimal 3x3x3 solver and we know God's number of 3x3x3 is 20 

Maybe I will think about doing this but I suspect it would be *much* higher than the average 51 that it achieves in practice...


----------



## antoineccantin (Jun 27, 2013)

Linear 4x4 FMC:

23 centers
35 edges
59 3x3 (PLL parity)
= 117 moves


----------



## uberCuber (Jun 27, 2013)

Solving as if a speedsolve: 132 moves, Yau method, PLL parity

I started to try a linear FMC, but CN Yau confuses the living hell out of me, so I gave up >_>


----------



## IAssemble (Jun 27, 2013)

Kirjava said:


> What *are* the current lower and upper bounds for 4x4x4?





cuBerBruce said:


> 67 block turns
> 77 single-layer turns
> 82 twists (face turns)
> 
> http://cubezzz.dyndns.org/drupal/?q=node/view/93




This is from a thread here on speedsolving.

My algorithm counts contiguous layers including one face turned by the same amount as a single move so this is probably close to "block turns" referenced above. So 67 looks like the the current upper bound for this approach.

I think I have only seen the lower bound quoted for "single-layer" turns...

Does anyone know of any other research?


----------



## IAssemble (Jun 27, 2013)

tx789 said:


> Well it's at least 40 I wonder if there's a pattern between god number for 2x2-3x3 3x3-4x4 ect



How do you know it is at least 40?

BTW there is a thread currently discussing this again here ;-)


----------



## Yellowsnow98 (Jun 27, 2013)

6...

Kidding, I'd say that it could be as high as 200 but that's just me.


----------



## Zoma (Jun 27, 2013)

I like the deck of cards analogy, but I don't get it. heheh


----------



## KongShou (Jun 27, 2013)

42 is the answer to everything


----------



## AvGalen (Jun 27, 2013)

I once made up this formula without any evidence.
(Amount of layers-1) * 10 + 1 for even layered cubes (or use a nice mod function if you want to get all mathy and stuff)
So
1x1x1 = (1-1) * 10 = 0
2x2x2 = (2-1) * 10 + 1 = 11
3x3x3 = (3-1) * 10 = 20
4x4x4 = (4-1) * 10 + 1 = 31
It seems really low but not improbable (and it is correct for 1, 2 and 3). I should simply see the amount of positions that can be reached on a 10x10x10 cube in 101 moves compared with the amount of total positions but I never could be bothered


----------



## ben1996123 (Jun 27, 2013)

tx789 said:


> I wonder if there's a pattern between god number for 2x2-3x3 3x3-4x4 ect



dont we all

i predict 38


----------



## qqwref (Jun 28, 2013)

Well, we already know that God's Number is Θ(n^2 / log(n)) (see http://www.speedsolving.com/forum/showthread.php?30231). So we can guarantee that any recurrence or formula that does not also grow the same way will eventually be wrong (and probably sooner rather than later).


----------



## kcl (Jun 28, 2013)

AvGalen said:


> I once made up this formula without any evidence.
> (Amount of layers-1) * 10 + 1 for even layered cubes (or use a nice mod function if you want to get all mathy and stuff)
> So
> 1x1x1 = (1-1) * 10 = 0
> ...


I was messing with something like this a few weeks ago but I did it wrong. I think you have it right..


----------



## uberCuber (Jun 28, 2013)

Yellowsnow98 said:


> I'd say that it could be as high as 200 but that's just me.



An upper bound of much less than 200 was already given in this very same thread....



cuBerBruce said:


> 67 block turns
> 77 single-layer turns
> 82 twists (face turns)
> 
> http://cubezzz.dyndns.org/drupal/?q=node/view/93


----------



## MaikeruKonare (Jun 28, 2013)

THANK YOU applemobile!!! Atheist Speed Cubers FTW! I vote we call it "Thee Algorithm" instead of "God's Algorithm".
Therefore, thee algorithm for a 3x3x3 is 20.


----------



## JasonK (Jun 28, 2013)

MaikeruKonare said:


> THANK YOU applemobile!!! Atheist Speed Cubers FTW! I vote we call it "Thee Algorithm" instead of "God's Algorithm".
> Therefore, thee algorithm for a 3x3x3 is 20.



You realise that the concept of "God's algorithm" and "God's number" don't imply the existence of a God, right?


----------



## qqwref (Jun 28, 2013)

MaikeruKonare said:


> I vote we call it "Thee Algorithm" instead of "God's Algorithm".


What? If we are going to call it something else, it ought to be Frank's Algorithm.


----------



## cubernya (Jun 28, 2013)

qqwref said:


> What? If we are going to call it something else, it ought to be Frank's Algorithm.



After Frank Morris?


----------



## qqwref (Jun 28, 2013)

Of course!


----------



## AvGalen (Jun 28, 2013)

qqwref said:


> Well, we already know that God's Number is Θ(n^2 / log(n)) (see http://www.speedsolving.com/forum/showthread.php?30231). So we can guarantee that any recurrence or formula that does not also grow the same way will eventually be wrong (and probably sooner rather than later).


and by "we" you mean "you and a couple of other people in the speedcubing community that understand math" and actually write things like "Θ" online, right?


----------



## AvGalen (Jun 28, 2013)

theZcuber said:


> After Frank Morris?


blasphemy to even doubt!


----------



## irontwig (Jun 28, 2013)

IAssemble said:


> This is from a thread here on speedsolving.



Those are just upper bounds though, right? What type of bound would a counting argument make and how long time would it take to compute a optimal solution for a probably harder than average (analogous to the super flip) 4x4x4 scramble?


----------



## AvGalen (Jun 28, 2013)

irontwig said:


> Those are just upper bounds though, right? What type of bound would a counting argument make and how long time would it take to compute a optimal solution for a probably harder than average (analogous to the super flip) 4x4x4 scramble?


optimal? Nobody knows but probably "centuries" so nobody is going to start such a calculation because there is no benefit to doing it.

The funny thing with that is always that if you start the calculation on a computer today it would take "100 years".
If you would start it 3 years from now computer power would have (historically) quadruppled and now it would only take "25 years".
So you will finish 78 years earlier by being lazy for 3 years


----------



## Yellowsnow98 (Jun 28, 2013)

uberCuber said:


> An upper bound of much less than 200 was already given in this very same thread....



I'm sorry, don't whack me I'm brittle.


----------



## whauk (Jun 28, 2013)

this is probably not big news... but i get a lower bound of 33 in OBTM by counting. there are 9 axes (R, U, L, D, F, B, Rw, Uw, Fw) and 3 possible turns on every axis (cw, ccw, 180°). so after n turns we have 27^n positions. so we want to find n such that 27^n > number of permutations on a 4x4x4. solving this inequality for n yields n > 32.04... > 32 so n must be 33 as it is a natural number.
i guess this can't be improved by more than 2-3 moves by removing symmetries, trivial identities...


----------



## TDM (Jun 28, 2013)

whauk said:


> i get a lower bound of 33 in OBTM


If 33 is a lower bound, then


AvGalen said:


> (Amount of layers-1) * 10, +1 for even layered cubes. So
> 1x1x1 = (1-1) * 10 = 0
> 2x2x2 = (2-1) * 10 + 1 = 11
> 3x3x3 = (3-1) * 10 = 20
> 4x4x4 = (4-1) * 10 + 1 = 31


You could try adding n-1 instead of adding 1 for even numbers. That way, a 4x4x4 would give (4-1)*10+(4-1)=33. For a 10x10x10, you'd get 99. Also "10x10x10 cube in 101 moves" using your formula comes out as 91, not 101 as you said.


----------



## ben1996123 (Jun 28, 2013)

TDM said:


> If 33 is a lower bound, then
> 
> You could try adding n-1 instead of adding 1 for even numbers. That way, a 4x4x4 would give (4-1)*10+(4-1)=33. For a 10x10x10, you'd get 99. Also "10x10x10 cube in 101 moves" using your formula comes out as 91, not 101 as you said.



that formeuler is silly

I want to know optimal movecount for megaminx superflip too


----------



## qqwref (Jun 28, 2013)

AvGalen said:


> and by "we" you mean "you and a couple of other people in the speedcubing community that understand math" and actually write things like "Θ" online, right?


I was referring more to the cube theory community as a whole - not in the sense that specific people know the information, but that it is information which has been publicly published and which we have access to.


Optimal megaminx patterns are likely to remain unknown for a while - there are just too many ways of going around the cube, and you can't apply 3x3x3 techniques like you can for 4x4x4 (at least for patterns occupying most of the minx).


----------



## IAssemble (Jun 28, 2013)

qqwref said:


> I was referring more to the cube theory community as a whole - not in the sense that specific people know the information, but that it is information which has been publicly published and which we have access to.
> 
> 
> Optimal megaminx patterns are likely to remain unknown for a while - there are just too many ways of going around the cube, and you can't apply 3x3x3 techniques like you can for 4x4x4 (at least for patterns occupying most of the minx).



At least ben1996123 didn't ask for God's Number for the Megaminx! 

According to wikipedia there are close to 1.01x10^68 positions on a 12 colored Megaminx.

I calculate that there are 4x12 possible first moves and after that 4x11 possible moves to continue without trivial cancellation (although many short sequences would be equivalent) (4 angles for each of 12 or 11 faces)

So N moves would reach no more than 4x12x(4x11)^(N-1) unique positions.

So for a (very weak) lower bound:

For 41 turns this would be ~2.6x10^67 which is not enough to reach all possible positions.
For 42 turns this would be ~1.1x10^69

I believe this means God's Number for the 12 colored Megaminx is at least 42 

EDIT1: I should have googled it first!

EDIT2: and reading this I now see a flaw in my reasoning about positions that are reachable in fewer than N moves... perhaps I should read up about this a bit more!


----------



## Jakube (Jun 28, 2013)

whauk said:


> this is probably not big news... but i get a lower bound of 33 in OBTM by counting. there are 9 axes (R, U, L, D, F, B, Rw, Uw, Fw) and 3 possible turns on every axis (cw, ccw, 180°). so after n turns we have 27^n positions. so we want to find n such that 27^n > number of permutations on a 4x4x4. solving this inequality for n yields n > 32.04... > 32 so n must be 33 as it is a natural number.
> i guess this can't be improved by more than 2-3 moves by removing symmetries, trivial identities...



By ignoring cases like R R', R L R2, ... you get a lower bound of 35. 
I build a recursive function: a(n) = 5832*a(n-4)+2268*a(n-3)+432*a(n-2), a(0) = 0, a(1) = 27, a(2) = 648, a(3) = 15066. 
I had a few beers earlier, but it should be correct. I will check it tomorrow again though.


----------



## mDiPalma (Jun 28, 2013)

This is probably a stupid question, but...

can it be proven/disproven that all 4x4x4 states can be reached by applying a 3x3x3 scrambling sequence followed by a 2x2x2 scrambling sequence (holding 2 layers as 1)?

That might suggest a very low upper bound.


----------



## Username (Jun 28, 2013)

mDiPalma said:


> This is probably a stupid question, but...
> 
> can it be proven/disproven that all 4x4x4 states can be reached by applying a 3x3x3 scrambling sequence followed by a 2x2x2 scrambling sequence (holding 2 layers as 1)?
> 
> That might suggest a very low upper bound.



Does comparing the amount of 4x4 positions with gods number on 2x2 and 3x3 help at all with this?


----------



## mDiPalma (Jun 28, 2013)

Username said:


> Does comparing the amount of 4x4 positions with gods number on 2x2 and 3x3 help at all with this?



I don't think so directly. There may or may not be a state that requires both an 11 move 2x2 scramble and a 20 move 3x3 scramble. The upper bound could be 30 or ever 29, considering cancellations.

But my proposal is nearly completely implausible.


----------



## ben1996123 (Jun 28, 2013)

mDiPalma said:


> This is probably a stupid question, but...
> 
> can it be proven/disproven that all 4x4x4 states can be reached by applying a 3x3x3 scrambling sequence followed by a 2x2x2 scrambling sequence (holding 2 layers as 1)?
> 
> That might suggest a very low upper bound.



dispruf: there are 3674160 states on a 2x2 and 43252003274489856000 on a 3x3, multiply them to represent combining a 2x2 and 3x3 scramble = 1589147803509597097320960000 wich is alot less than 7401196841564901869874093974498574336000000000


----------



## qqwref (Jun 28, 2013)

Can we get to all 4x4x4 positions by applying a 3x3x3 scramble, then a 2x2x2 scramble, then another 3x3x3 scramble?

EDIT: Never mind, any positions with solved centers and unpaired edges are impossible 


EDIT2:


Jakube said:


> By ignoring cases like R R', R L R2, ... you get a lower bound of 35.
> I build a recursive function: a(n) = 5832*a(n-4)+2268*a(n-3)+432*a(n-2), a(0) = 0, a(1) = 27, a(2) = 648, a(3) = 15066.
> I had a few beers earlier, but it should be correct. I will check it tomorrow again though.


I get that 34 turns are enough (there are 3.422... * 10^46 positions). Also, for the 4x4x4 supercube, with 7.072 * 10^53 positions, 40 turns are enough. These results echo ones I have from several years back, which is cool.

Similarly, if anyone's curious, 50 turns are enough for the 5x5x5, and 63 are enough for the 5x5x5 supercube.


----------



## cuBerBruce (Jun 29, 2013)

Lower bounds for up to 20x20x20 cubes for six different metrics can be found here. Also, lower bounds for 100x100x100 are given. (q/h-s = single-layer turns, q/h-w = outer block turns, q/h-b = block turns = any block of contiguous layers turned together)


----------



## qqwref (Jun 29, 2013)

Would I be correct in supposing that that approach treats RL and LR as the same? My numbers above did not do that, but just worried about not using cancelling moves such as RwRRw. (Also, I think your equivalent of my metric is h-w.) Using a canonical ordering for moves on the same axis, the four numbers I gave (34, 40, 50, 63) become 35, 41, 52, 65. The 35 and 52 match yours.


----------



## cuBerBruce (Jun 29, 2013)

qqwref said:


> Would I be correct in supposing that that approach treats RL and LR as the same?


Yes. For example, on the 4x4x4 from a given position, there are generally 4^3-1 = 63 new positions reachable from just making moves along one axis. (One layer can be regarded as a fixed reference.) The analysis uses one optimal (for the given metric) representation for reaching each of these 63 new states. So LR would not be considered distinct from RL. (But if the L face is treated as the fixed layer, a 3-layer wide R turn would be used in its place of L.)



qqwref said:


> My numbers above did not do that, but just worried about not using cancelling moves such as RwRRw. (Also, I think your equivalent of my metric is h-w.) Using a canonical ordering for moves on the same axis, the four numbers I gave (34, 40, 50, 63) become 35, 41, 52, 65. The 35 and 52 match yours.



I note that these were not my numbers. (Nor did I invent these abbreviations for the metrics - h-w, etc.) I note that I have produced actual God's algorithm numbers up to a distance of at least 7 for the six metrics in this thread.


----------



## windhero (Jun 29, 2013)

I dont really get the measurement CPU year as in it's very vague. It doesnt tell anything about the computing power now does it? What ever is the case I would atleast hope that a high end desktop CPU for regular customers would match whatever "super computer" they used a few years back. The technology does evolve at a very fast rate and improving is still very possible regardless of physical limitations that may slow it down in the future.

Does anyone know the computing power of the used CPUs? I know this is just the hardware and someone should actually go ahead and make a much better code for this to happen in our lifetime regardless of the technology advancing, but I'm still curious. I'm not sure if someone has suggested this but it would be fun to think that people would join in on this like on the group projects that are done on the PS3.


----------



## Stefan (Jun 29, 2013)

windhero said:


> I dont really get the measurement CPU year as in it's very vague. It doesnt tell anything about the computing power now does it? What ever is the case I would atleast hope that a high end desktop CPU for regular customers would match whatever "super computer" they used a few years back.



Apparently you missed what the page says:
_"it would take a good desktop PC *(Intel Nehalem, four-core, 2.8GHz*) 1.1 billion seconds, or about 35 CPU years, to perform this calculation"_



windhero said:


> The technology does *evolve at a very fast rate* and improving is still very possible regardless of physical limitations that may slow it down in the future.



How fast?


----------



## spyr0th3dr4g0n (Jun 29, 2013)

Would it be possible to determine if its an odd or even number without extensive simulation?


----------



## cubernya (Jun 29, 2013)

spyr0th3dr4g0n said:


> Would it be possible to determine if its an odd or even number without extensive simulation?



I doubt it, since it's normally not odd or even, but just within the upper and lower bounds.


----------



## windhero (Jul 1, 2013)

Stefan said:


> Apparently you missed what the page says:
> _"it would take a good desktop PC *(Intel Nehalem, four-core, 2.8GHz*) 1.1 billion seconds, or about 35 CPU years, to perform this calculation"_
> 
> 
> ...




Ah my bad.

Well for an example
This: http://www.newegg.com/Product/Product.aspx?Item=N82E16813131817&Tpk=Z9PE-D8 WS&IsVirtualParent=1

with 2 of these 
http://www.newegg.com/Product/Product.aspx?Item=N82E16819116492

makes 12 cores @ 3.8ghZ and its very overclockable even close to 4.8ghz.

Nehalem is a 45nm desktop cpu, wouldnt really call it a supercomputer even back in the day or ever. It's just a single CPU that used to be good a few years back. Now a cpu with that capacity can be even seen in low to mid end laptops. The options I suggested are regular desktop cpus as well.

Benchmarks:
3930K @ nearly 12.1k points
http://www.cpubenchmark.net/[email protected]+3.20GHz&id=902


Nehalem 2.8ghz quad core aka Xeon x5560 is at nearly 5.8k points
http://www.cpubenchmark.net/[email protected]+2.80GHz&id=1301


Benchmarks dont tell everything but just by the contrast between the setups you can imagine how a setup with 2x 6-core 12k point benchmarked CPUs perform against a single quadcore at 5.8k benchmark points.

I know people with more expensive gaming rigs so I would say it's very accessible if sponsored by a big company.

When I heard it was sponsored by google I figured it was done by a computer that regular people or even high end gamers dont use but this proves that my assumption was wrong.


Also note that this is an example based on a very quick lookup. I'm sure there's a mobo out there that supports the new hashwell cpus with a dual cpu slot. That setup would be even more powerful (high end 22nm cpus with 8 core each).


EDIT: I noticed that the motherboard I suggested also supports the Xeon E5 series of processors which are the most powerful CPUs to this day that are also available for regular customers.


Also this is what a super computer means in 2012
Thats 72,000 cpus. With a computer like that I suppose it wouldnt even take a day to calculate the gods number for a 3x3 (if all the cpus in this super computers are equivalent to a X5560 it would take 4 hours infact). 4x4 obviosly is a completely different story, I understand that. I also understand that there is no way we could get someone to loan a super computer such as this one even for a minute, not to talk about days. This is why the PS3 (or now ps4) method would be awesome, each console has 8 cores and hundreds of thousands are sold.





The yellowstone supercomputer for one solves 1.5 quadrillion operations per second. I dont know how many operations one 4x4 case requires but I suppose it would be possible to do it even now. The yellowstone is expected to rank in the top 25 in the world so this is just an example of a great super computer in 2012.



The best in 2008 was at 1.7 PFlops. The best of 2013 is at 33.8PFlops. I'd say they evolve very fast.

Regular desktop CPUs evolve at an equal rate.


----------



## qqwref (Jul 1, 2013)

windhero said:


> Nehalem is a 45nm desktop cpu, wouldnt really call it a supercomputer
> [wall of words]


That's entirely intentional. Think about it this way. Supercomputers can easily vary in computing power by orders of magnitude, the fastest one keeps changing, the computing speed is dependent on much more complex factors (algorithm parallelism, data transfer amount/speed between cores, etc.), and the speed of a supercomputer is hard to get an intuition for unless you've actually done a large computation on one. All this combines to mean that if you ask "how long will this algorithm take to execute on a supercomputer" you will get a wildly inaccurate, ever-changing, and basically irrelevant answer. And oh yeah, supercomputers can actually evolve even faster than personal computers, due to increasing numbers of cores and better networking technology between the cores. And all you have to do to get more cores is buy more, whereas there's a limit to what you can fit in a dekstop. And that's not even considering massive online "supercomputers" like GIMPS, whose speed is basically a product of the number of computers in use and the speed of the individual ones.

So that's why whenever people talk about how many years a computer would take they almost always use a commercially available desktop computer. It's a much better benchmark and is pretty close to the kind of thing many people have in their homes - so saying "this computation took 35 CPU-years" gives the reader a far better idea of how much computation was actually done.


----------



## Stefan (Jul 1, 2013)

windhero said:


> Benchmarks dont tell everything but just by the contrast between the setups you can imagine how a setup with 2x 6-core 12k point benchmarked CPUs perform against a single quadcore at 5.8k benchmark points.



About 2*12k/5.8k if it scales well, so maybe factor 4. Don't know why you mention the number of cores.



windhero said:


> Also this is what a super computer means in 2012
> Thats 72,000 cpus.



No. 72288 cores, not cpus. It's 9036 cpus.



windhero said:


> I dont know how many operations one 4x4 case requires but I suppose it would be possible to do it even now.



We're talking about roughly 10^26 as many states and they're more complicated than the 3x3's. If you use a million cpus and if it scales well, you're still a factor of 10^19 away, plus the more complicated states.



windhero said:


> Regular desktop CPUs evolve at an equal rate.



No. The super computers owe their performance increase to a large degree to the number of cpus, not just to individual cpu performance increases.


----------



## windhero (Jul 1, 2013)

Stefan said:


> About 2*12k/5.8k if it scales well, so maybe factor 4. Don't know why you mention the number of cores.
> 
> 
> 
> ...



Yes. Read what I said. I said that regular desktop CPUs evolve at an equal rate. That is because super computers use the same cpus, just in bigger amounts. You can compare desktop computers from a few years back and see a radical change in computing power. I know it's about more cpus in supercomputers, but my first example was exactly about that improvement in computing power of single cpus.

And I believe I aknowledged the difference in magnitude of the two, but I still wouldnt say it's impossible. I'm not saying it should be done or anything of the sort. I dont really believe anyone with the funds would want to invest in such a project. Those interested dont have the excess cash. Typical situation.

The benchmark results do not scale very well, compare points between the cpus at stock voltages and overclocked ones. More cores = more operations so I'd say it should help. Just needs a good script that can take advantage of those multiple cores.

All this is just wild speculation since no one will probably ever do this all the way.


----------



## jayefbe (Jul 1, 2013)

Windhero - you're missing the entire point. CPU-years are simply meant to give the casual observer an idea of how computationally intensive it would be to reach a solution. It's not literally how long it would take to reach a solution. Your arguments are actually supporting their usage.


----------



## Stefan (Jul 1, 2013)

windhero said:


> Read what I said.



I had. But ok, let's do it again:



windhero said:


> The best in 2008 was at 1.7 PFlops. The best of 2013 is at 33.8PFlops. I'd say they evolve very fast.
> 
> Regular desktop CPUs evolve at an equal rate.



That's a factor of 19.9 over five years. The X9770 was realeased in 2008 and has 4815 points (and I'm not even sure it was the best). Please show me today's desktop processor with 96000 points. Max I see is 12942. That's a factor of 2.7, not 19.9. And hardly seems "radical", btw.


----------



## IAssemble (Jul 2, 2013)

cuBerBruce said:


> Yes. For example, on the 4x4x4 from a given position, there are generally 4^3-1 = 63 new positions reachable from just making moves along one axis. (One layer can be regarded as a fixed reference.) The analysis uses one optimal (for the given metric) representation for reaching each of these 63 new states. So LR would not be considered distinct from RL. (But if the L face is treated as the fixed layer, a 3-layer wide R turn would be used in its place of L.)



Some of the 4^3-1 moves do not reach "new" positions. 3 of them are effectively the same position where the whole cube is re-orientated. I note in the thread to which you refer, it states "Also, the orientation of the puzzle is considered not to matter."


----------



## cuBerBruce (Jul 2, 2013)

IAssemble said:


> Some of the 4^3-1 moves do not reach "new" positions. 3 of them are effectively the same position where the whole cube is re-orientated.


No, the 4^3-1 moves result in distinct positions because the 4th layer is regarded as a fixed reference which serves to identify the orientation of the cube. If we didn't use 1 layer as a fixed reference, we would have 4^4-1 positions, and then obviously some of those would be equivalent when we regard the orientation of the cube not to matter.


----------



## qqwref (Jul 2, 2013)

Another way to say what Bruce is saying: since 4x4x4 has no fixed centers one easy way to fix the orientation is to fix the position of one corner. Then a single-layer turn with that corner can be thought of as a 3-layer turn on the opposite face. From that perspective it's easy to see that there are always 4^3-1 possible moves on each axis (in axial turn metric).


----------



## windhero (Jul 3, 2013)

Alright on another note. We know that super flip is the combination on the 3x3 that requires the most moves to solve, was this discovered by the computer or by someone just figuring it out? If it's the latter can a "superflip" position be figured out for a cube of a bigger order too? Or is there any guarantee that there are no combinations that require more moves than the super flip?


----------



## EMI (Jul 3, 2013)

windhero said:


> Alright on another note. We know that super flip is the combination on the 3x3 that requires the most moves to solve, was this discovered by the computer or by someone just figuring it out? If it's the latter can a "superflip" position be figured out for a cube of a bigger order too? Or is there any guarantee that there are no combinations that require more moves than the super flip?



The superflip was the first position that was proven to require 20 moves to be solved. It didn't prove there were no positions that required more than 20.


----------



## windhero (Jul 3, 2013)

Alright, thanks for clarifying.


----------



## Renslay (Jul 3, 2013)

Actually, people who did the proof were hoping for finding a position that requires 21 moves, since that would be "the hardest position ever known so far." Fortunetly or unfortunetly, the computer said that every case can be solved in 20 moves at most.


----------



## IAssemble (Jul 3, 2013)

cuBerBruce said:


> No, the 4^3-1 moves result in distinct positions because the 4th layer is regarded as a fixed reference which serves to identify the orientation of the cube. If we didn't use 1 layer as a fixed reference, we would have 4^4-1 positions, and then obviously some of those would be equivalent when we regard the orientation of the cube not to matter.



Ooops. I should read and think more carefully! Yes, that makes perfect sense now.


----------



## IAssemble (Jul 3, 2013)

windhero said:


> Alright on another note. We know that super flip is the combination on the 3x3 that requires the most moves to solve, was this discovered by the computer or by someone just figuring it out? If it's the latter can a "superflip" position be figured out for a cube of a bigger order too? Or is there any guarantee that there are no combinations that require more moves than the super flip?



It would be interesting to find a position that is demonstrably "harder" to solve for a 4x4x4 than general random positions...

Thinking about this from an "intuitive" perspective. In some sense I can "appreciate" why superflip requires a larger number of moves than random positions - each edge has to be moved away from its neighbouring corners and then put back next to them in the opposite orientation. For a random position, many edges will start separated from their neighbouring corners and only need putting next to them in the correct orientation.

As I said, this is not based on any real mathematical principles but rather just on "intuition". However, given this, can anyone think of similar kinds of patterns on a 4x4x4 cube that have this "intuitively hard" property that could be explored at some level to see if they appear to require more moves than randomly scrambled positions? Something like a position where every edge/corner piece is next to its neighbours but in the "wrong" orientation and every middle piece is next to edges in the wrong orientation?

I am aware from a mathematical sense that superflip is unique in that there are some interesting mathematical properties: see about 2:30 onwards in this video:






Does anyone have any ideas about a position on the 4x4x4 cube that has similar mathematical properties?


----------



## Stefan (Jul 4, 2013)

Superflip is highly symmetric, and symmetric positions apparently have a large probability of being very hard.

About 1 in 260,000,000 of all positions has symmetry.
About 1 in 275 of all hardest positions (needing 20 moves) has symmetry.

About 1 in 143,000,000,000 positions needs 20 moves.
About 1 in 150,000 symmetric positions needs 20 moves.

(Unless they already reduced the numbers by symmetry, not sure right now, but it'd be at most factor 96 or so.)

Thread with more information: http://cubezzz.dyndns.org/drupal/?q=node/view/63

I think there was some reasoning *why* symmetric positions are likelier harder, but I'm too tired to think right now. Anyway, if we could optimally solve 4x4 positions, I'd check out symmetric ones first as well.


----------



## Renslay (Jul 4, 2013)

IAssemble said:


> Does anyone have any ideas about a position on the 4x4x4 cube that has similar mathematical properties?



You mean that Superflip * A = A * Superflip for all A sequence of moves? (Which equals to ASA' = S)

S could not permute any elements, because if it permutes an element number 1 with 2:
S = (1 2 ... k) in cyclic permutation notation,
then I can find an A such that it permute 2 but not 1 (e.g., (2 k+1 ... k+n), hence SA != AS
Consequently, S cannot effect centers.

S also cannot effect the orientation of the corners (for a similar reason, since a corner has 3 orientations; for further reasoning, look up why the superflip is the only state for SA = AS in a 3x3).

Hence, a superflip in the 4x4x4 could only affect the edges; but on a 4x4x4, edges has only permutation (you cannot flip just one single edge), hence they form a permutation. Therefore, there is no superflip on a 4x4x4.

The "original" superflip does not work here, see this for example:
case1: AS

case2: SA


----------



## IAssemble (Jul 4, 2013)

Renslay said:


> You mean that Superflip * A = A * Superflip for all A sequence of moves? (Which equals to ASA' = S)
> 
> S could not permute any elements, because if it permutes an element number 1 with 2:
> S = (1 2 ... k) in cyclic permutation notation,
> ...



Thanks for this proof that position with properties similar to "superflip" cannot exist on a 4x4x4. I was coming to that conclusion myself but with less rigorous reasoning.


----------



## qqwref (Jul 4, 2013)

I think the presence of parity on 4x4x4 may mean that perfectly symmetric patterns are relatively easy to create. I wonder if a near-symmetric pattern such as an 11-flip will have a relatively long solution.


----------



## IAssemble (Jul 4, 2013)

qqwref said:


> I think the presence of parity on 4x4x4 may mean that perfectly symmetric patterns are relatively easy to create. I wonder if a near-symmetric pattern such as an 11-flip will have a relatively long solution.



Interesting idea.

I just tried "11-flip" with my latest 4x4x4 solver (using OBTM metrics).

For random positions it averages around 48 turns in 100s of CPU time but for "11-flip" it finds a 33 turn solution in the same time which suggests it is much easier to solve than a random solution.

Of course this result is inconclusive and it could just be that the algorithm is based on reduction so will naturally find solutions more easily for positions where the middles are solved and edges paired since it only has to find a way to fix the parity and then solve the 3x3x3 which is probably no longer in the superflip position...

Any other ideas for "hard" positions?


----------



## Christopher Mowla (Jul 4, 2013)

IAssemble said:


> Any other ideas for "hard" positions?


I know this question wasn't directed at me, but I'm curious how many moves it takes your solver to solve the following cases:
[1] Rw' U' R' U' Rw F' R' F' Rw'
[2] Lw F2 U2 l' U2 Lw U' R U l U2 l' U R' U Lw' F2 Lw'
[3] And just a "potential bad case" to check: the case generated by this set of algorithms.


----------



## ben1996123 (Jul 4, 2013)

IAssemble said:


> Interesting idea.
> 
> I just tried "11-flip" with my latest 4x4x4 solver (using OBTM metrics).
> 
> ...



what was the solution and what does it find for OLL parity?


----------



## IAssemble (Jul 4, 2013)

ben1996123 said:


> what was the solution and what does it find for OLL parity?



I left it running overnight and it found a 31 OBTM solution to 11-flip (although by default it does not actually display the solution so I will re-run it with that enabled)...


----------



## IAssemble (Jul 4, 2013)

cmowla said:


> I know this question wasn't directed at me, but I'm curious how many moves it takes your solver to solve the following cases:
> [1] Rw' U' R' U' Rw F' R' F' Rw'
> [2] Lw F2 U2 l' U2 Lw U' R U l U2 l' U R' U Lw' F2 Lw'
> [3] And just a "potential bad case" to check: the case generated by this set of algorithms.



The question was not directed at anyone in particular... I'm interested to hear from anyone who has ideas about what makes 4x4x4 positions "hard".

Many thanks. I'll try my algorithm on these positions later and let you know.



ben1996123 said:


> what was the solution and what does it find for OLL parity?



By "OLL parity" you mean a single, pure edge flip?


----------



## cuBerBruce (Jul 4, 2013)

Using my solver, I found a 28-move solution for for the 11-dedge flip using BTM. We know there exist positions requiring 29 block turns, so it's definitely not antipodal in BTM either.

M S r U2 r F2 r' D2 r E2 r U' f2 Rw2 U f2 U' Rw2 f2 D' B2 R2 B2 L2 D2 Fw2 U2 Fw2


----------



## ben1996123 (Jul 4, 2013)

IAssemble said:


> By "OLL parity" you mean a single, pure edge flip?



yes


----------



## Christopher Mowla (Jul 4, 2013)

cuBerBruce said:


> We know there exist positions requiring 29 block turns, so it's definitely not antipodal in BTM either.


It looks like it isn't for BQTM either:
d E M R D R' Bw f M d' M' Fw b M' F Uw M' R' S L F' U R D' R' E S2 R F' z' y (30 q-b ,29 h-b)

But for q-w, I'm not sure:
x' Rw' U F2 U' Lw' U2 Rw' U2 Rw' F' U2 F Rw' B2 L2 D2 L' F2 R' U' B' D L' F D U B2 R2 F D2 F' U2 (44 q-w, 32 h-w)
x l F U2 F' Rw U2 Rw U2 Rw U2 F U2 F' U2 r D' L2 U2 F2 R2 L F U' B' R U D B L2 F B' (44 q-w, 33 h-w)
r F U2 F' Rw U2 Rw U2 Rw R U2 F U2 F' U2 r B' U2 R B' L2 F' L' U F' U2 B L' R' U2 D B (44 q-w, 34 h-w)

Maybe Mr. Rokicki's 3x3x3 solver could solve the 3x3x3 part of the algorithms above in fewer qtm to possibly lower the move count to 41 q-w, where it needs to be (note that 19 htm is optimal for the 3x3x3 part of the 32 h-w alg, unfortuantely. It took over half an hour for cube explorer to find it).


----------



## ben1996123 (Jul 5, 2013)

something like this seems like it might need a lot of moves


----------



## cmhardw (Jul 5, 2013)

I've always thought that having every center group have 2 centers on a diagonal with matching colors, then have the other 2 colors on the other diagonal match each other but not the colors from the first diagonal would lead to difficult positions. I have absolutely no proof for this, it just seems intuitively difficult to solve.


----------



## mark49152 (Jul 5, 2013)

cmhardw said:


> I've always thought that having every center group have 2 centers on a diagonal with matching colors, then have the other 2 colors on the other diagonal match each other but not the colors from the first diagonal would lead to difficult positions. I have absolutely no proof for this, it just seems intuitively difficult to solve.



Yes I was thinking something similar, combined with 3x3 superflip around the outside. So each edge requires taking out, flipping and reinserting relative to its adjacent corner, as mentioned earlier, but lots of center slicing means lots of potential destruction to the edge pairing as well (or extra moves avoiding it). Again, no proof, just intuitive speculation.


----------



## Gabriel H (Jul 5, 2013)

i think that is something about 40 or 50 moves, because we have to do de centers, after de edges, and after we solve like the 3x3(20 moves god's number) and the parityes


----------



## Username (Jul 5, 2013)

Gabriel H said:


> i think that is something about 40 or 50 moves, because we have to do de centers, after de edges, and after we solve like the 3x3(20 moves god's number) and the parityes



Why would it automatically be solved with reduction? That made absolutely no sense


----------



## Gabriel H (Jul 6, 2013)

Username said:


> Why would it automatically be solved with reduction? That made absolutely no sense



I'm saying about the speedsolving, because i think that is very difficult to solve the 4x4 without Method, we have to use some method, so i think that's impossible to solve it without at least 40 or 50 moves.


----------



## ben1996123 (Jul 6, 2013)

Gabriel H said:


> we have to use some method, so i think that's impossible to solve it without at least 40 or 50 moves.



optimal solving methods are not reduction


----------



## IAssemble (Jul 6, 2013)

cmhardw said:


> I've always thought that having every center group have 2 centers on a diagonal with matching colors, then have the other 2 colors on the other diagonal match each other but not the colors from the first diagonal would lead to difficult positions. I have absolutely no proof for this, it just seems intuitively difficult to solve.



Something like this  U' B' Rw' D Uw' Bw2 B' F' Lw L' Bw' F D' U R B U?

Yes, intuitively I would have expected that it could be hard but as you can see from the 17 turn OBTM solution it is not


----------



## IAssemble (Jul 6, 2013)

mark49152 said:


> Yes I was thinking something similar, combined with 3x3 superflip around the outside. So each edge requires taking out, flipping and reinserting relative to its adjacent corner, as mentioned earlier, but lots of center slicing means lots of potential destruction to the edge pairing as well (or extra moves avoiding it). Again, no proof, just intuitive speculation.



This is probably not as bad as you might think because even with a reduction algorithm, the act of solving the centrers will disturb the 3x3x3 superflip so it is unlikely to be as hard to solve the 3x3x3 after the edges are re-paired. Intuitively, I would not expect this to be particularly hard.

And as an example, here is a 31 turn OBTM solution generated quite quickly by my solver  U' L' Fw Uw' U B Fw2 F Lw R' Dw R' B2 R F2 R2 U2 F D' B R' L2 U' L2 U L2 B' R B D2 L


----------



## kcl (Jul 6, 2013)

Stefan said:


> Apparently you missed what the page says:
> _"it would take a good desktop PC *(Intel Nehalem, four-core, 2.8GHz*) 1.1 billion seconds, or about 35 CPU years, to perform this calculation"_
> 
> 
> ...



Very. Think about it.. In the past ten years, technology has evolved at an incredible rate. The iPod was invented. The iPhone. New computers, new chips, processors, software. Cloud storage. The price of flash memory is less than 50c per GB now. That's an excellent example. Several years ago, a 1GB card could cost over $100. Now, a 128GB costs almost half of that. These are just a few examples I can think of off the top of my head.


----------



## mark49152 (Jul 6, 2013)

IAssemble said:


> This is probably not as bad as you might think because even with a reduction algorithm, the act of solving the centrers will disturb the 3x3x3 superflip so it is unlikely to be as hard to solve the 3x3x3 after the edges are re-paired. Intuitively, I would not expect this to be particularly hard.


Solving the centers would not break the edges away from their adjacent corners, but after thinking about it further, when flipped those edges need to be moved to the opposite corner anyway so you are right that this disruption could help. (As was also already pointed out earlier, but I missed it.)

Here's another idea on similar principle. Imagine the centers intact, and corners and edges in their correct relative positions but with each "tripod" of four rotated +1 around the corner tip. Thus, every center needs to be separated from its adjacent edges, breaking every tripod leg and requiring it to be restored. For good measure, three of the centers could be cycled.


----------



## IAssemble (Jul 6, 2013)

IAssemble said:


> This is probably not as bad as you might think because even with a reduction algorithm, the act of solving the centrers will disturb the 3x3x3 superflip so it is unlikely to be as hard to solve the 3x3x3 after the edges are re-paired. Intuitively, I would not expect this to be particularly hard.
> 
> And as an example, here is a 31 turn OBTM solution generated quite quickly by my solver  U' L' Fw Uw' U B Fw2 F Lw R' Dw R' B2 R F2 R2 U2 F D' B R' L2 U' L2 U L2 B' R B D2 L



I've been thinking further...

Bringing together ideas discussed so far (and again some "intuitive" thoughts):

Edge parity is a relationship between the edges and the centres. It is "hard" because 8 of the centre pieces have to be re-positioned relative to the others I believe.

The diagonal centre position that cmhardw suggested does seem relatively hard to solve purely in terms of the centres (because putting any two centres together does not put any adjacent centre together at the same time?)

So perhaps the composition of these two is "hard"?

Does anyone here have some mathematically-based reasoning that they can apply to this?

My solver does not immediately find particularly good solutions to this in OBTM although this is no real indicator of how long its optimal solution might be. Anyone else with a solver care to try?

Here is a 50 OBTM solution: Dw' B' Lw' Dw' D Bw L Dw L2 R F' Dw R B F' Uw' L' U2 B Dw2 R' U' F2 R F2 Dw2 Bw2 R F' R' Bw2 R B D' R U' F' R2 U F D L2 B2 D2 L' D2 B2 L' B L'

It has so far only found a 31 turn reduction that eliminates the parities (without the 3x3x3).

This makes me think... has anyone considered an optimal solver for just the reduction phase (including fixing the parities)? I realise that this would not lead directly to an optimal solver but it might be one way of reducing the upper bound on God's Number for a 4x4x4.


----------



## Carrot (Jul 6, 2013)

kclejeune said:


> Very. Think about it.. In the past ten years, technology has evolved at an incredible rate. *The iPod was invented. The iPhone.* New computers, new chips, processors, software. Cloud storage. The price of flash memory is less than 50c per GB now. That's an excellent example. Several years ago, a 1GB card could cost over $100. Now, a 128GB costs almost half of that. These are just a few examples I can think of off the top of my head.



What techonological leap are you implying? Wasn't the iPod just an mp4 player? and the iPhone... wasn't that just a phone with camera, touch screen and music library (I'm pretty sure similar things were already around)?


----------



## qqwref (Jul 6, 2013)

How about that diagonal center pattern, but with "2-cycles" of centers instead of 3-cycles (e.g. white-red, red-white, green-yellow, yellow-green, blue-orange orange-blue)? Maybe if we add OLL parity to the mix it will be pretty tricky.

Also, an idea: your solver seems to directly solve reduction and then 3x3x3, so what about finding a position that is very hard to reduce and then making it solve a 20f* 3x3x3 position after it?


----------



## irontwig (Jul 6, 2013)

How about just a scramble where (if possible) there's no one move pairs (wing-wing,wing-corner, wing-centre or centre-centre)?


----------



## Christopher Mowla (Jul 6, 2013)

IAssemble said:


> My solver does not immediately find particularly good solutions to this in OBTM although this is no real indicator of how long its optimal solution might be. Anyone else with a solver care to try?
> 
> Here is a 50 OBTM solution: Dw' B' Lw' Dw' D Bw L Dw L2 R F' Dw R B F' Uw' L' U2 B Dw2 R' U' F2 R F2 Dw2 Bw2 R F' R' Bw2 R B D' R U' F' R2 U F D L2 B2 D2 L' D2 B2 L' B L'
> 
> It has so far only found a 31 turn reduction that eliminates the parities (without the 3x3x3).


I found shorter solutions by hand (using my own "optimized" reduction method).

* (Total: 47 OBTM, Reduction: 29 OBTM, 3x3x3: 18 OBTM)*
Rw' F' Rw U2 F2 L F' R2 B Rw F U' R Uw F2 Uw' L R2 U B Uw R2 Uw' L' D F Uw' L2 Uw
F R' F L' U R2 D' R' F L B2 D2 R2 D2 R2 B U R

*(Total: 48 OBTM, Reduction: 30 OBTM, 3x3x3: 18 OBTM)*
Rw' F' Rw U2 F2 L F' R2 B Lw D' U' Fw L2 Fw' D2 R U' Fw D2 Fw' F2 D' R' B R U Bw' R2 Bw
R2 F2 D' L2 B2 U B2 U2 R B D' F' D R D' L' R F' x

I did get a 27 OBTM reduction, but it has PLL parity, just as the 4 or 5 28 OBTMs and another 29 I found did. :fp
Rw' F' Rw U2 F2 L F' R2 B Lw D' U' Fw L2 Fw' D2 F' R Fw D2 Fw' R2 U2 L' Fw R2 Fw' x


----------



## IAssemble (Jul 7, 2013)

cmowla said:


> I know this question wasn't directed at me, but I'm curious how many moves it takes your solver to solve the following cases:
> [1] Rw' U' R' U' Rw F' R' F' Rw'
> [2] Lw F2 U2 l' U2 Lw U' R U l U2 l' U R' U Lw' F2 Lw'
> [3] And just a "potential bad case" to check: the case generated by this set of algorithms.



My solver found:

[1] Rw F R F Lw' B R B Lw 9 turns OBTM
[2] Rw2 U2 Rw F2 U2 Lw' B2 U2 Lw2 D2 Lw' F R F U' F' R' D' F U F' D F U' 24 turns OBTM

I will try [3] later...



ben1996123 said:


> something like this seems like it might need a lot of moves



Not too bad?

Uw' R2 B2 Uw' B' L U' L Uw2 F2 Dw R2 Dw2 F' U2 D B2 L F D B R2 B L U F R' B2 R F' B' 31 turn OBTM



cmowla said:


> I found shorter solutions by hand (using my own "optimized" reduction method).
> 
> * (Total: 47 OBTM, Reduction: 29 OBTM, 3x3x3: 18 OBTM)*
> Rw' F' Rw U2 F2 L F' R2 B Rw F U' R Uw F2 Uw' L R2 U B Uw R2 Uw' L' D F Uw' L2 Uw
> ...



Interesting - I am impressed that you can find such good solutions by hand.

But I'm confused...

Did you use my sequence as a generator rather than a solver? I hadn't thought of this before, but depending on the permutation of the centre pieces of the same color, I think there may be many sequences that appear to solve a given scramble so that if the same sequences are applied to a solved cube (and not reversed) they will generate different positions! I believe this does not happen on a 3x3x3 cube because all positions are distinct. 

I was puzzled at first when I loaded your solutions because I could not get them to show diagonals on all four centres either by treating them as solvers or generators!

My sequence was intended to be a solver view but if you treat it as a generator, it creates the position that I suspect you used as the start position for your solve? Your solutions are from that position (which does not have diagonals on each face) to solved. These sequences are not precisely the inverse of my sequence because the same color middles are permuted in different ways...

Please can someone confirm whether my understanding is correct?

Perhaps for consistency and to avoid this happening again, we should all post either solvers or generators? What do you think?

In the mean time I fixed a minor issue with my solver that was causing it to miss exploring some potential reductions and it has subsequently found this *Solution* to the position I suggested which is the diagonal centres proposed by cmhardw with the addition of a single edge flip (note that I do not think that composing a generator for a centre diagnonal and a generator for a single edge flip generator will not necessarily generate because of the centre permutations):

U' R B' Rw2 B2 Fw2 Dw' D Rw L' Uw2 U D Lw F' R Uw R2 F' R2 F Uw' R' U F' U' R2 F D' L' D2 L B D' B U 36 turn OBTM


----------



## ben1996123 (Jul 7, 2013)

IAssemble said:


> Not too bad?



Did you do a single edge flip yet?


----------



## IAssemble (Jul 7, 2013)

ben1996123 said:


> Did you do a single edge flip yet?



The best it has achieved so far is:

U2 L2 Lw2 U2 F2 Lw F2 L Lw' F2 Lw2 U2 Lw R' F2 R Lw' F2 Lw L' F2 L F2 23 turn OBTM


----------



## ben1996123 (Jul 7, 2013)

IAssemble said:


> The best it has achieved so far is:
> 
> U2 L2 Lw2 U2 F2 Lw F2 L Lw' F2 Lw2 U2 Lw R' F2 R Lw' F2 Lw L' F2 L F2 23 turn OBTM



mirroring and simplifying a bit:

U2 2R2 U2 x U2 r' U2 2R U2 r2 x' U2 2L' U2 2L x U2 2R' U2 R' U2 x'

30qtm


----------



## IAssemble (Jul 7, 2013)

ben1996123 said:


> mirroring and simplifying a bit:
> 
> U2 2R2 U2 x U2 r' U2 2R U2 r2 x' U2 2L' U2 2L x U2 2R' U2 R' U2 x'
> 
> 30qtm



Indeed, it "could be better" compared with the known best pure edge flip algorithms  However, I think I expect this because of the method.

The algorithm is a reduction with parities fixed to a pure 3x3x3 position. It tries to find short solutions to the reduction phase without considering anything about the "simplicity" of the 3x3x3 position.

For example it finds this reduction for the pure edge flip case which is only 13 turns OBTM. I suspect is probably pretty short for an OBTM edge flip parity algorithm?

Uw' F R2 F' Uw' R2 Uw' R2 Uw' B' R2 B Uw'

I would argue that the chance of such an approach finding a reduction which just happens to end with the 3x3x3 solved is approaching 1 in 4.3x10^19 (possibly divided by some factors to take into account centre piece permutation and maybe less because the number of possible positions reached by a short reduction phase may be fewer than this. However, it is almost certainly far too low a probability to hit "by chance").

In order to find a good solution for a pure edge flip, I believe the algorithm would have to target the complete solution directly rather than by reduction. Of course it has already been observed that reduction is not optimal (although it it could be that the worst case position(s) has/have optimal solutions that are effectively reductions if it has a point after which only outer layer turns are made).

I am probably more interested in bounding general solutions rather than necessarily finding optimal solutions for positions that are known to be far below the lower bound of worst case. Although this is one of the things that has made me think about trying to "guide" the reduction phase towards 3x3x3 positions that are easier to solve rather than leaving it purely to chance.

Thinking further about the "reduction is not optimal" statement... could it be that reduction is optimal for the worst case positions and if so could it be proven?

What if it could be proven that:

1) one specific position (which "happens" to be one of the worst case positions) requires at least N moves
2) reduction of any position to a pure 3x3x3 position requires at most M moves
3) we already know that 3x3x3 is 20 moves worst case (thanks to Rokicki et.al.)
4) we were "lucky" and N = M+20

This would be the extreme case of using worst case reduction followed by worst case 3x3x3 to find an upper bound that happened to be equal to a lower bound found by some other method.

Even if we cannot do this, or we can do 1) and 2) but M+20 > N, finding either an N to increase the current lower bound or an M shown to reduce the known upper bound would be interesting!

Any thoughts?


----------



## Christopher Mowla (Jul 7, 2013)

IAssemble said:


> My solver found:
> 
> [1] Rw F R F Lw' B R B Lw 9 turns OBTM
> [2] Rw2 U2 Rw F2 U2 Lw' B2 U2 Lw2 D2 Lw' F R F U' F' R' D' F U F' D F U' 24 turns OBTM
> ...


Thanks. It looks like your solver is on the same page as I am for the 9 mover. For the second algorithm, I guess I wasn't being fair showing you a 21 OBTM solution I found (the briefest in OBTM I found), but I was just curious.



IAssemble said:


> Did you use my sequence as a generator rather than a solver?


You're correct. My mistake.

For the sake of it, I gave the inverse a shot, but the best I could create was a 56 OBTM solution (Reduction: 38 OBTM, 3x3x3: 18 OBTM).
F' B Dw' B2 F2 Dw Lw' F Uw' F2 Uw B' Uw B2 Uw' B F U' D Fw R2 Fw' U' R2 U B Rw B2 Rw' F2 L2 D' L D' F Lw D2 Lw'
F2 L U2 F2 R U' F L' F R2 U L' D2 B2 D' B' L' U' x' 

I didn't spend as much time on it as I should have, however. If this position manages to stay of great importance, I will have another crack at it...maybe I can shorten my solution a little more to perhaps be sub 50 in the future (if that's the minimum your solver can solve it in).

EDIT:
I just redid the ending of the reduction and got a 52 OBTM solution (Reduction: 35 OBTM, 3x3x3: 17 OBTM)
F' B Dw' B2 F2 Dw Lw' F Uw' F2 Uw B' Uw B2 Uw' R D F2 U Lw' F2 Lw R D2 L Bw' R2 Bw R' B R B' Lw' B2 Lw 
R F2 U' F2 D B2 L2 F' D2 F2 R' D2 B L' R U2 F2 x'


----------



## IAssemble (Jul 7, 2013)

cmowla said:


> Thanks. It looks like your solver is on the same page as I am for the 9 mover. For the second algorithm, I guess I wasn't being fair showing you a 21 OBTM solution I found (the briefest in OBTM I found), but I was just curious.
> 
> You're correct. My mistake.
> 
> ...



Ah - thanks for confirming.

I suspect that it may be harder to do the reduction now because now all 6 faces have diagonal centres whereas before you were working with only two?

I mentioned that it has already found a shorter solution: U' R B' Rw2 B2 Fw2 Dw' D Rw L' Uw2 U D Lw F' R Uw R2 F' R2 F Uw' R' U F' U' R2 F D' L' D2 L B D' B U 36 turn OBTM

So diagonal centres does seem to be "hard"...



qqwref said:


> How about that diagonal center pattern, but with "2-cycles" of centers instead of 3-cycles (e.g. white-red, red-white, green-yellow, yellow-green, blue-orange orange-blue)? Maybe if we add OLL parity to the mix it will be pretty tricky.



So perhaps I should invest some time looking at the 2-cycle cases as well as this 3-cycle case...



qqwref said:


> Also, an idea: your solver seems to directly solve reduction and then 3x3x3, so what about finding a position that is very hard to reduce and then making it solve a 20f* 3x3x3 position after it?



Yes, this is where my thoughts are heading... 

At a slightly different angle, does anyone have any analysis or intuition of edge parity vs. centre scramble? For solved centres it is easy to define edge parity but if the centres are scrambled I am not aware of a definite relationship. For example if you are "half way" through an edge parity algorithm, how does the "edge parity" and centres relate?

I believe that the edge parity relates to the number of quarter inner layer turns. I believe that an edge parity algorithm will always have an odd number of quarter inner layer turns. Is this correct? So when the centres are scrambled, changing edge parity only makes the reduction significantly harder if it forces significantly more turns in order to solve the centres (and pair edges) with an odd number of quarter inner layer turns than with an even number. Does that make sense?

For general, random scrambles I suspect that the centres can be solved with sequences of roughly equal length with either an odd or an even number of quarter inner layer turns (by "intuition" and empirical results) so perhaps edge parity only really makes positions with almost solved centres or symmetrical centres significantly harder?


----------



## qqwref (Jul 7, 2013)

IAssemble said:


> For example it finds this reduction for the pure edge flip case which is only 13 turns OBTM. I suspect is probably pretty short for an OBTM edge flip parity algorithm?
> 
> Uw' F R2 F' Uw' R2 Uw' R2 Uw' B' R2 B Uw'


This is a really cool alg!


----------



## Christopher Mowla (Jul 8, 2013)

qqwref said:


> This is a really cool alg!


It is, but it's not new. I'm suprised you don't remember it (a different variation of it, which translates to all cube sizes--using either wide turns or single slice turns, is in the wiki as the very first PetrusParity algorithm on the 4x4x4 parity algorithms page).

cuBerBruce found it almost 2 and a half years ago with a solver he made:



cuBerBruce said:


> For OLL parity (only), one such alg is:
> 
> Uw B' L2 B Uw B2 Uw R2 Uw R F2 R' Uw


He made a nice summary page of all of his optimal parity maneuver searches for the 4x4x4 on this page.

In fact, by studying cuBerBruce's algorithm, I made the following two algorithms (which you were interested in using for fixing parity on very large cubes) by just using the F face and U face: (History)
r' U2 F' U2 F U2 r' U2 r' U2 r' F' U2 F r'
l U2 F' U2 F U2 l U2 l U2 l F' U2 F l

Then I made it into <U,Rw,R> (History)
Rw' U R' U2 R U' Rw' U2 Rw' U2 Rw' U' R U2 R' U Rw'
, but Kåre Krig created this version of the algorithm independently with his solver about a year and a half before I made it. It's one of the first algorithms in his 3flip text document attached to this post (it's surrounded by outer layer turns).

And finally, I found a related path that was in <U, Rw,L> (History)
Rw' U' L' U2 L U Rw' U2 Rw' U2 Rw' U L' U2 L U' Rw'


----------



## IAssemble (Jul 8, 2013)

cmowla said:


> It is, but it's not new. I'm suprised you don't remember it (a different variation of it, which translates to all cube sizes--using either wide turns or single slice turns, is in the wiki as the very first PetrusParity algorithm on the 4x4x4 parity algorithms page).
> 
> cuBerBruce found it almost 2 and a half years ago with a solver he made:



It isn't quite the same as the one you mention. cuBerBruce's has turns on 5 different faces rather than 4 and the outer layer 180 degree turns are on three different faces. Although I suspect someone might be able to show how one can be derived from the other...


----------



## Christopher Mowla (Jul 8, 2013)

IAssemble said:


> It isn't quite the same as the one you mention. cuBerBruce's has turns on 5 different faces rather than 4 and the outer layer 180 degree turns are on three different faces. Although I suspect someone might be able to show how one can be derived from the other...


Yeah, I derived yours from his before I made that claim, just to be sure (but I am so familiar with cuBerBruce's alg, I didn't doubt for a second).

Yours
Uw' F R2 F' Uw' R2 Uw' R2 Uw' B' R2 B Uw'

cuBerBruce's
Uw B' L2 B Uw B2 Uw R2 Uw R F2 R' Uw
_(Note that cuBerBruce found over 10,000 optimal maneuvers in OBTM for both double parity and OLL parity-only cases. In this post, he gave a skeleton of how to generate a subset of the algorithms he found.)_

I'm going to transform cuBerBruce's algorithm into yours:



Spoiler:  Transformation



[1] Take the inverse:
Uw' R F2 R' Uw' R2 Uw' B2 Uw' B' L2 B Uw'

[2] Adding in cube rotations to affect the same portion of the cube as your alg,
z2 Uw' R F2 R' Uw' R2 Uw' B2 Uw' B' L2 B Uw' y z2
=
Dw' L F2 L' Dw' L2 Dw' B2 Dw' B' R2 B Dw' y'
= 

[3] Using wide turn equivalence Dw' = (Uw' y),
= (Uw' y) L F2 L' (Uw' y) L2 (Uw' y) B2 (Uw' y) B' R2 B (Uw' y) y'
= Uw' y L F2 L' Uw' y L2 Uw' y B2 Uw' y B' R2 B Uw' y y'

[4] Carrying through the first y cube rotation,
= Uw' F R2 F' Uw' y2 L2 Uw' y B2 Uw' y B' R2 B Uw'

[5] Carrying through the second,
= Uw' F R2 F' Uw' R2 Uw' y' B2 Uw' y B' R2 B Uw'

[6] The third,
= Uw' F R2 F' Uw' R2 Uw' R2 Uw' y' y B' R2 B Uw'
= Uw' F R2 F' Uw' R2 Uw' R2 Uw' B' R2 B Uw'
= yours


Same alg. It's very interesting that your solver finds solutions like these, however. I can't imagine what type of algorithm you use (despite that I've read about your description of its basics on this forum, but "you got the brains").


----------



## cuBerBruce (Jul 8, 2013)

cmowla said:


> _(Note that cuBerBruce found over 10,000 optimal maneuvers in OBTM for both double parity and OLL parity-only cases._



I used block turn metric, not outer block turn metric. Many use inner layer turns which count as 2 turns in OBTM.


----------



## ch_ts (Jul 8, 2013)

IAssemble said:


> The best it has achieved so far is:
> 
> U2 L2 Lw2 U2 F2 Lw F2 L Lw' F2 Lw2 U2 Lw R' F2 R Lw' F2 Lw L' F2 L F2 23 turn OBTM



I ran this single edge flip through my solver. It uses slice turns not wide turns, but it did turn up something I thought was interesting.

So I scrambled with this:
U2l2U2F2LlF2l'F2L2l2U2LlR'F2RL'l'F2lF2LF2

and on the way to solving it, it passes through this position:
r' F2 r2 U2 F2 r F2 U2 r F2 r2 (3-cycle of edges, not really sure what people call this, is it a half-edge? I'm using lowercase letters to denote the inner layer)

The actual way it continued from here seemed a little roundabout so I inserted a commutator instead like this:
r' F2 r2 U2 (D'fD F2 D'f'D F2) F2 r F2 U2 r F2 r2
= r' F2 r2 U2 D'fD F2 D'f'D r F2 U2 r F2 r2


----------



## Christopher Mowla (Jul 9, 2013)

ch_ts said:


> I ran this single edge flip through my solver...and on the way to solving it, it passes through this position:
> r' F2 r2 U2 F2 r F2 U2 r F2 r2 (3-cycle of edges, not really sure what people call this, is it a half-edge? I'm using lowercase letters to denote the inner layer)


It's a 4-cycle, silly. a 4-cycle + the proper 3-cycle creates a 2-cycle.

Just to let you know, the current minimum in OBTM for this case is 19. These two algorithms I found established this move count.
x' Rw2 U2 Lw' U2 r U2 Rw U2 x' U r U' F2 U r' U Rw2 x
x' Rw2 U2 Lw' U2 r U2 Rw U2 x' U' r U F2 U' r' U' Rw2 x

And the current minimum in OBQTM (qtm) for this case is 24. These two algorithms I found established this move count.
z Dw' M D Lw' Uw' r' Uw Lw Uw' Lw2' Bw' r' Bw Rw' R' u y' M' Uw x2 z' (I named it "the holy grail")
Rw' E Uw2 Fw Uw Rw' r' Fw' r Fw Rw Uw' Fw' Uw r Uw E' Rw



IAssemble said:


> At a slightly different angle, does anyone have any analysis or intuition of edge parity vs. centre scramble? For solved centres it is easy to define edge parity but if the centres are scrambled I am not aware of a definite relationship.


First of all, yes, all odd-numbered dedge flip algorithms have an odd number of inner layer quarter turns. Mathematically, there is no relationship between center scrambles and edge parity, neither on the 6-colored 4x4x4 or the 4x4x4 supercube. See example 5 on page 3 of my PDF.



IAssemble said:


> For example if you are "half way" through an edge parity algorithm, how does the "edge parity" and centres relate?


If we are talking about optimal algorithms for any move metric, it really depends (with algorithms which are longer than optimal, anything goes: there is no consistent pattern because there are so many more algorithms which are not move optimal). I have created a lot of these algorithms and decomposed most (if not all) other algorithms I tried to decompose.

The most interesting part of a 4x4x4 parity algorithm is where the extra quarter turn is. So the point of interest can be virtually at any point in the algorithm, though, as you said, it's more commonly closer to the middle than the immediate beginning or end.

So let's observe what the centers are like at the location where the quarter turn is:


Spoiler: Examples






Spoiler: OLL parity (only) algorithms which are not one dedge flips optimal in OBTM and optimal in OBQTM (qtm)



Taking your version of the 13 OBTM algorithm, and applying all of the algorithm before the extra quarter turn,
Uw' F R2 F' Uw' R2 Uw' R2 Uw' B' R2 B Uw'
, observe that the extra quarter turn is the next move, Uw', and notice that two red 1x2 center blocks are adjacent to each other in the u slice.





Spoiler: One dedge flip algorithms optimal in OBTM



Taking my two algorithms (which I have shown at the beginning of this post) and applying all moves before the extra quarter turn,
x' Rw2 U2 Lw' U2 r U2 Rw U2 x' U r U' F2 U r' U Rw2 x
x' Rw2 U2 Lw' U2 r U2 Rw U2 x' U' r U F2 U' r' U' Rw2 x
Notice that the extra quarter turn is the move r and notice that two white 1x2 center blocks are adjacent to each other in the r slice.





Spoiler: One dedge flip algorithms optimal in OBTQTM (qtm) and BQTM (q-b)



Taking my two algorithms (which I have shown at the beginning of this post), and executing all moves before the extra quarter turn...
z Dw' M D Lw' Uw' r' Uw Lw Uw' Lw2' Bw' r' Bw Rw' R' u y' M' Uw x2 z' (I named it "the holy grail")
The extra quarter turn is the move r'. Notice that in the r slice, the D and B faces contain two individual green X-center pieces AND the F and D faces contain two individual orange X-center pieces which are "adjacent" to each other in the same sense as the previous algorithms. Watch this (just for about a minute or so) for a vocal explanation of this formation of individual centers.

A similar situation holds for the second algorithm (the green and orange X-center pieces in the F, D, and U faces)
Rw' E Uw2 Fw Uw Rw' r' Fw' r Fw Rw Uw' Fw' Uw r Uw E' Rw





Spoiler: One dedge flip algorithms optimal in btm (h-b, BHTM, etc.)



As I stated here, there are only two main types of optimal algorithms in this move metric: symmetrical and non-symmetrical algorithms. (I define a symmetrical algorithm to be an algorithm which its first and last moves are inverses of each other. A non-symmetrical algorithm's first and last moves generally are not inverses of each other). Each type only has two distinct algorithms. So this gives us a total of 4 algorithms to look at. I put them and all of their transformations in the wiki here (note that algorithms which end in B2 could technically be two algorithms instead of one if we conjugate the algorithm with B2, since that won't change the location of the flipped dedge neither will it change the center which is rotated 180 degrees).

For the symmetrical algorithms, executing the portions of the algorithms before the extra quarter turn, we observe the same situation as we did for algorithms optimal in OBTM and OBQTM,
r2 B2 U2 l U2 r' U2 r U2 F2 r F2 l' B2 r2
r2 B2 U2 l' U2 r U2 r' U2 B2 r' B2 l B2 r2

For the non-symmetrical algorithms, we find that at the extra quarter turn, the two white 1x2 center blocks (which are going to be swapped with each other) are *opposite* rather than adjacent.
r' U2 l F2 l' F2 r2 U2 r U2 r' U2 F2 r2 F2
r B2 r' U2 l B2 l2 B2 U2 l U2 l' U2 l2 B2

I was successful to create a brief non-symmetrical 2-cycle algorithm in btm, but it's not optimal in btm (I made four 15 btm symmetrical algorithms), but we can see that all individual center pieces in the r slice in the top half of the cube is similar to the structure of the centers before the extra quarter turn for the optimal algorithms in OBQTM for the singe dedge flip case.
r' Uw Lw Uw' r2 Fw2 Lw' Fw r' Fw' Lw Fw2 r' Uw Lw' Uw'


Now, let's look at some more messy parity algorithms.


Spoiler: OLL parity (only) algorithm which are not one dedge flips optimal in BQTM (q-b)



We look at cuBerBruce's elegant 15 BQTM OLL parity (not double parity) solution:


cuBerBruce said:


> ...The curly braces indicate a choice of any of the moves listed within.
> 
> I note that the last two are mirror-symmetric to their own inverse.
> 
> { Uw, u, d } (lr') R D R' Fw f (ud') l' (u'd) Fw b (u'd) F { Lw, l, r } (OLL parity)...


Choosing the wide turns as the first and last moves in the curly braces and adding cube rotations at the end (to bring all composite centers into their original positions),
Uw M R D R' Fw f E' l' E Fw b E F Lw x2 z'

You'll find in the spoiler of this post, I decomposed this algorithm to:
(Uw F' B2 R B' U) (u2 L' R u' R' L u2) (U2 D' B F' L Dw)
where the red move is the extra quarter turn.

cuBerBruce's algorithm is what I call a "single slice turn based" algorithm because wide turns are not required, although they exist in the algorithm due to different slices merging as such. The "holy grail" algorithm and the non-symmetrical 2-cycle algorithm I have above I refer to as "wide turn based" because wide turns are required.

Observe the u slice when the porition of the algorithm before the extra quarter turn (Uw F' B2 R B' U) (u2 L' R): we have "double" of the 4 X-center piece formation described for the holy grail alg (and my oriented 2-cycle non-symmetrical algorithm r' Uw Lw Uw' r2 Fw2 Lw' Fw r' Fw' Lw Fw2 r' Uw Lw' Uw'), except that all of the pieces in the u slice are "slid" once. Watch this to see what I mean by slid.

The extra quarter turn in cuBerBruce's algorithm would make more sense if all of the center pieces in the u slice had the formation I put the center pieces in the r slice in to make the optimal h-b and q-b checkboard algorithm (f2 u' r2 Uw2 S') r (S Uw2 r2 u f2)





Spoiler: OLL Parity algorithms possibly optimal in OBTM and h-b in <U, Rw,R>



I can't recall at the moment exactly which one of Kåre Krig's algs I shortened to create the following 17 move algorithm, however we can see that the two white 1x2 center blocks are again adjacent to each other in the r slice before the extra quarter turn.
Rw U2 Rw2 U' Rw' U2 Rw U2 Rw' U Rw' Rw' U2 Rw2 U R2 U' Rw'

Obviously the alg I showed in my post before last in this thread is also currently the lowest in OBTM for the move set:
Rw' U R' U2 R U' Rw' U2 Rw' U2 Rw' U' R U2 R' U Rw'

If you look carefully, this is nothing more than (Rw' U2)4 Rw' with some U and R turns inserted. My decomposition for (Rw' U2)4 Rw', as I've shown before in another thread, is:

Rw'//setup moves 1
U2 Rw' U2 Rw
Rw2 U2//setup moves 2
Rw'//extra quarter turn
U2 Rw2//undo setup moves 2
Rw//undo setup moves 1

So the portion of this algorithm before the extra quarter turn is:
Rw' U R' U2 R U' Rw' U2 Rw' U2 Rw' U' R U2 R' U Rw'
, which, again the centers have the same formation as most of the algorithms mentioned thus far.





Spoiler: Optimal one dedge flip algorithm in OBTM in <U,Rw>



At the very beginning of the second spoiler in this post, I decompose one of the two optimal algorithms for this case in this intense move restriction set.
Rw U Rw' U Rw' U Rw2 U2 Rw2 U Rw' U2 Rw U2 Rw (Rw) Rw U2 Rw' U' Rw' U' Rw U Rw' U2 Rw U2
Again, notice the formation of the individual center pieces (blue and white) in the r slice in the F and D faces.

The long <U,Rw> algorithm I found is also in that post. It's an entirely different way to tackle the same case (not on the supercube, though) in the same move set. You will find that the individual center pieces (white and yellow) have a similar formation to the one in the r slice of the "holy grail alg".

Rw U Rw U Rw U' Rw' U2 Rw2 U2 Rw U2 Rw' U Rw2 U' Rw2 U' Rw U2 Rw' U' Rw U2 Rw' U Rw U2 Rw' U' Rw U2 Rw' U' Rw U2 Rw' U Rw U2 Rw' U' Rw U2 Rw' U' Rw U2 Rw' U Rw U2 Rw' U' Rw U2 Rw' U' Rw U2 Rw' U Rw U2 Rw U Rw2 U' Rw U2 Rw2 U2 Rw2 U2 (Rw') U2 Rw U2 Rw' U2 Rw' U2 Rw2 U2 Rw2 U2 Rw' U2 Rw2 U Rw' U' Rw' U' Rw' U' Rw U2 Rw' U Rw U2 Rw' U2 Rw U Rw' U Rw U2 Rw' U2 Rw U Rw' U Rw U2 Rw' U2 Rw U Rw' U Rw U2 Rw' U2 Rw U' Rw' U' Rw U Rw' U2 Rw U2 Rw' U' Rw U' Rw' U2 Rw U2 Rw' U' Rw U' Rw' U2 Rw U2 Rw' U' Rw U2 Rw' U' Rw U Rw' U2 Rw U2 Rw' U' Rw U' Rw' U2 Rw U2 Rw' U' Rw U' Rw' U2 Rw U2 Rw' U' Rw U2 Rw' (244,187)

*Note that this algorithm is single slice turned based*, as its base (which can be found under step6 in the spoiler in the second spoiler in the same post) can be applied to different orbits of wings of higher order cubes like the 6x6x6, but it no longer stays 2-gen. I cannot say that the 26 move <U,Rw> algorithm is single slice turn based, and, looking at the center piece formation in at the intersection of Fw and r, we see the same formation as was in my (holy grail alg). So I'd call it wide turn based.








IAssemble said:


> For general, random scrambles I suspect that the centres can be solved with sequences of roughly equal length with either an odd or an even number of quarter inner layer turns (by "intuition" and empirical results) so perhaps edge parity only really makes positions with almost solved centres or symmetrical centres significantly harder?


This seems to be the case.


----------



## IAssemble (Jul 9, 2013)

Thanks cmowla for taking the time to write such a comprehensive response!



cmowla said:


> ...
> 
> First of all, yes, all odd-numbered dedge flip algorithms have an odd number of inner layer quarter turns. Mathematically, there is no relationship between center scrambles and edge parity, neither on the 6-colored 4x4x4 or the 4x4x4 supercube. See example 5 on page 3 of my PDF.
> 
> ...



I think these statements are immediately useful to me  I am currently working on a way of optimising my reduction phase search to take into account edge parity earlier in the process to avoid wasting time searching branches which lead to reductions with edge parity which are later discarded. Confirming my understanding of odd-numbered dedge vs. inner layer turns is particularly useful and the concept of an "extra" quarter inner layer turn and its position is thought-provoking.

The rest of your response is also extremely interesting and I will take time to digest it and the links you provided. 



cmowla said:


> IAssemble said:
> 
> 
> > For general, random scrambles I suspect that the centres can be solved with sequences of roughly equal length with either an odd or an even number of quarter inner layer turns (by "intuition" and empirical results) so perhaps edge parity only really makes positions with almost solved centres or symmetrical centres significantly harder?
> ...



Thanks. I think this is reassuring that I am not heading in completely the wrong direction with my current attempts to optimize my solver a little


----------



## Stefan (Jul 9, 2013)

IAssemble said:


> I am currently working on a way of optimising my reduction phase search to take into account edge parity earlier in the process to avoid wasting time searching branches which lead to reductions with edge parity which are later discarded.



Have you considered different reductions? I'd for example be interested in reduction to 3x3x4 (instead of to 3x3x3), which doesn't even have a parity issue.


----------



## IAssemble (Jul 9, 2013)

Stefan said:


> Have you considered different reductions? I'd for example be interested in reduction to 3x3x4 (instead of to 3x3x3), which doesn't even have a parity issue.



I have thought about a number of different intermediate routes to get to a pure (without parity issues) 3x3x3. At the moment this is my main focus because it seems to be reasonably efficient and I already have a good 3x3x3 solver for the final phase ;-)

I have also thought about reducing to 2x2x2 (i.e. solving all 2x2x2 corner groups independent of their position). It is easy to implement an optimal solver for the final 2x2x2 phase, and this would also have no parity issues. But there is more work required to reduce to a 2x2x2 state since obviously there fewer positions of the 2x2x2 than a 3x3x3. I have some ideas about how the reduction phase(s) could be implemented but not actually tried any coding yet. Does anyone use this form of reduction on 4x4x4 or perhaps even bigger cubes? e.g. reduce 8x8x8 to 4x4x4 and then 2x2x2?!? The programmer in me asks if this is a way of designing an algorithm that is better then O(N^2)? Is this anything like the technique that was used to show large cubes could be solved in O(N^2/log(N))?

I haven't considered any other reductions.

Your idea of reduction to 3x3x4 is very interesting. Do you mean by no parity issue that the 3x3x4 can always be solved without having to split any of the 2x2x1 and 2x1x1 sub-blocks (or have I mis-understood what 3x3x4 means? I'm trying to visualize this!)

Does this mean you have an efficient (or even optimal?!?) solver for the final phase?


----------



## cubernya (Jul 9, 2013)

I have thought about reducing a 4x4 to a 2x2. I tried it once, but it was terribly slow and inefficient, so I don't think it's worth it. If you can find a reasonable way to do this, then implement it


----------



## ch_ts (Jul 9, 2013)

Reduction to 3x3x4 will result in people complaining "your 4x4x4 solutions are so long in qtm!"  But I'm interested too...


----------



## Stefan (Jul 9, 2013)

IAssemble said:


> Do you mean by no parity issue that the 3x3x4 can always be solved without having to split any of the 2x2x1 and 2x1x1 sub-blocks



I was thinking of this and yes, you can take apart and randomly assemble it and it can always be solved. Kinda like a double Domino. Simulating it on a 4x4x4 would allow more movements (like R F, where the above puzzle would block the F turn, you can't really do R but just R2), and maybe that would be interesting, too, though it's not what I had in mind.



IAssemble said:


> Does this mean you have an efficient (or even optimal?!?) solver for the final phase?



No, sorry. But I think it has (fixing one corner as reference, and not reduced by symmetries) 2*7!*8!*8!*8!/2^4 = 4.1e16 states, significantly higher than 2x2x2 and "a little" less than 3x3x3. So an optimal solver should be doable and fast.


----------



## qqwref (Jul 10, 2013)

IAssemble said:


> I have also thought about reducing to 2x2x2 (i.e. solving all 2x2x2 corner groups independent of their position). It is easy to implement an optimal solver for the final 2x2x2 phase, and this would also have no parity issues. But there is more work required to reduce to a 2x2x2 state since obviously there fewer positions of the 2x2x2 than a 3x3x3. I have some ideas about how the reduction phase(s) could be implemented but not actually tried any coding yet. Does anyone use this form of reduction on 4x4x4 or perhaps even bigger cubes? e.g. reduce 8x8x8 to 4x4x4 and then 2x2x2?!?


Many people have tried something like this for fun, but it never leads to decent times. It is simply very inefficient as well as hard to recognize (in your 8x8x8 example, reducing centers to four 3x3 blocks each is certainly not easier for a human than reducing them to one 6x6 block each). Perhaps these problems will be easier to overcome on a computer solver, but I do feel like a lot of moves will be required to reduce to 2x2x2.


----------



## Christopher Mowla (Jul 10, 2013)

The answer to this question might help us in some way lower the upperbound for the 4x4x4. What's the current upperbound of the 3x3x3 supercube (in htm and qtm)? Or has God's number been calculated for that already (if so, what's God's number for it)? I am not sure if this would help, but what is the upperbound if all corners are solved, and only centers need to be rotated and edges need to be solved?


----------



## cuBerBruce (Jul 10, 2013)

I just thought I would make it clear that there are two reduction parities (for normal 3x3x3 reduction), and it's only the edge piece permutation parity (seen after reduction as a dedge orientation parity, and called OLL parity) that is not related to the state of the centers.

The other parity, commonly called PLL parity, pretty much requires reduction to be completed to be well-defined. It might be referred to as a dedge permutation parity, but it's really related to the fact that on the 3x3x3, the total permutation parity of corners, edges, and centers must be even. So on a 4x4x4, the total permutation parity of corners, dedges, and composite centers must be even for PLL parity to be even. If we regard the solved centers as defining the orientation of the cube, then the composite centers are automatically even parity, and PLL parity then is just the total parity of corners and dedges.

Just another note, sometimes people use the word "edge" to mean a single edge piece, and sometimes people use the word "edge" to mean a composite edge (or dedge on the 4x4x4). Saying "edge piece" or "dedge" can be helpful in making it clear which one you mean to avoid any possible confusion.



cmowla said:


> The answer to this question might help us in some way lower the upperbound for the 4x4x4. What's the current upperbound of the 3x3x3 supercube (in htm and qtm)?



Well, it's known that 21f* positions exist. There is a 21f* position needing only centers rotated. It is also known (statistical evidence) that positions requiring more than 22 moves are a very small percentage. (A 2-phase solver solved 1000 random positions with none of the solutions being more than 22 moves.) I'm not aware of any firm upper bounds.


----------



## Christopher Mowla (Jul 10, 2013)

cuBerBruce said:


> Well, it's known that 21f* positions exist. There is a 21f* position needing only centers rotated. It is also known (statistical evidence) that positions requiring more than 22 moves are a very small percentage. (A 2-phase solver solved 1000 random positions with none of the solutions being more than 22 moves.) I'm not aware of any firm upper bounds.


Thanks, cuBerBruce. If I assume it to be 24f, would I be safe (seriously, to use it as an undeniable basis to establish an upperbound for another problem)?
I know this is technically off-topic from this thread, but in my second to last post, I mentioned cuBerBruce's 15 BQTM OLL Parity (only) solution for the center formation at the quarter turn. Well, by doing so, I can finally say that I understand that solution completely, and, naturally, I have reproduced the procedure, making longer algorithms, of course.

My shortest solution so far is a (19,18), but I most likely will attempt to try again later.
Rw U D' M' R U' D' U R U' Dw2 r' Dw2 U' L2 D' R' U' R L2 U Rw = Uw S L D' R Uw u l' Uw u L2 D' R' U' M L' F Rw z' (OLL Parity only)

However, I made some long but interesting Roux algs using the same idea. So, for those who have never looked at cuBerBruces algorithm as something pretty, perhaps the structure of these two algs might make you change your mind, because they really do have the same exact structure as cuBerBruce's alg, despite how unbelievable that might be. Note that I made an effort to have the conjugates around the quarter turn be Uw2 instead of u2, Uw u, etc., despite that second 3x3x3 part of the first algorithm cancels with the Uw2.

OLL Parity (only)
 r U' M' U M' U' M' U' M Uw2 r Uw2 U' M' U2 M' U M U2 M U M' U M U M' U' l' (31,28)

Double Parity
 r' U M' U' M' U M' U M Uw2 l' Uw2 M' U M U' M' U M' U M U2 M' U2 r (29,25)

I cannot claim these to be optimal, but I suspect they are probably pretty close for this algorithm structure and move set. They are basically double the moves as cuBerBruce's alg in block quarter turns!


----------



## ch_ts (Jul 10, 2013)

Stefan said:


> No, sorry. But I think it has (fixing one corner as reference, and not reduced by symmetries) 2*7!*8!*8!*8!/2^4 = 4.1e16 states, significantly higher than 2x2x2 and "a little" less than 3x3x3. So an optimal solver should be doable and fast.



How about this for an efficient but not optimal approach:
1. Reduce 4x4x4 to 3x3x4
2. Reduce 3x3x4 to 3x3x3 with E layer edges oriented.
3. Kociemba phase 2


----------



## Stefan (Jul 10, 2013)

ch_ts said:


> How about this for an efficient but not optimal approach:
> 1. Reduce 4x4x4 to 3x3x4
> 2. Reduce 3x3x4 to 3x3x3 with E layer edges oriented.
> 3. Kociemba phase 2



If you do that, I guess phases 2 and 3 could be combined like Kociemba's algorithm combines its two phases, so could be good maybe. But with 1000 times fewer positions than 3x3x3, I really think a "normal" optimal solver for 3x3x4 should be feasible.


----------



## Christopher Mowla (Jul 13, 2013)

Hey guys,

I have a few more questions.

[1] Besides cuBerBruce's post here, is there any history of previous (higher) upperbounds for the 4x4x4 (established by other people). If so, can you provide links?

[2] Is 22 slice half turns (I'm guessing this is h-b/btm,BHTM) still the upperbound to solve the centers? How about in other move metrics?

[3] Assuming that all centers are solved first so that there is an even permutation in the wing edges, has anyone ever tried to see what's the maximum number of inner layer slice turns (e.g., r, r2, not speaking of M,E,S) required to pair all edges without creating PLL parity? I doubt that this can help us compute god's number, but I thought I should mention it just in case no one has ever thought of it and we maybe able to use it somehow in the future...(plus it's a new variation of reduction)


Spoiler: Conjecture



[1] If all centers are solved so that there is an even permutation in the orbit of wing edges,
[2] If it is possible to solve at least one wing edge of all 12 dedges (where the "solved" wing edge can be "unoriented" or "oriented", as long as one of the two is there), for example (just look at the cube, not the generating solution!) using only 3x3x3 moves and possibly: ONE application of a 3-cycle algorithm in two dedges, for example, OR Stefans PLL parity algorithm r2 F2 U2 r2 U2 F2 r2 at the end of the edge pairing solution,
then
all dedges can be paired (without inducing PLL parity AND preserving the colors of the centers) using a maximum of 6 inner slice half turns. (Of course, this is allowing any number of 3x3x3 moves in between.)

_Note that an easy way to disprove my conjecture is to just find one counterexample which violates [2]._





Spoiler: Sketch of proof (With Examples)



A potentially "worst" case is a wing edge scramble like this. Here's a solution I came up with to pair all dedges using only 6 inner layer half turn slices.


Spoiler: Solution



Rw2 L' D L2 F' Rw R2 F Uw F' Fw2 D2 R2 U F Rw2 R' B2 R' Fw' Uw U2 Fw2 R Fw' U L' D Rw Uw' L Uw' D' Fw B R2 Uw' R2 L B

R L Uw R B Uw D Lw B Lw' U Lw' B Lw B' L Uw2 L' Fw L2 f' B' D' Lw S2 Lw' z' y//center solution

R B2 L2 D2 L' B2 U2 R2 F U2 L' F' U' F R F2 D' R D2//edge setup and solve corners.
L B r F D'L F' D r' D' F L' D F' B' L'//3-cycle edge pairing alg

F' U2 L2 B' R2 B2 D L' B D' R' F L R' B2 L' F U F' L' U//edge setup for iteration 1
b2u
U' L F U' F' L B2 R L' F' R D B' L D' B2 R2 B L2 U2 F//undo setup for iteration 1 (but don't affect the composite centers/3x3x3 supercube algorithm)

L2 R2 B2 U R2 B2 L' R B L R' B2 L' F2 D B2 D2 B' L' D U' F2//setup for iteration 2 (but don't affect the composite centers/3x3x3 supercube algorithm)
u' b2
D' R' B' D B2 D2 U2 B' U' F' D' F2 R2 B' L U' L // (solve as a 3x3x3, PLL parity and OLL parity is not present and composite centers can be rotated in any fashion)

Which can simplify to (using CubeExplorer)

Rw2 L' D L2 F' Rw R2 F Uw F' Fw2 D2 R2 U F Rw2 R' B2 R' Fw' Uw U2 Fw2 R Fw' U L' D Rw Uw' L Uw' D' Fw B R2 Uw' R2 L B

R L Uw R B Uw D Lw B Lw' U Lw' B Lw B' L Uw2 L' Fw L2 f' B' D' Lw S2 Lw' z' y

U2 B' U2 R2 D2 L2 D' B2 D F' L2 F D' F L' U' R' D B'
r F D'L F' D r'
F2 U' B R' D' L' B F' L2 D2 B L' F' L' F D' B U'
b2u
F D2 L2 D2 R2 F' L2 B2 U2 F R' F2 D L F2 D' B2 R' U2 B F' L' B'
u' b2
D' R' B' D B2 D2 U2 B' U' F' D' F2 R2 B' L U' L


Here's an alternate solution to the centers which creates a wing edge case which can be solved without an edge-pairing 3-cycle algorithm (in two dedges), but, since the corners need to be in an odd permutation to have half of all dedges solved, we get PLL parity, which we can cleverly cancel moves with at the end of the algorithm before the final 3x3x3 solving portion to use a total of 5 half turn inner slice moves.


Spoiler: Solution 2



Rw2 L' D L2 F' Rw R2 F Uw F' Fw2 D2 R2 U F Rw2 R' B2 R' Fw' Uw U2 Fw2 R Fw' U L' D Rw Uw' L Uw' D' Fw B R2 Uw' R2 L B//scramble
U' F Rw' Dw' B2 Dw D Lw B2 Lw' U B' Rw B2 Rw' D Bw U Bw2 R Bw2 R Bw R' Bw R U' Fw' U2 Fw D Fw D' Fw'//center solution
D2 B R2 B L' B' F' R D F2 R D' B2 D' L U2 L2
l2 d
L2 B2 L2 F2 L U2 B L2 B R U' B2 F R' U L U' L' B2 L U' F //doesn't change centers.
d' F2 U2 l2 U2 F2 l2//PLL parity cancelled with one of the two inner slices.
F2 U2 L R2 B2 F' L' B' U' L' D2 B' D' R2 D2 F' U2 R2


And of course center solution exists which generate cases that don't need PLL parity or an edge pairing algorithm to leave us with a 4 or fewer inner half turn slice dedge pairing solution.



Spoiler: Meat of proof (if statement 2 is indeed correct)



If statement [2] is correct, then note that, since we "solve" at least 12 wing edges (again, for example) and since the wing edges are in an even permutation, my conjecture would be proven TRUE (which might be a useful fact or not so useful).

It turns out (I have done all of the calculations, but here are the results) that all 39 even permutation cycle classes for 12 objects can be solved using two iterations of a 4-cycle, 2 2-cycle, 4 2-cycle, or a 4-cycle + 2 2-cycle. (Note that some cycle classes can be solved using more than one of these cycle class iterative solutions, but the cycle classes are listed under the solution cycle classes which solve them in the fewest number of moves)

*4-cycle (The move r, for example)*
{3}
{2,2}
{5}
{4,2}
{3,3}
{7}
{4,4}

*2 2-cycle (The move r2, for example)*
{3,2,2}
{2,2,2,2}

*4 2-cycle (The moves r2 u2, for example)*
{6,2}
{5,3}
{9}
{5,2,2}
{4,3,2}
{3,3,3}
{7,3}
{6,4}
{5,5}
{4,2,2,2}
{3,3,2,2}
{7,2,2}
{6,3,2}
{5,4,2}
{5,3,3}
{4,4,3}
{3,2,2,2,2}
{6,2,2,2}
{5,3,2,2}
{4,3,3,2}
{3,3,3,3}
{2,2,2,2,2,2}

*4-cycle + 2 2-cycle (The moves u r2, for example)*
{8,2}
{11}
{10,2}
{9,3}
{8,4}
{7,5}
{6,6}
{4,4,2,2}


Therefore all even permutations of 12 objects can be solved using at most 4 inner layer slice half turns. 
We cannot cancel any of the inner slice turns above with the edge pairing algorithm _unless the wing__ edges involved are in the axes of the axes of the inner layer slice turn..._you all are probably clueless as to what I'm saying, but just take note that my assumption of 6 moves or less assumes that the 4 moves to solve every case does NOT always cancel with one of the two moves from the edge pairing algorithm, so we have a total of 4 + 2 = 6. 
The order of the slice moves in both iterations doesn't matter. For example, if we are solving an 11-cycle (represented by {11}), then we could either do u r2 in iteration 1 and r2 u' in iteration 2, to abbreviate, (u r2, r2 u') OR (r2 u, u' r2) OR (r2 u',u r2) OR (u' r2, r2 u). Since this is the case, if we 
Cancel the last two inner layer slices (before the final 3x3x3 stage) with Stefan's PLL parity alg. r2 F2 U2 r2 U2 F2 r2, it leaves us with a maximum of 5 moves. 






EDIT:

Here's another example solve which includes an edge pairing algorithm but I moved the edge pairing algorithm to the beginning of the edge pairing process to reduce the number of moves (not that this makes a difference in what my conjecture is about, but...)

The same scramble cuBerBruce solved with his solver here.
L' Fw' L' Fw D' R2 D' Uw' L2 B' F2 L Rw2 F' Rw R2 B Fw Uw U2 L R' D R Uw2 B2 Fw F2 D' L Fw' Rw R2 B2 D2 F' D' L' D2 B'//scramble 

D2 r2 B' L Uw Bw' D2 Bw R Uw R' U' Fw' U2 Fw U2 F' Lw' Rw' D2 Rw F2 Rw' D2 Rw U' Fw' L2 Fw x y2//center solution

U F' L U' F r F' U L' F U' r' //edge pairing algorithm

L2 U' F2 D' F D2 U2 F2 L U L' R' B2 U F2 L2 B2 R'
r u2 //4-cycle + 2 2-cycle (iteration 1)
B' R2 D2 R2 D2 B2 F D2 U' L' B2 R U2 F D2 U' R' D B F2 L D'
u2 r'//4-cycle + 2 2-cycle (iteration 2)
D F2 L2 U' L F' L D F2 L2 B D F D2 B R2 B D' //3x3x3

EDIT2:
In the example in the edit above, I used an edge pairing algorithm, but I was successful in solving half of the dedges just using 3x3x3 moves.

D2 r2 B' L Uw Bw' D2 Bw R Uw R' U' Fw' U2 Fw U2 F' Lw' Rw' D2 Rw F2 Rw' D2 Rw U' Fw' L2 Fw x y2
R' D2 F2 L' F D' L2 R B' L' R' D U2 L R' D L2

So why did I use an edge pairing algorithm? The cycle class this formation created was a 12-cycle (an odd permutation) because, as you can see by the cube in the link above, only one wing edge is "flipped" in DF, so despite that the permutation of all 24 wing edges is even, for the "unsolved" wing edges, it's an odd permutation (I didn't show this step previously).

And, recall that 4 inner slices are only required *if we have even permutation cycle classes of 12 objects*. Well, applying the edge pairing algorithm to the two edges that I did was like doing a 2-cycle to make it into an {8,4}, an even permutation.

Just thought I should mention that to point out that there are two reasons why we would need to use an edge pairing algorithm in some situations, if my conjecture is correct, of course
1) To essentially "flip" a single dedge (in this example).
2) To essentially swap two dedges. (in the first example containing an edge pairing algorithm).


----------



## IAssemble (Jul 13, 2013)

cmowla said:


> [3] Assuming that all centers are solved first so that there is an even permutation in the wing edges, has anyone ever tried to see what's the maximum number of inner layer slice turns (e.g., r, r2, not speaking of M,E,S) required to pair all edges without creating PLL parity? I doubt that this can help us compute god's number, but I thought I should mention it just in case no one has ever thought of it and we maybe able to use it somehow in the future...(plus it's a new variation of reduction)
> 
> 
> Spoiler: Conjecture
> ...





Spoiler: Conjecture



My solver only considers solutions for the centers that have even edge permutations. It's edge pairing methods preserve edge parity. 

The rest of your post is thought provoking! I will re-read and try to digest the rest later.


----------



## qq280833822 (Jul 13, 2013)

cmowla said:


> [1] Besides cuBerBruce's post here, is there any history of previous (higher) upperbounds for the 4x4x4 (established by other people). If so, can you provide links?



With the three-phase reduction algorithm (which is used in the latest wca 4x4x4 scrambler/solver), the upper bound can be reducted to about 60 OBTM (40 moves' reduction + 20 moves' 3x3x3).

The three-phase reduction algorithm is enhanced from tsai's 8-step algorithm(http://cubezzz.dyndns.org/drupal/?q=node/view/73#comment-2588). I merged the step3 and step 4 in tsai's algorithm, and the god number of each phases are(OBTM):

step1: 8
step2: 14
step3/4: <=18?
step 5~8: 20 //3x3x3 without any parity, the oll party is fixed in step2, and the pll parity is fixed in step3/4

I haven't finished full calculation of the god number of step3/4. But after solving 100000 state randomly, I haven't found any state who need more than 16 moves.
Thus, the upper bound should be <= 8 + 14 + 18 + 20 = 60.


----------



## qq280833822 (Jul 29, 2013)

*The god's number of 4x4x4 is no more than 57*

After analyzing step3&4 of tsai's algorithm, the upper bound is reduced to 57 (OBTM) moves (step1: 8 moves, step2: 13 moves, step3&4: 16 moves, step5~8: 20 moves).


----------



## ben1996123 (Jul 29, 2013)

oo cool


----------



## cubernya (Jul 29, 2013)

At least we're making some progress 

Is there any lower bound that has been established?


----------



## ben1996123 (Jul 29, 2013)

theZcuber said:


> At least we're making some progress
> 
> Is there any lower bound that has been established?



34 or something


----------



## elrog (Aug 18, 2013)

I had a couple of crazy ideas a couple of days ago about finding gods number. I don't really expect either to help at all.

One idea I had was to find some kind of pattern that is always gods number of moves away from solved (something like superflip?). You could then just find the optimal solution to the pattern for whatever size cube. I know superflip itself won't work because a 2x2 would already be solved.

Another idea I had was to add up how many possible series of moves (like how cube explorer searches, but you wouldn't actually have to go through each position) you can have for that size cube until you reach its possible number of states. The problem with this though is cancelling out identical positions (like doing 2 different algs of the same permutation).


----------



## qqwref (Aug 18, 2013)

elrog said:


> One idea I had was to find some kind of pattern that is always gods number of moves away from solved (something like superflip?). You could then just find the optimal solution to the pattern for whatever size cube. I know superflip itself won't work because a 2x2 would already be solved.


It would be awfully hard to prove that a given pattern always requires as many moves as possible. Sure, if we somehow did it it would help, but I'm not seeing any way it could be done, or any obvious patterns that would fit the bill.



elrog said:


> Another idea I had was to add up how many possible series of moves (like how cube explorer searches, but you wouldn't actually have to go through each position) you can have for that size cube until you reach its possible number of states. The problem with this though is cancelling out identical positions (like doing 2 different algs of the same permutation).


This is exactly how people compute lower bounds for God's Algorithm.


----------



## Herbert Kociemba (Aug 18, 2013)

qqwref said:


> It would be awfully hard to prove that a given pattern always requires as many moves as possible. Sure, if we somehow did it it would help, but I'm not seeing any way it could be done, or any obvious patterns that would fit the bill.
> 
> 
> This is exactly how people compute lower bounds for God's Algorithm.



Yes. And here is a generating function I developed some times ago for the number of "canonical sequences" (where commutating moves and cancellations like U U' etc. are taken into account) in OBTM for all NxNxN cubes.
This means, the Taylor expansion of this functions gives the number of maneuvers with a certain length.

Mathematica Code:

gfh[n_,x_]:= 3/(6-4(3x+1)^(n-1))-1/2

In[12]:= Series[gfh[4,x],{x,0,7}]
Out[12]= 1+27 x+567 x^2+11745 x^3+243486 x^4+5047596 x^5+104639202 x^6+2169224064 x^7+O[x]^8

This means, on the 4x4x4 there are for example 567 maneuvers with length 2

The corresponding generating function for the summed up maneuver length is gfh[n,x]/(1-x)

In[13]:= Series[gfh[4,x]/(1-x),{x,0,7}]
Out[13]= 1+28 x+595 x^2+12340 x^3+255826 x^4+5303422 x^5+109942624 x^6+2279166688 x^7+O[x]^8

This means there are for example 595 maneuvers on the 4x4x4 with length at most 2 in OBTM.

Together with Chris Hardwick's(?) formula for the number of positions on the NxNxN it is now easy to get lower bounds.
Starting with 2x2x2 the lower bounds are

{9,18,35,52,75,99,128,158,193,229,270,312,359,406,458,511,568,626,690....}

Of course I cannot prove this (except for 2x2x2 and 3x3x3  ), but I am sure, that God's number is only 2 or 3 moves away from these lower bounds, so for 4x4x4 I assume 37 or 38.


----------



## qqwref (Aug 18, 2013)

That generating function looks awfully simple... can you explain how it works?


----------



## Herbert Kociemba (Aug 19, 2013)

qqwref said:


> That generating function looks awfully simple... can you explain how it works?



Only in OBTM it seems possible to derive a closed formula. Without loss of generality we fix the DBL cubie of the nxnxn cube and use only the outer block moves of the U, R and F axis. We note, that the OBTM for the 3x3x3 is equivalent to the standard half turn metric HTM.

The generating function (GF) for a single block move on a fixed axis is 1 + 3 x (there are 3 possibilities for a single move), the GF for an arbitrary number of moves on a fixed axis is (1+3x)^(n-1). I am aware that you have to think a bit about this fact until you believe it. On 3x3x3 (1+3x)^2= 1+6x+9x^2, so there are 6 ways to do 1 move on a fixed axis and 9 ways to do 2 moves on a fixed axis. Dan Hoey called such a sequence of commuting moves (all moves on a fixed axis commute) a syllable. If we ignore the "do nothing" syllable, the GF of a syllable then is (1+3x)^(n-1) – 1.

An arbitrary maneuver is just a sequence of syllables, where of course adjacent syllables have to be from different axes. Let's call a syllable of the U, R and F axis X, Y and Z. Any maneuver has the form X, Y, Z, XY, XZ, YX, YZ, ZX, XY, XYX, XYZ, YXY, YXZ,….. The nice thing with GF's is that you get the GF of a combination by multiplying the GF's of the parts. Lets call (1+3x)^(n-1) – 1 := a. Then the GF for XZ is for example a^2 and for YXZ for example a^3. To find the resulting GF we have to add all these together.We get

GF(x) = 1 + 3a + 3a*(2a) + 3a*(2a)^2 + 3a*(2a)^3 + …….

here 3a*(2a)^3 for example belongs to the 24 possible 4-syllable combinations.

GF(x) = 1 + 3a(1 + (2a) + (2a)^2 + (2a)^3 + …….) = 1+3a/(1-2a)

If your resubstitute a=(1+3x)^(n-1) – 1 you will get

GF(x)= 3/(6-4(3x+1)^(n-1))-1/2 q.e.d.

In quarter turn metric, the GF for single block moves is (1 + 2x + x^2) and this leads to 

GF(x) =3/(6-4(x+1)^(2(n-1)))-1/2


Using a partial fraction decompositon it is even possible to give an explict formula for the coefficients in the power series expansion of GF(x), but this would carry things too far here.


----------



## Christopher Mowla (Aug 30, 2013)

This idea has probably been thought of before years before my time, but what I am about to say is what I believe to be a more concrete description of what god's algorithm really means on the 4x4x4.

The mere explanation sounds to be very costly for computing power (but what else is new?), but this is probably what we're going to have to do if we ever want to compute god's number for the 4x4x4.



Spoiler: God's Algorithm for the 4x4x4



The basis of this approach is to have all possible corner solutions for the 2x2x2 cube up to length x in htm (where we assume that x is god's number in block half turns).

Does anyone have any idea about how many unique solutions (where L R == R L, for example) there are for solving all corner positions of the 2x2x2 up to a length of, say, 35 htm?

It's probably a very large number, but if we could store all possible solutions up to that length in a data base in alphabetical order (sort by the starting moves), it might aid us brute force god's number or at least lower the upperbound significantly...producing a one-phase 4x4x4 cube algorithm.

Assuming the structure of god's algorithm for some of the worst positions moves corners throughout the entire solution, we have to make an assumption: should the shortest path for a given scramble end with an inner layer slice turn, wide turn, or outer layer turn.

With this decision made, if one has access to all possible corner solutions up to length 35 htm, then if god's number is indeed 35 block half turn moves (or maybe a few moves less), we need to figure out an algorithm which solves the wing edges using the one of the corner algorithm skeletons and one which solves the centers using one of the corner algorithm skeletons. If the corner skeleton used for the wing edge solution is different than "" used for the center solution (which will most likely be the case), we search for additional corner skeletons which would work for each separately...and eventually we would find a match.

If we don't find a match, then god's number must be larger than 35.
If a match is found, we have found the shortest path for that particular position.

With this approach, it would be more feasible to actually find god's algorithm for a given position, because obviously the number of corner solutions increases as the length of those solutions increase...but with this approach, the constraint of the interconnectedness of the wing edges, X-centers, and corners would actually _help_ us and not work against us. Because...if the wing edges cannot be solved using a corner skeleton, we don't need to check if that same corner skeleton can be used to solve the centers (and vice versa). Lastly, since we could sort these corner skeleton solutions in alphabetical order, if the centers cannot be solved with the first move being U, for example, then we can automatically skip that in the search for which skeleton wing edges can be solved with.

EDIT:
In short, we can just search all corner skeletons to solve either the centers or wing edges (if one is less costly in computer time for whatever reason, we choose to search the corner solution skeletons to solve that piece type), and then we search all of the corner skeletons which worked for either the centers or wing edges to solve the other piece type, and we're done.


----------



## Herbert Kociemba (Aug 30, 2013)

cmowla said:


> Does anyone have any idea about how many unique solutions (where L R == R L, for example) there are for solving all corner positions of the 2x2x2 up to a length of, say, 35 htm?



There are 9*6^34=2,578,606,199,622,633,886,542,987,264 different 35 move htm maneuvers on 2x2x2, so this approach will not work.


----------



## qq280833822 (Oct 1, 2013)

qq280833822 said:


> After analyzing step3&4 of tsai's algorithm, the upper bound is reduced to 57 (OBTM) moves (step1: 8 moves, step2: 13 moves, step3&4: 16 moves, step5~8: 20 moves).



The proof is posted to http://cubezzz.dyndns.org/drupal/?q=node/view/525


----------



## CubePhysics (Feb 11, 2014)

Please pile this thread with sources as to lower bounds with the 4x4. As soon as I have enough I will use a server farm to try and prove or disprove algorithms, eventually finding God's Number!

Don't call this thread naive. Technology proved in 2010 that God's Number is 20. This year, 4 years after, will be the year that we will find it. Many may argue that according to Moore's Law, which is still alive, we are only <compute power of 2010>^2^2 today, but those who say that are naive themselves. They fail to realize that exponential values do not draw a straight line. While we may only be <compute power of 2010>^4 ahead, and the 4x4 is about 10^25 harder, it is possible (and with my own calculations, true) that they do not line up if you were to draw a line at all. The line that would represent technology advancements would be much steeper than the difficulty of the Rubik's cube, resulting in the possibility that God's Number is possible. As soon as I find a good online charting program, I will present this to you.

Please, pile and pile, row after row, reply after reply, fill up an entire hard disk's worth of resources! Thanks!



SenileGenXer said:


> We seem to have a lot of computing power now. I think it should be calculable.
> 
> How much computing power was needed to prove 20 on a 3x3 and how much time has gone by?



They said when they released gods number that a beefy computer would take 1.1 billion years to calculate what they did in a few weeks in one of googles computer farms.


----------



## qqwref (Feb 11, 2014)

If you don't understand how hard this problem is, you certainly don't know enough cube theory to have a shot at completing this project. At current computing speeds, all the computers in the world couldn't find God's Number for the 4x4x4 in a million years.

For reference, though, there is an upper bound of 57 moves OBTM and a lower bound of 35 moves.


----------



## Ollie (Feb 11, 2014)

http://www.youtube.com/watch?v=E9jwqibslUk

2:04 onwards begins to explain just how hard the problem was for the 3x3x3 and how 43 quintillion combinations (and much much less, I think) is even beyond Google's leftover CPU time.


----------



## Stefan (Feb 12, 2014)

CubePhysics said:


> They said when they released gods number that a beefy computer would take 1.1 billion years to calculate what they did in a few weeks in one of googles computer farms.



No.


----------



## IRNjuggle28 (Feb 12, 2014)

Slightly off topic. Apologies. What's God's number for 2x2?


----------



## Lucas Garron (Feb 12, 2014)

IRNjuggle28 said:


> Slightly off topic. Apologies. What's God's number for 2x2?



11htm, 14qtm.

Jaap's page usually has great coverage of the theory: http://www.jaapsch.net/puzzles/cube2.htm


----------



## Soren333 (Mar 10, 2014)

What is a God's number?


----------



## whauk (Mar 10, 2014)

the length of the longest shortest solution. i.e. every state can be solved with god's number or less moves.


----------



## unsolved (Dec 20, 2014)

*Hardest 4x4x4 scramble to solve at present?*



qqwref said:


> For reference, though, there is an upper bound of 57 moves OBTM and a lower bound of 35 moves.



Is there a cube position that is generally regarded as the most difficult to solve?

I would imagine the joining of long best-known solves for positions that seem to have no intersection would be strong candidates.

Maybe...






Created by 22 move corner twister + 15 move single dedge flip + one of the longest adjacent center swaps I solved (14 moves) == 51 moves total if no intervening shortcut. The centers open up that possibility. So take them away...





This is 37 moves if the dedge + corner twister are completely orthogonal

...or maybe...


----------



## cuBerBruce (Dec 20, 2014)

For twisty puzzles, the number of positions generally grows roughly exponentially with respect to the distance from solved, until you start getting a significant percentage of the positions covered. You then get a peak, and after that the number of positions at each successive depth will start dropping dramatically. Thus, we expect most of the positions to be quite close to the maximum distance. So choosing a position at random will likely get you a position at least close to the maximum. But picking a position at random will also be extremely unlikely to give you an actual maximal position. Positions with a lot of pieces solved can have a tendency to be not quite so deep.

Positions with high symmetry, while generally rare overall, have a tendency to be relatively common among antipodal positions. But symmetrical positions can also be fairly close to solved. The best way to guess at possibliities for the deepest positions might be to look at high symmetry positions that also seem difficult to solve.

We basically haven't yet been able to prove any specific positions to be very deep (in the range of what we estimate God's number to be), so it's pretty much unknown at this point what positions are deepest.


----------



## qqwref (Dec 20, 2014)

Here's my suggestion, superfliptwist plus symmetrically messed-up centers:


----------



## unsolved (Dec 20, 2014)

qqwref said:


> Here's my suggestion, superfliptwist plus symmetrically messed-up centers:
> http://www.speedsolving.com/wiki/ex...gbbogbrggbrrgryyorryorwoorwwoyyyybbygbwggwwww



I've been building solutions where only centers need to be solved, and you would be surprised that some of the messed-up cases have solutions that are not so deep. The deepest centers-only position I have solved so far is 14 turns. The latest version of my program has every 7-turn and fewer center position available, so just typing in a 7-turn scramble that has only centers needing solving should hit the hash table and be announced as such. I am working on the website now, I'll post a link when it is up.

P.S. Do you have a scramble sequence for your position?

*link to download latest versions:* http://lightningcloudcomputing.com/OO_4x4x4/Rubiks_Revenge_4x4x4_Program.shtml


----------



## IAssemble (Dec 20, 2014)

unsolved said:


> Is there a cube position that is generally regarded as the most difficult to solve?
> 
> I would imagine the joining of long best-known solves for positions that seem to have no intersection would be strong candidates.
> 
> ...



I like the idea, but if I understood the positions correctly, my (non-optimal) solver quickly finds several shorter solutions for your second and third cases including:

Second: 29 OBTM
Third: 26 OBTM

I'll try the first too in a while out of interest.



qqwref said:


> Here's my suggestion, superfliptwist plus symmetrically messed-up centers:
> http://www.speedsolving.com/wiki/ex...gbbogbrggbrrgryyorryorwoorwwoyyyybbygbwggwwww



My "get feeling" is that this has great potential to be a bad case!  Is this the position you mean?

My solver finds this 45 OBTM generator in a few minutes:
B R D R' D' R2 B' F2 R' B' U' F' D' B' F L2 R' U Lw' D' L2 B D L' B' Lw U F Lw F Lw2 D' F Lw U B Uw' B U D' Bw' Lw' D' Fw' R' // View at alg.cubing.net

And has just found this 40 OBTM generator:
L' D L2 B D B' L2 B' R' D' L2 D R2 B D2 L R' Rw B2 F D B2 L D' F' B D Lw F' B' Fw R' L' Lw2 Uw' D2 Rw2 D' B' U' // View at alg.cubing.net

BTW I doubt that this 40 OBTM sequence is optimal since it is (obviously?) using reduction, albeit with an optimal 17 move 3x3x3 section, and my "gut feeling" is that an optimal solution is likely to solve all pieces more "directly"/"randomly" than in three phases of middles, edge-pairing and optimal 3x3x3 that is typical of reduction methods.

Edit: it wasn't optimal as it has now found a 39 OBTM generator:
L' D F' U2 L' F2 D2 F2 B' R U R B L2 U D2 Uw R L2 B L2 D R' B' L B Dw R' L' Rw U' D' Dw2 Fw' B2 Uw2 B' L' F' // View at alg.cubing.net


----------



## qqwref (Dec 20, 2014)

Wow, great solutions! I'm glad mine turned out somewhat difficult  I feel like reduction of centers and edges together (as you seem to be doing) and then an optimal 3x3x3 stage is probably one of the best ways to go for suboptimal 4x4x4 solving. Of course, looking directly for an optimal solution is probably way out of reach.


----------



## Christopher Mowla (Dec 20, 2014)

IAssemble said:


> I like the idea, but if I understood the positions correctly, my (non-optimal) solver quickly finds several shorter solutions for your second and third cases including:
> 
> Second: 29 OBTM
> Third: 26 OBTM


Nice solutions, although unsolved's solver is not for OBTM, but for single slice half turn moves, and thus if he claimed to have gotten a 37 move solution to the second scramble, he matched your 29 OBTM in his solver's move metric.


IAssemble said:


> I'll try the first too in a while out of interest.


In his metric, I found a 38 move "direct" solution:
B2 L R f R2 f' R' F2 U2 R2 U2 R' F2 R2 U2 R' f2 R d R' U2 R d' R f' R2 U2 f2 U2 F2 R2 F2 f R2 f' L' R' B2

All I did was combine my 12 move double parity alg: f2 R d R' U2 R d' R f' R2 U2 f2 with an N perm. I then simply conjugated it. I suspect that your solver might use a wide turn last layer double parity algorithm + N-perm + setup moves, as this was the first route I chose.

BTW, nice solutions to qqwref's position!


----------



## unsolved (Dec 20, 2014)

IAssemble said:


> I like the idea, but if I understood the positions correctly, my (non-optimal) solver quickly finds several shorter solutions for your second and third cases including:
> 
> Second: 29 OBTM



That's interesting, from 37 down to 29.

What solver are you using? Do you have a link? I'd like to check it out.

Your 39-mover for the qqwref position seems to have flipped up-down and one other pair of sides. No matter, if a more direct scramble involves a rotation or 2, so be it. I will feed it into *OO_4x4x4 *when I get a chance. I am having it crank on something for the time being. I'm just curious to see if the 7-turns-from-solved center database has a chance (doubt it, too far away) but I am pretty sure when I complete the 14-turns database, it will be of some help


----------



## IAssemble (Dec 20, 2014)

unsolved said:


> That's interesting, from 37 down to 29.
> 
> What solver are you using? Do you have a link? I'd like to check it out.
> 
> Your 39-mover for the qqwref position seems to have flipped up-down and one other pair of sides. No matter, if a more direct scramble involves a rotation or 2, so be it. I will feed it into *OO_4x4x4 *when I get a chance. I am having it crank on something for the time being. I'm just curious to see if the 7-turns-from-solved center database has a chance (doubt it, too far away) but I am pretty sure when I complete the 14-turns database, it will be of some help



It is my own solver that I developed in order to achieve this which at the moment I have not shared - sorry: 




Thanks for observing the adjacent opposite double layer turns that could be optimized. I was aware that my solver occasionally does this because I've seen it do it with a physical cube on many occasions  It is because it assumes a fixed orientation for the colors (since it evolved from my 3x3x3 algorithms that had fixed orientation owing to the centre pieces and does not have the concept of tilting as part of its solution! I keep meaning to get round to making the optimization to combine moves like this and replace them with tilts or, better still, allow it to search directly for solutions with the final color placement in any orientation since there may be more direct solutions to do that than simply combining these moves with my existing algorithm.

Edit:


qqwref said:


> Wow, great solutions! I'm glad mine turned out somewhat difficult  I feel like reduction of centers and edges together (as you seem to be doing) and then an optimal 3x3x3 stage is probably one of the best ways to go for suboptimal 4x4x4 solving. Of course, looking directly for an optimal solution is probably way out of reach.



Thanks  My algorithm does not reduce edges and centres together. It does have a separate centers phase followed by an edge-pairing phase but in the same way that my (sub-optimal) 3x3x3 solver makes multiple searches starting with different attempts at each phase, it can find "lucky" solutions for the centres phase that allows it to find a "simple" edge-pairing phase. It is this behavior that probably looks like it is solving both together but I would suggest it is really solving the centers in such a way that "happens" to pair some of the edges 

And yes, I agree that a direct search for an optimal solution is currently way out of reach until someone has an insight into the group theory behind it that could help prune the search optimally or we manage to create quantum computers on a large scale?


----------



## unsolved (Dec 20, 2014)

IAssemble said:


> I keep meaning to get round to making the optimization to combine moves like this and replace them with tilts or, better still, allow it to search directly for solutions with the final color placement in any orientation since there may be more direct solutions to do that than simply combining these moves with my existing algorithm.



I believe the fastest way to do it is using 64-bit bitboards to detect the solved state, like I am doing now. I can "check" all 24 solved states with one instruction. No flipping of the cube, no calling conversion data structures. My 4x4x4 cube is constructed using only 6 variables, 64-bits each, one for each face. Each "sticker" is 4-bits: 0010 for top, 0011 for right, 0101 for front... etc, with 1101 for bottom (all primes in base 10). So I can check if a face is solved by testing if the cube.whatever_face == 0x222222222222222 or 0x3333333333333333 .... 0xDDDDDDDDDDDDDDDD. So my compound instruction tests cube.top = 0x22..., 0x33..., 0x55...,0x77..., 0xBB... or 0xDD..., ditto for right, front, bottom, left, back. It executes very quickly.



IAssemble said:


> And yes, I agree that a direct search for an optimal solution is currently way out of reach until someone has an insight into the group theory behind it that could help prune the search optimally or we manage to create quantum computers on a large scale?



There is hope. Remember, we just need to come up with an approach. It is obvious a great deal of pruning is needed. One of the questions I have been asking is, *"Can pruning techniques be combined in a non-hazardous way?"* Well, we know I have already come up with a hazardous solution  despite the fact that the over-aggressive pruning solved a 22-ply "snake" position in under one minute (and offered a few interesting non-regurgitated version of the scramble). 

The answer to the question is: yes! Consider this example:






We see* look-ahead* search and *back-end* pruning being combined successfully. Note this is different from Bruce's forward pruning of the 2x2x2 corners data. Once I add this 3rd type of pruning to these two pruning mechanisms, the search depths shown will probably be amazing.

I only need to generate one-ply worth of moves to see up to ply 6 when I have the 5-Turns-From-Solved database probed in RAM. In the diagram, I only have the 3-TFS loaded in RAM. Basically, for the cost of spawning 64-bit hash numbers and probing an O(1) hash table implementation, I get up to 5 plies of search. A very good trade.

Next, look at [Solution 0001]. It is during the 10th ply, and I only had to generate 7 plies' worth of nodes, yet it found a 13-ply solution! How? It probed the 6-Turns-From-Solution database that features positions where only centers are in need of solving, and it found a matching position. So, even from "ply 7" which is really "ply 10" when you are using a 3-TFS database, I can look ahead even further by using a specialized database I can query IF there is a "ring" of corners and edges solved (I don't need to call this database otherwise).

So, with enough tricks like these, we can shave up to 12-plies off searches for now. I am in the process of building larger center databases, and have enough resources to get to 10-TFS on my own. Coupled with an 11-ply max reduction with 2x2x2 corner pruning, and the 5-TFS database, there is a chance for a *26-ply reduction in search*.


----------



## qqwref (Dec 21, 2014)

I don't think those pruning table depths are additive. For example, with an 11-move corner pruning depth, all you can say is that a position is at least 11 moves from solved - you can NOT say that it is at least 11 moves from being in your 5-TFS database.


----------



## unsolved (Dec 21, 2014)

qqwref said:


> I don't think those pruning table depths are additive. For example, with an 11-move corner pruning depth, all you can say is that a position is at least 11 moves from solved - you can NOT say that it is at least 11 moves from being in your 5-TFS database.



In the case of forward pruning, you are correct. But a node pruned is a node not examined  Tossing out a position that was 11 moves from a candidate solution with no hope of being solved at the present level is almost always a good thing. Only now, we do a second test on the same node to make sure it is also out of range of the databases. Now imagine the multitude of 11-ply toss-outs and the resulting tree reduction. The *subset *of positions that get passed through might be soluble *within *the sum of the targeting ranges. That's 11 plies worth of "noise" that did not need to be waded through to hit upon it. I guess it can't be double-counted in this fashion.


----------



## cuBerBruce (Dec 21, 2014)

unsolved said:


> In the case of forward pruning, you are correct. But a node pruned is a node not examined  Tossing out a position that was 11 moves from a candidate solution with no hope of being solved at the present level is almost always a good thing. Only now, we do a second test on the same node to make sure it is also out of range of the databases. Now imagine the multitude of 11-ply toss-outs and the resulting tree reduction. The *subset *of positions that get passed through might be soluble *within *the sum of the targeting ranges. That's 11 plies worth of "noise" that did not need to be waded through to hit upon it. I guess it can't be double-counted in this fashion.



Like qqwref said, if one pruning table tells you that you are 6 moves from solved, and another pruning table tells you that you are 11 moves from solved, what does that tell you? It tells you that you are at least 11 moves from solved. It tells you nothing about whether or not you are at least 17 moves from solved or not.

There is such a thing as additive pruning heuristics, but you only assume pruning heuristics are additive if you have proven them to be. For instance, if you having a pruning table the says you need to make at least 6 outer layer turns (regardless of how many inner layer turns might also be needed) to arrive at the solved state, and another pruning table that says you need at least 4 inner layer turns (ignoring any outer layer turns are also needed) to arrive at the solved state, then you know that you must be at least 6+4 = 10 single-layer turns from solved.

This whole paragraph that I quoted just seems to be mostly word salad. I can't see that it provides any justification for any pruning heuristics being additive.


----------



## unsolved (Dec 21, 2014)

cuBerBruce said:


> Like qqwref said, if one pruning table tells you that you are 6 moves from solved, and another pruning table tells you that you are 11 moves from solved, what does that tell you? It tells you that you are at least 11 moves from solved. It tells you nothing about whether or not you are at least 17 moves from solved or not.



Which is what I realized when you combine *forward pruning*, such as 2x2x2 corners, and another method. If you see the very last sentence in my post, I mentioned *I guess it can't be double counted in this fashion.*

But it is certainly true if you combine *back-end pruning*, such as my TFS databases, with *advanced look-ahead search databases*, such as my new "center-only" TFS databases.

Take a closer look at this:







As shown in the depth of search, the 3-TFS database is active, reducing the effective tree by 3-ply at every depth. I only need to look at 36 nodes to know if there is a solution within a halo of 4-ply. I generate 2-ply worth of moves to have comprehensive knowledge of a 5-ply solution, etc.

At move generating depth 7, where ply-10 is being examined, I encounter positions that are proven to be 6 turns from a center-only solved state. That is looking ahead another 3-ply from the present depth. A 13-ply solution is found during move generation depth 7. This must be accounted for by some compounding measure where depth of solution = depth of center database + depth of game tree - depth of complete TFS database. 13 = 10 + 6 - 3 in this case. This is the exact formula I use to determine where in the PV to insert the move description for the solution that was found.

QED.





cuBerBruce said:


> There is such a thing as additive pruning heuristics, but you only assume pruning heuristics are additive if you have proven them to be. For instance, if you having a pruning table the says you need to make at least 6 outer layer turns (regardless of how many inner layer turns might also be needed) to arrive at the solved state, and another pruning table that says you need at least 4 inner layer turns (ignoring any outer layer turns are also needed) to arrive at the solved state, then you know that you must be at least 6+4 = 10 single-layer turns from solved.



Actually, I found out this is not true when I was first investigating solving the center databases. I started generating all the center positions that resulted from making only inner layer turns, adding them to a hash table in the order in which they occurred if they were unique, under the premise if the move sequences did not occur at a shallower depth, this must be the optimal path to the position. That was a faulty assumption. There are shortcuts to many inner-slice-only generated positions that involve turning the outer faces.


----------



## IAssemble (Dec 21, 2014)

cmowla said:


> Nice solutions, although unsolved's solver is not for OBTM, but for single slice half turn moves, and thus if he claimed to have gotten a 37 move solution to the second scramble, he matched your 29 OBTM in his solver's move metric.
> In his metric, I found a 38 move "direct" solution:
> B2 L R f R2 f' R' F2 U2 R2 U2 R' F2 R2 U2 R' f2 R d R' U2 R d' R f' R2 U2 f2 U2 F2 R2 F2 f R2 f' L' R' B2
> 
> All I did was combine my 12 move double parity alg: f2 R d R' U2 R d' R f' R2 U2 f2 with an N perm. I then simply conjugated it. I suspect that your solver might use a wide turn last layer double parity algorithm + N-perm + setup moves, as this was the first route I chose.



That was just the first that my solver found. How about this one? 

26 OBTM, 33(?) in his metric F' B2 L' F' L F L' F' L F L' F' L' Uw' F2 Uw L2 Dw' B2 Uw R2 Uw' F2 Uw' R2 Uw


----------



## qq280833822 (Dec 21, 2014)

qqwref said:


> Here's my suggestion, superfliptwist plus symmetrically messed-up centers:
> http://www.speedsolving.com/wiki/ex...gbbogbrggbrrgryyorryorwoorwwoyyyybbygbwggwwww



http://alg.cubing.net/?puzzle=4x4x4..._Uw2_B_F-_R-_F_R-_D-_R_D_L_F-_R_D-_L-_R_F_U2_
Scramble: L' D F' U2 L' F2 D2 F2 B' R U R B L2 U D2 Uw R L2 B L2 D R' B' L B Dw R' L' Rw U' D' Dw2 Fw' B2 Uw2 B' L' F' (copied from IAssemble's generator)
Solution: U L F' Fw2 L2 Rw2 U Uw' F B' Rw' y B U2 Uw2 F' B' Fw2 Uw2 B F' R' F R' D' R D L F' R D' L' R F U2 (34 OBTM)

Well I found a 34 OBTM solution. Therefore, it cannot be the "most difficult" state as the lower bound of the god number of 4x4x4 is 35.

-----Edit-----
32 OBTM solution found. 

http://alg.cubing.net/?puzzle=4x4x4...2_D-_R_U_R2_F2_R2_U_R2_B2_L-_F-_R-_U_R-_B2_U2
Solution: R F' Fw2 U D' R2 Rw2 Uw F B Fw2 Rw y F' L2 Rw2 Fw2 D' R U R2 F2 R2 U R2 B2 L' F' R' U R' B2 U2


----------



## qqwref (Dec 21, 2014)

Wow, nice o_o Is this just with your normal 4x4x4 solver?

And is it easier or harder to solve this position with untwisted corners (i.e. superflip + those same centers)?


----------



## qq280833822 (Dec 21, 2014)

qqwref said:


> Wow, nice o_o Is this just with your normal 4x4x4 solver?
> 
> And is it easier or harder to solve this position with untwisted corners (i.e. superflip + those same centers)?



Yes, I use my two-phase-reduction solver. I haven't tried solving the position with untwisted corner. However, you may notice that the reduction part is only 16 moves (no matter whether corners are twisted or not), much lower than a random state (about 22 moves' reduction).


----------



## unsolved (Dec 21, 2014)

qq280833822 said:


> Yes, I use my two-phase-reduction solver. I haven't tried solving the position with untwisted corner. However, you may notice that the reduction part is only 16 moves (no matter whether corners are twisted or not), much lower than a random state (about 22 moves' reduction).



So 33 moves STM is the best so far for the *Corner Twist Dedge* position? OBTM is cheating, you get two moves for the price of one 






And why are there only face turns for this?

http://alg.cubing.net/?puzzle=4x4x4&title=IAssemble&setup=L-_D_F-_U2_L-_F2_D2_F2_B-_R_U_R_B_L2_U_D2_Uw_R_L2_B_L2_D_R-_B-_L_B_Dw_R-_L-_Rw_U-_D-_Dw2_Fw-_B2_Uw2_B-_L-_F-&type=reconstruction&view=playback


----------



## IAssemble (Dec 21, 2014)

unsolved said:


> So 33 moves STM is the best so far for the *Corner Twist Dedge* position? OBTM is cheating, you get two moves for the price of one
> 
> http://lightningcloudcomputing.com/OO_4x4x4/hardest_solves/37.png
> 
> ...



My solver uses OBTM moves so it can turn either an outer layer or an outer and inner layer in a single move: e.g. F or Fw. It does not use "slice moves", but instead would do a sequence something like Fw F' to have the equivalent effect. This is mainly because this is the way I developed my algorithms by thinking about the way which to me seems most natural to physically manipulate large cubes: Fw F' is easier to do (for me) than the equivalent slice move. So actually you could consider that OBTM makes some things harder than STM! 

BTW I believe that the 20 move God's Number for 3x3x3 effectively is in OBTM metric? It does not include slice moves (that would be "cheating" as it is effectively two face turns in one  )


----------



## IAssemble (Dec 21, 2014)

qq280833822 said:


> Yes, I use my two-phase-reduction solver. I haven't tried solving the position with untwisted corner. However, you may notice that the reduction part is only 16 moves (no matter whether corners are twisted or not), much lower than a random state (about 22 moves' reduction).



Indeed - a very impressive solution!

Out of interest, is your two-phase reduction solver doing centers then edges, or edges then centers, or something else? My "gut feeling" (note that I have no formal background in group theory etc...) is that it is the edge-pairing that is perhaps most costly part of a reduction method. The centers, perhaps because of the freedom to permute the four centers on each face "seem" to be relatively easy to solve. Have people looked at trying to find un-paired edge positions in isolation that are "hard"? Perhaps those which the edges are un-paired in a single cycle. Consider a and A are the two edges that belong together, something like ab bc cd de ef fg gh hi ij jk kl lA AB BC CD DE EF FG GH HI IJ JK KL La or perhaps two cycles of ab bc cd de ef fg gh hi ij jk kl la and AB BC CD DE EF FG GH HI IJ JK KL LA?

Another potential grouping is in pairs e.g. ab AB cd CD etc. with appropriate permutation and orientation around solved centers and corners?

These "gut feel" to me similar to the 3x3x3 "superflip" position in that the edge flipping/pairing is hard and needs to be done in such a way that it preserves the corners and middles...

I'll try to create this but how about all edges in their flipped orientation (like 3x3x3 superflip) but them half of them exchanged in pairs with other edges to make half 6 cycles each of 4 edges, 2 of which are "superflipped" and 2 of which are "permuted superflipped" if that makes any sense?

Something like this:

"Superflip-Edge-Cycle2": R2 F' U2 F R2 U2 B U R D L' U F D' U2 B F2 U2 Rw2 F2 D' R F2 D Rw2 L' Fw2 Uw2 F U2 L2 Fw2 R F2 L D F' Uw2

Or that with one dedge flipped perhaps?

"Superflip-Edge-Cycle2-Dedge": L' D L D' F U2 B' U2 F L2 R2 U' F2 U R B2 R2 F Bw' R' U' B R U Bw D' L2 Uw F2 R2 F2 R' D' R' Uw2 Rw2 Uw' U Rw2 Uw' F' R' Uw' R2 Uw'

Are there known, groupings and permutations around the cube of un-paired edges that are considered hard to solve?

Edit:

I just made an interesting observation is that "Superflip-Edge-Cycle2" composed "Superflip-Edge-Cycle2" is Superflip with dedges opposite their natural position.... Does anyone think this "symmetry(?)" may be a significant indication of depth?

"Superflip-Edge-Cycle2 composed Superflip-Edge-Cycle2": R2 F' U2 F R2 U2 B U R D L' U F D' U2 B F2 U2 Rw2 F2 D' R F2 D Rw2 L' Fw2 Uw2 F U2 L2 Fw2 R F2 L D F' Uw2 R2 F' U2 F R2 U2 B U R D L' U F D' U2 B F2 U2 Rw2 F2 D' R F2 D Rw2 L' Fw2 Uw2 F U2 L2 Fw2 R F2 L D F' Uw2

Edit:

My solver is still running but the best it has found so far for "Superflip-Edge-Cycle2-Dedge-Flip" is now:

41 OBTM: Uw2 Fw L2 R2 Fw' U2 D2 B' Bw R' F' U R F Uw2 R2 Fw' L D B D' L' Fw F' D B2 U R F U' B2 L' U' B2 U' B2 U2 L2 F D' R'


----------



## unsolved (Dec 21, 2014)

Well since we're tossing out some more GNAs (God's Number Attempts) I might as well go again:






Position was created by applying:

1. 16-move "nearest edge swap" on the last layer.
2. single dedge flip elsewhere.
3. 14-move longest centers database solve, 3 centers on 2 adjacent faces
4. Long corner twister.

*P.S. I have a new version of my program where an ESCAPE key press interrupts the current search. You can then hit the UP ARROW key to retrieve prior scrambles, hitting it repeatedly to fetch older ones. That's how I played around to make sure this was the cube position I wanted.*


----------



## IAssemble (Dec 21, 2014)

unsolved said:


> Well since we're tossing out some more GNAs (God's Number Attempts) I might as well go again:
> 
> http://lightningcloudcomputing.com/OO_4x4x4/67.png
> 
> ...



Do you have a generator sequence for this position in textual form please?

And are you able to try to solve my experimental Superflip-Edge-Cycle2-Dedge-Flip with your solver?

Thanks

Edit:

Is this the position you mean? My solver found this generator in just over 2 minutes:

27 OBTM (31(?) STM) R2 D2 F2 D' F2 D2 F2 D R' U' F' L D F L2 U' Dw' F2 L2 B2 Uw' R Uw' B2 Uw L' F2

I suspect composing bad case sequences for edge-only, corner-only and centre-only moves is unlikely to result in worst case overall...


----------



## qq280833822 (Dec 21, 2014)

IAssemble said:


> My solver is still running but the best it has found so far for "Superflip-Edge-Cycle2-Dedge-Flip" is now:
> 
> 41 OBTM: Uw2 Fw L2 R2 Fw' U2 D2 B' Bw R' F' U R F Uw2 R2 Fw' L D B D' L' Fw F' D B2 U R F U' B2 L' U' B2 U' B2 U2 L2 F D' R'



33 OBTM (17 reduction + 16 3x3x3): Uw2 Rw' D2 R2 U2 Rw D2 L' U2 Rw D B R2 U B' Uw2 Fw2 B2 D2 F L D' U' L2 B2 D' R B' R D' L2 D2 U 

The question is, when the position is far enough (e.g. more than 20 moves), we are not able to solve the position *optimally* no matter how symmetric it is. Furthermore, for a random state, it's still hard to find a solution less than 35 moves right now (even when the scramble is less than 30 moves).


----------



## Christopher Mowla (Dec 21, 2014)

IAssemble said:


> That was just the first that my solver found. How about this one?
> 
> 
> 
> ...


Very nice.





Hey guys, can anyone's solver sub-40 (in OBTM), the position generated by the following scramble?
Rw Uw Lw' Uw' Rw' Uw Lw Uw' 
F2 R2 U' R2 U2 B' D' B F2 U' B' D F2 U F2 U' B
Fw' D2 Lw F' L U L' F u2 F' L U' L' F u2 Fw Lw' D Lw Fw' Lw' D Fw D

EDIT:
Or more generally, I am guessing that positions which consist of one half of the 4x4x4 to be completely solved (with the exception of some corner pure twists in the solved half), while the other half is unsolved, will force us to view the position the way it is and not be able to take advantage of symmetry.


----------



## qq280833822 (Dec 21, 2014)

cmowla said:


> Very nice. https://www.speedsolving.com/forum/images/smilies/smile.png
> 
> Hey guys, can anyone's solver sub-40 (in OBTM), the position generated by the following scramble?
> Rw Uw Lw' Uw' Rw' Uw Lw Uw'
> ...



31 OBTM solution (15 OBTM reduction + 16f 3x3x3): Fw' Rw Fw' Rw' Fw' Uw' Rw Uw' B2 L U2 Uw2 B2 Uw2 Fw2 F2 L2 F2 R' U2 B2 F2 R D' L2 R' D2 F2 R' B2 U


----------



## unsolved (Dec 21, 2014)

IAssemble said:


> Do you have a generator sequence for this position in textual form please?
> 
> And are you able to try to solve my experimental Superflip-Edge-Cycle2-Dedge-Flip with your solver?



One reason I am seeking out such positions is so that I can test them against one of my new pruning techniques. Since my solver is "brute force" and not a stage-solver, it will need every pruning trick in the book to tackle positions like these. I am a day or two away from this new version. At that time, I will resubmit my findings. I may have to go out and upgrade my computer to 128 GB of RAM though. It appears 64 GB is not going to work 



IAssemble said:


> I suspect composing bad case sequences for edge-only, corner-only and centre-only moves is unlikely to result in worst case overall...



It's a good start though, and it would be a speed-solver's nightmare in a competition


----------



## qqwref (Dec 21, 2014)

I don't think it would be hard to solve at all  I did
R2 D2 F2 D' F2 D2 F2 D R' U' F' L D F L2 U' Dw' F2 L2 B2 Uw' R Uw' B2 Uw L' F2
in 21.96 seconds with Yau, where a normal solve for me is 35-45.


----------



## unsolved (Dec 21, 2014)

cmowla said:


> Or more generally, I am guessing that positions which consist of one half of the 4x4x4 to be completely solved (with the exception of some corner pure twists in the solved half), while the other half is unsolved, will force us to view the position the way it is and not be able to take advantage of symmetry.



I'm not so sure of that now Chris. Some of my optimal solutions for as few as 7 moves in the centers-only database indicate that rotated state solutions are more common than you might think. If centers are disturbed, that always opens up the possibility for a rotated-state solve to be among the shortest solutions.

See this post for the first position where this was discovered.



qqwref said:


> I don't think it would be hard to solve at all  I did
> R2 D2 F2 D' F2 D2 F2 D R' U' F' L D F L2 U' Dw' F2 L2 B2 Uw' R Uw' B2 Uw L' F2
> in 21.96 seconds with Yau, where a normal solve for me is 35-45.



So can you annotate the steps undertaken as the Yau solution indicates?

Step 1: Apply ... to achieve ...
Step 2: Apply ... to achieve ...

etc.

I am completely unfamiliar with Yau but it sounds interesting.


----------



## cuBerBruce (Dec 22, 2014)

unsolved said:


> At move generating depth 7, where ply-10 is being examined, I encounter positions that are proven to be 6 turns from a center-only solved state. That is looking ahead another 3-ply from the present depth. A 13-ply solution is found during move generation depth 7. This must be accounted for by some compounding measure where depth of solution = depth of center database + depth of game tree - depth of complete TFS database. 13 = 10 + 6 - 3 in this case. This is the exact formula I use to determine where in the PV to insert the move description for the solution that was found



OK, I understand now pretty much what your solver is doing.

You are checking for a special type of position (in this case, all corner and edge pieces solved), and then checking a database to see if it knows how to solve it (or at least knows its depth), and then, if that's the case, reports that solution. These databases for these special cases can be significantly deeper than TFS databases can be.

In your example, you have a goal depth of 10, and building a search tree out to depth 7 since at that point you can determine if a 10-move solution exists for any of the nodes at depth 7 from the scramble position. But you also check if the position is of the special type. For a certain node, you find this is the case, and know that it has a 6-move solution. So you are basically checking for a possible solution that is *deeper than the current goal depth*. In this case, you find a solution that is 7 + 6 = 13 moves, while you haven't finished verifying if a 10-move solution exists. The solution you found *may be suboptimal*. In this case, it is not. My solver found an 11-move solution in about 8 seconds: *R B U2 r l U2 B2 D2 R B2 b2*.

Most optimal solvers don't bother spending any time looking for solutions deeper than the current goal depth. In doing so, there is a possibility you may be able to find a near-optimal solution much sooner than you would find a (guaranteed) optimal solution. On the other hand, you might simply spend extra time checking a lot of positions for such special cases without any success. You have to realize that the percentage of overall positions that have all corners and edges solved is miniscule. They may be somewhat over-represented among positions closed to solved, but you need to be careful in considering whether or not the possible benefit (and the likelihood of such benefit) outweighs the extra time spent.



cuBerBruce said:


> There is such a thing as additive pruning heuristics, but you only assume pruning heuristics are additive if you have proven them to be. For instance, if you having a pruning table the says you need to make at least 6 outer layer turns (regardless of how many inner layer turns might also be needed) to arrive at the solved state, and another pruning table that says you need at least 4 inner layer turns (ignoring any outer layer turns are also needed) to arrive at the solved state, then you know that you must be at least 6+4 = 10 single-layer turns from solved.





unsolved said:


> Actually, I found out this is not true when I was first investigating solving the center databases. I started generating all the center positions that resulted from making only inner layer turns, adding them to a hash table in the order in which they occurred if they were unique, under the premise if the move sequences did not occur at a shallower depth, this must be the optimal path to the position. That was a faulty assumption. There are shortcuts to many inner-slice-only generated positions that involve turning the outer faces.



No, your "counterexample" does not directly relate to my point.

Let's say you found a position that can be solved either with 6 inner layer turns (no other turns). Let's say there is another ("shortcut") solution having 2 inner layer turns and 2 outer layer turns. The inner layer pruning heuristic would say at least 2 inner layer turns are required. The face turn heuristic will say you need at least zero face turns because a solution exists that doesn't use any face turns. You add the two heuristics and you get that at least 2 + 0 = 2 turns are required. In actuality, you really need 4 turns in this example. But the additive heuristic has not overestimated the distance to solved, so it is a valid heuristic.


----------



## qqwref (Dec 22, 2014)

unsolved said:


> So can you annotate the steps undertaken as the Yau solution indicates?
> [...]
> I am completely unfamiliar with Yau but it sounds interesting.


1) Solve two opposite centers - already done
2) Solve three edges on the left center - already done
3) Solve last 4 centers without messing up the three edges - two centers were already done, so I just finished off the last two
4) Pair and insert last edge on left center
5) Pair remaining edges
6) Solve like a 3x3x3 with a solved cross

Remember that human solving methods are designed for random scrambles, so anything with a large chunk solved will generally save time, if sometimes only a small amount


----------



## unsolved (Dec 22, 2014)

cuBerBruce said:


> In your example, you have a goal depth of 10, and building a search tree out to depth 7 since at that point you can determine if a 10-move solution exists for any of the nodes at depth 7 from the scramble position. But you also check if the position is of the special type. For a certain node, you find this is the case, and know that it has a 6-move solution. So you are basically checking for a possible solution that is *deeper than the current goal depth*. In this case, you find a solution that is 7 + 6 = 13 moves, while you haven't finished verifying if a 10-move solution exists. The solution you found *may be suboptimal*. In this case, it is not. My solver found an 11-move solution in about 8 seconds: *R B U2 r l U2 B2 D2 R B2 b2*.



If you looked more carefully, you would have seen I was *testing* 3-TFS + the centers database. I am aware there are other solutions possibly <= the deepest find. In such cases, the program just continues searching. I needed to see how the program would behave when it encounters a position whose solution was beyond the range of the current depth. When I turn on the 5-TFS databases, the solution is found before the center databases are encountered.







The behavior I am looking for is the *ever-tightening noose*:






Here the program finds a 10-ply solution at depth 4 by hitting the 6-turn center database, which is improved within the same depth to 9-ply by finding a 5-turn center solution. Finally a 7-ply result without using the center databases at all trumps all. This demonstrates the program is capable of continuing to search for improvements.



cuBerBruce said:


> Let's say you found a position that can be solved either with 6 inner layer turns (no other turns). Let's say there is another ("shortcut") solution having 2 inner layer turns and 2 outer layer turns. The inner layer pruning heuristic would say at least 2 inner layer turns are required. The face turn heuristic will say you need at least zero face turns because a solution exists that doesn't use any face turns. You add the two heuristics and you get that at least 2 + 0 = 2 turns are required. In actuality, you really need 4 turns in this example. But the additive heuristic has not overestimated the distance to solved, so it is a valid heuristic.



I would like to see an example position where a solution depth = the sum of the two depths you mentioned. Take a position with a known optimal solving distance that uses only face turns. Pick another position with a known optimal solving distance comprised entirely of inner slice turns. Apply the scramble of position 2 to position 1 already scrambled. If what you are saying is true, there can be no shorter solution than the sum of these depths.


----------



## qq280833822 (Dec 22, 2014)

unsolved said:


> Since my solver is "brute force" and not a stage-solver, it will need every pruning trick in the book to tackle positions like these.



According to you description, in my viewpoint, your solver is a two-stage solver. The goal of stage 1 is defined as: {all states which can be solved in X moves (the X-TFS database), or all states with solved edge and corner (the center database)}.

And at stage 1, you use brute force search without any pruning, while at stage 2, you use a simple look-up table method to get the full solution. 

If it's true, as the length of stage 2 is quite small (e.g. less than 10 moves), the length of stage 1 needed would be relatively high (e.g. more than 15 moves) for a far enough state. In this case, you must do a full 15-move search (more than billions of billions of nodes), which is impractical right now I think.


----------



## unsolved (Dec 22, 2014)

qq280833822 said:


> According to you description, in my viewpoint, your solver is a two-stage solver. The goal of stage 1 is defined as: {all states which can be solved in X moves (the X-TFS database), or all states with solved edge and corner (the center database)}. And at stage 1, you use brute force search without any pruning, while at stage 2, you use a simple look-up table method to get the full solution.



Well my program has no intermediate goals, nor does it do anything "different" as a function of depth. It searches all moves. It generates a 64-bit hash number if "depth minus available databases" is in range. And, if so, it probes the hash table, resolves hash collisions, and returns a result if found. It continues to search *while depth_of_solution >= current depth*, and *depth_of_solution = 99* to start. So if it finds a center database solution beyond the current depth, there is a chance a better solution is waiting.



qq280833822 said:


> If it's true, as the length of stage 2 is quite small (e.g. less than 10 moves), the length of stage 1 needed would be relatively high (e.g. more than 15 moves) for a far enough state. In this case, you must do a full 15-move search (more than billions of billions of nodes), which is impractical right now I think.



But this is the exact nature of what I intended to design! My objective was not to make a fast stage solver. My objective was to make a brute force solver.

And 15 moves is "only" 4,790,008,577,248,538,697,216 by my calculation


----------



## qq280833822 (Dec 22, 2014)

unsolved said:


> Well my program has no intermediate goals, nor does it do anything "different" as a function of depth. It searches all movs. It generates a 64-bit hash number if "depth minus available databases" is in range. And, if so, it probes the hash table, resolves hash collisions, and returns a result if found. It continues to search *while depth_of_solution >= current depth*, and *depth_of_solution = 99* to start. So if it finds a center database solution beyond the current depth, there is a chance a better solution is waiting.



Well, I'll try to explain why I think your solver is a degraded two-stage solver. Let's compare your solver to an imaginary two-stage solver. 



> It searches all movs.


The two-stage solver searches all moves at stage 1, as there's no pruning table at this stage.


> It generates a 64-bit hash number if "depth minus available databases" is in range.


The two-stage solver generates a number to represent the state, if "depth minus maximum stage 2 length" is in range.


> And, if so, it probes the hash table, resolves hash collisions, and returns a result if found.


If we found that the number represents a state which can be solved in stage 2 (in another word, we finished stage 1), we will return the solution (as all solutions for stage 2 states has been generated before). 


> It continues to search *while depth_of_solution >= current depth*, and *depth_of_solution = 99* to start.


After finding a solution, the two-stage solver continue trying more stage 1 solutions *while depth_of_solution >= current depth*, and *depth_of_solution = 99* to start.


----------



## cuBerBruce (Dec 22, 2014)

unsolved said:


> I would like to see an example position where a solution depth = the sum of the two depths you mentioned. Take a position with a known optimal solving distance that uses only face turns. Pick another position with a known optimal solving distance comprised entirely of inner slice turns. Apply the scramble of position 2 to position 1 already scrambled. If what you are saying is true, there can be no shorter solution than the sum of these depths.



I am talking about using two admissible pruning heuristics for the *same position* and deriving a third admmissible heursistic by adding them (something not true in general, but may be true for particular heuristic functions). You are talking about *two different positions* and some relationship to a third position derived by composing maneuvers for those first two positions. That isn't what I'm talking about. You are trying to say that I'm claiming something that I'm not.


----------



## unsolved (Dec 22, 2014)

cuBerBruce said:


> That isn't what I'm talking about. You are trying to say that I'm claiming something that I'm not.



Bruce, my post was a request for clarification. Dissect your original post, and my interpretation was not out of the realm of possibility.

The way my program works, only 1 pruning mechanism operates on a position in question. I query the TFS database first and foremost, always. If there is no confirmed finding, I test to see if there is a "ring" position with only centers disturbed. No ring position, no query is necessary. If a ring position hits the center database, I check the depth reported. If that depth <= the shallowest (quickest solve) depth, I show the solution.

But now, even my misinterpretation of your post brings up an interesting question. Suppose we have a position from a scramble such as *RLFB RLFB RLFB*. There is no shorter move sequence to produce this position, and it was achieved using only face turns. There are other ways to create it, such as *R L U2 F2 U2 B2 R L F2 D2 B2 D2* but this requires the same number of moves, so it is of no consequence. Now let's look at something simple, like *u r u' r'*. It features only slice turns, and there is certainly no shorter way to create that position from a solved cube. So, what happens if we combine them? Is there a shorter way to create the position resulting from *u r u' r' RLFB RLFB RLFB*? I do not think there is. So that would mean we can add depths together if they are created from mutually exclusive cube component rotations. I think.


----------



## qqwref (Dec 22, 2014)

There may not be a shorter way for that particular position, but you can't prove it just based on (RLFB)4 and uru'r' being optimal in face-turns-only and slice-turns-only. When you are solving the whole cube, moves that help solve the corners and edges may combine with moves you use for solving the centers, or vice versa. There also may be multiple ways of solving the centers, and one could give an easier 3x3x3 solve than the other. If you want to prove that uru'r'(RLFB)4 is optimal, one way would be to prove that it requires at least 4 slice turns, and separately prove that it requires at least 12 face turns - but it is possible that one of these may be false, and that there may be a shorter solution.


Does anyone have a rough guess at God's Number for the 4x4x4 centers, where slice turns count as 1 but face turns count as 0? That is, how many slice turns a position may be demonstrated to require. In unsolved's metric (but not in BTM or OBTM), we should be able to add together the number of slice turns required by the centers and the number of face turns required by the corners.


----------



## cuBerBruce (Dec 22, 2014)

unsolved said:


> But now, even my misinterpretation of your post brings up an interesting question. Suppose we have a position from a scramble such as *RLFB RLFB RLFB*. There is no shorter move sequence to produce this position, and it was achieved using only face turns. There are other ways to create it, such as *R L U2 F2 U2 B2 R L F2 D2 B2 D2* but this requires the same number of moves, so it is of no consequence. Now let's look at something simple, like *u r u' r'*. It features only slice turns, and there is certainly no shorter way to create that position from a solved cube. So, what happens if we combine them? Is there a shorter way to create the position resulting from *u r u' r' RLFB RLFB RLFB*? I do not think there is. So that would mean we can add depths together if they are created from mutually exclusive cube component rotations. I think.



No, it doesn't work. Consider:

Maneuver 1: U R F (3 moves)
Maneuver 3: r2 b2 r2 u2 b2 r2 (6 moves)
Combined maneuver: U R F r2 b2 r2 u2 b2 r2 (9 moves)

Optimal solution of combined maneuver: f2 r2 f' b' u2 B' D' R' (8 moves)

An even more trivial case:

Maneuver 1: U D'
Maneuver 2: u d'


----------



## unsolved (Dec 23, 2014)

qqwref said:


> Does anyone have a rough guess at God's Number for the 4x4x4 centers, where slice turns count as 1 but face turns count as 0? That is, how many slice turns a position may be demonstrated to require. In unsolved's metric (but not in BTM or OBTM), we should be able to add together the number of slice turns required by the centers and the number of face turns required by the corners.



I found that if you eliminate face turns, the number of unique center arrangements per depth will be exhausted quicker than you might expect. I have a 550 MB text file with every possible center arrangement through depth 6, plus a few at depth 7, using face moves + slice moves. A vast majority of the moves are slice turns, of course.

Here are my counts of unique center arrangements per depth:


```
#define TOTAL_POSITIONS_TFS_CENTERS_DEPTH_04 4896
#define TOTAL_POSITIONS_TFS_CENTERS_DEPTH_05 9216
#define TOTAL_POSITIONS_TFS_CENTERS_DEPTH_06 212472
#define TOTAL_POSITIONS_TFS_CENTERS_DEPTH_07 1202928
```

While the numbers are small, the number of positions that must be examined to establish this is quite large. I examined all 24 rotated states during a 36^n move generation run to scan for uniquely-occurring positions with disturbed centers.

*Edit: But these are only counts with the corners and edges solved. I am thinking maybe this was not what you were asking.*


----------



## cuBerBruce (Dec 23, 2014)

unsolved said:


> *Edit: But these are only counts with the corners and edges solved. I am thinking maybe this was not what you were asking.*



Yes, it is different. I'm rather confident qqwref meant that the corner and edge pieces are to be ignored. Also, I understand that he also wanted face turns not to be counted. That is for each position at depth n, you try all 18 slice turns, and then (on each of these resulting positions) try all 4^6 different ways the 6 face layers can be turned. Count each _new_ state encountered as depth n + 1. (Considering the 4 rotated states of a face as equivalent can be used to reduce the effective number of states, but it's still a pretty large state space for a full breadth-first search.) Note that with the corners and edges ignored, the face layer turns are independent of each other. (They commute.)

I rather doubt anyone has determined God's number for this. One might get an estimate of it through solving thousands of random states or through a partial breadth-first search and using the derived branching factor.


----------



## dannah (Jan 3, 2015)

before you calculate it for the 4*4 what about the2*2?


----------



## Jakube (Jan 3, 2015)

dannah said:


> before you calculate it for the 4*4 what about the2*2?


11 moves


----------



## ryanmcg86 (Jan 20, 2015)

Renslay said:


> You mean that Superflip * A = A * Superflip for all A sequence of moves? (Which equals to ASA' = S)



is there some comprehensive list somewhere of all, or just all KNOWN move equivalents? like, as an example, LLL (3 moves) is the same thing as L'(1 move, for a total of 2 (3 - 1) move-amount difference), another would be RR' being the same as making no moves, whether you're talking about a 4x4x4 or a 3x3x3. if there isn't a list for all the equal sets where one is less moves than the other, we should start compiling one, because if you had all of them, you can calculate the permutations that can be solved in less moves than the number of moves in the initial randomizing. by being left with the unique cases that take x minimal moves to solve, where x is the number of moves made when initially randomized, you can take a summation of those cases and figure out what gods number is, for potentially any n x n x n cube, once the summation is equal to the total amount of unique states that cube can be in.


----------



## qqwref (Jan 20, 2015)

You could easily get a list of pretty trivial cases (moves that cancel), but all the decent solving programs already take the trivial stuff into account. Once you get into useful equivalencies, the list would get extremely large very quickly. It's certainly not easier to generate this list than to find God's Number by itself. Think about this: for every position that has two solutions, those two solutions are move equivalents, and solution1 + (solution2)' is the solved state. Now consider that a given position may have many many solutions of 20 moves or less - they are all equivalent with each other. And that's just the situation for 3x3x3, never mind 4x4x4...


----------



## ryanmcg86 (Jan 20, 2015)

qqwref said:


> You could easily get a list of pretty trivial cases (moves that cancel), but all the decent solving programs already take the trivial stuff into account. Once you get into useful equivalencies, the list would get extremely large very quickly. It's certainly not easier to generate this list than to find God's Number by itself. Think about this: for every position that has two solutions, those two solutions are move equivalents, and solution1 + (solution2)' is the solved state. Now consider that a given position may have many many solutions of 20 moves or less - they are all equivalent with each other. And that's just the situation for 3x3x3, never mind 4x4x4...



where would one find such a list? even the trivial cases, if not all the cases, but i don't know where such a list exists and i'm rather curious


----------



## jaap (Jan 21, 2015)

Way back in 1981 some identities were enumerated. There are essentially only 3 that use 12 quarter turns, but no shorter ones apart from the really trivial stuff, and about a dozen of 14q, and many more longer ones. Here are some historic posts from the cube lovers mailing list where they were first published:
http://www.math.rwth-aachen.de/~Mar...ris_C._Worrell__Re__Identities_(galore)!.html
http://www.math.rwth-aachen.de/~Martin.Schoenert/Cube-Lovers/Chris_C._Worrell__Identities....html
http://www.math.rwth-aachen.de/~Mar...orce_Report__The_fourteen-qtw_identities.html


----------



## ketchuphater999 (Jan 22, 2015)

You're all wrong. The 4x4 is the Rubik's Revenge, right? Revenge is supposed to be 'corrupting to your soul'. When god wants revenge?

*SATAN'S NUMBER!*​

But really, has no one derived a general function to get god's number for any cubical cube(wut)?


----------



## qqwref (Jan 22, 2015)

Gallifrey said:


> But really, has no one derived a general function to get god's number for any cubical cube([/SIZE][/SIZE]wut)?


No, of course there is no such formula... we only know the number for 2x2x2 and 3x3x3. Even if we had such a formula how could we possibly prove it was correct? We do know the number grows proportional to n^2/log(n) for an nxnxn cube, but apart from that, pretty much nothing.


----------



## Christopher Mowla (Jan 22, 2015)

qqwref said:


> No, of course there is no such formula...


Hey, you didn't tell him about my latest formula (and my final one)!


----------



## unsolved (Jan 23, 2015)

ryanmcg86 said:


> is there some comprehensive list somewhere of all, or just all KNOWN move equivalents? like, as an example, LLL (3 moves) is the same thing as L'(1 move, for a total of 2 (3 - 1) move-amount difference), another would be RR' being the same...



I did this for up to 5 moves. It's a 550 MB text file though.


----------



## Chrizz (Jan 23, 2015)

qqwref said:


> No, of course there is no such formula... we only know the number for 2x2x2 and 3x3x3. Even if we had such a formula how could we possibly prove it was correct? We do know the number grows proportional to n^2/log(n) for an nxnxn cube, but apart from that, pretty much nothing.



If God's number for 2x2 and 3x3 had been calculated rather than brute forced, a formula may be possible to setup for any nxnxn cube. 

Btw quantum computers can do many things at once right? They can check every solution for a scramble at the same time (if I'm understanding it correctly), so maybe we will be able to brute force God's number for the 4x4 within the next 10 or 20 years.


----------



## ketchuphater999 (Jan 23, 2015)

Chrizz said:


> If God's number for 2x2 and 3x3 had been calculated rather than brute forced, a formula may be possible to setup for any nxnxn cube.
> 
> Btw quantum computers can do many things at once right? They can check every solution for a scramble at the same time (if I'm understanding it correctly), so maybe we will be able to brute force God's number for the 4x4 within the next 10 or 20 years.



Most computers can do many things at once. for example, a computer with a 12-core processor can run 12 threads at once - you could say that it can do 12 things at once. It just depends on the CPU. Quantum computers are different because instead of 1s and 0s, they have 1s, 0s, and 'both at the same time'. I can't say I'm anywhere near knowledgable on them, but that's how I understand it.


----------



## Lucas Garron (Jan 24, 2015)

Chrizz said:


> a formula may be possible to setup for any nxnxn cube.


Unfortunately, no one has any idea whether a simple formula exists or what it would look like.
(Although we know how to get a value with roughly the right number of digits.)



Chrizz said:


> Btw quantum computers can do many things at once right? They can check every solution for a scramble at the same time (if I'm understanding it correctly), so maybe we will be able to brute force God's number for the 4x4 within the next 10 or 20 years.


Unfortunately, you're not understanding correctly. :-(

Quantum computers can only apply "parallelism" for problems with a certain structure. I don't know of any reasoning that suggests you can frame calculating optimal solutions or God's number using this structure.


----------



## qqwref (Jan 24, 2015)

Chrizz said:


> If God's number for 2x2 and 3x3 had been calculated rather than brute forced, a formula may be possible to setup for any nxnxn cube.


Too bad those numbers weren't calculated, then  There may eventually be a way to directly determine the diameter of a permutation group (that is, God's Number for a puzzle) but it isn't known yet.



Lucas Garron said:


> Quantum computers can only apply "parallelism" for problems with a certain structure. I don't know of any reasoning that suggests you can frame calculating optimal solutions or God's number using this structure.


Well, with sufficiently large memory and enough parallelism you can compute a God's Algorithm in one step per move. I'm sure you can guess what algorithm I'm thinking of.


----------



## Christopher Mowla (Jan 24, 2015)

Lucas Garron said:


> Unfortunately, no one has any idea whether a simple formula exists or what it would look like.
> (Although we know how to get a value with roughly the right number of digits.)


One of their results is that solving a single face of the nxnxn cube requires roughly the same number of moves it takes to solve the entire puzzle. Has anyone looked in to calculating the number of required moves it takes to solve one face of the 4x4x4, for example. (I know Bruce Norskog did such a search for the first center of the 5x5x5.) _Clearly this is more accurate as n gets large, but I'm just curious._


----------



## Chrizz (Jan 24, 2015)

Lucas Garron said:


> Unfortunately, you're not understanding correctly. :-(
> 
> Quantum computers can only apply "parallelism" for problems with a certain structure. I don't know of any reasoning that suggests you can frame calculating optimal solutions or God's number using this structure.



I read the article and I see that quantum computers would still take a long time to solve the problem, however, I do think that quantum computers are better at this than classical computers. In the article it says that you can reduce the time to find the solution to a problem from S/2 to √S. That obviously wouldn't be a significant enough reduction to calculate it with a today's computer, but it would be an improvement.
They also say that quantum computers exploit certain mathematical properties of the problem, which to me sounds like we should first know what the structure of the problem is, something we don't know as far as I know.

I think I'll have to revise my guess and say that it will be calculated before it will be brute forced.


----------



## unsolved (Feb 17, 2015)

*I think God's Number for the 4x4x4 is 32.*

I extended the recursive accumulator for unique 4x4x4 positions out this far. I noticed at depth 31, you get 

470,703,927,480,007,324,417,289,104,727,084,394,384,064,512

...and at depth 32, you get

12,875,779,855,238,747,700,213,127,810,947,408,348,230,811,648.

If there are 7,401,196,841,564,901,869,874,093,974,498,574,336,000,000,000 unique arrangements, then the total arrangements possible at depth 31 is too small to represent this number, and the depth 32 count is finally greater than it. I'm not sure at what point the cumulative total exceeds it, but to err on the side of caution, we can set 32 as the safe upper bound

I have the numbers for depths 1 to 16 listed here:

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

I'll fill the rest of them in later.


----------



## StachuK1992 (Feb 17, 2015)

There was a post here last night that said "do the same for 3x3."
I'd like that as well, to show some sort of consistency.

What you're doing is obviously above my head at this point, but seeing consistency with KNOWN 2x2 and 3x3 numbers would shed some belief. As is, it kinda seems like magic to get this number so soon.


----------



## unsolved (Feb 17, 2015)

StachuK1992 said:


> There was a post here last night that said "do the same for 3x3."
> I'd like that as well, to show some sort of consistency.
> 
> What you're doing is obviously above my head at this point, but seeing consistency with KNOWN 2x2 and 3x3 numbers would shed some belief. As is, it kinda seems like magic to get this number so soon.



I get these numbers for the 3x3x3:

depth 18 = 246,639,261,965,462,754,048
depth 19 = 3,292,256,598,848,819,251,200
depth 20 = 43,946,585,901,564,160,587,264

The number typically quoted for all 3x3x3 arrangements = 43,252,003,274,489,856,000 which looks promising, until you count the commas. Somehow, there are 1000 times as many positions at depth 20 as there are in this number.

So perhaps my supposition about the 4x4x4 is likewise off, or the 3x3x3 numbers I have are not correct.


----------



## StachuK1992 (Feb 17, 2015)

Damn.


----------



## unsolved (Feb 17, 2015)

StachuK1992 said:


> Damn.



Not necessarily a setback. If an order of magnitude above the permutation count is needed, just add 2 more to my number, and you get God's Number for the 4x4x4 is 34. Coming up with a proof would be the hard part, but at least we have a guideline in place that we didn't have before yesterday.


----------



## qqwref (Feb 17, 2015)

That kind of computation has been done before by several people. It's important to note it does depend exactly on what metric you use (especially for big cubes). It's a great way to get a lower bound on God's Number but I really don't recommend trying to estimate the actual number by adding an extra term to it.


----------



## Stefan (Feb 17, 2015)

StachuK1992 said:


> Damn.



You're surprised? Seeing it fail was the point


----------



## StachuK1992 (Feb 17, 2015)

I was not surprised, but was hopeful!


----------



## unsolved (Feb 17, 2015)

qqwref said:


> That kind of computation has been done before by several people.



I haven't come across any. Are there any existing links you could point me to for now?



qqwref said:


> It's important to note it does depend exactly on what metric you use (especially for big cubes). It's a great way to get a lower bound on God's Number but I really don't recommend trying to estimate the actual number by adding an extra term to it.



So has a lower bound of 32 already been established based on what you mentioned?

I was counting moves such as R, R', and R2 as 1 turn. Ditto for slice moves.


----------



## qqwref (Feb 17, 2015)

unsolved said:


> I haven't come across any. Are there any existing links you could point me to for now?


From googling "god's number lower bound": http://en.wikipedia.org/wiki/Optimal_solutions_for_Rubik's_Cube#Lower_bounds, www.cube20.org/, http://cubezzz.dyndns.org/drupal/?q=node/view/54, http://www.math.rwth-aachen.de/~Mar..._Hoey__Lower_bounds_for_the_4x4x4_(Long).html, https://www.speedsolving.com/forum/...4-Rubik-s-cube&p=725532&viewfull=1#post725532, https://www.speedsolving.com/forum/...od-s-number-is&p=650846&viewfull=1#post650846. I'm sure you can find more and I'm sure these are not all exactly the same approach.

I've also done similar calculations myself; a document with last modified date of mid 2010 lists numbers of 34 for the 4x4x4, 40 for the 4x4x4 supercube, 43 for the megaminx, 50 for the 5x5x5, 63 for the 5x5x5 supercube, 73 for the 6x6x6, 92 for the 6x6x6 supercube, 95 for the 7x7x7, 125 for the 7x7x7 supercube, 135 for the gigaminx, etc. Some of these may be off by one due to only taking the number of positions at a given depth into account rather than taking the sum of positions of depths up to that depth (a silly mistake, but the number of positions grows exponentially with a large base anyway, so it doesn't matter all that much ).



unsolved said:


> So has a lower bound of 32 already been established based on what you mentioned?


I don't have the numbers memorized since it depends exactly on what metric choice you use (there are many possibilities) and is ultimately not very useful.


----------



## cuBerBruce (Feb 17, 2015)

unsolved said:


> So has a lower bound of 32 already been established based on what you mentioned?



This post on the Domain of the Cube forum listed 32 as a lower bound using single-layer turns. It also gives values in 6 metrics for cubes up to 20x20x20.


----------



## unsolved (Feb 18, 2015)

cuBerBruce said:


> This post on the Domain of the Cube forum listed 32 as a lower bound using single-layer turns. It also gives values in 6 metrics for cubes up to 20x20x20.



Good information. I am quite fuzzy on the different metrics. I know of only 2. Are there formal definitions of each?


----------



## unsolved (Feb 18, 2015)

qqwref said:


> From googling "god's number lower bound": http://en.wikipedia.org/wiki/Optimal_solutions_for_Rubik's_Cube#Lower_bounds, www.cube20.org/, http://cubezzz.dyndns.org/drupal/?q=node/view/54, http://www.math.rwth-aachen.de/~Mar..._Hoey__Lower_bounds_for_the_4x4x4_(Long).html, https://www.speedsolving.com/forum/...4-Rubik-s-cube&p=725532&viewfull=1#post725532, https://www.speedsolving.com/forum/...od-s-number-is&p=650846&viewfull=1#post650846. I'm sure you can find more and I'm sure these are not all exactly the same approach.



Going through this list one at a time. It's going to take me a while but thanks


----------



## 2180161 (May 3, 2015)

Ok, so Im not good at this whole group theory, but maybe this will spark some Ideas. What is the most efficient 4x4 method out there? What is gods number for the individual steps for that? We dont know, however, we do know that there are 36 single layer turns on the 4x4 this include and are limited to (assuming we are using HTM):R, R' R2, F, F', F2 and so forth for the outer layer turns. However, we then have the inner layer turns:r, r', r2, f, f', f2 and so forth once more. Then judging by the number of those turns, we then have 1 possible permutation that has 0 moves to solve, 36 that take one, and so forth. So wouldnt we just do the same thing we did for 3x3? I mean we know the lower bound, but not the higher. Now if we count double layer turns, so Rr as one turn, then there are even more. So if we are allowing Rr as a single turn, we then have more possible turns. this adds another 18. so it is now 36+18=54. So to find the number of permutations for 2 turns, (not counting double layer turns) we would do 36^2, which would get us 1296, which is wrong because this is allowing turns to be doubled up, so R2, R'. So instead we have to subtract 3 from 36 to get 33 so it would end up being 36*33 or 1188. We still have the wrong number. this is because we have something where we think that we could do L' R', and it would be the same as L' R', so being 18 permutations per axis and 6 axis so we do 36*33-18*6=1080 possible permutations that can be solved using 2 moves. Just the start of something, and I could go on more, but I dont feel like it right now. CORRECT ME IF I AM WRONG.

I dont know how to explain how I got it, as I havent gotten it yet, but know exactly how to find it. So let x represent the number of turns using HTM as I described in my previous post. where Rr equals two turns.
36^x-18*3x and then add those up until we get the # of permutations of the 4x4. 
So a = 1 possible set of permutations, b equals another, and we would keep doing a+b+c etc. until a+b+c etc. equals 7.40*10^45 
So in conclusion, there are 1117 positions that can be solved with a maximum of two moves (counting the solved one). So is this gods algorithm for a 4x4? Or am I just an idiot who thinks he knows what he is talking about?

etc is just so I wouldnt have to type out many sets.


----------



## Ollie (May 3, 2015)

God's number = every single position on nxnxn can be solved in this number or less.
God's algorithm = the optimal solution for any position.

All you've done is attempt to calculate the number of positions that require 2 move or less.

tl;dr - no, you haven't.


----------



## ryanj92 (May 3, 2015)

2180161 said:


> etc is just so I wouldnt have to type out many sets.



You might want to read from here onwards, because i think this is what you are detailing


----------



## unsolved (May 3, 2015)

2180161 said:


> I dont know how to explain how I got it, as I havent gotten it yet, but know exactly how to find it. So let x represent the number of turns using HTM as I described in my previous post. where Rr equals two turns.
> 36^x-18*3x and then add those up until we get the # of permutations of the 4x4.
> So a = 1 possible set of permutations, b equals another, and we would keep doing a+b+c etc. until a+b+c etc. equals 7.40*10^45
> So in conclusion, there are 1117 positions that can be solved with a maximum of two moves (counting the solved one). So is this gods algorithm for a 4x4? Or am I just an idiot who thinks he knows what he is talking about?



There are only 999 unique positions that are 2 turns from the solved state.

There are 36 @ depth 1.

For each of these, there are 24 times as many at depth 2.
Add to this total the 135 possible turns involving 2 parallel planes, and you have (36 x 24) + 135 = 999.

I already carried out this calculation through to depth 32, which is where the count exceeds the number of permutations. So God's Number for the 4x4x4 cannot possibly be less than 32. It is a definitive lower bound. It is probably 35 or 36 though.


----------



## Chrizz (May 4, 2015)

How did you check up to depth 32 if that takes 307087377247055771290 times the age of the universe?

EDIT: I guess you haven't, you've just calculated how long it would take to check them all. Is 100 million/sec fast for modern computers?


----------



## unsolved (May 5, 2015)

Chrizz said:


> How did you check up to depth 32 if that takes 307087377247055771290 times the age of the universe?



The calculation is just a recursive formula. The 4x4x4 cube can be considered to have 3 separate types of move generators: Legal moves involving 1 rotating face, 2 parallel rotating faces, and 3 parallel rotating faces. A move such as *U R* is always permissible, but *U D'* is redundant because it is the same as *u' d* if you follow that up with a rotation *y*. So you have to avoid "double counting" positions that create the same cube that differ merely by a physical rotation. There are similar examples for 3 parallel face rotations.

So you have 3 formulas that give you the sum of "unique" permissible rotations, and if you add these up, you get the total move for a given depth.

if d(n) = the total moves at a given depth n, you have

d(1) = R1(1) + R2(1) + R3(1)

There is no way to make 2- or 3-turns @ depth 1 since you only have 1 move.

R1(1) = 36; R2(1) = 0; R3(1) = 0;

So d(1) = R1(1) = 36.

The next level you have to add 1-rotating face totals + 2-rotating face totals.

d(2) = R1(2) + R2(2) + R3(2)

Again, R3(2) = 0 since you can't rotate 3 parallel faces with only 2 moves.

R1(2) = 24 * d(1) = 24 * 36 = 864
R2(2) = 135

d(2) = 864 + 135 = 999

Now at depth 3, you have R3(3) = 72 for the count of legal 3-parallel rotations.

So:

R1(3) = 24 * d(2) = 24 * 999 = 23976
R2(3) = 90 * d(1) = 90 * 36 = 3240
R3(3) = 72

d(3) = 23976 + 3240 + 72 = 27288

For each depth from now on:

R1(n) = 24 * d(n-1)
R2(n) = 90 * d(n-2)
R3(n) = 48 * d(n-3)
d(n) = R1(n) + R2(n) + R3(n)

R1(4) = 24 * d(3) = 24 * 27288 = 654912
R2(4) = 90 * d(2) = 90 * 999 = 89910
R3(4) = 48 * d(1) = 48 * 36 = 1728

d(4) = 654912 + 89910 + 1728 = 746550

So you just keep feeding the numbers into this recursive formula and you get what I have shown.

There is a possible way to "improve" on these counts, and make the total slightly lower, but I don't have these coefficients yet.



Chrizz said:


> Is 100 million/sec fast for modern computers?



The 4x4x4 solving program I wrote averages 20,000,000 turns/second on a slow 3.1 GHz machine.
I think, but I am not sure, that this is the fastest move generator out there. We never really did an official test.


----------



## Chrizz (May 5, 2015)

unsolved said:


> The 4x4x4 solving program I wrote averages 20,000,000 turns/second on a slow 3.1 GHz machine.
> I think, but I am not sure, that this is the fastest move generator out there. We never really did an official test.


So depth 9 or 10 is about as far as we can get now? So… will we ever find Gods number by brute forcing?


----------



## unsolved (May 5, 2015)

Chrizz said:


> So depth 9 or 10 is about as far as we can get now? So… will we ever find Gods number by brute forcing?



I can now reach depth 17 in 4 days worth of searching with my program.

I pre-load certain positions into RAM and can prune 6 turns from the end of the search (back-end pruning) and this allows the program to use forward pruning to parse through 11 plies worth of positions. So 11 + 6 = 17.

It's technical, but I am working on trying to get the program up to 20 plies. With enough RAM, it can be done.


----------



## Chrizz (May 7, 2015)

unsolved said:


> I can now reach depth 17 in 4 days worth of searching with my program.
> 
> I pre-load certain positions into RAM and can prune 6 turns from the end of the search (back-end pruning) and this allows the program to use forward pruning to parse through 11 plies worth of positions. So 11 + 6 = 17.
> 
> It's technical, but I am working on trying to get the program up to 20 plies. With enough RAM, it can be done.



That's impressive! What kind of computer would be needed to find God's number?


----------



## unsolved (May 7, 2015)

Chrizz said:


> That's impressive! What kind of computer would be needed to find God's number?



When I first started writing my 4x4x4 program, it was slow. Not only that, it explored more nodes than it had to. It took a great deal of input from some talented minds to guide me along the way to make it better. At first, I reduced node counts by pruning from the back end. This has the best benefit of any technique since it effectively reduces the branching factor by an exponential amount. The results are also *constant*. By that I mean I prune the same amount from the search no matter what is being searched. This can only be true when you prune the *trunk* of the tree.

The tree also has branches, and leaves, much like its analog counterpart. The next undertaking I designed only the *leaves* to be pruned. If specific types of positions were encountered, I did not have to search any further. The search halted for that particular set of moves, which were already at a terminus, so not much was gained in the grand scheme of things. It was not a constant pruning technique, it was a variable pruning technique.

The most recent thing I implemented prunes the *branches*. Oddly enough, every other programmer who has a 4x4x4 program has already implemented something like this. The most common form of branch pruning is the *Corners *database. Since corners can only be disturbed by moves involving face turn moves, if the corners are known to be a certain distance from a solved state, then it is impossible to solve a cube with fewer moves. So, if you are in the middle of an 8-move search, and your program is building the line of play: A, B, C, D, E, F, G, H, if before generating move A the corner configuration of your cube is 9 moves from being solved, you don't have to generate ANY moves! You'll never solve it in 8 turns. Likewise, after generating Move A, if your corners can't be solved in 7 turns, no matter what moves follow, you don't have to generate them. After move B, the same is true if the corners database says the new candidate position is more than 6 turns from a solved state.

So the corners database is helpful in two ways. No unnecessary moves need to be made, and it also verifies that the necessary ones are getting you closer to the solution. You can imagine some moves you make just contribute further to the scramble. 

We can use information like this to see what it would take to create a "Super Program" capable of making a solver that always finds a solution in God's Number (or better) number of moves. An insufficient scramble, and indeed, every known "alg" is an example of a cube position that can be solved in fewer than God's Number of moves.

Let's start with a speculation that God's number is 36 for the 4x4x4.

The forward end of the search must meet the back end of the search.

Right now, I have back-end data through 7 turns on my supercomputer. That means I would still have to solve the cube through a distance of 29 moves from the scramble.

But... the good news is, the deepest corners database entry is 11 turns. In the event a scramble has an 11-turn corner orientation, we can effectively chop off 11 turns from the distance.

29 - 11 = 18 turns.

The program would race through the first 10 turns because there is no 10-turn solution to the corners configuration, and now it effectively starts searching at depth 11.

But I also have a database of edge cube entries. The deepest one is 7 turns also. But, the beauty of this is, it is not entirely dependent on face turns. A combination of face turns + slices turns is required to solve most edge positions optimally. So, technically speaking, even a 7-turn edge position can be pruned. Imagine an 18-move scramble that first moves only the faces 11 times to a unique 11-turn corner database entry, then move only the slice edges 7 more times in such a way that a redundant position with fewer moves is not encountered. Hypothetically, an 18-move prune can take place. I say hypothetically because it is extremely rare but it is not impossible.

So now the program might be capable of carving 7 more turns off the search.

29 - 11 - 7 = 11 turns.

A very deep search could be achieved that would solve this position, but those 11 turns would be much slower than a depth-11 search natively. It's because you're really parsing the search space at the greater depth, you're just spending 99% of your time pruning.

If we toss contemporary technology aside and dream of a future machine, say one with a back-end pruning capability of 12 turns and an edge pruning capable as deep as edges can go, then along with the 11-turn corner database, we could probably solve every scramble of a 4x4x4 in God's Number of turns or fewer.


----------



## rokicki (May 7, 2015)

unsolved said:


> When I first started writing my 4x4x4 program . . .



You've made a ton of progress; great job.

I do want to mention here that "finding God's number" and "solving a single random position" are very
different problems; so far your program focuses on the latter, but solving the former is many, many
orders of magnitude more difficult.

At the moment, we cannot expect to solve a single "random" position of the 4x4x4 optimally, even if
we were given access to the top supercomputer in the world for a year. (3,000,000 cores, assume
a depth-14 pruning table, 100M evaluations per core per second). At some point this may change, and
we may have optimal 4x4x4 solvers, probably due to a combination of better techniques and better
technology.

Finding an optimal solution for a random position takes time roughly proportional to the total number
of positions in the puzzle divided by the memory size of the computer we are using.

But proving God's number requires two things. We need to find a position at the purported distance
(and prove that position takes this number of moves), and then we need to *somehow* show that
all other positions can be solved in this number of moves or fewer.

So far our best technique for doing this takes time proportional to the number of positions---there is
no division by the memory size of the computer. And that's assuming everything goes our way
(for instance, on the 3x3x3, we had to wait for machines with 4GB of memory to become commonplace;
the basic idea was ready for years before that happened. For the 4x4x4, we probably need a *lot*
more memory than this to become commonplace.)

But who knows. Someone might make a tremendous leap and figure out some technique to avoid
exploring much of the space. Maybe that person is unsolved. We shall see.


----------



## unsolved (May 7, 2015)

rokicki said:


> You've made a ton of progress; great job.



The three biggest improvements I can't take too much credit for. The original move generation idea by Jakube and the minimization of the tree generated by the move generator was quite a few people, the corner database (finally!) was your originally suggested by you and Bruce, and the fixed-corner move generator that Herbert pointed out to me. I don't think I would have been able to do any of that in a vacuum.



rokicki said:


> I do want to mention here that "finding God's number" and "solving a single random position" are very
> different problems;


 Understood and I agree. When I mentioned *"Imagine an 18-move scramble that first moves only the faces 11 times to a unique 11-turn corner database entry, then move only the slice edges 7 more times in such a way that a redundant position with fewer moves is not encountered. Hypothetically, an 18-move prune can take place. I say hypothetically because it is extremely rare but it is not impossible."* I was hoping it was clear this was a discussion about a single hypothetical position.



rokicki said:


> At the moment, we cannot expect to solve a single "random" position of the 4x4x4 optimally, even if
> we were given access to the top supercomputer in the world for a year. (3,000,000 cores, assume
> a depth-14 pruning table, 100M evaluations per core per second).



I have completely changed my stance about optimizing the speed of move generation after seeing what the two forward pruning mechanisms do that I employ now. Pruning is everything, move generation is nothing. A new pruning paradigm is needed to get us to the next level of performance.




rokicki said:


> ...For the 4x4x4, we probably need a *lot*more memory than this to become commonplace.)



Definitely. Either that or some "magic bitboard" still waiting to be discovered that drops the memory requirement by something that outpaces the growth of base-2 explosion.



rokicki said:


> But who knows. Someone might make a tremendous leap and figure out some technique to avoid
> exploring much of the space. Maybe that person is unsolved. We shall see.



I have one more idea I am trying to code for the upcoming FMC contest. A completely new pruning idea. I am trying to make sure it is, as you say, "permissible." It's a shame that my other one that solves the snake position in 22 moves turns out not be a Karnaugh Map Tautology. Using Godel's work as a primer made me realize such an undertaking was futile to try. But I found out experimentally through computer science.


----------



## qqwref (May 7, 2015)

unsolved said:


> Right now, I have back-end data through 7 turns on my supercomputer. That means I would still have to solve the cube through a distance of 29 moves from the scramble.
> 
> But... the good news is, the deepest corners database entry is 11 turns. In the event a scramble has an 11-turn corner orientation, we can effectively chop off 11 turns from the distance.


Sadly, I am pretty sure it doesn't work that way. The position is at least 11 turns from solved, not at least 11 turns from being in the 7-turns-from-solved database; in fact, it might be only 4 moves from being in the 7-turns-from-solved database.



unsolved said:


> Imagine an 18-move scramble that first moves only the faces 11 times to a unique 11-turn corner database entry, then move only the slice edges 7 more times in such a way that a redundant position with fewer moves is not encountered. Hypothetically, an 18-move prune can take place.


This may be the case if the two pruning tables truly are additive. If you really do have edge positions that require at least 7 slice moves, no matter how many face turns you have done, then yeah, you should be able to prove some positions are at least 18 moves from solved.



unsolved said:


> we could probably solve every scramble of a 4x4x4 in God's Number of turns or fewer.


If we could do this (or at least solve random 4x4x4 positions optimally), it would certainly be a great first step. However, it is still very far from being able to find out God's Number. There are 7.4 * 10^45 positions (perhaps decreased by a factor of 48 or so due to symmetry, if you are being clever) so it is certainly not doable to just loop through them and optimally solve them all. Even a coset solver, like what was done for 3x3x3, would require either a gigantic amount of space or a gigantic amount of processing time (or both). A 1 PB table holding one bit per position is still only 9 * 10^15 positions. I certainly agree with rokicki that a huge leap will be required to solve this puzzle anytime soon - 4x4x4 has about 2^87 times as many states as the 3x3x3, so even if Moore's Law holds, with current techniques I'd expect to have to wait until 2140 or so.


----------



## rokicki (May 8, 2015)

qqwref said:


> . . . if Moore's Law holds, with current techniques I'd expect to have to wait until 2140 or so . . .



The good news here is that for optimally solving a random position, the speed is roughly proportional to
the instruction execution rate times the amount of memory used. Since Moore's law is increasing
both (number of cores for one, and aggregate memory size for the other), optimal solvers end up
getting a double-barrel boost from Moore's law.

Of course, now that machines that can easily handle HD video fit in your pocket, there's less incentive
for performance improvements on commodity hardware and more focus on making the computer as
thin as possible.


----------



## unsolved (May 8, 2015)

rokicki said:


> Since Moore's law is increasing
> both (number of cores for one, and aggregate memory size for the other)



Yeah most people mistakenly believe Moore's Law refers to time required to double the processor performance. It doesn't. It refers to the duration required to *cost-effectively* double the number of transistors on a die. It would be interesting to see if this relationship still holds now that Intel made a 3D transistor that takes up less surface area on the 2D planar portion of the die. They are down to 22 nm technology. That's almost 20 times smaller than the smallest wavelength of light we can see! How do you debug that? 

It's funny how after all of my explaining, some people still don't understand how my *TFS *databases work. Of course they are *trunk pruners* and only queried after the move generator has produced an entire move sub-sequence to depth *D - n*, where n is the greatest distance available in the database. The *branch pruning* databases are forward pruners, and may be engaged at any time during the sub-sequence generation process. If a corner database's cube position can't be solved in fewer than *C* moves, and I am at distance *D - x < C*, I am guaranteed that there is no solution available in the remaining number of moves not-yet-generated, so I can prune.

Concrete example:

Trying to search to depth D = 12
TFS database n = 7
Program generates moves A, B (x = 2) of the 5 moves it has to generate before it queries the TFS. 
Position after moves A,B,C,D,E is guaranteed to be in the TFS-7 database if they lead to a 7-turn solution. 
Shorter solutions are also found with 1 database query (TFS-0 through -7 is combined into one buffer).
Say the corner database says scramble + A + B yields a distance C = 11.

The cube can't be solved in fewer than 11 moves *from here*, guaranteed.

I made moves A, B already. There are D - x = 12 - 2 = 10 moves remaining in the program's horizon. 
If there was a solution of depth D - 1 = 11, it would have been found on the prior iteration.

Therefore, with 10 moves remaining to the terminus, and no solution possible < 11 moves according to the corners database, I can prune and stop searching.

It does not matter that the program is 3 moves away from the TFS database. The solution is demonstrably not present.

*EDIT: To Cmowla, can't access my email right now. I am running your 22-move scramble on the 5x5x5 on this 4.7 GHz server:*



Spoiler











And here is what it looks like:



Spoiler











A concrete example for the 5x5x5 cube, where pruning has even more radical results:



Spoiler











The program is searching remarkably fast even on a non-supercomputer workstation. It hit a peak of *117 trillion positions/second* when it finished depth 10 on the 5x5x5 in one second. It is holding at about 81 trillion/second for the deeper searches, mostly a function of its deep pruning.



*Edit 01: I am running into the problem now where the node count exceeds the maximum value of a 64-bit integer!*


----------



## qqwref (May 8, 2015)

rokicki said:


> The good news here is that for optimally solving a random position, the speed is roughly proportional to
> the instruction execution rate times the amount of memory used. Since Moore's law is increasing
> both (number of cores for one, and aggregate memory size for the other), optimal solvers end up
> getting a double-barrel boost from Moore's law.


Indeed, but I'm more talking about a full computation, which I don't think can be sped up much by throwing additional memory into pruning tables. I could be wrong, though. My starting point for that date estimate was 2010, when God's Number was proven - I assume that single cubes could be solved optimally many years before that.



rokicki said:


> Of course, now that machines that can easily handle HD video fit in your pocket, there's less incentive
> for performance improvements on commodity hardware[...]


I heard somewhere that chip manufacturers were having trouble increasing the performance any further, which is why they have started moving towards more and more cores... I may be mistaken, though.


----------



## unsolved (May 9, 2015)

YouTube video of the 5x5x5 "desktop computer" version (< 12 GB RAM) still solves it in a decent amount of time.

The first clump of text is the program reading the wing edge forward-pruning databases through 5 turns. The second clump of text is reading the corner forward-pruning database through 8 turns. The last group of colored text is building the 5-turns-from-solved back-end-pruning database on the fly. Then it loads a 10-turn scramble for a last layer 3-cycle position. This shows that combining forward- and backward-pruning can be powerful. Note the corners are already solved in this scramble, so it was mostly the (very small) wing-edge-05 database + TFS-05 that was responsible for this performance.






*EDIT: 186,175,388,666,006,296,695 nodes in 14 minutes + 14 seconds!*






Translating these 5x5x5 pruning mechanisms to the 4x4x4 cube now. There is no middle edge on the 4x4x4 so pruning by that cube subset will not translate, but I'm hopeful that the others will be seamlessly ported.

At depth 12, the node count exceeds a 64-bit integer. I did not convert my nodes/second to such a large data type because I thought there would never be a need for such a thing! (That's why there is ???? after depth 11).


----------

