# How would a purpose-built "alg generator" program work?



## atmosopher (Jan 2, 2020)

Currently the state of the art is to input cube states for, say, a last layer case or an EOLine into Cube Explorer and have it solve the case (near-)optimally.

However, I wonder if there is room for improvement here. I've been thinking about building a program that can, say, accept a definition of "what a ZBLL case is" (or "what an EOLine is") and generate, say, 20 algs for each ZBLL case (respectively, each EO case) on its own. 

What I'm not sure about is if there is a better way to generate algs to "go from one incompletely specifird cube state to another" than simply applying the two-phase algorithm. 

What I mean by "incompletely specified" should be familiar as the "grey" stickers from a Cube Explorer search. For example, for EOLine we don't care about the starting or ending positions of the corners, or the permutation of non-DF/DB edges.

Any ideas/suggestions/advice/criticism of the idea itself would be appreciated.

---

My explorations so far have centered around building partial pruning tables for the subsets of the pieces that we want solved (say an "FR pair pruning table" if I wanted to generate last slot F2L pair algs, which only considers the orientation and permutation of the FR edge and the DFR corner, as well as the rest of F2L, but ignores last layer orientation and permutation) and applying a simple one-phase iterative-deepening DFS that stops when all the pieces we care about have the orientation and permutation we want, but I'm feel this might not be the best way to go.


----------



## Bruce MacKenzie (Jan 4, 2020)

As it happens I just spent the last two days modifying an optimal solver of mine to do partial solves. My pruning table keys on solving the down face. So any solution will always have the down face exactly solved. One can specify for each of the other 12 cubies whether they are to be solved exactly, only the orientation is to be solved, only the position is to be solved or to ignore it.

The IDA routine systematically searches the move tree looking for a turn sequence that solves the down face, lopping off tree branches using the pruning table. When a down face solution is found it is tested to see if the other 12 cubies match the search criteria. If it does not match the program searches ever deeper for down face solutions until it finds one which does match the search criteria for the upper cubies.

Here's an example where a randomly chosen up face permutation is solved for orientation

Parameters
goal: oo oo oo oo DF DR DB DL FR FL BR BL oo oo oo oo DRF DFL DLB DBR
metric: ftm

INPUT:
1 U R' U R2 B2 U R' B' R U' B2 R2 U' R

State 1
Target Depth: 1 2 3 4 5 6 7 8 9 10 11 12
B' R' U' R B R' L2 D F D' R L2
Time: 10.40 sec


----------



## atmosopher (Jan 4, 2020)

I've been writing something kind of like HARCS that's aimed at finding efficient solutions using human methods, so what I do is create partial pruning tables based on subsets of EO/EP/CO/CP (e.g. DF/DB permutation and the entirety of EO for an EOLine step) and perform IDA* with that, then go on to (continuing the ZZ example) an FB step whose goal condition and prune table involves the pieces of the first block, but which is also stipulated to have to preserve EOLine (and hence also gets to use the EOLine prune table), and so on. Much like in your example, the specifications of the method/steps/prune tables are accepted as input, and I aim to extend it with support for user-defined steps such as ZBLL.

I'm just wondering to what extent this naive approach can be improved; e.g. for EOLine I just realised that we can reduce by y2 symmetries.


----------

