Development of a megaminx solver

[Exmestify]

But thats where its starting to get really interesting!

i need to take an introductory group theory class to understand this :sob
but congrats!!

 

[qq280833822]

Although I don't know if anyone will actually use it, I tried integrating megaminx random-state scramble into cstimer.

 

[ichcubegerne]

Although I don't know if anyone will actually use it, I tried integrating megaminx random-state scramble into cstimer.

Which solver is it using? Also can I see the scrambles somewhere? (I cant see it on cstimer yet)

 

[qq280833822]

Which solver is it using? Also can I see the scrambles somewhere? (I cant see it on cstimer yet)

I implemented a similar method as your master's thesis myself. You can set the scramble type to "Megaminx->random state" in the beta version ( https://cstimer.net/new/ ).

 

[ichcubegerne]

I implemented a similar method as your master's thesis myself. You can set the scramble type to "Megaminx->random state" in the beta version ( https://cstimer.net/new/ ).

The solutions seems to average 100+, I wonder what you are doing different?

 

[qq280833822]

The solutions seems to average 100+, I wonder what you are doing different?

The current average solution length should be between 90 and 95.
In the use cases of cstimer, the computation time (including initialization) is only a few seconds, so the size of pruning tables and the number of candidate solutions at each stage is very small.

 

[academicmaslow]

Interestingly, there is a somewhat related project currently happening at MIPT (Moscow Institute of Physics and Technology). A team there is building a robot designed to solve a Megaminx as fast as possible, with the long-term goal of pushing toward a world-record-level solve.

Right now the work is focused on developing very fast solving algorithms specifically optimized for robotic execution.

I recently wrote a short overview of the project and the broader idea here:
https://medium.com/@academicmaslow/megaminx-the-puzzle-where-humans-still-beat-robots-d1f7aad692cb

 

[ichcubegerne]

Interestingly, there is a somewhat related project currently happening at MIPT (Moscow Institute of Physics and Technology). A team there is building a robot designed to solve a Megaminx as fast as possible, with the long-term goal of pushing toward a world-record-level solve.

Right now the work is focused on developing very fast solving algorithms specifically optimized for robotic execution.

I recently wrote a short overview of the project and the broader idea here:
https://medium.com/@academicmaslow/megaminx-the-puzzle-where-humans-still-beat-robots-d1f7aad692cb

Nice article, i am always happy about reading my name somewhere (in a positive context ofc). I have one question:
"Current algorithms guarantee solutions of no more than 116 moves. Using modern search techniques could reduce this to 90–120 moves on average.", I assume the 116 moves is taken from this discussion, which was a group effort of Ben and me, but has already been improved to 114 by Tom. What I dont understand is the second sentence, because the average movecount is already a lot lower and I am unsure how you would land above 116 in any case there.

 

[academicmaslow]

Nice article, i am always happy about reading my name somewhere (in a positive context ofc). I have one question:
"Current algorithms guarantee solutions of no more than 116 moves. Using modern search techniques could reduce this to 90–120 moves on average.", I assume the 116 moves is taken from this discussion, which was a group effort of Ben and me, but has already been improved to 114 by Tom. What I dont understand is the second sentence, because the average movecount is already a lot lower and I am unsure how you would land above 116 in any case there.

Thanks for taking a look! The numbers in that paragraph come from a discussion in the MIPT robot developers’ group. The figures from your research are actually listed separately in the section below. And thanks for pointing that out — I’ll update that part to reflect 114 moves and mention that the average is below 100.

 

[Alexander Chervov]

Dear Colleagues

Our CayleyPy project aims to develop machine learning assisted methods to solve puzzles, in particular Megaminx.

Everybody is very welcome to collaborate !

Currently we have some successes.
In particular here is benchmark challenge for Megaminx:

CayleyPy Megaminx Solve Optimally

Write your name in the history of science - solve the problem unsolved from 1982

www.kaggle.com

Here is around 1000 random scrambles. Leaderboard Score - sum of the solutions lengths for each sample.

Current Leaderboard
Vladislav Kuznetsov 81633
DrozdovDan 89670
Tomas Rokicki 93606

At the moment we are even above Tomas @rokicki

Any way would be happy to find any one interested - there are lots of questions - from AI to string theory - related.
@Ben Whitmore

 

[Alexander Chervov]

I think with the computational resources that I have, it would be possible to get an upper bound using a 6 phase method (but I wouldn't be able to use it in a solver):

1. 2x2x3 block (reduce to 8 faces) (1.871 trillion states)
2. Extend with two 2x2x1s to make a "triangle" (reduce to 6 faces) (13.377 billion states)
3. Extend with a 1x2x3 and 2x2x1 (reduce to 4 faces) (7.088 trillion states)
4. Reduce to 3 faces (32.380 billion states)
5. Reduce to 2 faces + EO (2.189 billion states)
6. 2gen (7.999 trillion states)

Computing the upper bound for steps 1 3 and 6 would take quite a long time (probably over a month in total) but it should in theory be possible on my machine. Also maybe there's a different 6 phase method that has more evenly distributed state sizes but I couldn't think of one. 5 phase isn't possible for me because it would require an average state size of almost 40 trillion which is bigger than what I can do.

Please take a look on the message above -- https://www.speedsolving.com/threads/development-of-a-megaminx-solver.93202/post-1693123
Would be happy to collaborate on these or other topics

 

[rokicki]

Dear Colleagues

Our CayleyPy project aims to develop machine learning assisted methods to solve puzzles, in particular Megaminx.

Everybody is very welcome to collaborate !

Currently we have some successes.
In particular here is benchmark challenge for Megaminx:

CayleyPy Megaminx Solve Optimally

Write your name in the history of science - solve the problem unsolved from 1982

www.kaggle.com

Here is around 1000 random scrambles. Leaderboard Score - sum of the solutions lengths for each sample.

Current Leaderboard
Vladislav Kuznetsov 81633
DrozdovDan 89670
Tomas Rokicki 93606

At the moment we are even above Tomas @rokicki

Any way would be happy to find any one interested - there a lots of questions - from AI to string theory - related.
@Ben Whitmore

I haven't given this much effort, and probably won't for a while, but that 81,633 is pretty impressive.

 

[ananasclassic]

Please take a look on the message above -- https://www.speedsolving.com/threads/development-of-a-megaminx-solver.93202/post-1693123
Would be happy to collaborate on these or other topics

hello everyone!

this is my first post in this thread.

I passed the 80,000 threshold at the cayley-py-megaminx competition a few hours ago.

 

[rokicki]

For those not following everything: note that the Cayley competition uses quarter-turn metric, not the more conventional face-turn metric, so getting to 80,000 (for something like one thousand positions!) is pretty impressive!

 

[xyzzy]

For those not following everything: note that the Cayley competition uses quarter-turn metric, not the more conventional face-turn metric, so getting to 80,000 (for something like one thousand positions!) is pretty impressive!

I was thinking that 80 moves wasn't very impressive, given that humans could achieve the same, but yeah, 80 moves in QTM is a lot more impressive.

 

[ananasclassic]

I just found 48-FTM superflip solution, which I believe is the shortest known so far.

I also found 50-FTM solution, that corresponds to only 54 moves in QTM.

 

[rokicki]

That's really phenomenal. The best I was able to do, with huge effort some years back, was 55 moves, so this is a huge improvement. Can you telll us a bit about your approach?

Also, what's the best pure solution you can come up with (that's one that preserves center twist; that is, it solves a "picture megaminx".)

 

[ananasclassic]

That's really phenomenal. The best I was able to do, with huge effort some years back, was 55 moves, so this is a huge improvement. Can you telll us a bit about your approach?

Of course

In short, I used the CayleyPy approach from this article.

For the 54-QTM solution, I used an improved model that predicts distances for all neighbors at once (I used it for a sub-80k submission to a kaggle competition) with a beam size of 2^27. The solution took about 15 hours on a server with an A100x1. After that, I simply glued together consecutive rotations of the same face (in one place, I swapped two commuting moves) and obtained a 50-FTM solution.

I found this result to be very good, considering that optimizing solutions in the QTM and FTM metrics are different tasks. However, I achieved almost the best known solution in one metric by optimizing the other.

Therefore, for the 48-FTM solution, I did not make any significant changes to the approach from the article. I trained a new model for about 6 hours and used beam search with a beam width of 2^23, which solved the scramble in 3 hours. The solution with a beam width of 2^25 is currently running for about 10 hours and may provide a shorter path.

 

[ananasclassic]

Also, what's the best pure solution you can come up with (that's one that preserves center twist; that is, it solves a "picture megaminx".)

I’ll definitely try to solve it.

Right now, I need to focus on preparing my bachelor’s thesis — it will actually be about the Megaminx — and for now I’ll be working on more down-to-earth experiments.

 

[acrystal]

Could you guys give me some intermediate tips on megaminx?