Consider whether cubing.js could be made ready for solution method DAGs

[anicolao]

Steps to reproduce the issue

In issue https://github.com/cubing/cubing.js/issues/224 we started to discuss whether or not I should be implementing my method editor on top of onionhoney's code or on top of cubing.js and I committed to log a new issue about it.

This issue is meant to create a discussion about requirements and readiness/lack of readiness in cubing.js for such a feature with an eye towards potentially prioritizing and implementing the requirements.

Observed behaviour

Currently I am not sure how much if any of the functionality I need already exists or is planned for cubing.js.

Expected behaviour

The very beginnings of the method editor looks like this:

The basic idea is to let the user define a DAG in a style not that different from how you might explore a filesystem. At the root of the system are method names - "Fridrich", "Roux", and so on. Having selected a method, the first stage of the solution needs to be added, and then stages that can follow it, and so on.

In the pictured rather simple example, the "Fridrich" method is being defined as a linear sequence of stages which are cross, followed by f2l, oll, pll, and finally START (solved). When the user clicks on one of these stages, the mask editor appears below and allows the user to see what the stage consists of (or edit what the stage consists of if the stage required isn't already defined). The pictured cross shows that the user of the "Fridrich" method expects a cross to be built on the "D" face.

Solve reconstruction proceeds as follows: each stage will have a set of orientations in which it can be recognized, and an optional 'free face' which can be considered correct if any of its four positions matches the mask.

The first stage is normally the only one which will use orientations. The user might decide to define an x2y option for Roux solvers, an x2 option for Fridrich solvers, or a cn option depending on what their start is like. Let's suppose that in this Fridrich example, the user is willing to build either the white or yellow cross to begin with as Fridrich herself would do (she has stated that full CN seems incredible in reference to a current speedcuber). Then this cross mask is correct (the option to set the x2 orientation is not yet in the GUI, but pretend it is there).

Solve reconstruction proceeds by finding which cross the user made, and orienting the cube appropriately for the remainder of the solve (eg. with white as the D face instead of yellow, using the push_back operator requested in another bug to rewrite the balance of the solve). The playback of reconstruction will show the user building the white cross on the bottom face and then proceeding to f2l with masks appropriate to the stage. Here's a slightly different example of what this looks like in a roux solve at reconstruction time:

In this example, the solve has been rewritten to reflect the user's actual first block given x2y colour neutrality, and the mask on the cube is highlighting the blue/white cubies for the first block so that the user can more easily figure out the 7 move solution that is proposed rather than the 9 move solution they actually executed (and arguably it's really a 6 move solution as it includes a rotation right after inspection).

In a similar way, the Fridrich example would show the user better executions of the same cross that they picked.

Finally after all this explanation we're ready to talk some requirements:

• the software has to be able to recognize a mask that is in a single orientation in any of a number of provided orientations, and report back what the correct orientation is;
• the software has to be able to 'push back' a rotation through the solve to reorient it accordingly;
• the software has to be able to solve from scrambled to the end of the first stage (cross or fb in these examples, but an arbitrary mask in general)

That's sufficient for first block reconstruction. For later stages, the user can also define faces that don't get twisted (for example, the L face in Roux after fb is done) and the software will rewrite L moves as r x' and then use push_back to push an x up to the x' and cancel them so that the alg remains correct.

Between stages, the software needs to be able to find idiomatic solutions which is to say given a knowledge of which faces the user will turn to get from stage X to stage Y, produce a short solution using those face turns and not other options.

At that point, the system is able to do a decent solve reconstruction of any method a user is willing to build the DAG for.

As a more complicated example DAG, for a Roux solver you'd want possible start phases to be fb or fb_u, where fb_u is a first block with a mismatched center. After fb_u, the user could go to fb or to sb_u, and after that to sb. However in terms of features required of the underlying system, these cases fall out naturally from just two things: a solver/simplifier that can find better solutions than the user's own using the user's constrained moveset, and the ability to rewrite solutions by pushing back arbitrary moves through the alg string to retain its meaning while displaying the moves from a new angle.

Finally also on top of these same features, the method can be evaluated for average move requirements by applying the solver to some number of scrambles, say 100 or 1000 scrambles, and providing the example solves and statistics back to the user. This could enable the user to assess whether doing an odd maneuver like mismatched centers is actually worth it in terms of average efficiency, though it does not yet help them assess the alg count/extra recognition complexity that is implied.

Getting this far would be a good milestone, but there is more beyond.

For each stage, it would be desirable to create a generator of scrambles for that stage that can reach every possible state. Something that can produce generators suitable for the trangium batch solver would be ideal. Ideally this would happen without user intervention as producing these generators manually is difficult to understand and error prone. Once this is implemented, for any solution method the user defines the system can generate an alg sheet for each edge in the DAG for the user allowing them to actually learn and practice their method or realize that it is too large to be reasonable.

If that too is achieved, finally all methods in the system can be put in a leaderboard where they can be sorted by average move count, a move ergonomics metric meant to be predictive of potential speeds for solving, and a number of algs count. Such a leaderboard could enable more disciplined exploration of the space of human-oriented solution methods.

Environment

All platforms.

🖼 Screenshots

No response

Additional info

No response

[anicolao]

I forgot a thing I want to be able to build but I don't think it adds any new requirements: given this definition of a solution method, the system should be able to automatically generate:

• a beginner's tutorial, which knows the minimal set of algorithms that enable navigating a path through the solution dag even if not the optimal path;
• a set of trainers for algs the user will need to master to progress in the method, sorted by value (that is, algs for situations that occur more frequently during the 1000 evaluation solves should be learned/trained first to maximize the user's progression)
• a human-readable document form summary of the method (stages, alg sheets, etc) so that an experienced solver can start by reading a comprehensible overview of the method and its algs.

[lgarron]

Some main thoughts:

• This functionality is a very important goal for me personally.
• @rokicki and I would like to build on the search functionality on https://github.com/cubing/twsearch/, but this is blocked on finding a reliable way to produce a ready-to-use WASM build that can be vendored into cubing.js.

After that, a lot of our common goals become much more feasible. Do you have any interest in researching how to produce a sufficient WASM build?

[anicolao]

The problem is I'd be much more interested in producing an efficient solver for 3x3 than working with a more general and inevitably slower solver. The solver I am using right now is the one from onionhoney's code and it is just barely fast enough; I can do cube reconstructions including re-solving all 5 sub-phases in a little less than a second, so there is a noticable delay between completing your solve and seeing the reconstruction but most users will write it off to network latency.

Optimizing the solver so that it can accomplish the reconstruction goal in < 100ms seems more feasible with some variation of Kociemba's algorithm than with a general solver, but perhaps it is possible with either approach. (Or for that matter impossible; if the user's chosen solution method involves 5 stages as mine does, this does require running each solve in < 20ms though admittedly the expected solution lengths are short (on the order of 4-10 moves.)

At the moment, since the solver I am using is fast enough, I am more focused on actually producing the UI and corresponding method definitions and trainers and solve reconstructions. As you can see from the screenshots, solve reconstructions are "done" or at least good enough to be getting on with, so method definitions are next.

Is the UI even possible for the general case? Does every twisty puzzle have a convenient 2D projection for building the masks, and does twizzle already have a generic mask format and stickering for all the twisty puzzle types?

[rokicki]

Resolving subphases should be reasonably quick if twsearch makes it online. But yeah, work with what you have.

For the general case, yes, there is indeed a standard 2D projection for all the puzzles (really, just the five platonic solids).

-tom

On Sat, Oct 15, 2022 at 10:12 PM anicolao @.***> wrote:

The problem is I'd be much more interested in producing an efficient solver for 3x3 than working with a more general and inevitably slower solver. The solver I am using right now is the one from onionhoney's code and it is just barely fast enough; I can do cube reconstructions including re-solving all 5 sub-phases in a little less than a second, so there is a noticable delay between completing your solve and seeing the reconstruction but most users will write it off to network latency.

Optimizing the solver so that it can accomplish the reconstruction goal in < 100ms seems more feasible with some variation of Kociemba's algorithm than with a general solver, but perhaps it is possible with either approach. (Or for that matter impossible; if the user's chosen solution method involves 5 stages as mine does, this does require running each solve in < 20ms though admittedly the expected solution lengths are short (on the order of 4-10 moves.)

At the moment, since the solver I am using is fast enough, I am more focused on actually producing the UI and corresponding method definitions and trainers and solve reconstructions. As you can see from the screenshots, solve reconstructions are "done" or at least good enough to be getting on with, so method definitions are next.

Is the UI even possible for the general case? Does every twisty puzzle have a convenient 2D projection for building the masks, and does twizzle already have a generic mask format and stickering for all the twisty puzzle types?

— Reply to this email directly, view it on GitHub https://github.com/cubing/cubing.js/issues/233#issuecomment-1279893999, or unsubscribe https://github.com/notifications/unsubscribe-auth/AAMOLS5EO6V2AQR4FUCT2P3WDOFDRANCNFSM6AAAAAARGFMQBY . You are receiving this because you were mentioned.Message ID: @.***>

--

• https://cube20.org/ http://cube20.org/ - https://golly.sf.net/ http://golly.sf.net/ - https://experiments.cubing.net/ -

[anicolao]

In the end, I had to do a fair bit of rework on onionhoney's solver and I will probably write my own instead. Since what I currently have is based on onionhoney's code, continuing to modify it is the path of least resistance.

However, if you'd want a javascript solver of the style I am going to write in cubing.js, I would consider contributing it here instead. It's very simpleminded - virtually a brute-force search - but here it is:

1. There needs to be a data structure to represent 'masks', which have 1 in positions that are significant, and 0 or undefined elsewhere, that correspond to the full puzzle representation (that is, the full puzzle representation can't be missing a spot because of parity; every cubie needs to be represented). In cubing.js this looks like a good fit as a parallel to KState, a KStateMask type with an array for each orbit with the mask bits (which could also be represented as true/false if that's preferable).

2. A Pruner class needs to be implemented that can tell you the minimum distance to the goal state from a given state given a specific moveset. The way this gets implemented is that the goal state (usually START/solved) masked by the KStateMask is at distance 0, and distinct states that are reachable by one action from the moveset are at distance 1; then for each of those, newly reachable states are at distance 2, and so on. The Pruner gets given its tree size in levels and builds a table of states to distances. States beyond the maximum level are reported back as distance max+1 (remember this return value is merely a lower bound).

3. The Solver is given a target solution length and proceeds more or less by brute force and ignorance, applying each move in the moveset to the scrambled state, checking if the reached state + the number of moves so far exceeds the solution length desired. If so, that branch is pruned; else it is added to the frontier. The solver will exit after any of the following is true: (a) a time limit is exceeded; (b) a state exploration limit is exceeded; (c) the number of solutions asked for has been found; or (d) no further solutions can be found.

The efficiency of this solver is dominated by the number of moves in the moveset, followed by the ability of the pruner to hold a large number of states for pruning in its table, followed by the ability to recognize similar states. The Pruner will provide an interface to generate a key for a KState and the form of this key impacts its ability to hold a large pruning table as well as the ability of the solver to skip seen states. Initially this encode method can do something relatively simple like generate a string of the masked cubie state from the KState (after rotating so that centers are fully solved).

This approach is capable of generating algorithms of length about 11 in sub-second times after pruning tables are generated if the moveset isn't too large (e.g. all 3x3x3 puzzle moves available via 3 faces). Pruning tables of depth 5 take a few seconds to generate (once) and create fewer than 5 million nodes.

At the moment I am thinking of associating the movesets with the masks, but this is not really the right approach(tm). Really the masks correspond to nodes in a dag, and the movesets correspond to edges - so that if you are for example reaching a corners oriented state from an f2l state, that is different than reaching corners oriented from roux blocks. So really it should be (mask, mask) -> moveset and the solver should know the source and destination mask and have a way of looking up the moveset. It just turns out to be initially convenient to have (mask, moveset) pairs that you give to the solver.

The pruner could also be optimized to look at the moveset in order to determine of certain cubies are not relevant to the encoding process. E.g. when solving second block, L moves are usually outlawed, and so there is no need to focus on preserving the cubies in the first block and therefore no need to encode them. This could allow a much bigger pruning table. However in this case it turns out second block is solved between 2 and 10ms so there's hardly any value making it faster. There is probably value for OLL or PLL solves, say if you seek OLL or PLL algs that only involve R,U,F. CMLL is pretty slow, often requiring upwards of 10s to find a 10 move solution given a large moveset, so it might be worth it for cases like that.

[lgarron]

Thanks for the feedback!

Since my last comment on this thread, I've invested some time and we've gotten twsearch to the point that we can start putting it into cubing/search. I'll defer to @rokicki about whether a Pruner interface would work.

[anicolao]

Nice! Can twsearch do what I need - take a cube state from a source mask to a destination mask via a provided moveset?

[lgarron]

Nice! Can twsearch do what I need - take a cube state from a source mask to a destination mask via a provided moveset?

Yes, that is its main purpose. 😉

[anicolao]

I looked for a mask data structure in the codebase and failed to find it - what is it called?

[lgarron]

I looked for a mask data structure in the codebase and failed to find it - what is it called?

Right now there is just StickeringMask:

https://github.com/cubing/cubing.js/blob/8ff79c59418dac0508d9d0c0bff949dabb0466d3/src/cubing/puzzles/stickerings/mask.ts#L27

Do you need it for any particular reason other than future calls to twsearch?

[anicolao]

The Mask is at the core of the method editor pictured in the opening comment to this bug. Each stage of a method consists of:

1- A mask that defines the desired cube state 2- A 'free face' that can be rotated arbitrarily to get multiple states to match the mask 3- An 'orientation specification' that defines whether or not the whole cube may be rotated to match the mask (that is, treat a different colour pair as 'up' and 'front') 4- A 'frozen face' which is never turned if the user passes through this stage of the solve (which converts L -> r) 5- A 'moveset' which is in the wrong place but which is the set of moves the user may use to go to the next stage (this rightfully ought to be associated with each edge in the graph instead of being on a source or destination node)

The solver is given the cube state at the end of the prior stage, the moveset it may use, the desired destination mask, and the maximum number of moves it may use (currently the minimum of the user's solution and 11 or 12 depending on my mood).

Pairs of masks are also used to set the stickering for each phase as seen in the other bug that happens to contain the code that does it. Note that a pair is needed as the desired display state depends on what edge you are on.

The existing StickeringMask seems quite a bit more complicated than what I'd want, which is really just booleans for each array of indexes and orientations.

[lgarron]

The existing StickeringMask seems quite a bit more complicated than what I'd want, which is really just booleans for each array of indexes and orientations.

Hmm, I'm still not quite clear on what you're asking for. Are you asking for a simpler data structure to represent a mask in your current code? Perhaps even to represent an entire stage?

[anicolao]

What I have right now is a datatype MaskT that comes from onionhoney's code, which represents a cube as a CubieCube which contains up to 6 arrays, cp, co, ep, eo, tp, to. This corresponds approximately to how KState represents the cube but in KState the arrays are named for the orbits as in state.stateData['CORNERS'].pieces is the same thing as cp, and state.stateData['CORNERS'].orientation is the same thing as co. The MaskT datatype, then, looks pretty much exactly the same as CubieCube; and in cubing.js it would look pretty much exactly the same as KState; except that valid values for the mask are only 1 and 0 or true/false. Then, given a KState and a Mask, it is trivial to determine which cubies to use to encode a KState, just map across all the orbits filtering on the booleans from the mask.

[anicolao]

So in case that's still not clear, I should say I want pretty much exactly what I have now. However, there is no chance at all that you'll want to accept MaskT for your solver, because it only does 3x3x3 puzzles and even worse the indices are not in the same order as the order in KState. So currently whenever I go between the two libraries I have to apply a permutation to make things match up. While if this was all implemented on top of cubing.js, it makes sense to simply have a mask data structure that corresponds to KState in every way, which could be used by the solver as well as pruning code, the solution editing code, and the stickering code. In a most perfect universe it would also be used by the editing code's UI, but that's all hand-coded anyway since I couldn't make stickering do double duty for editing.