Automating method-space search

[shadowslice e]

So nowadays it's generally accepted that on 3x3, most "human developable" methods have been found and either are used or have been tossed out. So as an experiment, I made a genetic algorithm in python which works using a modified version of ksolve++ which generates methods for 2x2.

Consider this mostly a proof of concept because 2x2 is easy. I would be interested in any feedback or suggestions on how this could be applied to bigger cubes (since computing time becomes an issue)

Spoiler: Videos

 

[ImmolatedMarmoset]

This is really fascinating! I’d really love to play around with the code; I’ve just started to get into python and this seems like a fun project, if complicated. Would you consider releasing the python code?

Kudos by the way, this is really amazing.

 

[shadowslice e]

This is really fascinating! I’d really love to play around with the code; I’ve just started to get into python and this seems like a fun project, if complicated. Would you consider releasing the python code?

I might though admittedly it's not really anything special and requires installing a lot of packages. I'll see if I can make a tutorial to get it working for other people but I can't guarantee anything.

 

[dudefaceguy]

This is really cool! I was just thinking about something similar for the 3x3, but not focused on creating actually efficient methods useful for speedsolving. Instead, I want random methods that are puzzling to solve. I was envisioning a simple decision tree, which would output a randomized series of steps that would result in a solved cube. The point would be to give the solver an interesting and perhaps funny problem to solve. For example, it might come up with something ridiculous like this:

Orient all corners on the R face
Solve edges in the E layer
Solve a 2x2x2 block anywhere on the cube
Solve all corners
Orient remaining edges
Solve remaining edges

Seems like this would be easy to make, and fun to try.

 

[shadowslice e]

This is really cool! I was just thinking about something similar for the 3x3, but not focused on creating actually efficient methods useful for speedsolving. Instead, I want random methods that are puzzling to solve. I was envisioning a simple decision tree, which would output a randomized series of steps that would result in a solved cube. The point would be to give the solver an interesting and perhaps funny problem to solve. For example, it might come up with something ridiculous like this:

Orient all corners on the R face
Solve edges in the E layer
Solve a 2x2x2 block anywhere on the cube
Solve all corners
Orient remaining edges
Solve remaining edges

Seems like this would be easy to make, and fun to try.

Eventually I might try to move this to 3x3 but the problem (and the main reason I didn't do it in this) is that 3x3 is much bigger than for 2x2 so it can't evaluate in any reasonable time

I will see if there's a way to do it somehow but I'm not optimistic tbh

 

[Christopher Mowla]

I'm surprised that there weren't more replies to this! Pretty cool, shadowslice e.

I really haven't looked into genetic algorithms, but do they by any chance involve repeating short algorithms?

The reason I ask is because I just thought to use the moves (L' R' D) as a base to make a 12-cycle, 11-cycle, 10-cycle, and 9-cycle algorithm for the purpose of solving (or at least correctly placing) the first four edges in my newly updated beginner's guide. (I started with L' R' D and observed that it was a 10-cycle. So I then tried to make the other higher cycles from it for the sake of consistency.)

Although not in my guide, I also found (L' R' D) (L2 R2 D) (L' R' D) to do an 8-cycle of corners which preserves the top four edges, (L' R' D) L (L R D') L' to do a 7-cycle of corners, (L' R' D) L (L' R' D) L D' R2 D2 for a 6-cycle, and (L' R' D) D' L D R D for a 5-cycle.

So, if one uses a repeated sequence to correctly orient pieces after they are solved (one by one) in this manner, it takes far less "intelligence".

(And speaking of my guide, you can also see that the last page is for PLL. It's strictly based on repetition. No cube rotations are used.)

This is why I am asking.

 

[aerocube]

this is really cool,perhaps one day the ai will spit out a method better then any current 2x2 method that people can consistently sub 1 on

 

[shadowslice e]

I'm surprised that there weren't more replies to this! Pretty cool, shadowslice e.

I really haven't looked into genetic algorithms, but do they by any chance involve repeating short algorithms?

The reason I ask is because I just thought to use the moves (L' R' D) as a base to make a 12-cycle, 11-cycle, 10-cycle, and 9-cycle algorithm for the purpose of solving (or at least correctly placing) the first four edges in my newly updated beginner's guide. (I started with L' R' D and observed that it was a 10-cycle. So I then tried to make the other higher cycles from it for the sake of consistency.)

Although not in my guide, I also found (L' R' D) (L2 R2 D) (L' R' D) to do an 8-cycle of corners which preserves the top four edges, (L' R' D) L (L R D') L' to do a 7-cycle of corners, (L' R' D) L (L' R' D) L D' R2 D2 for a 6-cycle, and (L' R' D) D' L D R D for a 5-cycle.

So, if one uses a repeated sequence to correctly orient pieces after they are solved (one by one) in this manner, it takes far less "intelligence".

(And speaking of my guide, you can also see that the last page is for PLL. It's strictly based on repetition. No cube rotations are used.)

This is why I am asking.

In this case, the genetic algorithm specifies which pieces to solve in what order. It essentially creates a "genome" which dictates that.

this is really cool,perhaps one day the ai will spit out a method better then any current 2x2 method that people can consistently sub 1 on

I would be very surprised if the ai does find anything better than human developed methods on 2x2 since it's a very small puzzle so the possibilities are somewhat limited. On the other hand, it is reasonably plausible that on bigger cubes it may find something interesting though there are a few issues in doing that just yet since the computing power required is a lot higher than I have access to and there needs to be some way to quantify more abstract concepts such as ergonomics and look ahead (the former of which I have some ideas on how to do but the latter I have no clue)