# God's Number in QTM is 26



## Lucas Garron (Aug 3, 2014)

This was announced at US Nationals today.

http://cube20.org/qtm/

Tomas and Morley worked with the Ohio Supercomputing Center using 29 CPU-years.

The only known distance-26 position is superflip + 4 spots:
U U F U U R' L F F U F' B' R L U U R U D' R L' D R' L' D D


----------



## Renslay (Aug 3, 2014)

Finally! I waited for this result for so long!
Huge, huge, huge congrats!

"We did not find optimal solutions to each position, but instead only solutions of length *20* or less." - uhm, is that state correct? Or just a copy-paste error from the 20f text?


----------



## 10461394944000 (Aug 3, 2014)

o awesome !!

STM next

edit: what is the current lower bound for STM?


----------



## qqwref (Aug 4, 2014)

Whoa! So awesome.


----------



## Kirjava (Aug 4, 2014)

cool :U



10461394944000 said:


> STM next



totally


----------



## Frubix (Aug 4, 2014)

Cool


----------



## rokicki (Aug 4, 2014)

Thanks, all! Morley spearheaded getting the computer time, and that
was the main impediment.

You're right, there are some typos I'll have to fix. I'm editing this from
Hawaii (just got back from the beach) otherwise I'd be more "on" it.

I *think* the current STM lower bound is 18, but I'm not sure.

Also note that we did not prove there is only a single distance-26 position
(but I strongly suspect there is only that one, and indeed I have some
machines going right now looking for more deep positions.) More on that
when I get back to the mainland.

I hope everyone is having fun in Jersey City; I really wanted to go but
am having fun in Hawaii nonetheless.

Thanks to the event organizers for giving us space in the program.


----------



## Renslay (Aug 4, 2014)

It surprised me that there so few 26q* positions! The number of 20f* positions are about 490,000,000, but there are only a handful of 26q*?! Mindblowing!

Also, what are the chances to explore the distance/#states table? For the face turn metric, 15 depth is the farthest where we know the exact number of positions, and that result is many years old by now. I noticed that the estimation of depth 20 is updated (from 300,000,000 to 490,000,000) some times ago, I don't know if that is true for the other depths. I guess it would require tons of computational resources; is there a chance that there will be an algorithm specifically aimed for this? Currently, how much work would be required for distance 16?


----------



## Stefan (Aug 4, 2014)

Awesome!

And yes, STM next, please 

Superflip with or without fourspot is 16s*, superfliptwist with or without fourspot is 17s*. Maybe superflip variations will finally not be among the hardest positions?


----------



## guysensei1 (Aug 4, 2014)

STM is HTM but with slices counting as 1 move right? Why not have SQTM where it's QTM but slices are counted as 1 turn?


----------



## Stefan (Aug 4, 2014)

guysensei1 said:


> Why not have SQTM



We do have that. It's just not popular.


----------



## Dane man (Aug 4, 2014)

Wow, nice work. Congrats on the find!


----------



## Kirjava (Aug 4, 2014)

We also have ATM


----------



## goodatthis (Aug 4, 2014)

I would really like to see ATM next, that's a really interesting metric.

EDIT: just saw kirjava's post


----------



## 10461394944000 (Aug 4, 2014)

Kirjava said:


> We also have ATM



that would be cool too


----------



## G2013 (Aug 4, 2014)

Wow! Amazing result, I wish I was there when they did the announcement!

And what program can be used to calculate the optimal QTM solve to a given scramble?


----------



## Renslay (Aug 4, 2014)

G2013 said:


> And what program can be used to calculate the optimal QTM solve to a given scramble?



Hm, an update to CubeExplorer for finding sub-optimal and optimal solutions in QTM might be a good idea!
But on the other side... How many actually would use it?


----------



## 10461394944000 (Aug 4, 2014)

is there a video of the announcement?


----------



## cuBerBruce (Aug 5, 2014)

10461394944000 said:


> is there a video of the announcement?



This is my video of the main part of the announcement. I was not aware in advance that this announcement would be made, and so I had just had to shoot this from where I was and with the digital camera I had with me. The audio is distorted; there is much background noise; and people near me talking and drowning out what the speaker was saying, at times. Hopefully, someone else has a better recording.


----------



## cubernya (Aug 14, 2014)

I just had the idea: I wonder what God's number is if we exclude all primes? So just R and R2 are allowed, not R'. Of course, we could require R2 and R' because of symmetry, but that is indifferent.


----------



## Herbert Kociemba (Aug 17, 2014)

theZcuber said:


> I just had the idea: I wonder what God's number is if we exclude all primes? So just R and R2 are allowed, not R'. Of course, we could require R2 and R' because of symmetry, but that is indifferent.



If R and R2 count as 1 move, then R' counts as 2 moves in the metric you suggest. In QTM R and R' count as one move and R^2 counts as 2 moves. If you count the number of canonical maneuvers for each length you get the same distribution as in QTM and hence the same lower bound which is 21 (see http://cubezzz.duckdns.org/drupal/?q=node/view/236). I suspect Gods number in the neighborhood of Gods number for QTM.


----------



## Robert-Y (Aug 17, 2014)

Renslay said:


> Hm, an update to CubeExplorer for finding sub-optimal and optimal solutions in QTM might be a good idea!
> But on the other side... How many actually would use it?


You have no idea how much I would use this. Also if it had the option to ignore all post U moves, then we basically have the perfect program for finding speed optimised algorithms.


----------



## Herbert Kociemba (Aug 17, 2014)

Robert-Y said:


> You have no idea how much I would use this. Also if it had the option to ignore all post U moves, then we basically have the perfect program for finding speed optimised algorithms.



What do you mean with "ignore post U moves" ?


----------



## Musicalboy2 (Aug 17, 2014)

Herbert Kociemba said:


> What do you mean with "ignore post U moves" ?



I think he means U moves after an alg, like that which would usually be called AUF rather than part of the alg itself.


----------



## Robert-Y (Aug 17, 2014)

^Yes, most of the time we don't care about any U turns at the end of an algorithm. For example, every LL algorithm that we all learn does not include a U/U'/U2 at the end of the algorithm. Most of the time, I do not want any U turn at the end of an algorithm to contribute to its move length.


----------



## Herbert Kociemba (Aug 18, 2014)

Robert-Y said:


> Most of the time, I do not want any U turn at the end of an algorithm to contribute to its move length.



Ok, I understand. I suppose you work with the module for incomplete cubes to generate the algorithms. If you search for example for an algorithm of length 12, in the current version you also have to look at the maneuvers of length 13 which end in an U, U2 or U' move. But is that really so uncomfortable?


----------



## Musicalboy2 (Aug 18, 2014)

Herbert Kociemba said:


> Ok, I understand. I suppose you work with the module for incomplete cubes to generate the algorithms. If you search for example for an algorithm of length 12, in the current version you also have to look at the maneuvers of length 13 which end in an U, U2 or U' move. But is that really so uncomfortable?



I haven't done nearly as much work on algs as Robert Yau has, but from my very limited experience, the longer the algs get, the more time the program takes. So I'm thinking that while it might not seem at all significant for searching length 12/13, perhaps, say, length 17/18 there is a significant difference, and you really just end up sifting through more algs... He also did use the word "perfect", so perhaps there's little difference, but would be a nice feature to have anyway.

While we're on the topic of cubeexplorer, I'd actually really love a feature where the program can deduce and fill in the missing stickers - it doesn't seem like it should be hard to automate, and it'd make reconstructions (without scrambles) easier.


----------



## Christopher Mowla (Aug 18, 2014)

Musicalboy2 said:


> While we're on the topic of cubeexplorer, I'd actually really love a feature where the program can deduce and fill in the missing stickers - it doesn't seem like it should be hard to automate, and it'd make reconstructions (without scrambles) easier.


Your request is equivalent to saying there is only one solution to the equation x + y= 100. You have to assume a value for either x or y in order to solve this equation.

Similarly, Cube Explorer would have to assume the position meant by a user, but it isn't always straightforward which position should be assumed, as there is more than one possibility in many cases.

If Cube Explorer assumes the wrong position (which is more than likely), what good is the reconstruction? If it gives you all possible positions, are you willing to search through all of them to find the correct one?


----------



## Musicalboy2 (Aug 19, 2014)

cmowla said:


> Your request is equivalent to saying there is only one solution to the equation x + y= 100. You have to assume a value for either x or y in order to solve this equation.
> 
> Similarly, Cube Explorer would have to assume the position meant by a user, but it isn't always straightforward which position should be assumed, as there is more than one possibility in many cases.
> 
> If Cube Explorer assumes the wrong position (which is more than likely), what good is the reconstruction? If it gives you all possible positions, are you willing to search through all of them to find the correct one?



I mean those colours which it can deduce, of course. Say you have two known stickers on a corner, and a colour scheme. Only one possible sticker can go in the remaining spot. Or say you have 3 known white-(colour) edges and one white-blank edge. Obviously there's only one colour left. This isn't hard for a human to figure out, but still somewhat time consuming. Or I'm slow. but either way...

Edit: Or the worst, I think, is if you had just one piece left, completely blank. There's only one way this piece can be placed to make the cube solvable, but yet unless I fill in the piece, cubeexplorer will try to find an optimal solution, which is often really slow.


----------



## Herbert Kociemba (Aug 19, 2014)

Musicalboy2 said:


> I mean those colours which it can deduce, of course. Say you have two known stickers on a corner, and a colour scheme. Only one possible sticker can go in the remaining spot. Or say you have 3 known white-(colour) edges and one white-blank edge. Obviously there's only one colour left. This isn't hard for a human to figure out, but still somewhat time consuming. Or I'm slow. but either way...
> 
> Edit: Or the worst, I think, is if you had just one piece left, completely blank. There's only one way this piece can be placed to make the cube solvable, but yet unless I fill in the piece, cubeexplorer will try to find an optimal solution, which is often really slow.



There is the "autofix colors" options, I just tried it and it seems indeed to be broken or does not work correctly. I will put this onto the todo list. Pieces which can be uniquely be identified though some stickers are missing should indeed be completed with this option selected.


----------



## Swordsman Kirby (Aug 19, 2014)

Heh, I saw Morley Davidson get called up to the staff area before the announcement, and I asked him "God's number for QTM?" and he responded with something like "did I give it away already?"


----------

