What's the Monkey number of the Rubik's cube?
ฝัง
- เผยแพร่เมื่อ 9 มิ.ย. 2018
- 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.infinitemonkeylab.com
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/0909.2636 (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.stackexchange.com/questi...
Here are the World Cubing Association rules on scrambling twisty puzzles for competitions:
www.worldcubeassociation.org/...
Here is a link to a video which shows the scrambling program tnoodle in action: github.com/thewca/tnoodle/pul...
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
:)
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.
Great video! I loved the way you walked through your explorations.
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.
I'm so glad you included the bit at the end about the quarter turn metric. Having a single antipode is so much more satisfying. Also, I'm glad I watched to the end before I commented.
The quarter-turn metric is the way to go as far as I am concerned :)
Your videos are fantastic and I'm looking forward for more :D
Well, I just finished my teaching at uni for a while so I finally got a bit more time for making videos :)
Stupendous!
Very nice video!!
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....
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
I don't know why, but for some reason the words "devil's algorithm" kept coming to mind.
It's on my list :)
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.
In speedcubing we say "turns" for what you mean "twist". "Twist" means phisicall corner rotation whitout turning the cube.
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.
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 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.
Hey Mathologer, are you possibly having any merch with these shirts? I'd love to buy the: "Math. Nothing 2b^2 of!". It's like my greatest mission yet as a math student. Love your videos!
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?
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.
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.
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?
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
I remember bringing the scrambled to solved problem up about a year ago. The people I asked kept insisting the answer was 20, because that's what google told them.
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
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).
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.
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?
Deep Blue, great reference!
Finally found someone that understand the cube and know there's WCA
0:08 lol im a speedcuber and a hardcore mathologer fan.
I always get chills when someone says my first name in a TH-cam video
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.
'Our three monkey problems' makes me think of the three body problem, but with monkeys...
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.
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/)
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.
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
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.
Do your simulations show the percentage of states visited by those random walks from solved to solved? Or the expected number of twists to visit all states? That might explain intuitively why the "scrambled to solved" path is longer than "solved to solved"
I was catching up on some old ones I hadnt seen. like this one. i recently watched a video by Lazslo Babai from 6 years or so on the graph isomorphism problem.
he links the string isomorphism problem to that. he describes the string isomorphism problem by means of the Rubik Cube.
randomly stick stickers onto 2 cubes, can you find an algorithm to determine whether or not one can be "moved" to be the other.
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.
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.
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...
Did anyone else notice that at 3:25 when the twenty is hilighted, the cube that represents it is in a super flip configuration?
Well spotted :)
10:15 are you sure? We're in 2018 and Max Park is a beast xD
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.
I prefer counting quarter-turns but I guess a half-turn can be done as quick as a quarter turn so execution time must be differentiated from counting cycles.
Please do some continued fractions videos, it's something nobody makes videos about :)
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.
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
Monkey'ing a cube wouldn't be a straightforward task on a supercomputer, since the calculation has to be done in series, and supercomputers work in parallel.
Though I think you could make a parallel algorithm to do the job. To monkey-solve a random cube:
1) Each node starts with a solved cube (the "node cube") and constantly applies random moves. Each time a move is made, record the state of the cube in a hash table, along with the *inverse* of the move made. (if we want a verifiable solution, store the data in two hash tables, so we can discard cube states later; if we don't care about the moves used to solve, we don't need to record them) Each node calculates this list until it receives the current cube (the "objective cube").
2) When a node receives the objective cube, check if any recorded cube states from the node cube match. If a match exists, then the objective cube is solved. The solution is all the previous moves to objective cube (by other nodes), plus every inverse move in the list of moves added before and including the matching record in the hash table.
3) If there is no match, then take the node cube and apply its permutation to the objective cube. (i.e. apply every move this node has generated, all at once). Then pass the objective cube on to the next node, reset the node cube to a solved state, and start a new hash table for recording moves (delete the old states, but keep the list of moves if you want to look at it later)
I assert that this algorithm will provide solutions with the same distribution as a simple monkey solver.
This algorithm is also light on network resources and automatically adjusts to network lag and cluster size (nodes will just keep calculating while waiting). It seems like a perfect candidate for a distributed computing effort.....
Nice
I had a feeling when the average number of turns was equal to the number of configurations that the proof would involve the fact that all configurations are functionality the same.
I've been thinking about the pocket cube recently. If one restricts to turning only one axis, then the options can be represented one-dimensionally. Of course, it is a circular geometry (or 1D spherical). If we use two axes, then the geometry of configurations seems almost 2D spherical, but in this case it is noncommutative. I'm beyond my depth at that point, but I would love to learn more.
It's helpful to fix one corner of the 2x2x2 in space and just turn the three faces that do not contain this corner. Then you can build things up by just twisting one of the faces (your circular), then two and then the full 3. I'll actually do a video soon in which I'll talk about this sort of stuff :)
I look forward to the future video. I think drawing it out as a network is not too much trouble, but I've been trying to think about how to represent it in (some sort of) space, given the noncommutative structure. I also wanted to represent it geometrically, recognizing, as you said, that each position is equivalent to the others. That is, the structure of the whole network of configurations looks the same from any node. As a side note, if I've done my calculations correctly, restricting the 2x2x2 to only two rotational axes limits it to 28197 configurations but the god's number (htm) would be 12.
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?
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
@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.
I think I'm missing something: The sketch of the proof tells us that we can consider any starting configuration of a cube, and the expectation will be the same: the number of permutations. But isn't that exactly what we're asking the monkey to do in problem 2?
"and the expectation will be the same". You have to be clear about what expectation we are talking about here. It is the expected number of steps it takes to get back to this configuration when you start at this configuration :)
Ok, then I get it.
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
at 3:39, the subtitles should read stochastic instead of sophistic, no?
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.
ОБ ЭТОМ Я ДОДУМАЛАСЬ17ЛЕТ НАЗАД.И ДЕЛАЛА ГЕНЕРАЦИЮ ИЗ БУКВ.ЖАЛЬ,ЧТО ВЫГЛЯДИТ ТАК,БУДТО ОН ПРИДУМАЛ ЭТУ ЗАДАЧУ,А ДРУГИЕ-ТИПА НЕТ( спасибо за русский перевод!
i like it
Time to crowdfund a supercomputer for Mathologer to solve this by brute forcing!
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
sir Mathologer you are my ideal plss tell me how to make a Mathematics channel like you
Aren't the configurations dependent? To me it seems like this proof (14-15 min) is for the case when you can randomly go from one to another, like rolling a dice.
The configurations are certainly "dependent", but the main thing to realise is that once the monkey hits a configuration it basically starts the whole experiment again from this configuration but this time with respect to that new configuration. And so we can expect from that point on for the cube to return to this state in essentially the same way as for the solved configuration. And when we are averaging it does not matter that it took a while to get to the new state in the first place because we are averaging over arbitrarily large numbers :)
It was the best of times, it was the blurst of times.
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
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.
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
3:22
Or Jeff Goldblum's powerbook.
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
Is there an online petition or some "official" place to write to PBS?
If I used the proof method to get the scrambled->solved number as well, wouldnt i end up also getting # of configurations as my answer? What am i missing?
In the proof we are averaging over the lengths of intervals between dots that follow each other in columns (solved to solved), at the same time we use the fact that the contribution to this average of the irregular way things start out vanishes in the long run :)
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
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?
Ok, complete wild guess on my part. 43.252B*4/3^(1/3)= 47.6 Billion moves.
I also guestimate the 1 sided cube at 33.9 moves. using the same approach.
For curiosity my formula is : #of configurations * ((n+1)/n)^(1/n) .
Too bad, that logic does not hold up. I assume you meant to say the expected number of moves to solve a random 1x1x1 is 33.9, but it is 24.75.
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 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?
lmaoo 10:10 "the god of speedcubing"
Well, he certainly is :)
Can someone tell me book collection I am thinking of but can’t remember that his shirt is referencing.
Mr Men series
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.
I just have a question, if I remember right the 43 quintillion also includes the impossible states, those that could never be archived by twisting a cube, so on the average from solve to solve are we taking them into consideration or not? Or I'm wrong and the 43 quintillion is only of accessible states?
The the 43 quintillion are only of accessible states. For the 3x3x3 to get the total number of all configurations, accessible and inaccessible you have to multiply this number by 12 :)
Mathologer Thanks, I guess the number of states is way bigger than I remembered.
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.
Consider my mind blown.
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
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 :)
feliks' 4.22 is the world record
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.
Was Mr. Polster ever a Pollster?
Why is the expected value so much larger from a scrambled cube than from a solved cube? Would you not expect to essentially cycle through each permutation within the next 3.6 million turns just like from the solved state?
I get that it is more likely to accidentally make cancellations in your moves from a solved state and that this brings down the average, but why does this bring it down to exactly the number of combinations? It seems like this would be the special case rather than the "default" case.
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!
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).
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!
Hi I'm trying to find twisty puzzles that are solvable with 3x3 algorithms. EX: mirror cube, ghost cube, and megaminx. Anyone know of any others?