The Rubik's Contraption | Hacker News Reader

The Rubik's Contraption

build-its-inprogress.blogspot.com

297 pointsjonbaer63 comments

Is there a category for robot solvers that have to fulfil the same requirements as a human solver?

In other words, I'd like like to know how fast you can build a robot that has to start with the cube lying on a table in front of it, and the manipulators (hands, in the human case of course) being away from the cube, with the timer stopping when the cube is back on the table and the manipulators are back in their original position?

Picking up and putting down a cube from a known location, and visually analyzing it, are both solved problems. It's a boring and arbitrary restriction. One could just as well require the manipulators start 100 yards away, which would be biased toward fast-moving robots.

>> Picking up and putting down a cube from a known location, and visually analyzing it, are both solved problems. It's a boring and arbitrary restriction.

In that case, solving a Rubik's cube is a solved problem. It's become boring thing to watch machines do it. These machines are somewhat impressive in their own way, but the task they are doing has no point. I'd even say because "solving" is no longer relevant, the machines should be manipulating the cube in known (non random) patterns since we're down to comparing speeds.

There is no point to solving a Rubik's cube in the fastest manner possible for humans either. It's just a challenge that some people do for fun. Just like this project is a challenge with slightly different constraints.

Similarly, building a robot that has shafts fixed to the cube’s centres is a solved problem. Quite boring indeed.

Replying to myself to add: maybe we could see a triathlon with three stages of intellectual pursuit added to the three stages of physical activity.

Run one hundred meters, solve a Rubik’s Cube, swim one hundred meters, solve a riddle, cycle five kilometres, then the first two who complete that have to head off in a game of Go.

Why not? There’s people advocating eSports be included in the Olympics, so I’m open to anything at this stage.

See also Chess Boxing: https://en.m.wikipedia.org/wiki/Chess_boxing

And Turing’s “round-the-house” chess: after you move, run around the house, if you get back before your opponent's move you are entitled to a new move.

Amazing! Thank you! I'd not seen this before.

That would be interesting. Though this rule has a handicap that human solvers do not. They do not inspect the cube prior to starting the clock; unlike in human solves where they are given time to study the cube before the clock starts.

That's a fair point, and it would make sense to allow the same for the robot. That could mean that you can allow for preprogramming the layout before. Or you could put two cameras on the robot to take pictures of 5 of the sides. I believe you can infer the last side based on knowledge of the others.

In any case, given the fact that the human record for solving a cube is about 4.5 seconds, building a robot that can beat that would certainly be possible, but likely harder to do than the one from the article.

”I believe you can infer the last side based on knowledge of the others.”

Can you? If you flip all four edge pieces on the bottom face the bottom color shows up at all four side faces, and you wouldn’t be able to determine whether those four edge pieces got permuted, too.

Thinking a bit more about it, this problem already pops up if the bottom face has either:

- three edge pieces that share a color, with that color showing on the side.

- two pairs of edge pieces that share a color, with the twice shared colors showing on the side.

The first isn’t uncommon; if you pick three edges at random, the probability that they share a color is 1 * 6/11 * 2/10 = 6/55, and there are four ways to pick three edges from the bottom face, for (I think) a total probability of 24/55 - 4 * 6/55 * 1/9 (the probability that all four share the same color), or a probability of over 1/3 (if that seems high, consider the following: because of the pigeonhole principle, between the edges of any face of the cube there always is at least a pair sharing a color). That means that, even ignoring the second possibility, there’s at least a 1:24 probability of seeing this problem on a random cube.

Not all cube configurations are achievable by cube moves. That is, if you pull off one corner of a cube, rotate it, and stick it on again you get a cube which cannot be solved (except by disassembling it again).

I think it actually is possible to infer the sixth side of a cube if you can see the other 5, because only only one configuration of the remaining side is actually acheivable.

Good point. I stand corrected.

In retrospect, it was obvious enough that I should have thought of it.

If you know the centre piece colours of five sides you know the remaining centre, the one you can’t see, must be the remaining colour.

Quite. But we're talking about the permutation of the edge pieces on that face. You wouldn't be able to infer where they needed to be moved to if they were all just showing the bottom face colour.

Oh, I see. Yes, that's obviously what your comment was saying. Thank you for clearing that up.

They say the machine spend about 50ms adquiring images and solving, and 335ms moving the cube.

> The cameras had trouble distinguishing red and orange faces, so they painted the orange faces black to make them stand out better.

This is awesome. I love that this is what they did to solve this problem, versus something overly technical, like tuning the cameras or post-processing the images.

As a former competitive speedcuber, I basically had to do something similar but I went with a fluorescent orange (and fluorescent green to distinguish from blue) rather than black. At a slow speed it isn't much of an issue but when speedsolving, blue-green and red-orange take just a bit too long to distinguish even for my human eyes.

Or, they cheated

They also overtightened it

Eh, even the official rules for people AFACT[0] only require that the colors be distinct; special exceptions are also afforded for people with visual disabilities.

[0] https://www.worldcubeassociation.org/regulations/#article-3-...

It’s not really a disability when you can’t detect a difference between 2 colours in tenths to hundredths of a second.

Dude, it's a robot. And the very fact that they were able to do this, regardless, is amazing.

Cheating implies they were deliberately misleading about what they did.

They also explain why they overtightened it.

Url changed from https://arstechnica.com/gadgets/2018/03/homemade-robot-smash... ("Robot smashes Rubik’s Cube record with 0.38-second solve"), which points to this.

The blog post for the software side is at http://blog.cactus.zone/2018/03/rubiks-solver-software.html.

We noticed that all of the fast Rubik's Cube solvers were using stepper motors and thought that we could do better if we used better motors

It looks like they're using brushed DC motors, which reminds me of what happened with inkjet printers --- they originally used stepper motors for both axes, but then switched to a DC motor + encoder because it was both cheaper and faster while being just as accurate.

I did not know the playstation eye camera was a cheap way to do 120 fps capture. Good to know!

Really cool! It looks like they have some overshoot on their servos. I think adding some damping to their control loop to get closer to critical damping would shave a few percent off their time.

You’re assuming they’re using a linear controller, and they’re way ahead of you [1].

But I don’t think they’re overshooting per se. I think they’re landing the centers in the right place, but the outer pieces account for most of the moment of inertia, and they’re flexible, so the overall assembly is deforming. Deriving the optimal control law for that could be a bit messy. I would guess that it involves bringing the center piece nearly to a stop slightly short of 90 degrees and then gently bringing it the rest of the way.

[1] https://build-its-inprogress.blogspot.com/2017/12/controls-r...

I wonder if slightly overshooting on purpose, then running the motor in reverse for a moment would actually be faster.

They talked about how "mistakes" in the tuning often resulted in exploding cubes. I have a feeling they probably tried that or something like it but it just puts too much stress on the cube.

>> It looks like they have some overshoot on their servos.

Even in simple linear systems with a PID, a bit of overshoot may improve the response time. It's not always desirable but in this case there is no problem with it. I also liked the other commenters idea that perhaps the parts of the cube are moving further than the centers and then falling back in place.

With the right cube, like the one they’ve used, one with fairly large-radius corners on the centre piece and inside corners of the other pieces, you can / should be able to start turning the next face before the current face as come to rest.

Though I suspect the thing might fly apart if timed wrong. That’d be worth watching.

There is indeed a video on YouTube of the cube being turned into pieces. I think it was linked in the Ars Technica article.

Oh, indeed there is. I didn't scroll much past the first video.

Has the Rubik's cube been "solved" in the sense that from any state we can determine the fastest solution, guaranteed?

I'm aware of human friendly algorithms that aren't always optimal.

Yup, the search space has been completely explored. You can read more about the effort to do so here: http://www.cube20.org

This MIT open courseware lecture explains more about the optimum move sequence to solve a Rubik's cube. Some people call this perfect sequence of moves the "God path." https://youtu.be/s-CYnVz-uh4?t=25s

Yes. We know the greatest lower bound distance to any solution (20 turns) and we can always find the minimum length solution.

Edit: maximum -> GLB

Rather than "maximum", don't you mean the largest minimum is 20 turns? I'm pretty sure I can do 21 turns and not solve it.

Yea, it's the maximum over the minimal solutions for each configuration.

Yes, edited, meant greatest lower bound.

The instructions took 45 ms, and the execution took about 330 ms. If the machine goes faster, there's an increasing problem with tuning so the cube doesn't break. I think it may be better to design custom cubes for machine with similar material and dimensions. Toy manufacturers only factor in human solvers, such as: speed, corner cutting, locking, corner twists & popping.

Taking that to the ultimate conclusion: the cube should be encoded in the L1 cache.

Could we make it small enough to fit it in the registers?

Absolutely, even with some waste. Naively, each sticker can have one of six colors, which needs 3 bits, but let's make it 4 for easier handling. There are 9x6=54 stickers, so we'd use 54*4=216 bits. Easily fits into four 64-bit registers.

The article says it includes image capture and computation time. How does image capture identify the color of the tiles at the center of the faces, hidden behind the motor's arms? Or is the cube initial orientation known?

The way a Rubix cube works, the center tiles never move.

Why is that relevant to the question?

All it means is that you only have to look at them once, at the beginning of the solve.

But since computers have memory, that’s true for all the tiles.

It's not per solve, it's "per cube".

That is, the top center is always the same color, for every solve.

Presumably after you mix up the cube, you can put it in the machine in any orientation, can’t you?

I still can't even visualize how the sides spin and rotate on that axis.

x2 speed on the youtbe video is dope. https://www.youtube.com/watch?v=nt00QzKuNVY

> With a a typical Rubik's Cube solution taking 19 to 23 turns

Hmm, so it's not finding the perfect solution but instead one close to perfect. I'm curious as to time tradeoff of trying to find a solution that does one spin better, but takes longer to compute.

No, I think this is reflecting the fact that the optimal solution for some initial states is shorter than for others, though I could be mistaken.

God's number is 20: http://www.cube20.org/

From potentially incorrect memory, one can find the actual optimal solution pretty quickly, but that needs a giant lookup table that functions like an end-game table. Their lab might not have a machine with enough memory. Keep in mind that it would be a net loss if the solver took even 15ms longer.

Or 26 in the quarter turn metric http://www.cube20.org/qtm/ which is probably what matters for a robot, since 180 degree turns take longer than 90 degree turns?

Variable disorderliness.

I'd be interest to know if the previous move affects the speed of the next.

It might be possible the longer solutions are mechanically quicker.

Getting a better cube would solve the explosion problem and make it turn faster, i suppose. Magnetic cubes are out there, reducing lockups and explosions with better corner cutting ability. I'm interested to see how it would go with a good cube.

Reply on news.ycombinator.com