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.