What's the Monkey number of the Rubik's cube?
ฝัง
- เผยแพร่เมื่อ 2 ต.ค. 2024
- NEW (Christmas 2019). Two ways to support Mathologer
Mathologer Patreon: / mathologer
Mathologer PayPal: paypal.me/mathologer
(see the Patreon page for details)
The "Monkey number" is the average number of twists it takes to solve a Rubik's cube starting from a randomly chosen scrambled position and by making random twists. It's pretty obvious that this number will be gigantic but nobody knows the exact value of this number nor even how gigantic a number we are talking about.
So what are the Monkey numbers for the 3x3x3 or the 2x2x2? How do you create a mathematically certified random scramble of a Rubik's cube? And how would a virtual Monkey solver fare in an actual speedcubing competition? Accompany me the Mathologer, my friend Erich Tomanek and our pet monkey as we explore these and other confounding Rubik's cube puzzles.
Check out Erich's infinite monkey lab website: www.infinitemon...
This fairly accessible article by Peter Doyle contains the maths necessary to calculate the Monkey number in terms of the transition matrix of the markov chain associated with the Rubik's cube : arxiv.org/abs/... (see in particular Proposition 3).
That the mean recurrence (or return) time is equal to the number of configurations of a Rubik's cube is a corollary of some basic results in the theory of stochastic processes. I came across this insight for the first time in an answer by TonyK to the following question on stackexchange: math.stackexch...
Here are the World Cubing Association rules on scrambling twisty puzzles for competitions:
www.worldcubea...
Here is a link to a video which shows the scrambling program tnoodle in action: github.com/the...
Notes on implementing the 2x2x2 experiments: As with counting configurations of the 2x2x2, we fixed one corner cubie and twisted the three faces not containing this corner. In this video I only report on the most interesting aspects of Erich and my playing around with this circle of problem. We tried lots of other things. Happy to discuss in the comments :)
Many thanks to Jeremy Fleischman and Lucas Garron for their help with understanding how the World Cubing Association creates scrambles of twisty puzzles for cubing competitions. Thank you to Erich for programming all those virtual cubing monkeys. And, as usual, thank you to Marty for nitpicking early drafts of the script and to Danil for his Russian support.
Enjoy!
I’ve got something quite different for you today. Usually when I start making a video I know “all the answers” before I even start writing up the script. Not so today. This video is about a circle of more or less open problems that I personally find very interesting, that I don’t know all the answers to and that are not very well known. My main mission today is to get you interested in these problems by reporting on some neat partial results that my friend Erich and I came across while playing around with these problems last month and hopefully even inspire some of you to do some original research. So a TH-cam video to inspire research :) What do you think of this idea?
Progress update on the problems (20 June 2018) I posed at the end of this video:
Two of you, David Stolp and Mark Miller really went for it with my 2x2x2 challenge at the end and succeeded in calculating very good approximations of the Monkey numbers of the Pocket cube. Here is what they did, in their own words. Also, if you are interested in joining the quest for other Monkey numbers, Mark has put together a Slack organisation (link at the end or ask me for his e-mail address).
David Stolp:
Average twists to solve (half-turn metric): 4410504.275
Average twists to solve (quarter-turn metric): 4647940.184
Let X be a random variable representing how many twists it takes the monkey to get from a solved state back to a solved state. The answer we seek is (E(X^2)/E(X)-1)/2. E means expected value. As noted in the video, picking a random configuration is equivalent to picking a random time in the monkey's history, thus asking how long it takes to solve a random start state is equivalent to asking when the next solved state is after a random point in time.
To compute E(X^2), I used a computer simulation. Initially there were way too many states. The state graph has many symmetries, so many states can be combined together. Doing this resulted in a graph with just 77802 states. I simulated the first 2000 twists. After 2000 twists, the probability density function of X is indistinguishable from a geometric distribution, so I used that as an optimization to get the final result.
Mark MIller:
Rather than statistical estimates from repeatedly selecting moves [which I have gathered was the strategy employed by Erich Tomanek], these are calculations from the matrix representing transition probabilities in the random walk, which was solved numerically with the SciPy sparse linear algebra module. It's exact... up to some decimal precision. :)
QTM - 4,647,941.44707
HTM - 4,410,505.47686
Pretty close to the empirical numbers, indeed!
The second part is a request of you. In response to the request for serious research, I put together a Slack organization [mathologersmonkeycube.slack.com] for people who are willing and interested to discuss the problem of the 3x3x3 cube. The invite link to the slack group is join.slack.com/t/mathologersmonkeycube/shared_invite/enQtMzgwODc1NjAwMzg3LWJjOGEwYWJlYTYwZjZkZmM4NDg5YWNkOWIzNzhiYTE3NzU1NDI4NGUwZjI3ODBlNTJjMWZjNmUyYjViZmM5YjI
Mathologer I have got a different proof for 1+2+3+4+5+6... =-1/12 . If U want to see it reply me
There is also something called the slice turn metric which counts turns of the middle slices separately :)
Mathologer I study in grade 9 and I have absolutely no idea what U just said however I will look forward to it
There is also something called the slice turn metric which does count turns of the center slices :)
You should look at the library of Babel, it’s like the monkey thing your friend does
"To be or not to be that is the gznutnik." - one million years in.
It is a nice gnzutnik to consider, though. Worth the wait.
To be or not to be that is the covefe
Gznutnik is now a word.
Bcdhjgvnhgvfdtbnifωωχηηφφηξилрстлдоопсва🤣
It was actually, "To be or not to be, that is the gzornmplat;" and it was Bob Newhart on his 2nd album, _The Button-Down Mind Strikes Back_ (1960), in a track titled, "An Infinite Number of Monkeys."
Fred
Fun fact: the early versions of tNoodle were primarily coded at Thai Noodle 2 near UC Berkeley, which is where it gets its name.
fun fact indeed :)
Yes indeed. Shame about Infinite Series.
:( agreed
tbh I didn't notice; now I'm sad
@@abstractapproach634 I stopped watching after the Kelsey left. I watched because it contained higher quality math, but annoyingly, it was framed in a juvenile setting and I think that alienated both younger and older audience members alike.
Yesterday I've rewatched almost all of your videos and was wondering when you were going to upload next.
What a surprise! :D The way you present them is unique, and the cameraman just makes it all 100 times better
Also wow you sure do love rubik's cubes
:)
Hey can you do a video about using math to get out of the inside of a Rubik’s cube? I got sucked into another giant Rubik’s cube again and was thinking about your maths when trying to figure out how I get out.
I'm glad someone has publicly come out and said that decision to end Infinite Series was shit. It really was. It was one of the best maths youtube channels around. and I don't buy into the change of hosts being innately bad. I actually loved all 3 of them. People just don't like change.
10:11 "Okay, so the God of speedcubing is Feliks Zemdegs."
why is this so true
But _is_ it true? Or is it just the best thing a monkey has typed since the invention of the typewriter?
So i dont unterstand why the average from random to solved to should be more than the number of States. Both the random and the solved state are more or less imdistiguishble so the number should also be the number of possible States. The Simulation might have a bug or using non random numbers....
'Our three monkey problems' makes me think of the three body problem, but with monkeys...
I'm curious if you and Erich explored the shape of the distribution for the recurrence time (rather than just the mean)? I suspect it is fat-tailed vs. a normal distribution because of scenarios like the 2-move solve you pointed out. Understanding this distribution might be helpful with the "mean time from equilibrium" question.
"Understanding this distribution might be helpful with the "mean time from equilibrium" question." Yes, I was also pretty hopeful in this respect for a while and I still believe that there may be some insights to be gained in this respect. However, the first couple of things that came to my mind all did not really get me anywhere :)
I don't understand why the random to solved can be longer than solved to solved. Why is that possible?
jwrm22
You can solved the solved to solved with a shorter time because with luck you can solve it in only 2 turns or a little bit more (wich is not the case with the unsolved)
I thought the same (going from solved to solved should be the same as from solved to scrambled to solved), but not all possible ways from solved to solved go through a state of sufficient "scrambledness", and those that don't pull down the average (solved -> solved) by quite a lot, because they are very short, compared to the average.
The solved to solved don't necessarily need to go through a position that is particularly scrambled, so it's more likely to just finish the cube in 1-5 moves or something a decent amount of the time. This brings the average down quite a bit, while the amount of twists needed to scramble it don't make up for the decreased average.
Exactly. If you start with a solved cube, after the first move, the cube is only one move away from being solved. Every time the second randomly-chosen move is the inverse of the first move, your "solved-to-solved" figure gets a 2 averaged in.
I wonder if its possible to devise a metric for how scrambled a cube is.
Cube is one move away from being solved... does wrong move
M Lienau happens to me all the time...
That's OK -- you're still only two moves away from being solved, so you have a decent chance of solving in two more moves.
I was sure that the mean time from equilibrium should be equivalent to mean recurrence time the until 13:10. Then you pointed out that the monkey can benefit from undoing his moves up to that point only in the mean recurrence time scenario. Interesting.
Yes -- the mean recurrence time is lower because for the first few moves after the solved position, there's guaranteed to be a short solution and the monkey might stumble across that. But from a random position, there's unlikely to be a short solution available.
Do the half- and quarter-turn metrics here count turning the middle layer instead of some face? I expect that in both cases that isn't considered a valid move and you need to turn both parallel faces instead, but I'm not sure.
Yes, that's right :)
Yes, HTM and QTM deal slice moves as two outer layer moves. There is also STM (slice turn metric) which handles slice moves as a single move (besides that it acts like HTM).
In this model the centres are fixed and cannot be turned, so it takes two moves to perform a slice turn
A really nice video again :) I approve as a speedcuber and student of Mathematics.
That's great. I actually sometimes find it a bit frustrating that a lot of mathematicians just hate everything about twisty puzzles and that on the other hand the vast majority of speedcubers just don't see the point of treating twisty puzzles as actual puzzles to be sorted out and not just an exercise in pattern recognition :)
Mathologer Actually, at the moment I'm taking a course in abstract algebra and I really enjoy learning about Group theory concepts and applying them to a cube.
So what's the intuition behind it taking longer to solve a scrambled cube than to scramble, then solve? I assume that's due to "lucky" barely scrambled configurations?
And how long are the necessary mixing times actually? My vague guess is, that something like twice the maximum number to solve (i.e. 40 or 52) would suffice?
And finally, is there any substantial difference between the metrics?
Like, if you want to be efficient with respect to one or the other, does the most efficient sequence of moves ever change? - I assume the answer is no, since if quarter turns are ever more efficient, the half-twist metric will just use those. But maybe there are instances where, I don't know, two half-twists (= four quarter twists) can accomplish a solution just as fast as three quarter twists (pretty sure this particular example won't work due to the quarter twists not both being even or both being odd, but something to that effect) which would then mean the most efficient half-twist path is longer (in terms of quarter twists) than the most efficient quarter twist path...
This is too complicated for me, I mean, I can barely do a 1x1x1 cube :/
I've got just the 1x1x1 problem for you at the end :)
luclily 1x1x1 cubes come solved out of the box, so i always just throw the old one away and buy a new one. it's very clever.
Indeed, 1x1x1 is hard, I want 0.5x0.5x0.5 :) But btw, I wam wondering here if it's possible to every construct some formula to actually calculate any n*n*n cube just by putting "n" into a given formula/algorithm, whatever, knowing, that the algorithm itself should be more clever though than just the brute force method ...
It depends how the 1x1x1 cube is sitting in the box and which way its opened. There a 23 in 24 chance that it won't be solved unless its packaged to sit in the solved configuration with careful instruction on which way to open the box.
RCB Am I the only one who still calls him NerdBubbleGum?
Agree, we shouldn’t have to wait for monkeys or anyone to scramble/unscramble possible combinations of particles in any multiverse to continue to enjoy “PBS Infinite Series“. Not a forward-thinking decision on the part of PBS to cancel it. The hosts, all 3, were gifted presenters of fascinating, thought-provoking material normally obtuse for almost anyone without a higher mathematics background. The kind of show (like yours) that can inspire folks to pursue math and science careers as they realize mathematics is a rosetta-stone for deciphering creative processes at work in nature, and which also reveals ways for them to create the kind of better future we all hope to live in.
Enjoyed this video. Look forward to other Boltzmann (via monkeys if you want) related topics you might choose to do. In an era where content decisions can correlate with lowest common denominator trends, glad you are continuing to make videos.
I stopped monkeying around with the Rubik's Cube about thirty years ago. Ducci Sequences and Pythagorean Triads are far more satisfying
You should give cubing another go. What really interests me when it comes to twisty puzzles is finding my own solutions in a systematic way. There is so much great maths to be found there. I talk about the main very simple key insight in this video th-cam.com/video/-NL76uQOpI0/w-d-xo.html
at 3:39, the subtitles should read stochastic instead of sophistic, no?
Very interesting and amusing, as allways👍. Question: what is the number scrambled configurations that actually require at least 20 movements? It seems to me that a fair competition scrambler should make sure that the starting configuration is one of these combinations
There are about 500 million such configurations (www.cube20.org/)
I don't know why, but for some reason the words "devil's algorithm" kept coming to mind.
It's on my list :)
Given a solved Rubik's Cube, what is the most number of scrambling moves that can be made before there is more than one solution to unscramble it with the same number of moves? I suspect it's more than 5 or 10 but how would you prove what it is.
Finally found someone that understand the cube and know there's WCA
Is there an online petition or some "official" place to write to PBS?
with the monkey you are imposing blindness, we know monkeys have some puzzle solving int, but you make them blind and take the worst case
I don't know if it's because of the left out details, but the proof you gave in this video did not manage to convince me. After thinking about it some more I accepted that the result might be correct, but it still seems completely counter-intuitive.
What were you talking about 20:05 how could they and why didn't you help us help you help us all, by helping us at sending complaints...
Andreas Aristokrates wow, I understood your train of thought, wow. Well said.
that train of though is almost worth a video on it's own :)
I feel it
For your math did you use quarter turn metric, half turn metric, or slice turn metric? It would have an effect on the results.
If you watch to the end I talk about half turn and quarter turn metric and what influence using one or the other has on these numbers. To start with all numbers are w.r.t. the half turn metric :)
Mathologer OK thanks, sorry about that.
It was the best of times, it was the blurst of times.
It's been tested and we know that no amount of immortal monkeys will ever recreate Shakespeare. The test result with just a single monkey was several pages of a single letter and a broken keyboard (so the mortality of the monkey didn't even matter as it rendered typing impossible). Thus, I believe applying this to a magic cube shows that a monkey will do the same twist over and over before throwing the cube or pulling it apart.
When the computer "explodes"and rearranges all of the pieces, wouldn't it be possible for it to make a parity error?
Yes, that's why I said only 1/3 of the cubes you get this was are actually solvable by twisting. In the very early days of this channel I made a video about how you can recognise easily whether or not things will work out : th-cam.com/video/ukMnXwF9y4c/w-d-xo.html
More importantly....WTF is a Monkey number?!
Wie rechnet man eigentlich die ganzen verschiedenen Möglichkeiten aus, wie ein würfel verdreht sein kann? Also wie zum Beispiel beim 2x2x2 die 3,674,160
so a curvy copter is not substantially identical. I feel like even calculating move numbers much less gods number would be dificult
I think the average solving time is greater than average recurrence time because of short recurrence sequences like U U’ or U R R’ U’ I think if we consider several main cases, we may get a good approximation of the average solving time. But if you ask for the exact expression, I don’t see how.
This is exactly correct. For the first few moves after a solved position, you're guaranteed that a short solution exists, and there's a small but significant chance that you'll randomly follow one of those paths.
I thought 58 seconds was a bit much for randomly solving a Pocket Cube, so I wrote a monkey in c++ that solves in ~0.2 seconds.
cool, is it graphical or do you give it some kind of data structure and it spits out moves?
It was a data model that permutated until it solved.
78000 twists seems awfully slow to me if it's just random moves. Any reason for this?
Even in a rather slow programming language (say python) you can get up to the order of 100k to a million random numbers in a second, and for faster implementations you can get a lot more than that (e.g. 10 million in half a second with pypy). So unless there is some huge cost of permuting the cube and checking for correctness the 78k figure seems weird.
Absolutely, what Erich did there was definitely far from optimal. In fact, I am pretty sure he used Python. So definitely lots of room for improvement. We really just wanted to get the ball rolling and intuition some intuition. Very happy to leave it to the experts to really go for it :)
My thoughts on the 3x3x3 God's number:
Rather than solving every possible configuration, one might make a matrix of every possible configuration, and then track how to get there from a good state. One would start with one twist and then add that to a tree structure. Then add every possible single twist and add those configurations to the tree. One could then track how many steps (from solved) are required to get all the possible configurations. Still requires a super computer however..
My time to solve the 3x3x3 is about the minutes. I adapted those steps to 2x2x2 but I'm not all familiar with that yet.
I feel like a more interesting version of the second problem would be to see how many random moves it takes on average to solve a specific cube configuration. I'm guessing that there's some symmetry in the graph of configurations that makes it so that this number is only dependent on how many moves away that configuration is from a solved cube, which would immediately let you solve problem #2 by computing a weighted average, while also containing a solution to problem #3.
What's more, I feel like that problem might be easier, or at least easier to approximate. Given a configuration c, let l_c be the minimum amount of moves needed to solve it, and let s(c) be the (random) result of performing a random move on c.
Evidently, if l_c=0, l_s(c)=1, and l_c=20=>l_s(c)=19
However, if l l=c=1, there's a 1/12 chance l_s(c)=0, and a 11/12 chance l_s(c)=2. Similarly for l_c=19
For 2>=l_c
There is a similar idea with monkeys instead of letters. In a finite amount of time (which can also be veeeery long, but much shorter than an infinite amount of time) you could try out all possible colour combinations of an image of a defined size like 1920x1080 with a defined colour depth like 24 Bits. The result would be ANY image you could possible imagine. That idea is quite mind blowing. There is a blog post about that idea: www.mathegedanken.de/bitmap-zeigt-alle-bilder
It might seem counter-intuitive that solved to solved takes fewer moves on average than scrambled to solved. You might think "But it has to go through scrambled first so why isn't solved to solved twice as long?" The solution was hinted at in the video, but maybe a more blatant explanation is needed. Solved to solved includes the possibilities where you simply do one or two moves and then reverse them, so solutions that are much less than the average. It also includes many that are much larger, where you maybe come withing one of solving the cube, and then stray away from the solved state for a while. This is what brings the average to the total number of possible states. However, when you are going from "well scrambled" to solved, you are not allowing the starting configurations that would only take one or two moves to solve the cube, but maybe only ones that take at least 5 moves, making it much less likely to get a short solve. This means the larger numbers still occur but the smaller ones do not, so the average gets driven up.
Is a quarter turn of the middle rank of the cube considered a single turn, or may one only twist a top-bottom-or-side away from the rest of the cube in a single move?
Starting from fully solved cube and twisting it once in any direction gives one random position, it can be solved with one twist backwards, that's the shortest random move, but if one turns it instead to the same direction again and then back again and then back to the original direction and so on then we are at a loop and no solution can be found, unless one changes the direction of turn just before the solution. So the number is the mean value between infinity-1 and 1
Problem solved... :)
Randomness does not mean diversity, just one turn of the cube gives one possible random position the cube can be at. It's just as valid random position than one that has been twisted thousands of times. Twisting the cube in a loop one step forward and one step back is just as random as any other move.
Jyrki Koivisto but it's much less likely.
It's just as likely, that's the way randomness works. It has no prejudice for one move over the other. Just think about it, looping infinetely just before the solution is just as random as any other move. You could twist the cube in any other direction randomly and infinitely if you wish just loop it such that the solution will not be found and the solution will still be between infinite-1 and 1
The cube can be twisted infininetly and no solution will ever be found (if one is just about to solve the cube, then just don't. There's always a move to be done that doesn't solve the cube), that's the main point. And the move will still be as random as the others. But all it takes is one turn and the cube is solved. "number" that has no limit is very much larger than any "number" before it, so it doesn't matter how long one twists the cube, but still the solution will come just before infinity or else there is no solution.
Yes, but the probability of that infinite sequence of "wrong" moves is only infinitesimal, which is why the _average_ recurrence time is N (number of states of the system).
Hi,
I really like your videos, but here in the case of the 3x3x3 there is something you forgot to consider.
If you start with a solved 3x3x3 cube, and later got it with only two centers rotated (by a quarter for instance), then the cube is solved though the state is not the one you started with.
Said otherwise, there is not only one combination for a 3x3x3 cube to get solved, as there is no orientation needed for the center of each color, and this is even more true (truer?) for greater cubes.
However, what you told is perfectly true if you switch the color of the centers for an oriented pattern (like a sign with no symetry by 180° rotation, the letter A for instance, but not the letter Z). Photographs or pictures generally do the job as well.
To check my words, get a 3x3x3 Rubik's cube and see how the logo is oriented on the whites, then shuffle it and give it to solve to somebody who doesn't know how it was oriented.
There is only one chance on four the logo will be oriented the same when the cube is solved again... so now imagine you have a logo on each colors...
I tried to evaluate by myself, it took me only a few minutes to identify about one hundred (well I stopped at 82) different combinations for which the 3x3x3 cube is solved with only colors. And as I told you this is even "worse" for bigger cubes (because the center part is then also bigger).
Hope this helps.
Karl Deux what you say is an excellent insight however the way that the solved cube is measured isn't based on one of the centers, in which case you would be right, but rather on one of the corners, thus leaving only one possible solution assuming that corner is stationary
I think the mean time from equilibrium for the 1x1 cube is 42 moves
See SmileyMVC posts below, it is 24 from solved to solved and 24.75 for scrambled to solved.
The discussion on half-turn and quarter-turn metrics didn’t mention if turning a middle layer counts as a single step. I’m guessing it counts as one step, despite the prevailing move notations representing a center turn as two turns of the flanking layers.
Actually in both these metrics slice moves are counted in terms of two turns of flanking layers. There is a third kind of metric called slice turn metric where any turn of any layer, by any angle, counts as one turn. God's number for this metric could be less than 20 (but at least 18 :) There are also anti-slices, imbalanced anti-slices, compound slices and anti-slices, compound imbalanced anti-slices and various metrics that incorporate these specialised turns.
Mathologer - My first thought was since it’s possible to turn the middle layer independently, it should count as a single move. But then I started thinking of n-layer cubes. In retrospect, I think a single move should be defined as fundamentally and generalizably as possible, which would be a quarter-turn slice move. I take that to mean the player chooses any slice plane, partitioning the pieces left and right, and then do a quarter turn of those two partitions in either direction. With that definition, turning a 3-cube’s middle layer a half turn would comprise four quarter-turn slice moves, two quarter turns in each side. Otherwise we’d have to count a synchronous turn of the first, third, and sevenths layers as a single move.
Consider my mind blown.
Is it bad that this makes me think of Dr. Scratchensniff from Animaniacs?
Don't know what to say the monkeys won't do.
sir Mathologer you are my ideal plss tell me how to make a Mathematics channel like you
10:28 4.22 SECONDS?!
I probably couldn't even swap two edges in that amount of time!
XDCool123 ! No one can, swapping 2 edges is impossible.
Swapping 2 edges is impossible for a rubik's cube
Some of the monkeys watching this video might be insulted by your portrayal of monkeys as incapable of learning to solve a Rubik's Cube any more efficiently than random chance. Especially if you use a monophyletic phylogenetic definition of "monkey", which would include humans.
What are the numbers for those 3x3x3 cubes with pictures on each of the six faces where the orientation of the center square of each face has to be correct?
6:20 SLAVE?
1x1x1 cube puzzle solution: 24.75
I did this with the PRISM Model Checker using a markov chain.
Here's the module:
dtmc
module m
s : [0..65] init 0;
[] s=0 -> 1/24:(s'=61)+1/24:(s'=62)+1/24:(s'=64)+1/24:(s'=65)+1/24:(s'=16)+1/24:(s'=12)+1/24:(s'=13)+1/24:(s'=15)+1/24:(s'=26)+1/24:(s'=21)+1/24:(s'=23)+1/24:(s'=24)+1/24:(s'=31)+1/24:(s'=32)+1/24:(s'=34)+1/24:(s'=35)+1/24:(s'=46)+1/24:(s'=42)+1/24:(s'=43)+1/24:(s'=45)+1/24:(s'=56)+1/24:(s'=51)+1/24:(s'=53)+1/24:(s'=54);
[turn] s=61 -> 1/6:(s'=62) + 1/6:(s'=65) + 1/6:(s'=46) + 1/6:(s'=13) + 1/6:(s'=21) + 1/6:(s'=51);
[turn] s=62 -> 1/6:(s'=61) + 1/6:(s'=64) + 1/6:(s'=56) + 1/6:(s'=23) + 1/6:(s'=12) + 1/6:(s'=42);
[turn] s=64 -> 1/6:(s'=62) + 1/6:(s'=65) + 1/6:(s'=16) + 1/6:(s'=43) + 1/6:(s'=24) + 1/6:(s'=54);
[turn] s=65 -> 1/6:(s'=61) + 1/6:(s'=64) + 1/6:(s'=26) + 1/6:(s'=53) + 1/6:(s'=15) + 1/6:(s'=45);
[turn] s=16 -> 1/6:(s'=12) + 1/6:(s'=15) + 1/6:(s'=31) + 1/6:(s'=64) + 1/6:(s'=26) + 1/6:(s'=56);
[turn] s=12 -> 1/6:(s'=16) + 1/6:(s'=13) + 1/6:(s'=51) + 1/6:(s'=24) + 1/6:(s'=62) + 1/6:(s'=32);
[turn] s=13 -> 1/6:(s'=12) + 1/6:(s'=15) + 1/6:(s'=61) + 1/6:(s'=34) + 1/6:(s'=23) + 1/6:(s'=53);
[turn] s=15 -> 1/6:(s'=16) + 1/6:(s'=13) + 1/6:(s'=21) + 1/6:(s'=54) + 1/6:(s'=65) + 1/6:(s'=35);
[turn] s=26 -> 1/6:(s'=21) + 1/6:(s'=24) + 1/6:(s'=32) + 1/6:(s'=65) + 1/6:(s'=16) + 1/6:(s'=46);
[turn] s=21 -> 1/6:(s'=26) + 1/6:(s'=23) + 1/6:(s'=42) + 1/6:(s'=15) + 1/6:(s'=61) + 1/6:(s'=31);
[turn] s=23 -> 1/6:(s'=21) + 1/6:(s'=24) + 1/6:(s'=62) + 1/6:(s'=35) + 1/6:(s'=13) + 1/6:(s'=43);
[turn] s=24 -> 1/6:(s'=26) + 1/6:(s'=23) + 1/6:(s'=12) + 1/6:(s'=45) + 1/6:(s'=64) + 1/6:(s'=34);
[turn] s=31 -> 1/6:(s'=32) + 1/6:(s'=35) + 1/6:(s'=43) + 1/6:(s'=16) + 1/6:(s'=21) + 1/6:(s'=51);
[turn] s=32 -> 1/6:(s'=31) + 1/6:(s'=34) + 1/6:(s'=53) + 1/6:(s'=26) + 1/6:(s'=12) + 1/6:(s'=42);
[turn] s=34 -> 1/6:(s'=32) + 1/6:(s'=35) + 1/6:(s'=13) + 1/6:(s'=46) + 1/6:(s'=24) + 1/6:(s'=54);
[turn] s=35 -> 1/6:(s'=31) + 1/6:(s'=34) + 1/6:(s'=23) + 1/6:(s'=56) + 1/6:(s'=15) + 1/6:(s'=45);
[turn] s=46 -> 1/6:(s'=42) + 1/6:(s'=45) + 1/6:(s'=34) + 1/6:(s'=61) + 1/6:(s'=26) + 1/6:(s'=56);
[turn] s=42 -> 1/6:(s'=46) + 1/6:(s'=43) + 1/6:(s'=54) + 1/6:(s'=21) + 1/6:(s'=62) + 1/6:(s'=32);
[turn] s=43 -> 1/6:(s'=42) + 1/6:(s'=45) + 1/6:(s'=64) + 1/6:(s'=31) + 1/6:(s'=23) + 1/6:(s'=53);
[turn] s=45 -> 1/6:(s'=46) + 1/6:(s'=43) + 1/6:(s'=24) + 1/6:(s'=51) + 1/6:(s'=65) + 1/6:(s'=35);
[turn] s=56 -> 1/6:(s'=51) + 1/6:(s'=54) + 1/6:(s'=35) + 1/6:(s'=62) + 1/6:(s'=16) + 1/6:(s'=46);
[turn] s=51 -> 1/6:(s'=56) + 1/6:(s'=53) + 1/6:(s'=45) + 1/6:(s'=12) + 1/6:(s'=61) + 1/6:(s'=31);
[turn] s=53 -> 1/6:(s'=51) + 1/6:(s'=54) + 1/6:(s'=65) + 1/6:(s'=32) + 1/6:(s'=13) + 1/6:(s'=43);
[turn] s=54 -> 1/6:(s'=56) + 1/6:(s'=53) + 1/6:(s'=15) + 1/6:(s'=42) + 1/6:(s'=64) + 1/6:(s'=34);
endmodule
rewards
[turn] true : 1;
endrewards
and the property is: R=? [ F s=65 ]
A state is characterized by two numbers. The first is its front side, the second its top side. Opposite sides are 1-4 and 2-5 and 3-6. Each line represent an action called "turn" with six equally likely outcomes. The first line specifies the initial state from which you go to any state with a equal probability. The reward specifies 1 reward for each turn action (i.e. for every action except the first one). The property asks for the reward accumulated specifies a reachability reward, i.e. what reward will be accumulated on average ("R=?") when my goal is hit ("F", stands for finally) where the goal is to be in state 65. State 65 is my declared solved state but any other valid state works here too.
Run that through PRISM using the exact engine you get 99/4 or 24.75.
With the 2x2x2 this method may work as well. You just need some good encoding for the cube state and maybe a super computer (PRISM starts to struggle when numbers become 6 digits usually, for the 2x2x2 we'd need 7 digits even).
Where can I sign up for PBS Infinite Series to produce videos again? I loved their videos as much as I love yours!
Leave a comment on their last videos and also leave a couple of comments to this effect on some of the other PBS channels you like :)
It should be noted that monkeys, like humans, are notoriously non-random. Also, rather destructive. See "Notes Towards the Complete Works of Shakespeare" (2002) by Elmo, Gum, Heather, Holly, Mistletoe and Rowan.
Transmission Control
The typewriters used in the experiment ended up rather unsanitary, if I remember correctly.
I don't unterstand how the number of turns from problem 3 should be different from the answer for problem 2.
Why should these be different?
It does not matter (only for us) in which the cube is in the initial state.
We could pick any other configuration to start with and run Problem 3 again...
the second number is higher because in the first case, after 1 twist the cube is exactly 1 twist from being solved. After two is either solved (by undoing the move) or is exactly 2 moves from being solved. Similar cases exist for all even numbered moves and the early ones contribute significantly to the average.
Makes sense. Thanks!
Wouldn't there be multiple 'solved' configurations for the 2x2x2, since the solved cube can be in one of 24 orientations? This would bring the mean recurrence time down by a factor of 24.
Standard is, just like how the centers of a 3x3x3 are considered to never move, that a specific corner is considered to never move.
I'm a bit confused by the result for the average number of moves to randomly descramble. Could someone tell me what is wrong with the following argument?
Randomly descrambling a random configuration is like starting off at some extremely large (and random) N on the diagram at 15:00 and seeing how many moves it takes to visit the solved configuration. Since we are starting at a random N, the average number of moves to the next recurrence will be exactly half the recurrence time. (i.e. 1837080, not 4.5 million for 2x2x2)
Is there some stipulation that the random starting position be at least some number of moves away from solved?
The Monkey number? Well, I don't know, maybe it's the "Humans' intellectual superiority has gone far beyond far, transcending that of monkeys, to the point where monkeys can't count." So no Monkey number for you.
You joke that it should be a piece of cake for a supercomputer to do it. However, this kind of thing would be exceptionally easy for an AI to learn. The numbers of moves is far far less than an average Go game. AI's have already surpassed humans in that. With enough runs (thousands? millions?) an AI would be able to solve it nearly instantly.
0:08 lol im a speedcuber and a hardcore mathologer fan.
When you say "on average" is that the mean moves required by all solutions or the time it takes for the average monkey to solve the puzzle (i.e. median)? Big difference here I suspect (skewed distribution?) and one where both are quite suitable summaries of the problem given.
0:35 Really? Then why can I never solve a Rubik's Cube, even with far more than 20 turns?
God must not exist! Theism is a lie! All Hail the Godless Universe!
I don’t understand why solving the randomized cube takes more random tries than solved to solved
Basically there's a good chance that your 2nd turn will undo the first (or that your 3rd and 4th turns will undo the first two, etc.) which lowers the average by a lot.
I feel like I'm missing the obvious here but at 14:17 I don't exactly understand how the diagram can contain N dots. Can somebody explain that?
I think I might have an idea to approach the 2x2x2 problem, but I need some clarification, as somewhere in the comments i saw you saying you have a 1/12 chance to come back after one move. I'm not quite sure how you get to 1/12. To stick with notation usually used, there is U, U', U^2, D, D', D^2, B, B', B^2, F, F', F^2, L, L', L^2, R, R' and R^2. Regardless of the first move, there are 2 that solve it. It in reverse and it's opposite one in the other layer. So where is this 1/12 coming from? What am i missing?
Use quarter turn metric
Even in quarter turn metric, there are 2 out of 12 that solve the cube. Suppose R is our first move, both R' and L solve it.
tbpotn good point. Are you sure the comment you saw didnt refer to the 3x3x3? Because there it would be 1/12
I guess that is possible!
Hm. The proof for the mean recurrence time wouldn't even necessarily require that all of the states of something are similar. The only requirement really is that all states tend towards being equally probable as the number of steps goes to infinity.
Great video! I loved the way you walked through your explorations.
Your Mathologer monkey will never beat Felix if your monkey does solve the puzzle like a bogosort XD
Im not sure if you have accounted for this, a wile back I realized that the rubiks technically doesn't just have one solved state, their are actually thousands of them, possibly even tens of thousands of solved states in a regular rubiks cube, it might be a little hard to wrap ones head around it, but you can rotate the the middle prices on a regular rubiks cube, and I suspect if you tell a computer only to look for one of theses solved states it may entirely pass by so perfectly solved positions just because the center pieces weren't oriented currently, is this accounted for in theses calculations? if not you could be massively overstating the average amount of turns it takes to reach one of the thousands of different solved states
In speedcubing we say "turns" for what you mean "twist". "Twist" means phisicall corner rotation whitout turning the cube.
I love my cube.
Is this the kind of thing ergodic theory talks about?
ОБ ЭТОМ Я ДОДУМАЛАСЬ17ЛЕТ НАЗАД.И ДЕЛАЛА ГЕНЕРАЦИЮ ИЗ БУКВ.ЖАЛЬ,ЧТО ВЫГЛЯДИТ ТАК,БУДТО ОН ПРИДУМАЛ ЭТУ ЗАДАЧУ,А ДРУГИЕ-ТИПА НЕТ( спасибо за русский перевод!
IS THAT A 10x10
Ur vdos r osme.But can you PLEASE make them shorter? You'll get a lot of views
Are there multiple ways of having a solved Rubik's Cube? for example if the centers could be rotated 90 180 or 270° it would also be in a different configuration, but still solved?
yes, if you have a picture cube where you can see the center rotation, the cube can be completely solved with the centers still being rotated (no one center can be turned 90° only 180° or 2 centers each 90°)
Yes, these states are all considered "solved" on a normal cube. You can get cubes where the centres do have an orientation; these are known as "supercubes". Here's what a 4x4 supercube looks like:
i.imgur.com/h3UoxCA.jpg
Some also have arrows on; solving the cube normally may leave the central arrow pointing in the wrong direction.
Solving these normally is not much different to solving a regular cube, but it would certainly change the calculations in this video!
math amatics In real life yes, but in this experiment the centres of the cube are fixed, and therefore there is only one solution
Question No 3: Why use a monkey at all when having a solved Rubik's cube?
Stupendous!
19:08
Wait, what? So for any of possible states a Rubik's cube can be in, and that every cuber perform several algorithms on to solve, you could actually solve it in less than 20 moves? That doesn't sound right... EDIT: I just googled about this. Well, they count a 180° turn as a single turn, and I consider that to be two turns. So god's number is a little bigger.
God's number is 26 if you count in quarter turns. In mention this towards the end of the video :)
Average twists to solve (half-turn metric): 4410504.275
Average twists to solve (quarter-turn metric): 4647940.184
Let X be a random variable representing how many twists it takes the monkey to get from a solved state back to a solved state. The answer we seek is (E(X^2)/E(X)-1)/2. E means expected value. As noted in the video, picking a random configuration is equivalent to picking a random time in the monkey's history, thus asking how long it takes to solve a random start state is equivalent to asking when the next solved state is after a random point in time.
To compute E(X^2), I used a computer simulation. Initially there were way too many states. The state graph has many symmetries, so many states can be combined together. Doing this resulted in a graph with just 77802 states. I simulated the first 2000 twists. After 2000 twists, the probability density function of X is indistinguishable from a geometric distribution, so I used that as an optimization to get the final result.
For half-turns only, I get E(X) = 24, E(X^2) = 1600.8 (exact), monkey number = 32.85 (exact). For the bandaged case, with quarter-twists only, I get E(X) = 29160, E(X^2) = 2769802402 (not exact), monkey number = 47492.68. For bandaged with half-twists allowed, I get E(X^2) = 2572392092 (not exact) and monkey number = 44107.73
I just quoted your initial post and that by Mark Miller in my comment pinned at the top of this comment section. Mark also put together a Slack organization [mathologersmonkeycube.slack.com] for people who are willing and interested to discuss the problem of the 3x3x3 cube (if you are interested in getting in touch with him directly please send me an e-mail and I'll forward his address to you)
join.slack.com/t/mathologersmonkeycube/shared_invite/enQtMzgwODc1NjAwMzg3LWJjOGEwYWJlYTYwZjZkZmM4NDg5YWNkOWIzNzhiYTE3NzU1NDI4NGUwZjI3ODBlNTJjMWZjNmUyYjViZmM5YjI
return to monke
Can someone tell me book collection I am thinking of but can’t remember that his shirt is referencing.
Mr Men series
God's number for turns needed to transform one "solved" position to any other?
1 if you can flip the whole cube over, three if you cant (turn each third). if you want to get the opposite face its 3 half, 6 quarter. adjacent faces are 1 quarter and ..... a lot of half turns (*I think you'd have to practically undo and resolve the cube to get to an adjacent color with half turns). This is a more interesting question than I thougtht it wold be when I started my reply cool.
ANYONE KNOW HOW MANY HALF TURNS TO GET AN ADJACENT SIDE TO THE TOP????? It's three quarter turns, but I think maybe alot of half turns.
I'd be curious to now if any of the "unsolvable random configurations" can be solved with quarter turns only.
@7:45 At this point I'm really interested in why my intuition is wrong. Intuitively, it _feels_ like starting with a solved cube, putting in 100 random twists to randomize it, then randomly solving, should give the answer to Problem 1 less the number of random twists at the start. But the answer to problem 2 is significantly larger than the answer to Problem 1.
Mathematics is frequently counter-intutiive so that in and of itself is fine. I'm just wondering what the problem in the intuitive reasoning is.
I think your intuition breaks down by overestimating the likelihood you would successfully invert the sequence of 100 twists you made and what it means for those 100 twists to randomize the cube.
If the 100 twists actually randomizes the cube (i.e. chooses one of the N configurations uniformly at random) then it doesnt matter if this was done with 100, 1000 or 100000 twists. The problem is still the same.
Furthermore, in the video he mentioned that any configuration can be solved with 20 moves or fewer. So if we assume that we need 20 moves then the probability we correctly perform the sequence of 20 moves is (1/27)^20 or approximately 10^-20. Which is a very small number. The probability that you exactly invert your sequence of 100 moves is much worse.
@@a63bd8lkjbf98
Thanks for responding! :)
"I think your intuition breaks down by overestimating the likelihood you would successfully invert the sequence of 100 twists you made and what it means for those 100 twists to randomize the cube."
Hmm... Let me see if I'm understanding what you're saying.
First, I'll restate the problem I'm having a little bit better:
It takes an average of 3,674,160 twists to go from solved back to solved.
Let's re-run that test, two instances in parallel. We give Monkey A a solved cube and get it to start twisting randomly.
After Monkey A has done a couple of hundred twists, we stop it. We then copy the cube it currently has, and give the copy to Monkey B. Both monkeys then start randomly twisting their own cube at the same rate.
My intuition tells me that both monkeys should arrive at the solved cube in the same number of random steps.
However, Monkey A is doing mean recurrence time, and Monkey B is doing mean time from equilibrium. And the host is telling us that Monkey A takes 3,674,160 twists on average, and Monkey B takes 4,500,000 twists on average.
Intuitively, that seems kind of bonkers.
If I'm understanding you correctly, is the problem that Monkey A isn't _actually doing_ a mean recurrance time? In the example above, we're not truly doing mean recurrance, because any example where Monkey A accidentally solves the cube too early by randomly reversing its own sequences gets removed from the data set for Monkey B. Which means that all of the instances where a mean recurrance test finishes before the "couple of hundred" threshold are removed from the data set, and this inflates the count for Monkey B?
Or am I completely lost here?
Thanks again. Genuinely confused here. Appreciate the help.
For a 1x1 cube it is O(1)
Insofar as it makes sense to use big-O notation for single numbers, it's O(1) for any fixed size of cube. Big-O only makes sense when you're measuring with respect to a variable that can go to infinity.
2x2x2 Rubiks cube should be called the Twobiks Cube
Lol I’m the only cuber here
I spotted one more somewhere else in this comment section :)
I get it so. every combination if you were to randomly scramble the cube for as many combinations as there are. to the power of as many combinations as there are. there would be an equal number of chances for it to be any given combination including solved and completely scrambled.
Something like that???
I only understand about 2/3 of the math related terms you say, but that’s probably because I’m still taking calculus in high school
I once held a seminar lecture about random walks on an integer lattice, and one of the results was that the expected recurrence time was infinite (for the symmetric case). Makes sense, since in this case the number of possible states is infiinite.
This whole circle of idea is definitely worth another video, Polya's theorem especially is something I'd really like to do at some point :)
Only in 3-or-greater dimensions, though.
This argument only applies to finite state spaces. In one or two dimensions, the expected recurrence time is finite; it's only infinite for three or more dimensions.
So I know \how\ to do the problem given at the end of the video, but it involves me making a 24 by 24 matrix, with each row and column corresponding to one of the states, with 0's everywhere unless you can transition from the row state to the column state, in which case you put an entry of 1, with the states in the same order for the rows and columns. Then, you divide each row by its sum, to change it into the probability matrix, which you then modify by setting each entry in the row and column of the solved position to 0, and call this matrix A. Then if a vector x has the probability of the matrix being at a certain state (each entry corresponding to the column), Ax has the probability of all of the twisting you can do to the matrix.
This is a symmetric matrix, and since it has this "probability minus a little bit" feel, we hope that as n goes to infinity, A^n*x goes to 0. Note that what we care about for average solve time is slightly different- the percentage of cubes that achieve the solved state at step i+1 is it is |x_i|-|Ax_i|=|x_i|-|x_(i+1)|=f(i+1), so really what we want is the sum from i=1 to infinity of i*f(i)
So, if there is some nice, closed form version of f(i), you can probably plug it into wolfram alpha. And thankfully for us, there is, because as already mentioned, A is real and symmetric, and as such has an eigenvalue decomposition and can be written as VDV', where D is a diagonal matrix and V is orthogonal.Then, f(i+1)=|x_i|-|VDV'x_i|=|VD^iV'x_0|-|VD^(i+1)V'x_0|, where we set x_0 to be the matrix with 1/24 at every position, i.e. an equal chance to be at every ruby position state, and you're done!
… except that I don't know how to simplify down f(i).
Lets try a different strategy: this time, we're going to change the matrix A so that the entry corresponding to the row and column of the solved position is 1. , i.e. once you are at the solved position, you stay there. Then, set f(i+1)=x_i+1,(solved position)-x_i,(solved position)=x_(i+1)*e_s-x_(i)*e_s=e_s*(x_(i+1)-x_i), where e_s is the standard basis column vector corresponding to the solved position, and * is inner product. Notice that the "direction of the subtraction" reversed. Then, we still want the sum from i=1 to infinity of i*f(i). We still need a closed form for f(i+1), and the approach starts off the same way, but is much more successful- f(i+1)=e_s*(x_(i+1)-x_i)=e_s'(VD^(i+1)V'x_0-VD^iV'x_0)=e_s'V(D-I)D^iV'x_0. Grouping usefully, this becomes: f(i+1)=(e_s'V(D-I)) D^i (V'x_0), using the same x_0 as before.
f(i) then is not geometric, but its close- For some constants a_m, it can be written as a_1D_1^i+a_2D_2^i+…a_24D_24^i, which is definitely good enough to get a number for the sum from one to infinity of i*f(i), by separating each of the terms and summing them up separately.
There are 2 flaws in this approach: The eigenvalue decomposition is not guaranteed (and in fact, probably wont) only contain say algebraic numbers in it, particularly if done iteratively (like every computer ever does it), but this would just need to be checked for this example, and the other flaw is I reallyyyy don't want to make the matrix
Either way you cut it, this does not seem to be the correct way of doing this calculation. Anyone have any comments on this or better ways to do it?
Well, apparently this is basically the right thing to do, because I think the paper cited uses (much more elegant) versions of the same basic idea
How come God's number exists but God doesn't exist?
So the "god number" is 20, but that's in reference to an arbitrary cube position (that we call "solved"). Does that this mean that every one of the 43 quintillion positions can be transformed into any other arbitrary position in 20 moves or less?
If I understand it correctly yes. What is not clear to me is whether God's number is a stochastic determination or a true maximin; if it's stochastic, then it is possible that arbitrary -> arbitrary may take more than 20 moves.
Yes, since there's nothing special about the behaviour of any particular cube state. A more helpful way to think about this is that God's number is the diameter of the state space, which is the maximum number of twists needed to get from one state to another. Because we're dealing with a group, the state space looks the same from any state, so it takes at most 20 twists to get from any state to any other state, including from any scrambled state to solved. For further reading on this look up Cayley graph, which is the "state space" of a group.
true maximum.
+CorwynGC - thanks!
feliks' 4.22 is the world record
On average, it would take a human 70 years to die