Development of a megaminx solver

[ichcubegerne]

Hello,
as some of you might have already heard somewhere, I am currently developing a megaminx solver as a project at university. Since my solver has now finally come to a point of producing valuable results, I thought, I would start documenting a bit of what is going on in this thread.

Current state: The solver utilizes basic blockbuilding to solve up to Last 2 Faces within an upper bound of 89 moves. For this purpose I generated lookuptables for a fixed order of blocks, so it can solve each substep optimally. It currently generates random states to solve for testing purposes.

I will now generate an EO table, aswell as a 2 sided search for a 2gen finish. That means that I will generate a lookuptable for a depth of 13 and then check if a given state is in that table and if its not, it will generate moves from that state to eventually connect to the lookuptable. Hence the second step has to be generated for each solve respectively. Since gods number for 2gen on megaminx is believed to be 26, this will generate up to 67 milion states on both sides. Since worst cases are really rare, it will be a lot faster to solve actual states with tho. (I will implement some kind of exception that can catch if the search goes beyond 13, cause then the 26 has been disproven. However even if a 27 mover exists, it seems unlikely that one is generated by chance).

At that point (Probably achieved tomorrow, since I like procrastinating learning for my exam), I have a functioning solver, I might prove an upper bound by splitting the 2gen phase into 2 substeps, just so there is an actual proven upper bound, but such a bound would be pretty bad anyway, so it seems hardly worth it. Either way, that would conclude the project. I will post the statistics on the substeps here, when thats all done.

HOWEVER I only consider this a starting point for future development. As you might have already realized, solving EO is basically a total waste of moves and we dont even have a (good) upper bound on gods number, since the 26 is not proven yet, just to name a few examples. There is A LOT left to do and I currently hope that my Professor considers this a worthy topic for a masters thesis. Either way, I will continue developing this, but if it becomes my thesis topic, development will be a lot faster.

Lastly I wanna give a huge thanks to Mallard-Creator Jonas Balsfulland for helping me out a lot with implementation advice.
Since I havent programmed in years, this was very much appreciated and helped accelerate the early development a lot.

-Alexander Botz

 

[abunickabhi]

Hello,
as some of you might have already heard somewhere, I am currently developing a megaminx solver as a project at university. Since my solver has now finally come to a point of producing valuable results, I thought, I would start documenting a bit of what is going on in this thread.

Current state: The solver utilizes basic blockbuilding to solve up to Last 2 Faces within an upper bound of 89 moves. For this purpose I generated lookuptables for a fixed order of blocks, so it can solve each substep optimally. It currently generates random states to solve for testing purposes.

I will now generate an EO table, aswell as a 2 sided search for a 2gen finish. That means that I will generate a lookuptable for a depth of 13 and then check if a given state is in that table and if its not, it will generate moves from that state to eventually connect to the lookuptable. Hence the second step has to be generated for each solve respectively. Since gods number for 2gen on megaminx is believed to be 26, this will generate up to 67 milion states on both sides. Since worst cases are really rare, it will be a lot faster to solve actual states with tho. (I will implement some kind of exception that can catch if the search goes beyond 13, cause then the 26 has been disproven. However even if a 27 mover exists, it seems unlikely that one is generated by chance).

At that point (Probably achieved tomorrow, since I like procrastinating learning for my exam), I have a functioning solver, I might prove an upper bound by splitting the 2gen phase into 2 substeps, just so there is an actual proven upper bound, but such a bound would be pretty bad anyway, so it seems hardly worth it. Either way, that would conclude the project. I will post the statistics on the substeps here, when thats all done.

HOWEVER I only consider this a starting point for future development. As you might have already realized, solving EO is basically a total waste of moves and we dont even have a (good) upper bound on gods number, since the 26 is not proven yet, just to name a few examples. There is A LOT left to do and I currently hope that my Professor considers this a worthy topic for a masters thesis. Either way, I will continue developing this, but if it becomes my thesis topic, development will be a lot faster.

Lastly I wanna give a huge thanks to Mallard-Creator Jonas Balsfulland for helping me out a lot with implementation advice.
Since I havent programmed in years, this was very much appreciated and helped accelerate the early development a lot.

-Alexander Botz

This is a great project to attempt Alex!

I am excited to follow more developments, keep us updated on this thread.

I understand there is still a lot of work to be done. What programming languages and frameworks are you using?

What is your roadmap before you have a v0 mega solver ready?

 

[ichcubegerne]

This is a great project to attempt Alex!

I am excited to follow more developments, keep us updated on this thread.

I understand there is still a lot of work to be done. What programming languages and frameworks are you using?

What is your roadmap before you have a v0 mega solver ready?

Thanks!

I am using the language "Go", as I was recommended by Jonas. I was mostly searching for an easy language cause of my rather weak programming background. My code is probably nightmareish to an experienced coder, but its a start and works

It is currently missing the solving capabilites of Last 2 faces. Pretty much what the third paragraph says is the roadmap to v0. However before I make any code public, I would like to clean up the code and add some quality of life improvements. This will most likely take until the project is finished in late october. I tested it on a random move scramble with an actual megaminx and it worked so far. I suspect to finish v0 tomorrow, probably. Its not a lot left, so that should be done really quickly. I will post an update along with the solving statistics when thats done!

 

[abunickabhi]

Thanks!

I am using the language "Go", as I was recommended by Jonas. I was mostly searching for an easy language cause of my rather weak programming background. My code is probably nightmareish to an experienced coder, but its a start and works

It is currently missing the solving capabilites of Last 2 faces. Pretty much what the third paragraph says is the roadmap to v0. However before I make any code public, I would like to clean up the code and add some quality of life improvements. This will most likely take until the project is finished in late october. I tested it on a random move scramble with an actual megaminx and it worked so far. I suspect to finish v0 tomorrow, probably. Its not a lot left, so that should be done really quickly. I will post an update along with the solving statistics when thats done!

Go is nice language. I have never tried it. I am guessing it should be easy to pick up since I am proficient with C.

Are you keeping your codes in git? Or hosting them on GitHub by October or November?

Do you wish to contact non-cubers who are good programmers to brainstorm ideas to make the algorithm for the remaining parts?

Also for megaminx, we only have an upper bound of God's number right?

 

[ichcubegerne]

Go is nice language. I have never tried it. I am guessing it should be easy to pick up since I am proficient with C.

Are you keeping your codes in git? Or hosting them on GitHub by October or November?

Do you wish to contact non-cubers who are good programmers to brainstorm ideas to make the algorithm for the remaining parts?

Also for megaminx, we only have an upper bound of God's number right?

If you know C, its gonne be a walk in the park. I feel like it was ultra easy to pick up.

Nothing is really kept anywhere yet. I just have a single file with all of the code.

I want to keep this a purely personal project at least until its involvement with my studies has gone past. I want to contribute as much as possible myself, before making this a community effort, since thats whats best for my studies currently. Also I have a pretty long todo list for this project so I dont need any new ideas for a while. When I actually need help, I will ask for it But for the time beeing, I will be a bit careful with what I publish.

For megaminx the only upper bound that I have found is from an age old post that mentioned a robotic solver at around 190. This has already been turned to dust by my solver, even with a primitive finish.

 

[abunickabhi]

If you know C, its gonne be a walk in the park. I feel like it was ultra easy to pick up.

Nothing is really kept anywhere yet. I just have a single file with all of the code.

I want to keep this a purely personal project at least until its involvement with my studies has gone past. I want to contribute as much as possible myself, before making this a community effort, since thats whats best for my studies currently. Also I have a pretty long todo list for this project so I dont need any new ideas for a while. When I actually need help, I will ask for it But for the time beeing, I will be a bit careful with what I publish.

For megaminx the only upper bound that I have found is from an age old post that mentioned a robotic solver at around 190. This has already been turned to dust by my solver, even with a primitive finish.

What is the new upper bound for megaminx?

Do people publish these upper bounds in a research journal?

 

[Billabob]

The Wiki gives a lower bound of 48: https://www.speedsolving.com/threads/lower-bound-for-megaminx-in-htm-and-qtm.35724/#post-1190421
And an upper bound of 194: http://forum.cubeman.org/?q=node/view/328#comment-2657
Unsure if this is up to date. 194 does seem weak. Very much looking forward to an update from you, good luck with the project and congrats with the progress so far. Have you considered trying alternate solutions for the final blockbuilding step to influence EO? Avoiding bad cases could save moves.

 

[ichcubegerne]

The Wiki gives a lower bound of 48: https://www.speedsolving.com/threads/lower-bound-for-megaminx-in-htm-and-qtm.35724/#post-1190421
And an upper bound of 194: http://forum.cubeman.org/?q=node/view/328#comment-2657
Unsure if this is up to date. 194 does seem weak. Very much looking forward to an update from you, good luck with the project and congrats with the progress so far. Have you considered trying alternate solutions for the final blockbuilding step to influence EO? Avoiding bad cases could save moves.

Integrating EO into the previous step is the first thing on my todo list after v0 has been finished. It is very well possible, that that would completely remove the EO step without any additional moves on the upper bound.

I think that upper bound is up to date, it was generally not easy to find anything on the topic.

 

[ichcubegerne]

Solver works now (at least as far as my testing went), to give some insight into the current statistics:

It seems to average around 95 moves currently, tested on a couple 100 random states.

Upper bounds for substeps: (D layer starts with a 2x2x2 Block, rest are pretty straightforward attachments)
DLayerBlock1: 10
DLayerBlock2: 9
DLayerBlock3: 9
DLayerBlock4 (Full D F2L): 14
ULayerBlock1: 8
ULayerBlock2: 13
ULayerBlock3: 13
ULayerBlock4: 13
EO: 13 (yes yes I know,its just a placeholder)
2Gen: conjectured 26

This yields 128 as a conjectured upper bound, waiting for the 2gen bound to be proven. EO can most likely be swallowed by the previous block pretty much completely, so getting it to 120 or less should be very easy. However the project ends with this v0. I will update this thread after my presentation in late october/early november to let you know if I will continue development for my masters thesis or turn it into a community project if that is not possible. Until then, I wont publish my code or the tables.

Feel free to ask any questions that you have.

Since my todolist on this project is pretty long already, please abstain from giving any improvement ideas. Its likely that they are on my list already. When I have worked through my own ideas and I feel like I need more, I will let you all know

 

[Ben Whitmore]

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.

 

[ichcubegerne]

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.

My project is more directed into constructing a well peforming solver, especially one that runs on average hardware. The gods number I found was just a side result, but it is obviously not a good bound. Your 6 phase computation would surely decimate anything that I can do.

If you ever feel the motivation to go through that effort, then I wish you good luck. It will sadly be the point where my direct contributions to the bound of gods number will end, but the results are gonna be interesting. Maybe I can come up with some other ideas of phases to test tho, so I might stay involved with that aswell.

For the sake of my project, the results of your last 2 steps would be really helpful tho. While I am currently planning to do the fifth one myself with some tweaks on my code, I basically still need the proof for 2gen gods number beeing 26, in order for my conjectured bound to be proven. This is definitely out of reach for my hardware, at least in reasonable computation time. So if you are are ever feeling motivated to start somewhere, I would be very happy if you would do that first (I would also be happy, if you let me do the 5th one myself)

I will however not be able to continue working on this project until after my exam in a month, so implementing the fifth step will have to wait, sadly. (I would rather do this, than my exam)

 

[ichcubegerne]

Its current Ao1000 PB is 94,99 moves (I am going to make some small improvements soon, maybe get it down to sub 90)

 

[ichcubegerne]

Big Update: (V1.0)
The "small improvements" that I wanted to make got a little bit out of hand, as per usual with passion projects.

Replacing maps with Arrays:
The hashmaps that I previously used to store the lookuptables have been replaced by arrays. For that I improved the hash-functions from a bitwise storage to an actual one to one enumeration of all states. This has drastically decreased the storage space needed for the tables, aswell as the RAM needed for computing solutions and also drastically increased the decoding speed.

EO has been integrated into the previous block:
The EO step no longer exists, and is instead solved along with the previous Block. The 13+13=26 moves that those steps required have hence been reduced to 17 (I didnt expect 4 extra moves to be needed for this step at all) and the upper bound for gods number has been reduced to 119. Reworking my code to support generation of such big tables (2189721600 states), even with the switch to arrays, and the resulting amount of bugfixing was definitely the majority of the work. I wont go into detail with that here.

Other Optimizations:
The last 2 steps have their own internal structure now. Since the majority of the megaminx is solved at that point it is just generally beneficial to use much smaller structures to solve those steps, instead of the whole megaminx. This was one of the relevant parts to enable the elimination of EO, but has also substantially decreased the computational effort for the 2gen phase, because a lookuptable has to be generated to connect to the pregenerated lookuptable each time.

I just did an Ao1000 for testing and the result was 89.56 moves. The previous one was actually counted as one move worse than it actually was, I have fixed that. For now I want to give each step their own structure, to improve the generating speed of tables. This should be a lot easier than what I had to do previously, because those substructures differ from the supstructures that were passed onto them (It will also clean up the code, it looks catastrophic). I will basically spend some time improving what I already have until my presentation and probably start with solution trees and pruning afterwards.

 

[ichcubegerne]

The blockorder has now been changed such that unergonomic moves are getting removed earlier (Thanks @Cuberstache for reminding me that this is a good idea ). The reduction is now:
<R,U,F,L,BR,BL,FDR,FDL,DR,DL,DB,D>
<R,U,F,L,BR,BL,FDR,FDL,DR>
<R,U,F,L,BR,BL,FDR,FDL>
<R,U,F,L,BR,BL,FDR>
<R,U,F,L,BR,BL>
<R,U,F,L,BR>
<R,U,F,L>
<R,U,F>
<R,U>

I think when I have implemented solution trees with pruning, this could be a very viable alternative to Pochmann scrambles. It already globals sub 90 and it should easily go down to 75-70 global with that. It would take some getting used to the D Layer moves, but keep in mind that there is only few of them in an actual solution.

 

[Ben Whitmore]

I have now verified that the 2gen step can always be solved in 26 moves: https://www.speedsolving.com/threads/gods-algorithm-for-megaminx-u-r.93480/#post-1624670

 

[rokicki]

How many moves does this take to solve megaminx superflip?

 

[Christopher Mowla]

How many moves does this take to solve megaminx superflip?

I know your secret! Megaminx - Flips and Twists - Pure Superflip

(For those who didn't know of Tom's work in this area, here's the bottom-most algorithm listed on that page animated at alpha.twizzle!)

 

[rokicki]

I know your secret! Megaminx - Flips and Twists - Pure Superflip

(For those who didn't know of Tom's work in this area, here's the bottom-most algorithm listed on that page animated at alpha.twizzle!)

A couple of us have been pushing on megaminx superflip for a while. But I'm truly excited about this new megaminx solver, and curious about how it does for this particular position. I don't expect it to be competitive with the solutions on the web page you reference (which took many many days of CPU) but it's an interesting benchmark nonetheless.

 

[ichcubegerne]

I apparently forgot to activate notifications for this thread, so sorry for responding so late.

I have now verified that the 2gen step can always be solved in 26 moves: https://www.speedsolving.com/threads/gods-algorithm-for-megaminx-u-r.93480/#post-1624670

Thanks a lot again! This was the final piece that was still needed for the bound on gods number.

How many moves does this take to solve megaminx superflip?

76 moves, a lot better than I would have expected: Twizzle view
(Also I now know that the mechanism I have for counting moves in my solver doesnt work, because it told me the solution is 77 moves)
Interestingly it seems to be pretty lucky with the block order in the beginning. The second and third block are really short, which would have not been the case if I went for a different block order.

I only recently learned about the existence of twizzle, I will adjust the notation I am using to twizzles notation for the sake of consistency (and frankly because twizzles notation is just better) when I get around to it. Lucas wanted to set up a meeting with me to discuss the implementation a bit aswell.

 

[ichcubegerne]

Hello again,
I finally return from procrastination and Calc1 tutoring to continue this project, which has now turned into my thesis topic. In the next couple of weeks I will be working on several things with the help of my universities HPC:

-Verifying the 2gen table that was been generated by Ben.
-Generating a table that combines phases 1 and 2
-Swapping phases 4 and 5 in order to merge phases 3 and 5 (ergonomically it seemed to not really make a difference). I am unsure what impact this will have as I previously tested swapping those phases and it yielding worse results, but since I can merge steps, it might help, I am mostly judging phases on their depth distribution table and the resulting average and max depth, we will see what I get.
-I have ordered a 12TB hard drive, so I can use the resulting tables directly in the future. This will get rid of the annoyances I had with the 2gen step and make future work a lot easier.

This will also require a lot of changes to how the solver currently works, so I am excited to learn some new things about coding aswell
There is more on my todo list for later stages of my thesis, but this whats going to happen right now, I will keep you posted!