New deep learning technique solves Rubik's Cube without assistance | Hacker News Reader

New deep learning technique solves Rubik's Cube without assistance

technologyreview.com

111 pointsrbanffy23 comments

Inaccurate article on one point - they say that in 2014 it was proved the smallest number of moves to solve is 26... but in 2010 it was proven to be 20 moves actually. [1]. (And the article they linked to was from 2008 anyway and said that 25 moves was the max needed as of 2008 best knowledge)

They probably were referring to the "quarter turn metric" which is 26 quarter-turn moves, but "moves" in speedcubing almost always refers to face turns. And this is made more confusing by the article since the article they linked to was regarding face turns as well.

Both of course are mentioned at cube20.org [2]...

[1] https://www.bbc.com/news/technology-10929159

[2] http://www.cube20.org/

I suppose the answer might be in the actual article, but

> In chess, by contrast, there is a relatively large search space but each move can be evaluated and rewarded accordingly. That just isn’t the case for the Rubik’s Cube.

I don't follow this at all -- how do you reward an individual chess move other than by using a reward system that may or may not be anywhere near fully accurate like counting material? Seems pretty similar to solving a Rubik's cube.

I think the idea is that chess positions are an absolutely sorted state where you have a large space, but can give a full ordering to the positions.

That said, I think I agree with you. The Rubik's cube is amusing because it literally is just permuting numbers. You can build a transversal set where you quite literally just pick the permutations in order to get back to sorted. I haven't gone through the effort of building up the transversal set, yet, but http://taeric.github.io/cube-permutations-1.html was where I started playing with the idea.

I mean, yes, you can get more complicated. And no, I have not gone through the effort yet to see how much time the set takes to build up. Pretty sure it won't take long, though.

Most chess solvers definitely use material count and similar "simplistic" heuristics. I don't know of any similar heuristics for a rubik's cube.

https://en.wikipedia.org/wiki/Computer_chess#Leaf_evaluation

>how do you reward an individual chess move other than by using a reward system that may or may not be anywhere near fully accurate like counting material?

If you just count material and look 30 moves ahead you will not get outvalued by a human. The reward system does not need to be perfect to be useful, but there does need to be one.

I know it's too much to ask, and this accomplishment is impressive, but when I read the headline I thought that solving Rubik's Cube 'without assistance' might mean building a mechanical apparatus to solve the cube.

Those do exist, though, and could probably be connected to such an algorithm as this one.

Interesting how the solver preferred to build a 2x2x2 block and then match/solve pairs until it could then apply ABA' sequences (commutators in cubing parlance). Very reminiscent of something between Lars Petrus' and Ryan Heise's method. There's a more rigid version called Tripod.

As an avid speedcuber I'd be very interested in the datasets.

https://arxiv.org/pdf/1805.07470.pdf

Results are compared with known optimal algorithms for the Rubik's cube: Kociemba's algorithm, Korf's algorithm.

https://en.wikipedia.org/wiki/Optimal_solutions_for_Rubik%27...

please, link to arxiv abstracts, not directly to the pdf.

The PDF has an abstract as well…were you looking for something in particular?

As noted in other comments: viewing PDFs on a phone can be a hastle, and PDFs take a lot more data & time (on slower/mobile connections) to load.

I logged in on a desktop just to respond to this comment in particular, even though I almost always use my phone, if that helps put this in perspective.

Why request this? Is there some common wisdom here I’m missing? You should probably include the reason or else this just seems like a weirdly petty request

The HTML page takes an order of magnitude less time to load than the PDF (1 vs. 8 seconds) on my phone.

PDFs are hard to read on phone. The abstract page is better if you just want to read abstract. Some PDFs can also contain large images, which is again bad for mobile if you only really wanted to read abstract.

We need AMP/PWA for PDFs!

We sort of do for arxiv: https://www.arxiv-vanity.com/

Also from the main Arxiv page, you can click on the links to each of the authors, see the version history, etc

I am a fan of this Chrome extension that fixes these links: https://chrome.google.com/webstore/detail/redirectify/mhjmbf...

Ugh, I'm tired of every new ML idea being described as a "deep learning technique". Yeah they use neural networks but the idea is not NN specific.

Other than that, awesome paper.

Dupe. I assumed HN checks if an article with the same link was already submitted ?

This exact same article / link was already posted a day ago: https://news.ycombinator.com/item?id=17320218

Plus another link, plus the original research link.

I was also under that impression, and that dupes tended to include GET params or were a mobile URL or something, but these two are actually the exact same URL.

It only checks for a short time in the past, since duplicate submissions are explicitly allowed when the previous submission didn't have a discussion/many upvotes.

Reply on news.ycombinator.com