AlgExplorer: command-line utility to assist in alg searching

[Teoidus]

Description of program in title.

Essentially what the program I am working on is doing is

Spoiler: boring technical stuff, feel free to skip

pulling a bunch (~4000) of solves from cubesolv.es, collecting all the algorithms in a file, and then using the file to construct a 2nd order markov model of "algorithm-like" move sequences (not quite deep learning, but good enough for this task imo).

To evaluate algs based on how "algorithm-like" they are, I compute the sum of the log of the transition probabilities for each move in the alg (log-likelihood). Algs with high log-likelihood (close to 0) are interpreted as being "more speedsolve-worthy" than algs with low log-likelihood (far less than 0).

With this program I'm able to (in 1-2 seconds usually) take a list of ~1000 CE solutions, generate a list of ~20000 solutions which include all possible ways to rewrite things like L F L' into r U r' and other substitutions, give each of these solutions a score, and then output a clean list (sorted by score and categorized by movecount) with the algs most worth considering near the top.

The program is still in development, but I have been using it in its current form to help a friend generate ZZLLs. He will send me, usually, a list of CE 500-1000 algs and I will send back a ranked list; if a good algorithm for the case already exists on algdb.net, these algorithms are almost always top results in the sorted list, and if the algorithm on algdb.net is not good, we are often able to find a much better replacement alg in 1-2 minutes. These good algs are often in the middle of depth 17-18 CE solutions, so I can't imagine how long it would take to find them by mentally trying each alg up until then.

Here are some sample inputs and outputs (EDIT: as @TDM pointed out, these outputs are actually from when I was using a different mathematical method. It got the job done okay, but was an approximation and pretty sloppy mathematically. I'm presently too lazy to update these, but maybe I will tomorrow. damn math majors and their scrutiny):
https://puu.sh/w9Lz8/29b8e5f6dc.txt (in), https://pastebin.com/2CshfYRV (out)
https://puu.sh/w9MX2/aecf94a58b.txt (in), https://pastebin.com/xgZaeZtp (out)
https://puu.sh/waKF7/7b47f467d0.txt (in), https://pastebin.com/Vxy1FBns (out)
https://puu.sh/w9Bwp/42c2c4bcdd.txt (in), https://pastebin.com/mm7xm0St (out)

I have some fancier features planned as well (considering not only substitutions, but also removing pre/post auf, considering rotations before each alg, etc). It's written in Python, so you'd need that to run it, but if there's enough people wanting an .exe I will look into specifics of compiling .py's.

 

[Atunez]

I can agree, this was a better experience for myself and Teoidus, we tried genning some ZZLLs *which are the algs i gave as my input* and each of them took about 4 minutes to pick the best one, since it was all sorted out for us, HOWEVER, the alg that is said to be the best, is not always the case, it may be, and if not just look like 2 algs below and you should have what you need.

In the end, I r8 8/8

 

[Underwatercuber]

This is what I need in my life

 

[Arc]

Noice. Small suggestion, handle AUF so algs start with a y rotation (not counted in move count) and strip ending AUF entirely.

 

[mDiPalma]

i dont know what a python is but

cool and good

 

[FastCubeMaster]

Looks good! This is the type of stuff I hope to be doing in my future years.

 

[Liquorice]

It sounds very promising. But how exactly do I use this program? I downloaded python but I don't understand anything.

 

[Teoidus]

It has to be run from the command line. If you are on windows, this means opening command prompt (windows key + r, then type cmd + enter), setting current directory to the directory algexplorer.py is in, and then running the python script from there (details about what commands to use are in readme.txt). It is a bit involved... in the next version I'm planning to release a batch file that'll come with the script to help out windows users (will leave out mac users for a bit and i'm assuming anyone running any type of linux is rolling their eyes right now)

 

[Liquorice]

Thanks, that helped a lot. However, I get an error regarding line 43, "TypeError: can't multiply sequence by non-int of type "float"".
Specifically, this is what happens after writing
algexplorer.py yperm_ruf.txt trained.txt -s -p 5 -o output.txt

Processing yperm_ruf.txt - extracted 237 algorithms.
Performing substitutions Traceback <most recent call last>: File "|||||||||\algexplorer.py", line 43, in <module>
sys.stdout.write<"|"*<newfrac-frac>>
TypeError: can't multiply sequence by non-int of type 'float'

 

[Teoidus]

Ah, that means youv'e got python 3 and not python 2 (which is what I used to write this program). There are a couple fixes:

- install python 2 and uninstall python 3
- change the source code yourself (you will just have to replace (newfrac-frac) with int(newfrac-frac))
- install python 2, don't uninstall python 3, but put python 2 in front of python 3 in your PATH

 

[Liquorice]

Thank you very much! It works like a charm now. I think this will revolutionize speedcubing. Removing pre/post auf would also be a huge help. I don't even know how many times I've been discovering a suprisingly good alg just to see that I already found it in another move count set. And it takes forever to delete them manually.
Rotations would also be helpful, although you can still do this with little effort in CE and make one set for each angle.

 

[Teoidus]

FUN PROGRESS UPDATE (a peek at what v2.0 will contain):
After 6-7 hours of coding (I'm not actually very familiar with Python, using this project to learn it) and relearning how basic recursion works several times, I've managed to write a fully functional algorithm parser for AlgExplorer. In v1.0 I simply used strings to represent algorithms, and split(" ") to break them down into an array of moves for constructing the Markov model, makingsubstitutions, and other fancy manipulations.

The issue with this is that cubesolv.es occasionally has things like (U D') or F (R U R' U')2 F', and these don't play nicely with my primitive string-split (currently the Markov model the program uses contains entries for a move called "U')2", which of course doesn't make any sense). With the new parser, strings like these will be interpreted correctly.

Additionally, I'm choosing to switch internal representation of algorithms from strings to Algorithm objects which contain int arrays--this I hope will produce significant speed gains (for example, the Markov model will be a simple 2dimensional array instead of a "2-dimensional hash table", and evaluations for each algorithm can be cached in a member variable in each Algorithm object, making sorting much more efficient)

Below are some sample outputs of this parser. As you can see it doesn't get tripped up by weird stuff like R5 or RUR with no spaces in between, and expands parentheses properly (including that last one, F triple inverse double sexy F'...).

 

[xyzzy]

There are a couple fixes:

- install python 2 and uninstall python 3
- change the source code yourself (you will just have to replace (newfrac-frac) with int(newfrac-frac))
- install python 2, don't uninstall python 3, but put python 2 in front of python 3 in your PATH

Or, install Python 2 and invoke it explicitly as python2.

… Or, use the `round` built-in function. Which you'll have to call as `int(round(x))` in Python 2 (versus `round(x)` in Python 3), because Python 2 had some design """"quirks"""". Or use the integer division operator (two slashes instead of one), which works the same in both Python 2 and Python 3.

(please stop using Python 2, really)

 

[Teoidus]

Or, install Python 2 and invoke it explicitly as python2.

… Or, use the `round` built-in function. Which you'll have to call as `int(round(x))` in Python 2 (versus `round(x)` in Python 3), because Python 2 had some design """"quirks"""". Or use the integer division operator (two slashes instead of one), which works the same in both Python 2 and Python 3.

(please stop using Python 2, really)

Yup, have since put in the int divide and am working with python 3 now. Didn't realize there were such differences...

 

[Liquorice]

Suggestion: Add S to the input moves (and possibly other slice moves). Not sure if it's possible to add a value for this sort-of-rare move, but nevertheless I get this error, so I can't get the output file without computing algs with no slice moves.
line 16, in rewriteone
face = faces.index<moves[j][0]>
ValueError: 'S' is not in the list

 

[Teoidus]

AlgExplorer 2.0

Patchnotes:
- Added AlgExplorer.bat, a user-friendly batch file
- Added support for substitutions on algorithms with slice moves
- Added parsing of input algorithms that handles cancellations (R U R' U' U R2 -> R U R)
- Added flag -b: uses Chad Batten's evaluation scheme
- Added flags -tl <ltrims> and -tr <rtrims>: trims movestypes in ltrims and rtrims from left and right of algorithms, respectively
- Changed internal representation of algorithms and Markov model
-> Faster substitutions and ranking
-> Slower algorithm extraction and file output
- Fixed bug with progress bars (now display 10 |'s regardless of input size)
- Fixed bug with Python 3.x handling int division differently

 

[AlphaSheep]

Would you consider putting this on Github or similar?

 

[Teoidus]

Would you consider putting this on Github or similar?

What would be the advantage to doing so? I can definitely do that, just curious.

 

[Calode]

What would be the advantage to doing so? I can definitely do that, just curious.

Makes it easier to collaborate if anyone wants to contribute.

 

[Teoidus]

Alright, everything in it's current state is on Github: https://github.com/teoidus/AlgExplorer