Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Brainstorming official WCA integration #4

Open
1 task
gregorbg opened this issue Jul 10, 2022 · 4 comments
Open
1 task

Brainstorming official WCA integration #4

gregorbg opened this issue Jul 10, 2022 · 4 comments

Comments

@gregorbg
Copy link

gregorbg commented Jul 10, 2022

(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 [email protected] :)

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 in order to efficiently generate scrambles that comply with the high standards set forth by the WCA Regulations.

  1. 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
  2. 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.
  3. 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)
  4. 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.
    1. 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 "makes sense". EDIT: I just realised that you came up with this approach in the first place, so nevermind my explanation 😄
    2. 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 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:

  1. Provide JNI bindings and ship mingw62, darwin and linux binaries with TNoodle releases.
  2. Provide full WASM support and embed the assembled code into the browser frontend. Let the browser entirely handle the scrambling.
  3. (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!

@rokicki
Copy link
Collaborator

rokicki commented Jul 10, 2022 via email

@gregorbg
Copy link
Author

Thank you for your detailed and enthusiastic feedback! I agree that for the "zesty details", a more interactive platform is desirable. However, I cannot seem to be able to figure out how to create an account for the Slack you mentioned it. When I navigate to cubing-org.slack.com, it prompts me to login with an existing account. Could you perhaps try to invite me at gregor.billing.dev(at)gmail.com?

On a wider scale, I understand your argument about runtime efficiency and the classical optimisation VS generalisation trade-off. There's another part to the story here, which I only very briefly touched upon in my original message. People (relatively) often approach WST about JS/Python/native/... ports of TNoodle because they want to use "official" scrambles in their application. The general public understanding of what a scramble is and how it's computed is somewhat narrow, and even if we suggest using mark2 (or nowadays, cubingJS) people reply that this won't satisfy them since "it's not TNoodle".

Now we can't possibly hope to educate every person out there about what a random state scramble is and why it matters. But by moving the WCA scrambling routines to some "general" search engine like yours, my hope is that people will understand that literally any random state scrambler is as good as the next and the only difference is runtime efficiency.
Of course, there are deeper implications here as well (is my solver of choice actually correct? Which puzzles can reasonably use random state and which ones use random moves for now?) but I wanted to point this out as part of my motivation for starting this discussion. Looking forward to a more thorough debate later on, just need to figure out how to join the Slack Workspace 😄

@rokicki
Copy link
Collaborator

rokicki commented Jul 11, 2022 via email

@lgarron
Copy link
Member

lgarron commented Jan 5, 2023

For reference, I'm using cubing/cubing.js#250 to track functionality that is needed to replace TNoodle.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

3 participants