Implement a variation of a `KPattern` mask where pieces can be fully ignored.

[lgarron]

Currently, masks are just repurposed KPatterns where some pieces are set as identical and some orientations are ignored.

The way to set a piece to "ignored identity" is to assign it a piece number distinct from the un-ignored pieces, shared with other ignored-identity pieces in the same orbit. This has worked really well for us, allowing for implementations like:

• Kociemba 2-phase with decent performance and no 3x3x3-specific code.
• Skewb scrambling without doing fancy math for cross-orbit constraints.

However, consider Kilominx phase 1:

• 5 pieces are selected (to be eventually placed on the back face).
• Those pieces must be moved so that none of them are on the F face.

This can be implemented trivially using a super naïve search and writing custom code to filter solutions. But I would like to be able to implement this without puzzle-specific code.

My instinct would be to implement this by assigning the 5 pieces a certain piece number (say, 1, and the other pieces a different piece number (say, 0), e.g.:

{
  "CORNERS": {
    "pieces": [0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0]
    // …
  }
}

Then the target pattern/mask for the search just needs to express that all locations of F are occupied by 0 pieces. This is easy. But we also need to specify that all the other locations can contain either 0 or 1. I don't think this is possible using our current masking. This has several implications:

1. We need a way to express that the piece identity at a given location is either 1) ignored-identity, or 2) allowed to be from a certain subset.
2. We need a way for IDFS to apply the "ignore some piece identities" mask any time it checks for the target pattern. We can do this with a trait, although I don't know how this will impact perf / what optimizations can be done.

• Perhaps instead of applying the target maskand then comparing the pattern, we could just have a "check if pattern A matches mask B" function that can short-circuit.

3. For puzzles where perf matters, we need to figure out how this affects prune tables.

[lgarron]

Note that there are some cases where "ignore this piece completely" sounds desirable, but may not be. For example, consider two masks:

• One that marks all LL edges and all LL corners as indistinguishable.
• One that marks DF and DB as indistinguishable.

Then it might be desirable to compose these, in which case the two sets of indistinguishable pieces must be kept distinct. This could be handled as follows:

• Prefer using piece groups instead of marking piece identities as ignored-identity, where possible.
• Use ignored-identity pieces a lot, but when composing masks with ignored pieces, either:
  • Merge sets of ignored-identity pieces from the constituent masks by default. I think this is the most "intuitive", but makes it harder to implement use cases like the one above.
  • Keep sets of ignored-identity pieces from the constituent masks separate by default. This can cause surprises by ending up with an over-constrained mask. In the best case, someone notices what went wrong, but it's quite possible people would construct searches that take longer and have more moves. Also, this may introduce the need to implement an "merge some sets but not others" API down the road, which I think is overly complicated.
  • Explicitly require specifying what to do. This is certainly safer, but un-ergonomic.

So I think I would favor indistinguishable pieces instead of ignored for patterns that we provide in code and in docs, e.g. for the OLL target mask, at least until we understand the problem space further.

[lgarron]

Also also: there is a similar issue with "ignored orientation" vs. "unknown orientation". Perhaps the same approach can help provide a way to distinguish these (or eliminate the need to) at the same time.

[ArhanChaudhary]

Semi-related. I am looking to find the shortest algorithm that yields a cycle type on any KPuzzle, for example the shortest algorithm on the 3x3x3 that induces a 2 cycle on 1 edge, 8 cycle on 4 edges, 5 cycle on 5 edges, 3 cycle on 1 corner, 2 cycle on 2 corners, 9 cycle on 3 corners. I am implementing this and rewriting puzzle logic from scratch based on ideas from twsearch and the reference Korf's algorithm implementation (the code will all be open source in accordance to the license). This feature could be useful to also have in twsearch.

[rokicki]

Sounds very nice! Compare the -A option in the C++ twsearch which focuses on searching for algorithms that affect only a few pieces, using three distinct strategies. If you are focused on only the shortest algorithms, the ordertree.cpp code is intended to be modified for exactly such searches.

On Thu, Jan 9, 2025 at 5:10 PM Arhan Chaudhary @.***> wrote:

Semi-related. I am looking to find the shortest algorithm that yields a cycle type on any KPuzzle, for example the shortest algorithm on the 3x3x3 that induces a 2 cycle on 1 edge, 8 cycle on 4 edges, 5 cycle on 5 edges, 3 cycle on 1 corner, 2 cycle on 2 corners, 9 cycle on 3 corners. I am implementing this and rewriting puzzle logic from scratch based on ideas from twsearch and the reference Korf's algorithm implementation (the code will all be open source in accordance to the license). This feature could be useful to also have in twsearch.

— Reply to this email directly, view it on GitHub https://github.com/cubing/twsearch/issues/86#issuecomment-2581540186, or unsubscribe https://github.com/notifications/unsubscribe-auth/AAMOLS4HORJK7DBZPOFXQM32J4MYTAVCNFSM6AAAAABU3S5HESVHI2DSMVQWIX3LMV43OSLTON2WKQ3PNVWWK3TUHMZDKOBRGU2DAMJYGY . You are receiving this because you are subscribed to this thread.Message ID: @.***>

--

• https://cube20.org/ http://cube20.org/ - https://golly.sf.net/ http://golly.sf.net/ - https://alpha.twizzle.net/ / -

[ArhanChaudhary]

Sounds very nice! Compare the -A option in the C++ twsearch which focuses on searching for algorithms that affect only a few pieces, using three distinct strategies. If you are focused on only the shortest algorithms, the ordertree.cpp code is intended to be modified for exactly such searches. … On Thu, Jan 9, 2025 at 5:10 PM Arhan Chaudhary @.> wrote: Semi-related. I am looking to find the shortest algorithm that yields a cycle type on any KPuzzle, for example the shortest algorithm on the 3x3x3 that induces a 2 cycle on 1 edge, 8 cycle on 4 edges, 5 cycle on 5 edges, 3 cycle on 1 corner, 2 cycle on 2 corners, 9 cycle on 3 corners. I am implementing this and rewriting puzzle logic from scratch based on ideas from twsearch and the reference Korf's algorithm implementation (the code will all be open source in accordance to the license). This feature could be useful to also have in twsearch. — Reply to this email directly, view it on GitHub <#86 (comment)>, or unsubscribe https://github.com/notifications/unsubscribe-auth/AAMOLS4HORJK7DBZPOFXQM32J4MYTAVCNFSM6AAAAABU3S5HESVHI2DSMVQWIX3LMV43OSLTON2WKQ3PNVWWK3TUHMZDKOBRGU2DAMJYGY . You are receiving this because you are subscribed to this thread.Message ID: @.> -- - https://cube20.org/ http://cube20.org/ - https://golly.sf.net/ http://golly.sf.net/ - https://alpha.twizzle.net/ / -

Very cool, didn't know the -A option did that. In the far future when I'm finished implementing the cycle type solver in my project I can look into modifying ordertree.cpp to adapt my code with the -A flag. I wasn't able to find that specific cycle type in the output of -A, so I think it would be a welcome addition.

[DougCube]

These sort of ideas would very likely fix most of the performance issues I've been facing for developing a CH2 solver.

[lgarron]

These sort of ideas would very likely fix most of the performance issues I've been facing for developing a CH2 solver.

That's very useful to know! Could you give examples of an pattern and target for an orbit where fully ignored pieces would be helpful over grouping all the pieces in an orbit you don't care about?