cubing / mark2

Client-Side Javascript WCA-Style Scrambler

WCA-Style Puzzle Scrambler: Mark 2 [BETA]

This is not the official WCA scrambler, although it may proposed as one.

The name "Mark 2" represents that this is an entirely rewritten second-generation system for the WCA, and is also a reference to the attempt to convert all scramblers into Markov Random State Scramblers.

Goals

• Replace all scramblers by high-quality random scramblers, where possible (reasonable alternatives otherwise).
• Implement everything entirely in client-side Javascript. Everything should work in a browser online OR offline, without any other effort. (e.g. no remote/local servers or executables to start. Sorry, tnooodle.)
• Unify the old scramblers into one, easy-to-use interface for generating competition scrambles.

New Features

• Markov Random-State 3x3x3 and Square-1 scramblers.
• Clearer clock and Square-1 notation.

Style Guide

• When updating a scrambler, update date of the version at the end of the file.
• Make sure all scramblers use implement a setRandomSource(src) methoda and use randomSource.random() instead of Math.random().
• Always loop over an array using for (var i=0; i < array.length; i++) instead of for (var i in array).

Credit

Software

• GWT for Java -> Javascript compilation.

People

• Jaap Scherphuis (original scramblers for all puzzles
• Tom van der Zanden (2x2x2)
• Conrad Rider (2x2x2 and 3x3x3 ini)
• Walter Souza (Square-1 solver from Prisma Puzzle Timer)
• Herbert Kociemba (for the Kociemba two-phase algorithm)
• Stefan Pochmann (Megaminx)
• Clement Gallet (Megaminx)
• Syoji Takamatsu (Pyraminx)
• Andrew Nelson (Square-1 drawings)
• Michael Gottlieb (Square-1)
• Lucas Garron (Square-1, Mark 2)
• Evan Gates (QBX)
• Shuang Chen (Fast GWT-compiled 3x3x3 scrambler and Square-1 scrambler)

mark2's Issues

Puzzle faces should have bold outlines.

So that the net is easy to compare to a real cube.

Fix all closures.

Private variables should be private, and only public methods should escape encapsulation.

It can be easy to leak into global state by leaving out a var keyword, especially when assembling old scrambler code. An examination of the values attached to window will reveal some more to be cleaned up.

Console logging in web worker should be forwarded to main thread.

Simple proxy functions (e.g. defining a non-empty console.log for the worker) and should do it.

Issue: general log messages vs. detail messages?

Don't default to Math for random source in scramblers

Force something to be passed in, even if it's just Math. That way, instead of silently falling back to Math, you'll get an error.

Don't crash if client tries to generate 0 rounds

Can happen with some accidental UI scrolling.

Investigate the best randomization methods for big cubes and Megaminx.

4x4x4-7x7x7 and Megaminx are the only puzzles without random-state scramblers. Except maybe for 4x4x4, such scramblers are likely to remain infeasible (or at least impractical) for a while.

3x3x3 random-turn scrambling (I think) is more random if we alternate axes every turn. There are a couple of such ways to vary scrambling on higher-order cubes, e.g.

• Alternating axes vs. doing a lot of consecutive R, 2R, Rw moves, etc.
• Double turns vs. single turns.
• Slice turns vs.
• On megaminx:

We should come up with some decent randomness metrics (e.g. distribution of centers among faces) and figure out what makes for a good distribution according to reasonable metrics.
(Question: how much should we bias this to existing cube methods?)

See Stefan's 3x3 scramble analyzer. This would probably good to generalize; a tool to analyze arbitrary permutation puzzle (a la ksolve) and metrics for all state-machine scramblers seems very feasible and useful, though a bit tricky.

Pressing Enter while adjusting round numbers should start scrambling

Like an HTML for submits using Enter.

Face labels

For plan views.

Display updates about scramble generation progress.

Probably using setTimeout(...) callbacks.

Also figure out a reasonable set of things to console.log(...).

# groups for each round.

Scramble set selection should have a field for it.

Consider trying to find shorter 3x3x3 solutions

Especially for earlier rounds?

It's unclear if / when / how this would be practical.

Stop Button

For browsers that don't halt as easily on their own when you try to nuke the page.

Change the HTML page title to the competition name

So that e.g. PDF export suggests the competition name.

Benchmark seeding is not working?

Seems to produce different scrambles every time. Probably some random source getting dropped some time.

Considering requiring a random source to ini the randomness in all the scramblers. Client has to pass in something (even Math) to make it work.

Each worker needs to be properly seeded.

Create Benchmarks and Unit Tests

Commandline and in-browser.

Commandline

• Pre-commit hooks?

In-browser

• Automated tests to let users know if there are any issues, and what they might be.

IE and Firefox 3.6 compatibility.

Apparently innerHTML of a tbody is read-only sometimes. http://stackoverflow.com/questions/555965/javascript-replace-innerhtml-throwing-unknown-runtime-error

Robust Exception Handling

Encapsulate web worker manager.

Create .zip file releases

And just include the important stuff. Maybe condense files?

Separate issue for the last comment on issue #4.

Info Panel

For credits and stats like current scrambler version and implementation details.

Test Printing

Test cross-OS and cross-browser:

• Make sure everything prints properly
• Make sure every set of scrambles on a page.
• Make sure that (e.g. when generating more than 5 scrambles for a set) scrambles don't get printed on top of another due to page breaks.

Define the mark2 interface for scramblers

Methods and behaviour.

As of December 25, 2011:

• version
• initialize(callback, randomSource, statusCallback)
• setRandomSource(src)
• getRandomScramble()
• drawScramble(parentElement, state, w, h)

Multi BLD

These might take a while to generate, but there should be the option.

It's probably reasonable to fit a bunch more scrambles on a page, with smaller images (or maybe scrambles and images in a more compact layout?

Figure out what whether to allow settings and how.

e.g. scramble length or color scheme.

Look into converting Java scramblers via GWT

Make each scramble a clickable link?

To <alg.garron.us> or eventually <alg.cubing.net>.

If so, the formatting should be transparent, e.g. same color and formatting (no underline) as normal text. Subtle hover effect is okay.

Look into web workers.

Async scramble generation would be useful for 3x3x3.

Direct URLs

Allow URL hash to specify rounds to generate, as well as a boolean paramater that starts generating instantly.

Remove build.sh

build.sh is not used anymore. (It was intended for building a version of the HTML with Javascript embedded, so that Chrome could load the web worker code from a blob. This also seems to be subject to the same restrictions. Unfortunately, that still means that web workers don't work in Chrome when running from file://.)

Allow round reordering

I was wary of this at first, but I think the code can be adapted without too many UX issues.

updateSetCount bug

Embed ASCII versions of the scramble sets somehow.

Ideally, it should be easy to parse and import the scrambles from ether the website or the PDF. This allows the data to be archived compactly (e.g. on the WCA website).

Don't set parentElement width inside drawScramble(...)

This is a current workaround in all the scramblers. Instead, the width (and height? max height?) should be passed down drawScramble()....

12c1) needs a revision.

(x, y) and / should be separated again.

http://www.worldcubeassociation.org/regulations/#notation

HTML5 Offline Support

See the following examples:

• http://www.cubing.net/twisty.js/offline.html
• http://www.qqtimer.net/offline.html

Also, include a .zip in releases so that everything can be downloaded into a stand-alone directory.

Clock and Megaminx Images

Create a standard event order.

Object iteration is in arbitrary order, but it would be nice to have the order consistent among all browser. This just needs a reference array with the eventIDs in some order.

Utilize (0, y) moves in the Square-1 scrambler.

The current Square-1 scramble uses any (6, 0) or (x, 0) moves to insert a middle flip half the time (to make middle slice parity work out). (0, 6) and (0, y) should also be used if (x, 0) is not available.

Look into Backbone.js or Knockout.js

Codify terminology

Make consistent with the WCA, and normalize throughout the codebase.

e.g.

• round
• scramble set
• scramble
• event

Clean up all the old WCA scramble code.

e.g.

• Remove all the "global" variables remaining in each of the scramble closures.

Generate Fewest Moves sheets

Scramble strips and FCFs.

Create all round elements in the DOM before firing off scramblers.

Could help e.g. on mobile Safari, which has expensive DOM manipulation and message passing (especially if there is a lot of it going on, and interleaved).

UX

What I'm imagining right now: You're presented with a list of events. You simply click to increase/decrease the number of rounds per event (in addition to entering the competition), and the events all get generated with appropriate default round names.

For 4 rounds, this would be as follows:

• Round 1
• Round 2
• Round 3 (Semi-Final)
• Round 4 (Final)

The interface should still have a list where the events can be customized. This can be doe using pre-existing formats like "Combined Round" and "Best of 3".

Options:

• Cover sheet (just to look pretty, and also with instructions).
• Collation? (Probably not; just print twice collated.)

FMC scrambles will have FCFs, so the instructions should make it clear what to do with them.

Random-state centers for 4x4x4

Maybe also 5x5x5.
Since most speedcubers begin with centers, we should run various metrics on the current 4x4x4 scrambler and see if the centers are random enough. If not, we can apply a random scramble to the centers (ignoring everything else) followed by some amount of random moves.
It should be checked that this doesn't compromise the randomness of other parts of the puzzle significantly.
(Perhaps only use this for speedsolve, not BLD?)

Consideration: Could a reduction-style 4x4x4 computer solver produce scrambles that are at least as fast and accurate to scramble as current scrambles?

Ensure extremely high-quality random seeding

The current Mersenne twister library limits us to 0xffffffff (16^8 or 4,294,967,296) seeds, so we'd need a good source of entropy.

We don't need ultimate cryptographic-level security because

• there are much easier ways to cheat in cubing than trying to find the seed used for some scrambles, and
• this is really hard in Javascript, anyhow.

However, it might be nice to expand the seed size to ensure that

• All states for all puzzles are possible, and equally likely (or very close). For 3x3x3, we need a seed significantly over 10^20
• Identical scrambles due to a duplicate seed are extremely unlikely.

initByArray(seedArray, seed) can get us a bit more randomness, but eventually we'll probably need a Javascript library with a huge period/seed. We need relatively few random numbers, so it can be slow.

Include scrambling hints/directions

Perhaps an (optional) cover sheet for the competition. Redundant info per scramble page should be minimal (and universally easy to understand, ideally language-independent).

• Square-1?
• Puzzle orientation images:

e.g. http://www.worldcubeassociation.org/regulations/scrambles/pyraminx.gif:

Staying in Cube Shape is good for scrambling

From Mike Hughey:

I just actually tried a few of the scrambles. I didn't realize that it starts off solving the cubic version, then moves away from square at the end. So it's kind of like one of my BLD solves in reverse - cool! That actually makes it much easier to scramble - the puzzle stays cubic until the last 7 or fewer moves or so. So if you mess up early, you'll know you did, and it will be relatively easy to solve and try again since you don't have to get to square (unless you mess up at the end). This seems a lot nicer than the old scrambler, actually. (http://www.speedsolving.com/forum/showthread.php?33576-Square-1-WCA-Style-Markov-Random-State-Scrambler-in-Javascript&p=682633&viewfull=1#post682633)

This should be mentioned somewhere.

Cross-Browser background animations

Vendor prefixes!