cubing
Symmetry reduction for rust facing API
I noticed that the rust facing implementation of twsearch seemingly doesn't perform symmetry reduction for search, in the pruning table population and idf implementation. The C++ side of twsearch seems to perform these optimizations in calcsymm.cpp, though, besides the light introduction from docs/architecture.md, I have no idea how it works. Are there any plans for implementing optimizations regarding symmetry and rotations? If not, I can attempt to rudimentarily port it myself, but my cube theory knowledge is admittedly relatively minimal.
I think the first step to getting it into the Rust code would be to figure out how to distinguish "moves" from "rotations". Right now the C++ code does it based on the move name, but an alternate approach is to do it based on the pieces moved.
I'd be happy to answer specific questions or add text to the architecture document if you can point out where things are insufficiently clear.
On Sun, Jan 5, 2025 at 8:12 PM Arhan Chaudhary @.***> wrote:
I noticed that the rust facing implementation of twsearch seemingly doesn't perform symmetry reduction for search, in the pruning table population https://github.com/cubing/twsearch/blob/efb207e11162174360e3ae49aa552cda1313df81/src/rs/_internal/search/hash_prune_table.rs#L95 and idf implementation https://github.com/cubing/twsearch/blob/efb207e11162174360e3ae49aa552cda1313df81/src/rs/_internal/search/idf_search.rs#L340. The C++ side of twsearch seems to perform these optimizations in calcsymm.cpp, though, besides the light introduction from docs/architecture.md, I have no idea how it works. Are there any plans for implementing optimizations regarding symmetry and rotations? If not, I can attempt to rudimentarily port it myself, but my cube theory knowledge is admittedly relatively minimal.
— Reply to this email directly, view it on GitHub https://github.com/cubing/twsearch/issues/84, or unsubscribe https://github.com/notifications/unsubscribe-auth/AAMOLS4HHIY23PG7IFH6GUL2JH7ERAVCNFSM6AAAAABUU2V2CWVHI2DSMVQWIX3LMV43ASLTON2WKOZSG43DSNZXHAYDIOA . 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/ / -
Yeah, this would definitely be great to have at some point.
We have the SearchOptimizations trait that this can plug into when once need this for an implement (probably 4x4x4), although it could be directly implemented into individual coordinates when the math allows.
I think the first step to getting it into the Rust code would be to figure out how to distinguish "moves" from "rotations". Right now the C++ code does it based on the move name, but an alternate approach is to do it based on the pieces moved. I'd be happy to answer specific questions or add text to the architecture document if you can point out where things are insufficiently clear. … On Sun, Jan 5, 2025 at 8:12 PM Arhan Chaudhary @.> wrote: I noticed that the rust facing implementation of twsearch seemingly doesn't perform symmetry reduction for search, in the pruning table population https://github.com/cubing/twsearch/blob/efb207e11162174360e3ae49aa552cda1313df81/src/rs/_internal/search/hash_prune_table.rs#L95 and idf implementation https://github.com/cubing/twsearch/blob/efb207e11162174360e3ae49aa552cda1313df81/src/rs/_internal/search/idf_search.rs#L340. The C++ side of twsearch seems to perform these optimizations in calcsymm.cpp, though, besides the light introduction from docs/architecture.md, I have no idea how it works. Are there any plans for implementing optimizations regarding symmetry and rotations? If not, I can attempt to rudimentarily port it myself, but my cube theory knowledge is admittedly relatively minimal. — Reply to this email directly, view it on GitHub <#84>, or unsubscribe https://github.com/notifications/unsubscribe-auth/AAMOLS4HHIY23PG7IFH6GUL2JH7ERAVCNFSM6AAAAABUU2V2CWVHI2DSMVQWIX3LMV43ASLTON2WKOZSG43DSNZXHAYDIOA . 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/ / -
I spent the day brushing up on cube theory. I can certainly try my hand at porting symmetry reduction from C++ to Rust after I implement puzzlegeometry in cubing.rs as that is more important to get working for my use case. We will ideally want to support group inversion pruning in the Rust port as well (if not already in twsearch) for another 2x factor in pruning table size. I have a few questions:
I was wondering if you could elaborate more on this idea, from docs/architectures.md:
We only compute the value of the first permutation element of the first set for each symmetry element. We take the least resulting value, and identify only those symmetry elements that give us that value. If there is only one symmetry element left, we know precisely which full conjugation to perform, and we do that one and return.
I'm not sure what "first set" refers to, and even after rereading, this section is difficult to comprehend. Maybe an example could help me understand.
I noticed in your original cube20 paper that a novel set cover solution to be described in a later publication was able to reduce the number of cosets to be checked 2.5x, but I wasn't able to find this publication or details of how it worked online. Is this only applicable to coset solvers? If not, twsearch would greatly benefit from such a number.
Lastly, I poked around the codebase some more and realized that gensymm from calcsymm.cpp is never actually called anywhere. If not in that file, which part of twsearch performs the relevant symmetry reductions?
Thanks!
In this context, I'm referring to the first set (as in Set) of pieces in the puzzle definition (as in, perhaps, corners for the 3x3x3) and of that set, the first element (perhaps the piece in the upper right front location). For the 24 elements of the symmetry group, we calculate the piece in that location for the conjugated permutation, identify the least value (lexically), and eliminate any symmetry group elements that don't put that piece in that location. This is a performance hack; normally we'd have to compute the full conjugation for each of the elements of the symmetry group and find the lexicographically least, but we can pare down the elements of the symmetry group on a piece-by-piece basis.
Consider the four symmetries of the square (omitting reflection), with the permutation of corners (2 1 3 4). The conjugated permutations are (2 1 3 4), (1 3 2 4), (1 2 4 3), and (4 2 3 1). Instead of computing all of these out fully, we just compute the first element of each (so 2, 1, 1, and 4 here), and we see that only the second and third (with the element 1) have any chance of being the least lexicographically, so we drop from consideration the first and the fourth, and only continue with the second and third. (We then compute the second element, which gives 3 and 2 respectively, and determine that the third symmetry group element gives the lexicographically least conjugation, and finish the computation of only that element.)
We never did publish the work we put in to compute the set cover and thus reduce the number of cosets needed to resolve God's number. The amount of CPU we used to compute this reduction was significant and only relevant because of the vastly greater amount of CPU needed for the entire problem; in the end we just decided not to write it up and submit it. I can dig up some of what we have written if you are curious, but it's unlikely to be of value in twsearch as it was very specific to the 3x3x3 and the Kociemba subgroup.
On Tue, Jan 7, 2025 at 4:24 AM Arhan Chaudhary @.***> wrote:
I think the first step to getting it into the Rust code would be to figure out how to distinguish "moves" from "rotations". Right now the C++ code does it based on the move name, but an alternate approach is to do it based on the pieces moved. I'd be happy to answer specific questions or add text to the architecture document if you can point out where things are insufficiently clear. … <#m_2650601195739409780_> On Sun, Jan 5, 2025 at 8:12 PM Arhan Chaudhary @.> wrote: I noticed that the rust facing implementation of twsearch seemingly doesn't perform symmetry reduction for search, in the pruning table population https://github.com/cubing/twsearch/blob/efb207e11162174360e3ae49aa552cda1313df81/src/rs/_internal/search/hash_prune_table.rs#L95 https://github.com/cubing/twsearch/blob/efb207e11162174360e3ae49aa552cda1313df81/src/rs/_internal/search/hash_prune_table.rs#L95 and idf implementation https://github.com/cubing/twsearch/blob/efb207e11162174360e3ae49aa552cda1313df81/src/rs/_internal/search/idf_search.rs#L340 https://github.com/cubing/twsearch/blob/efb207e11162174360e3ae49aa552cda1313df81/src/rs/_internal/search/idf_search.rs#L340. The C++ side of twsearch seems to perform these optimizations in calcsymm.cpp, though, besides the light introduction from docs/architecture.md, I have no idea how it works. Are there any plans for implementing optimizations regarding symmetry and rotations? If not, I can attempt to rudimentarily port it myself, but my cube theory knowledge is admittedly relatively minimal. — Reply to this email directly, view it on GitHub <#84 https://github.com/cubing/twsearch/issues/84>, or unsubscribe https://github.com/notifications/unsubscribe-auth/AAMOLS4HHIY23PG7IFH6GUL2JH7ERAVCNFSM6AAAAABUU2V2CWVHI2DSMVQWIX3LMV43ASLTON2WKOZSG43DSNZXHAYDIOA https://github.com/notifications/unsubscribe-auth/AAMOLS4HHIY23PG7IFH6GUL2JH7ERAVCNFSM6AAAAABUU2V2CWVHI2DSMVQWIX3LMV43ASLTON2WKOZSG43DSNZXHAYDIOA . 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/ / -
I spent the day brushing up on cube theory. I can certainly try my hand at porting symmetry reduction from C++ to Rust after I implement puzzlegeometry in cubing.rs as that is more important to get working for my use case. We will ideally want to support group inversion pruning in the Rust port as well (if not already in twsearch) for another 2x factor in pruning table size. I have a few questions:
I was wondering if you could elaborate more on this idea, from docs/architectures.md:
We only compute the value of the first permutation element of the first set for each symmetry element. We take the least resulting value, and identify only those symmetry elements that give us that value. If there is only one symmetry element left, we know precisely which full conjugation to perform, and we do that one and return.
I'm not sure what "first set" refers to, and even after rereading, this section is difficult to comprehend. Maybe an example could help me understand.
I noticed in your original cube20 paper that a novel set cover solution to be described in a later publication was able to reduce the number of cosets to be checked 2.5x, but I wasn't able to find this publication or details of how it worked online. Is this only applicable to coset solvers? If not, twsearch would greatly benefit from such a number.
Lastly, I poked around the codebase some more and realized that gensymm from calcsymm.cpp is never actually called anywhere. If not in that file, which part of twsearch performs the relevant symmetry reductions?
Thanks!
— Reply to this email directly, view it on GitHub https://github.com/cubing/twsearch/issues/84#issuecomment-2575153835, or unsubscribe https://github.com/notifications/unsubscribe-auth/AAMOLS7JJ6JMV6RAMRQGVQD2JPBRRAVCNFSM6AAAAABUU2V2CWVHI2DSMVQWIX3LMV43OSLTON2WKQ3PNVWWK3TUHMZDKNZVGE2TGOBTGU . You are receiving this because you commented.Message ID: @.***>
--
- https://cube20.org/ http://cube20.org/ - https://golly.sf.net/ http://golly.sf.net/ - https://alpha.twizzle.net/ / -