The Search For God's Number

one two three forty-three quintillion that's how many positions are possible on the rubik's cube but how many moves would it take to solve every single one of them if you just learned the beginner method you would need over a hundred moves every single time top level speedcubers can solve it in around 55 moves but what if you were perfect what if you could just look at the cube and find the shortest solution every single time if god tried to solve a rubik's cube what is the most number of turns he would ever need that number is also known as god's number when the rubik's cube was released in 1980 people already began speculating about what god's number might be but finding god's number would be such a difficult problem that no one knew the answer and also no one even knew what to do to find the answer could we formulate a mathematical proof or would we have to somehow go through all 43 quintillion possible cases and in that case would it even be possible for us to find it as it turns out yes we can find god's number but it took 30 years before the search was over 30 years people started thinking about this the year pac-man for the arcade came out and they didn't find the answer until super mario galaxy 2. needless to say finding god's number is an extremely hard problem and in this video i'll be explaining some of the major breakthroughs on the way to finding god's number okay i kind of lied there is one simple trick you can use to find god's number you just have to write some code that does the following generate every single possible scrambled position try every sequence of moves until you solve each scramble and of course record how many moves that took and just wait for the code to run through all the scrambles now if you did that you would have a list of all the optimal solution lengths and the longest one would tell you what god's number is turns out the hardest part of this is actually waiting for the code to finish running now computers are a bit tricky and it was hard to get an exact number on how long this would take to run but in several billion years when the sun dies and our solar system becomes inhabitable be sure to bring the computer with you as it's not even close to done so computers aren't fast enough but that doesn't mean that they can't help we just need a smarter approach where we can still have a computer do some of the heavy lifting so instead you can try to approach god's number from two sides the upper bound and the lower bound and if you keep making discoveries that can drop the upper bound and raise the lower bound then eventually you would literally squeeze out god's number finding a lower bound for god's number or god's number is at least some number of moves is actually very easy i know that god's number is at least 2. why do i know that because i found a position that cannot be solved in one move how can i be sure that i can't solve this in one move well you can just try all the possible sequences of one move and none of them will solve this there are 18 possible one moves you can do and that is just pick one of the six sides and turn it one of three ways so that could be clockwise or counterclockwise or a half turn so i've proven that god's number is at least two because one is not enough to solve this position of course that's very obvious but the logic of that can go much further now imagine this what if you tried to write a full list of solutions to every single possible scramble well you would die but if you could do it you would have a full list of completely unique move sequences 43 quintillion of them with no repeats clearly if god's number was too low then all of these solutions would be quite short and you wouldn't be able to have 43 quintillion unique move sequences so how long do these solutions need to be for you to have that full unique list so there are 18 possible choices for your first move so once you pick one of them then the next move can only have 15 choices because otherwise you would just repeat the first layer now if you just do 18 times 15 times 15 times 15 and so on then this number will exceed 43 quintillion after 17 moves which means if you just write 17 move combinations it looks like you have enough to fill up that list but you don't have to write a 17 move sequence you could write one shorter than that so once you add up 17 with all the ones below it then this is way more than enough okay i kind of lied the way we were counting moves is actually not perfect we counted too many anytime you do two parallel turns for example r followed by l this is actually identical to if you just switch the order so if i did l followed by r that's the same thing originally we counted that as two different sequences but they should be the same so anytime this happens you actually have to remove the duplicate and also after you turn to parallel sides you can't turn either one of these as your next turn which means from here you actually only have 12 choices for the next move unfortunately this means there is no very simple yet accurate formula for how many move sequences you can write you could still run the calculation by hand but it's not very fast and it's easier to have a computer do it for you how to write code is beyond the scope of this video but here's what it would look like as you can see the number of possible move sequences you could write with up to 17 moves doesn't quite get to 43 quintillion but with 18 moves there is enough so if 18 moves is enough to write this list then why can't we say that god's number is 18. well hang on there we never proved that 18 could write every solution it could just write enough unique sequences now not every unique sequence is going to give you a different position there are many duplicates you'd have to get rid of and once you do that then 18 probably can't cover all the positions but we can't really be sure so at this point all we know is 17 is definitely impossible 18 maybe but maybe not enough so 18 is the lower bound god's number has to be at least 18. [Music] okay so we found a lower bound now let's go for an upper bound but the thing is an upper bound is actually a lot harder to prove see with a lower bound i just found one by saying this scramble takes at least two moves so god's number has to be at least two and that was really simple but with an upper bound i'd have to show you that every single scramble can be solved in at most a certain number of moves and how do you do that of course you can't just go checking every scramble because that would take too long so instead you need to make a solving method and prove that that method never takes more than a certain number of moves now here's a quick example of what i mean with the popular cfop speed solving method if you add up the worst case optimal solution for each step you will get a total of 69 moves in other words move optimal cfop will never take more than 69 moves to solve any scramble so 69 is the upper bound for god's number if you ask me that's a pretty great upper bound but of course we could go further in 1992 herbert cosiemba invented the cosiemba algorithm which is a method for solving the cube i just want to clarify here that cosiemba's algorithm is not what we normally think of as an algorithm in cubing the cubing definition of algorithm is usually just a set sequence of turns that solves the same thing every single time and that's not really what algorithm means algorithm usually means a sequence of steps and exactly what you do may change depending on the case and that's really what we call a solving method so cocyemba's algorithm is a solving method and not a set sequence of turns just making that clear so here's how cosymba's algorithm works in stage 1 you reduce the cube to a state that is solvable using only these moves u d f2 b2 r2 and l2 i will explain that in a moment then in stage two you solve the cube using only that moveset let's see what this looks like on a cube so you start with any scramble of course and then the first stage is you do some moves that turns it into something like this what you're seeing here is all of the corners are oriented to be the same on both sides and the edges are also oriented in the same way and the equator edges are placed in the equator if you do this then the cube will be solvable using this restricted moveset getting the cube like this is also known as domino reduction and that's because it makes it just like the domino cuboid which has the same restricted moveset the next step is just to solve the rest oh and uh do all of it in as few moves as possible i can't do that cosiemba's algorithm was designed with a few goals in mind use a low number of moves and be possible to solve with computers so how does this method save moves well take a look at a completed stage 1. none of these pieces even need to be solved but if you think about it that can be a lot better that's because as long as i stick to the restricted moveset of stage two then i'll never break the progress from stage one see stage one is always completed no matter what i do here and that's actually very different from something like a speed solving method where if you solve the first two layers as you try and solve the last layer you're constantly breaking the progress of the first two layers and every time i do break the progress of the first two layers then i have to restore it at the end and that's a lot of wasted moves which is why something like cosiembus algorithm is so efficient now what makes this method good for computers well remember how solving the whole cube has 43 quintillion cases that's too many for cosimba's algorithm stage 1 has about 2 billion cases and stage 2 has about 20 billion cases together that is about 22 billion cases which is a lot but is also a far more manageable number on top of that each case is much easier to solve since you don't have to solve the whole cube okay let's bring this back to god's number if you run it through a computer you'll find that stage 1 needs at most 12 moves and stage 2 needs at most 18 moves that's 30 moves in total to solve the cube but then michael reed a mathematician analyzing this method did something clever for all the longest solutions he checked if you could change a move in stage one and have that lead to a shorter solution in stage two kind of like if you change the way you did your first two layers to get an easier last layer or even a last layer skip as it turns out that was always possible so instead of 30 moves cosiemba's algorithm can always solve the cube in 29 moves or less setting the new upper bound for god's number so cosiemba's algorithm is quite an efficient method if it can always solve any scramble in 29 moves or less but we can do better than that did i say better i mean perfect remember how i said you can change the way you do stage one and that may lead to a shorter stage too well you could also just find a longer way to solve stage one and even though you now have a longer stage one solution that could lead to a luckier stage too and you can just keep doing this check longer and longer stage 1 solutions until eventually you can stop as stage 1 becomes so long that there's no point in searching anymore but eventually along the way you may find a stage 2 solution so short that this is actually a lot better than just finding the best stage 1 followed by the best stage 2 solution and in theory this always leads to the shortest possible solution for any scramble but in reality this was the 1990s and their computers were just not fast enough [Music] earlier we concluded that 17 moves was not enough to make the full list of solutions and you definitely need at least 18 moves to do that but that was a non-constructive proof and what that means is we never found any of the positions that actually require that many moves we just showed that it must exist well that's about to change meet the superflip the superflip is a position that has all of the corners solved but all the edges are in the correct spot and flipped for a long time we knew a 20 move solution to the super flip but we didn't know if there was anything shorter than that and since hard scrambles like this are very rare then it was worth looking deeper the super flip is very unique in that no matter which way you hold the cube it's exactly the same thing and doing the super flip again just solves it because of this any solution to the super flip can be mirrored reversed rotated to a different orientation of the cube or even shifted to begin at a different point in the solution and on top of that you can do any combination of these that might sound like a headache to completely take into account but that actually makes things a lot easier here's what i mean if you're trying to find the shortest solution to the super flip you already know that it begins with r how can you know that well double turns only can't solve flipped edges so there has to be a single turn somewhere in the solution it doesn't have to be the r layer but you can just rotate the solution so that it is if it's counterclockwise then just reverse the solution and finally if it's not at the start you can just rearrange the solution so that it is this is super useful because if you were looking for a 19 move solution to the super flip then instead of looking for 19 different moves you could just say the first move is r and now you're looking for the last 18 moves which is much faster any time reduction you can get on a computer when you solve this is a big deal and that's just deducing one of the moves that's barely scratching the surface of optimization you can do with a superflip pattern michael reed who i mentioned earlier managed to find all of the ways you could take advantage of the super flip symmetry and then try to find the optimal solution for this by running it through cosiembus algorithm on his computer and remember to actually find an optimal solution with cocyamba's algorithm just takes too long so if it weren't for these clever tricks around the symmetry then he would not have been able to find the optimal solution and what was the result he found that the superflip requires 20 moves to solve you can't do it in shorter than that and thus the lower bound for god's number was raised to 20. just to see what he was up against i tried running the super flip through cube explorer on my laptop which is from 2020 and not 1995. and it took 23 minutes the super flip may be hard for computers but for me piece of cake kocimba's algorithm you can go take your 23 minutes i'm out here shattering world records in the 10 years from 1995 to 2005 the lower bound didn't change and the upper bound dropped by only one meanwhile computers were getting much faster and a big leap in progress was starting to look possible in 2010 a team was assembled to finally put an end to the search thomas brickitsky herbert cosiemba morley davidson and john dethridge decided to solve every single scramble to find god's number yeah all of them that's what i suggested at the start what was the point of all this then why were they making all these discoveries if in the end they were just going to solve them all well remember how i said find the optimal solution through brute force to every scramble was a bad idea it's still a bad idea but thanks to all the previous discoveries there is a way to kind of do that cosiembo's algorithm is significantly faster at solving the cube compared to just doing a brute force search sure finding the shortest solution may not always be that fast but most of the time it doesn't even need to find the shortest solution since we now know that the lower bound is 20 moves then there's no point in finding solutions shorter than 20. we just need to show that each position can be solved in 20 moves even if that's not the optimal solution and we can just move on to the next case and that's much faster also remember how reed optimized the way he found the optimal solution to the superflip by taking advantage of a bunch of symmetries to make the time shorter well turns out you can take advantage of some kind of symmetry in almost every position for example you can hold a cube in 24 different orientations or hold it up to a mirror and these can all be treated as having the same solution just of course flipped or rotated which reduces the number of cases we have to actually solve by a factor of about 48. so the strategy is simple do what i said at the start except use an actual solving method don't look for optimal solutions find a workaround so you're not actually checking 43 quintillion positions okay that's not really similar anymore but even with all these optimizations it would still take a computer 35 years to try and go through all the positions and find out what god's number is but unlike that number from before you can now do this in a short amount of time if you have the right connections the team distributed the program among a large number of computers at google and then they waited there were two possibilities for what could happen next either the computer would go through all of the scrambles and find that all of them can be solved in 20 moves or less or it would be able to show us a new position we've never seen before that requires even more moves either way we were about to know the answer and not in 35 years but in only a few weeks the answer was found every position can be solved in 20 moves or less the lower bound and upper bound finally met and god's number was determined to be 20. so why is god's number 20 i mean yeah the computer told us is 20 but that's not a very satisfying answer well of course it's complicated but here is my best shot at a logical explanation as you turn the cube the number of positions that you can reach grows exponentially so of course it doesn't take as many moves as you might expect to reach 43 quintillion different possible move sequences but why isn't there a position out there that just takes 25 or even 30 moves to solve why doesn't something like that exist well i think that has to do with a few things for one when you turn one side you're moving eight pieces which is a lot but not a lot out of the 20 total pieces on the cube so you're actually doing a decent amount of work without being too intertwined with all the other pieces and plus all the pieces are actually quite close together so for example if you want to get the two farthest pieces from each other to go to each other's spot it only takes two moves eighteen plus two makes twenty yeah that's definitely not how that works but sometimes it's not the answer that matters perhaps if it weren't for the elusive gods number we wouldn't have coseyemba's algorithm which is now used for generating official scrambles and competitions it's used for finding new algorithms and competitors in the fewest moves events can use it to analyze how their solutions could have been better in fact stage one of cosiemba's algorithm or domino reduction has recently become a popular method in fewest moves competitions although what's most incredible to me is that despite the overwhelming complexity of this problem humans were able to solve it and yeah we did use computers along the way but if it weren't for all the clever optimizations and solutions that were come up with by all the people working on this problem that computer would still be running and you know what else is still running the end of 2020 discount at the jperm store depending on where you live these next few days may be your last chance to get something delivered before christmas such as a present for your parents you've been dreading thinking about a link is in the description and of course if you buy anything you will be helping to support this channel thanks for watching and i'll see you all next time you

Channel: J Perm

Views: 276,333

Rating: 4.9561906 out of 5

Keywords: rubik's cube, j perm, jperm, speedcube, cubing, 3x3, 20 moves, god's algorithm, speedcubing, efficient, solving, kociemba, domino

Id: YsWKrxAbopk

Length: 20min 47sec (1247 seconds)

Published: Wed Dec 02 2020