Thread: "ClojureScript scrambler and some ideas about a near-optimal solver"

From: Andy F <legomany3448@gmail.com>
Date: Wed, 1 Aug 2018 00:49:54 -0400
Subject: ClojureScript scrambler and some ideas about a near-optimal solver



--0000000000000706af0572586d27
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

Hello again!

I have been hard at work the last several days creating my scrambler
(much thanks to
pentaquark394 for the original Python script!), solution video
, and solution explanation
LUqt0/edit?usp=3Dsharing>.
(If anyone is planning on using my Clojure code, feel free, but be aware
that I may change the piece order soon.)

I agree with Marc that a compilation of useful algorithms is an excellent
idea; perhaps a wiki page may
be in order?



Now on the subject of scramblers ...

The ideal scrambler for any puzzle would generate a random solvable state
and produce the optimal sequence of moves to arrive at this state.
Generating the "optimal" move sequence is rarely practical, so most 3^3
scramblers simply find a near-optimal sequence of moves using Kociemba's
2-stage algorithm or similar
, which
is still usually around 20 moves. I don't think there's been much research
into this problem on the 2^4, so I'll throw some numbers here just to get
some Fermi estimates. I should probably preface this by saying that I am by
no means an expert in combinatorics or optimal cube solving, and that I am
probably glossing over a numerous details that matter more than
easy-to-compute numbers, but I want to get some conversation started about
this.

# 2x2x2 states
7! * 3^6 =3D 3.67416e+6

# 3x3x3 states
8! * 3^7 * 12! * 2^11 / 2 =3D 4.325200327449e+19

# 4x4x4 states
8! * 3^7 * 24!^2 / 24^7 =3D 7.4011968415649e+45

# 2x2x2x2 states
s24 =3D 15! / 2 * 12^15 / 3 =3D 3.3578945333849e+27
# Taking one piece as completely solved, there are 15 pieces to permute,
divided by 2 two for permutation parity, and 15 pieces to orient (12
orientations each), divided by 3 for corner twist parity

I think the 2^4 is most comparable to the 3^3 in terms of search space, but
even then it has nearly 10^8 times as many states.

Kociemba's algorithm consists of two steps: orientation (reduction from D R L F B> to ) and permutation (solving the puzzle using
). These numbers give a rough estimate of the search space
involved with these steps, so any 2^4 algorithm should aim for similar
numbers in each stage.

# Kociemba 3^3 stage 1 cases
3^7 * 2^11 =3D 4.478976e+6

# Kociemba 3^3 stage 2 cases
8! * 12! / 2 =3D 9.656672256e+12

There's no way to adapt this algorithm directly to the 2^4 without having
an unreasonably large search space. Instead, I've come up with an outline
for a 3-stage method as follows:

1. Orient U/D stickers (in vertical orientation)
2. Orient and separate I/O stickers
3. Permute all pieces

This produces some quite reasonable-looking (using Kociemba's stages as a
baseline) case counts.

# Stage 1 cases
4^15 =3D 1.073741824e+9
# Taking one piece as solved, there are 15 pieces to orient; we only care
about the position of the sticker that belongs on U/D, and there are four
places this could be

# Stage 2 cases
3^14 * (15! / 8! / 8!) =3D 3.847300689375e+9
# Taking one piece as solved, there are 15 pieces to orient, divided by 3
for corner twist parity, and 15 pieces to permute, but divide by 8! for I
and 8! for O since we don't care about permutation within the layer

# Stage 3 cases
7! * 8! / 2 =3D 1.6257024e+8
# Taking one piece as solved, there are 7 pieces to permute on the I layer
and 8 pieces to permute on the O layer, divided by 2 for permutation parity
# This is basically the PBBL step that I've proposed elsewhere -- the
number here does not accounting for any symmetric cases, of course

Besides producing eerily even case counts (I'm not sure how well these
correspond to the average time or move count required to solve the step), I
chose these steps based on the move subsets they permit. Because the
primary purpose of this is to produce easy-to-execute scramble sequences,
I've only included certain easy-to-execute moves:

Stage 1:
{UD}[{xyz}{123}] - 18
U[U{123}] - 3
D[D{123}] - 3
{RLFB}2 - 4
vertical restack - 1
=3D 29 moves

Stage 2:
{UD}[{xyz}{123}] - 18
U[U{123}] - 3
D[D{123}] - 3
{RLFB}2 - 4
=3D 28 moves

Stage 3:
{UD}[y{123}] - 6
{UD}[{xz}2] - 4
U[U{123}] - 3
D[D{123}] - 3
{RLFB}2 - 4
=3D 20 moves

Note that I've included some moves, such as U[U], that toggle permutation
parity. This is intentional; my primary purpose here is not necessarily to
create a random-state *solver*, but a random-state *scrambler*. A
random-state scrambler that is guaranteed to produce a valid state needs
not worry about performing parity-violating sequences, as long as the whole
scramble preserves parity. With this taken into account, the number of
cases for stage 3 should really be 7! * 8! =3D 2.032128e+8, which is still
fine.

Note that in stage 2, only the restacking move is disallowed (which makes
sense since now the "frame" of the puzzle would be fixed), and in stage 3
the set D> has been reduced to D>, turning
the puzzle into what are effectively two PBL-ready 2^3 puzzles that happen
to be entangled such that a move on one must be accompanied by a move on
the other in the same direction.

I'm curious to hear other ideas about this, and whether anyone would be
willing to try writing such a solver (bonus points if it's in Clojure =F0=
=9F=98=89)
since doing this efficiently goes quite beyond my current CS knowledge,
though I'd be willing to give it a shot anyway.

- Andy

P.S. All of my future emails will be sent from my ajfarkas12 address rather
than legomany3448.

--0000000000000706af0572586d27
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

Hello again!

I have been hard at =
work the last several days creating my CE/2x2x2x2-Scrambler">scrambler=C2=A0(much thanks to pentaquark394 for =
the original Python script!), solu=
tion video
, and l-XJ50Q96wOvy-grfpBVy_wmv9Ed_CLUqt0/edit?usp=3Dsharing">solution explanatio=
n
. (If anyone is planning on using my Clojure code, feel free, but be a=
ware that I may change the piece order soon.)

I agree wi=
th Marc that a compilation of useful algorithms is an excellent idea; perha=
ps a wiki page=C2=
=A0may be in order?



=
Now on the subject of scramblers ...

The ideal scr=
ambler for any puzzle would generate a random solvable state and produce th=
e optimal sequence of moves to arrive at this state. Generating the "o=
ptimal" move sequence is rarely practical, so most 3^3 scramblers simp=
ly find a near-optimal sequence of moves using rg/math/imptwophase.htm">Kociemba's 2-stage algorithm or "https://en.wikipedia.org/wiki/Optimal_solutions_for_Rubik's_Cube">simi=
lar
, which is still usually around 20 moves. I don't think there=
9;s been much research into this problem on the 2^4, so I'll throw some=
numbers here just to get some Fermi estimates. I should probably preface t=
his by saying that I am by no means an expert in combinatorics or optimal c=
ube solving, and that I am probably glossing over a numerous=C2=A0details t=
hat matter more than easy-to-compute numbers, but I want to get some conver=
sation started about this.

, monospace"># 2x2x2 states
ospace,monospace">7! * 3^6 =3D=C2=A0pace,monospace">3.67416e+6
ace">
# 3x3x3 stat=
es
8! * 3^7 * 12! * 2^=
11 / 2 =3D 4.325200327449e+19
ospace">
# 4x4x4 s=
tates
8! * 3^7 * 24!^2=
/ 24^7 =3D=C2=A0
7.4=
011968415649e+45

<=
/font>
# 2x2x2x2 states>
s24 =3D 15! / 2=
* 12^15 / 3 =3D=C2=A0
">3.3578945333849e+27
=
# Taking one piece as completely solved, there are 15 pieces to permute, di=
vided by 2 two for permutation parity, and 15 pieces to orient (12 orientat=
ions each), divided by 3 for corner twist parity

>
I think the 2^4 is most comparable to the 3^3 in terms of search spac=
e, but even then it has nearly 10^8 times as many states.

iv>
Kociemba's algorithm consists of two steps: orientation (reduct=
ion from <U D R L F B> to <U D R2 L2 F2 B2>) and permutation (s=
olving the puzzle using <U D R2 L2 F2 B2>). These numbers give a roug=
h estimate of the search space involved with these steps, so any 2^4 algori=
thm should aim for similar numbers in each stage.

=
# Kociemba 3^3 stage 1 casesv>
3^7 * 2^11 =3D 4.478976e+6>

face=3D"monospace, monospace"># Kociemba 3^3 stage 2 cases
v>8! * 12! / 2 =3D 9.656672256e+12t>

There's no way to adapt this algorithm dire=
ctly to the 2^4 without having an unreasonably large search space. Instead,=
I've come up with an outline for a 3-stage method as follows:
v>
  1. Orient U/"monospace, monospace">D stickers (in vertical orientation)
  2. =
    Orient and separate I/=3D"monospace, monospace">O stickers
  3. Permute all pieces
  4. =
This produces some quite reasonable-looking (using Kociemba=
's stages as a baseline) case counts.

ce=3D"monospace, monospace"># Stage 1 cases
monospace, monospace">4^15 =3D 1.073741824e+9
=3D"monospace, monospace"># Taking one piece as solved, there are 15 pieces=
to orient; we only care about the position of the sticker that belongs on =
U/D, and there are four places this could be
"monospace, monospace">
pace"># Stage 2 cases
=
3^14 * (15! / 8! / 8!) =3D 3.847300689375e+9
"monospace, monospace"># Taking one piece as solved, there are 15 pieces to=
orient, divided by 3 for corner twist parity, and 15 pieces to permute, bu=
t divide by 8! for I and 8! for O since we don't care about permutation=
within the layer

=
# Stage 3 cases>
7! * 8! / 2 =3D 1.6257024e+=
8
# Taking one piece a=
s solved, there are 7 pieces to permute on the I layer and 8 pieces to perm=
ute on the O layer, divided by 2 for permutation parity
ont face=3D"monospace, monospace"># This is basically the PBBL step that I&=
#39;ve proposed elsewhere -- the number here does not accounting for any sy=
mmetric cases, of course

Besides producing =
eerily even case counts (I'm not sure how well these correspond to the =
average time or move count required to solve the step), I chose these steps=
based on the move subsets they permit. Because the primary purpose of this=
is to produce easy-to-execute scramble sequences, I've only included c=
ertain easy-to-execute moves:

Stage 1:
<=
div>{UD}[{xyz}{123}] - 18
<=
div>U[U{123}] - 3
t face=3D"monospace, monospace">D[D{123}] - 3
=3D"monospace, monospace">{RLFB}2 - 4
ace, monospace">vertical restack - 1
=3D 29 movesiv>

Stage 2:
e">{UD}[{xyz}{123}] - 18
e">U[U{123}] - 3
D[D{1=
23}] - 3
{RLFB}2 - 4font>
=3D 28 moves

Stage 3:
ont face=3D"monospace, monospace">{UD}[y{123}] - 6
ace=3D"monospace, monospace">{UD}[{xz}2] - 4
"monospace, monospace">U[U{123}] - 3
ce, monospace">D[D{123}] - 3
space">{RLFB}2 - 4
=3D 20 moves

N=
ote that I've included some moves, such as U[U], that toggle permutatio=
n parity. This is intentional; my primary purpose here is not necessarily t=
o create a random-state=C2=A0solver, but a random-state scrambler=
. A random-state scrambler that is guaranteed to produce a valid state =
needs not worry about performing parity-violating sequences, as long as the=
whole scramble preserves parity. With this taken into account, the number =
of cases for stage 3 should really be=C2=A0ce">7! * 8! =3D 2.032128e+8, which is still fine.

v>
Note that in stage 2, only the restacking move is disallowed (which =
makes sense since now the "frame" of the puzzle would be fixed), =
and in stage 3 the set <U<x z> D<x z>> has been reduced t=
o <U<x2 z2> D<x2 z2>>, turning the puzzle into what are e=
ffectively two PBL-ready 2^3 puzzles that happen to be entangled such that =
a move on one must be accompanied by a move on the other in the same direct=
ion.

I'm curious to hear other ideas about thi=
s, and whether anyone would be willing to try writing such a solver (bonus =
points if it's in Clojure=C2=A0=F0=9F=98=89) since doing this efficient=
ly goes quite beyond my current CS knowledge, though I'd be willing to =
give it a shot anyway.

- Andy

=
P.S. All of my future emails will be sent from my ajfarkas12 address r=
ather than legomany3448.



--0000000000000706af0572586d27--





Return to MagicCube4D main page
Return to the Superliminal home page