Pure JavaScript solvers for random state 3x3 scrambles

[pglewis]

I know this has been discussed in the past (by doing a little archaeology) but I feel like this topic needs a revisit as we approach 2018. Device resources and JavaScript VM implementations have made significant advances in the past 6-8 years and some of the traditional assumptions from the past may no longer be true.

Unprioritized list of some goals

• Clear, GPL-compatible license
• 100% client-side JS, can function without a network connection from any compliant browser
• Does not need to be an optimal solver, just good enough for random state scrambles
• As performant as possible

I do not grasp Kociemba 2-phase right now (nor any other approach for that matter). I'd be willing to learn and/or look into existing implementations with an eye on benchmarks and ideas for optimization. I've seen a few implementations out there that do not have a clear licence status. I've also fiddled with cubejs and I know it is explicitly GPL-compatible.

I'd love to discuss some ideas on this topic and any links to other implementations that fit the criteria to compare benchmarks.

 

[xyzzy]

Pretty much every online timer uses min2phase (which is written in Java) compiled to JS, and min2phase is available under GPLv3.

(I know roughly how to code solvers, and I've written my own implementations of Kociemba's 2-phase algorithm before, but I definitely cannot claim to know how to do the "as performant as possible" part. If you have any questions not related to speed, I can answer those, but speed-related questions are outside of my expertise.)

 

[pglewis]

Thanks. I had already found a few species that evolved from ports of min2phase but they had no explicit license information in the source file (no GNU preamble) nor in the repository. Being ignorant of the history I initially ignored them as "license unclear". I would still rather find a port that has an unambiguous license, the ones I've found contain varying modifications and other features. Knowing their foundation started with GPL code sets my mind at ease though. As far as I understand, modifying GPL'ed code automatically makes the modified code GPL but even in an unlikely worst future case I could always create a port from scratch.

On performance, that family is much faster at initialization than cubejs. The one I'm currently testing is a few hundred ms on my desktop/Chromium from init to getting a first scramble-- which is amazing and production-worthy-- but for the sake of some mobile devices it would be nice to see what else could be squeezed out of it.

Optimization is a black art and doing it in front of an optimizing compiler and VM is extra tricky. Micro-benchmarking like you see a lot on jsPerf can lead to incorrect conclusions. The simplicity of the tests often allows for VM optimizations that are ultimately not testing what you think you're testing. Then there is a lot of old "wisdom" floating around that sprouted in the days of naive JS VMs and persist today even though it's potentially counterproductive.

Spoiler: This should be required viewing for anyone attempting to optimize JavaScript

The biggest gains usually come from insights you only get if you fully grok the domain, though, so I'm hamstrung in that dept.

 

[pglewis]

Also, in case it isn't obvious, the primary target for optimization is the one-time initialization of the data needed by the solver. I'm sure there's room for improvement of the solver itself but it's more than an order of magnitude faster than init. Improvements to the algorithms involved in building the pruning tables and other related data is probably biggest bang for the buck.

 

[Mike Hughey]

Would this do as a min2phase with valid GPL?
https://github.com/thewca/tnoodle

Nice thing is that it's WCA official software too, which I suspect will all always be GPL.

 

[pglewis]

Would this do as a min2phase with valid GPL?
https://github.com/thewca/tnoodle

Nice thing is that it's WCA official software too, which I suspect will all always be GPL.

Yeah, as far as I can tell that one is only built into an "even the kitchen sink" js file of nearly 20k LOC (though admittedly I haven't really dug-in). It's on my list to check out and benchmark and it's a safe fallback if unclear licensing ever does become an issue. But as-is, it's much larger than what is needed for just a basic solver and random state scrambler and would need to be pared down or at least modularized so you can cherry pick just the pieces you need for your application.

 

[bcube]

• 100% client-side JS, can function without a network connection from any compliant browser
• As performant as possible
• Does not need to be an optimal solver, just good enough for random state scrambles

For optimal solutions, is there any other solver than Solver 2 worth noticing in 2024?

 

[swipymam]

For optimal solutions, is there any other solver than Solver 2 worth noticing in 2024?

https://github.com/efrantar/rob-twophase

«This is an efficient Rubik's Cube solving algorithm designed particularly for the use by high-speed robots. At its core, it is a highly optimized C++ version of Herbert Kociemba's two-phase algorithm that combines many of the best tricks from the excellent implementations RubiksCube-TwophaseSolver, min2phase and cube20src with some further improvements.»

Based on all this, there is an implementation on RUST, but traces of it have been lost or removed.

 

[Gil.zussman]

Also, in case it isn't obvious, the primary target for optimization is the one-time initialization of the data needed by the solver. I'm sure there's room for improvement of the solver itself but it's more than an order of magnitude faster than init. Improvements to the algorithms involved in building the pruning tables and other related data is probably biggest bang for the buck.

I had the exact discussion with @Lucas Garron about a week ago.

I written the implementation for the kociemba algorithm for a lower end machine where the initialization took 30-60 seconds to process.


I ended up precalculating them into a file, and loading them now takes 0.8 seconds.

IIRC, other solvers implementations, like squanmate, take the first run to process and save the tables. Next runs it takes meaningless time to load them.