rokicki
commented
1 year ago Wow, what a well-thought-out and carefully written proposal!
The main drawback I see is that twsearch is intended to be very general, and at the moment to do this it sacrifices quite a bit of speed. Indeed, twsearch doing a normal 3x3x3 search is on the order of 50 times slower (!) than a bespoke 3x3x3 solver (this is measured with large memory and many cores, and may be different at browser and wasm sizes, but not too much different). I expect similar differences for other puzzles.
While I'm working on closing this gap, I suspect it is just too large to make twsearch fully practical for the places where TNoodle is currently being used.
For the short term (likely at least the next few years), I'd recommend sticking with tnoodle and maybe getting help (I might be convinced to help; I've played a bit with tnoodle and am super impressed with its capabilities). As long as the tnoodle licensing is clear, we may be able to "save" the best parts of tnoodle and/or reimplement the bits we don't need so much, likely in a fashion that it can be easily integrated into the browser.
(There are some ideas I've been playing with in twsearch---for instance, instead of first generating pruning tables and storing them and then using them, I generate them on the fly and only write them to disk if I spend enough time to make that worth the effort---and at browser sizes, this may not even ever be necessary. Twsearch does have a --nowrite option that disables writing pruning tables to disk.)
Let's chat about this somewhere more interactive; I recommend the slack channel that Lucas has made for cubing software, which is cubing-org.slack.com. I'll be there today so ping me if you want.
On Sat, Jul 9, 2022 at 8:55 PM Gregor Billing @.***> wrote:
Hey there! Reaching out via GitHub Issues, but feel free to move this to another discussion forum or to email via @.*** :)
For a while now, there had been this thought in the back of my mind to abandon the tnoodle-lib scrambling code in favor of a general scrambler. Recently, WST has been contacted about native / JS implementations of TNoodle (again) which has reminded me of those thoughts and ideas. Your project has caught my eye, so I'd like to brainstorm a little bit on whether (and if so, how) this could be integrated into the WCA software stack. Disclaimer
The entire idea of abandoning our own scramblingg code came along because there's nobody on the current team (myself included) who has a full, in-depth understanding of all the different scramblers we use. I have a solid working-knowledge of state-space search and group theory, but I am far from what you would call "fluent" in a human language and I am also not very familiar with the specific application domain of twisty puzzles. As such, any of my suggestions and ideas would entail significant support and some form of committment by the current maintainers of the library. Please keep that in mind when going through this list. Required features in twsearch to replace tnoodle-lib
Several custom libraries in TNoodle, namely min2phase, threephase and sq12phase that are originally forked from Chen Shuang's solvers include optimisations that I believe we need to efficiently generate scrambles that comply with the high standards set forth by the WCA Regulations.
- I saw that there is basic support for two-phase search on 3x3x3, but the readme file currently states that it is not very optimised. These optimisations should be included to reach feature parity with https://github.com/cs0x7f/min2phase/blob/master/Algorithm.md
- There needs to be a similar support for Three-Phase solving of 4x4x4, although with the optimisations from (1) this arguably "only" entails writing the correct definition files for the separate phases.
- There needs to be support for an optimised Square-1 phase algorithm, as we currently rely on sq12phase for the WCA. Unfortunately, this specific scrambler is not very well documented and probably requires digging through the Java code to find out what it does. It also potentially(?) requires support for block moves with the Square-1 "slash" move (/ notation)
- There are other event-specific requirements like the R U F' padding for FMC and block moves (or rotations on even NxN cubes) that "break" the white-top green-front orientation for BLD. These are not specific to the search engine but need to be supported in terms of pre-moves when performing the state search.
- The padding is not as simple as finding the random state scramble and then affixing moves, but rather restricting the axes at the start and end to guarantee this padding.
- The orientation-breaking moves seem to be a simple matter of "reformulating" an L as Rw on 3x3 towards the end of the scramble. If my understanding of the existing TNoodle code is correct, this won't be terribly hard to implement.
--> WST currently does not have any significant capacity to contribute implementations of these features, apart from occasional support and troubleshooting. Integrations into the existing stack
The core reason behind maintaining our own Java solution in the first place is the portability to allow Delegates offline generation of scrambles by downloading a portable JAR archive. Shifting our implementation to a library that is written in C++ requires us to deal with machine code. Two possible paths forward are:
- Provide JNI bindings and ship mingw62, darwin and linux binaries with TNoodle releases.
- Provide full WASM support and embed the assembled code into the browser frontend. Let the browser entirely handle the scrambling.
- (Potentially) provide Python native bindings, because people keep asking about scrambles in Python every now and then. However, that's just a "cherry on top".
--> WST does potentially have the capacity to contribute either of the two integrations with some initial support by the current maintainers of the project, to understand the "entry points" and overcome initial bootstrapping. We would also be willing to take responsiblility to maintain these bindings in the long run.
There also remains the question of SVG drawing because TNoodle needs to produce images of puzzles so (human) scramblers can check what they did during competitions. For that, we need bindings to generate a full state representation of a puzzle for a given scramble string. In a first step, this representation could then be converted to an internal TNoodle representation that reuses the old drawing code. Perspectively, we'd want to move away from that code in favor of standardised SVG templates that follow the "ksolve spirit" of one rectangle/triangle per cubie. Details would be too much for the scope of this discussion, and the bottom line is that drawing scrambles is not an immediate concern for this library as long as we can parse puzzle states from a given scramble string.
--> WST does have the capcacity to provide this compatibility layer during the potential "phase-out" period of the old tnoodle-lib.
Lastly, the usage of this library seems to be pretty CLI-heavy. With TNoodle, we would ideally want a more "integrated" way of working with the scramblers, such that we don't have to write temporary files to some dummy directory only to delete them immediately after the solution was found. Also, we would probably include an option in the TNoodle frontend where Delegates can tick a box about "I want to store pruning tables locally". If they don't check that box, it would be cool to have a feature to compute the necessary pruning tables once at startup and keep them in memory until TNoodle (or whatever other program using these bindings) is closed.
--> WST does potentially have the capacity to contribute either of the two integrations with some initial support by the current maintainers of the project, to understand the "entry points" and overcome initial bootstrapping.
For now, this covers all of my thoughts. If you have anything to add feel free to do so, otherwise I'm excited to hear what you have to say about this idea in general. Thanks for your contributions and your work on this library!
— Reply to this email directly, view it on GitHub https://github.com/cubing/twsearch/issues/4, or unsubscribe https://github.com/notifications/unsubscribe-auth/AAMOLS7U6V6GY64SDLOCBSLVTJCRRANCNFSM53ELFNVQ . You are receiving this because you are subscribed to this thread.Message ID: @.***>
--
gregorbg
lgarron
(See below for original post)
Original post
Hey there! Reaching out via GitHub Issues, but feel free to move this to another discussion forum or to email via software-admin@worldcubeassociation.org :)
For a while now, there had been this thought in the back of my mind to abandon the
tnoodle-libscrambling code in favor of a general scrambler. Recently, WST has been contacted about native / JS implementations of TNoodle (again) which has reminded me of those thoughts and ideas. Your project has caught my eye, so I'd like to brainstorm a little bit on whether (and if so, how) this could be integrated into the WCA software stack.Disclaimer
The entire idea of abandoning our own scramblingg code came along because there's nobody on the current team (myself included) who has a full, in-depth understanding of all the different scramblers we use. I have a solid working-knowledge of state-space search and group theory, but I am far from what you would call "fluent" in a human language and I am also not very familiar with the specific application domain of twisty puzzles. As such, any of my suggestions and ideas would entail significant support and some form of committment by the current maintainers of the library. Please keep that in mind when going through this list.
Required features in
twsearchto replacetnoodle-libSeveral custom libraries in TNoodle, namely
min2phase,threephaseandsq12phasethat are originally forked from Chen Shuang's solvers include optimisations that I believe we need in order to efficiently generate scrambles that comply with the high standards set forth by the WCA Regulations.sq12phasefor the WCA. Unfortunately, this specific scrambler is not very well documented and probably requires digging through the Java code to find out what it does. It also potentially(?) requires support for block moves with the Square-1 "slash" move (/notation)R' U' Fpadding for FMC and block moves (or rotations on even NxN cubes) that "break" the white-top green-front orientation for BLD. These are not specific to the search engine but need to be supported in terms of pre-moves when performing the state search.LasRwon 3x3 towards the end of the scramble. If my understanding of the existing TNoodle code is correct, this won't be terribly hard to implement.--> WST currently does not have any significant capacity to contribute implementations of these features, apart from occasional support and troubleshooting regarding the existing tnoodle-lib code.
Integrations into the existing stack
The core reason behind maintaining our own Java solution in the first place is the portability to allow Delegates offline generation of scrambles by downloading a portable JAR archive. Shifting our implementation to a library that is written in C++ requires us to deal with machine code. Two possible paths forward are:
mingw62,darwinandlinuxbinaries with TNoodle releases.--> WST does potentially have the capacity to contribute either of the two integrations with some initial support by the current maintainers of the project, to understand the "entry points" and overcome initial bootstrapping. We would also be willing to take responsiblility to maintain these bindings in the long run.
There also remains the question of SVG drawing because TNoodle needs to produce images of puzzles so (human) scramblers can check what they did during competitions. For that, we need bindings to generate a full state representation of a puzzle for a given scramble string. In a first step, this representation could then be converted to an internal TNoodle representation that reuses the old drawing code. Perspectively, we'd want to move away from that code in favor of standardised SVG templates that follow the "ksolve spirit" of one rectangle/triangle per cubie. Details would be too much for the scope of this discussion, and the bottom line is that drawing scrambles is not an immediate concern for this library as long as we can parse puzzle states from a given scramble string.
--> WST does have the capcacity to provide this compatibility layer during the potential "phase-out" period of the old tnoodle-lib.
Lastly, the usage of this library seems to be pretty CLI-heavy. With TNoodle, we would ideally want a more "integrated" way of working with the scramblers, such that we don't have to write temporary files to some dummy directory only to delete them immediately after the solution was found. Also, we would probably include an option in the TNoodle frontend where Delegates can tick a box about "I want to store pruning tables locally". If they don't check that box, it would be cool to have a feature to compute the necessary pruning tables once at startup and keep them in memory until TNoodle (or whatever other program using these bindings) is closed.
--> WST does potentially have the capacity to contribute either of the two integrations with some initial support by the current maintainers of the project, to understand the "entry points" and overcome initial bootstrapping.
For now, this covers all of my thoughts. If you have anything to add feel free to do so, otherwise I'm excited to hear what you have to say about this idea in general. Thanks for your contributions and your work on this library!