Browse Groups

• ## algorithms for computer solving the 4x4x4

(5)
• NextPrevious
• Hi everyone, I ve worked out an algorithm for a computer solver for the 4x4x4 (actually I ve got 2 variations) They work by matching up the edges and solving
Message 1 of 5 , Aug 29, 2006
View Source
Hi everyone,

I've worked out an algorithm for a computer solver for the 4x4x4
(actually I've got 2 variations) They work by matching up the edges
and solving the centers and then simply solving like a 3x3x3. They
average slightly over 60 moves stm but the solutions can be made even
shorter by upgrading the Thistlethwaite portions to a Kociemba-style

Go here:
http://www.geocities.com/c_w_tsai/solver4/

for descriptions and sample solutions.
• Hi! Very interesting methods. I will study them later. How do u go about solving each step? Trial and error only? Are they suitable for speeding at all??
Message 1 of 5 , Aug 30, 2006
View Source
Hi!

Very interesting methods. I will study them later. How do u go about
solving each step? Trial and error only? Are they suitable for
speeding at all??

Cheers!

-Per

> --- In speedsolvingrubikscube@yahoogroups.com, "ct" <c_w_tsai@...>
wrote:
>
> Hi everyone,
>
> I've worked out an algorithm for a computer solver for the 4x4x4
> (actually I've got 2 variations) They work by matching up the edges
> and solving the centers and then simply solving like a 3x3x3. They
> average slightly over 60 moves stm but the solutions can be made
even
> shorter by upgrading the Thistlethwaite portions to a Kociemba-style
> solution or possibly made optimal.
>
> Go here:
> http://www.geocities.com/c_w_tsai/solver4/
>
> for descriptions and sample solutions.
>
• This is very similar in nature to my 4x4x4 computer method. Tsai used 7 or 8 stages while I used only 5. Still he seems to be getting very close to the typical
Message 1 of 5 , Sep 1, 2006
View Source
This is very similar in nature to my 4x4x4 computer method. Tsai used
7 or 8 stages while I used only 5. Still he seems to be getting very
close to the typical number of moves that I get with my solver (in the
neighborhood of 60). While I decided to look at a multi-stage solution
ending with the "4x4x4 squares coset," it's interesting to see that
someone else has looked into using a different set of stages. In this
case, the later stages eliminate the inner slice moves altogether, so
that these later stages are like solving a 3x3x3.

I had suspected Tsai did something like an IDA* search for each step
since he didn't show any tables giving numbers of positions of a given
distance from the goal state for each step. It would be nice to have
worst-case number of moves for each step, but that would require
carrying out a God's algorithm calculation, or running his IDA* search
for every effectively unique position of each step. I would have to
believe that for the 7-stage (or 8-stage) method, they would add up to
more than 79, the value I got from my 5-stage method. Fewer stages
should result in a lower worst case value.

I note that like the current version of my solver, it appears that
Tsai's solver does not optimize across the stage boundaries. For
instance, if the last move of one stage is F, and the first move of
the next stage is F2, it does not combine the two moves to become F'.
This simple optimization technique could be used to make a small
decrease in the number of moves used on average.

Since the 4x4x4 does not have fixed centers, step 1 would only need to
put the R and L centers on any opposite faces, not necessarily the R
and L faces. Of course, then either an explicit cube reorientation
would need to be applied so that those faces become the R and L faces,
or the moves for the rest of solution must be remapped accordingly.
That is, the solver could reorient the cube for its internal workings,
but would output the moves so that they correspond to the initial
orientation of the cube. That is what my solver does. So the solved
cube may end up with the colors in a different orientation, but it's
still considered solved. With my solver, the cube may end up in any of
the 24 possible orientations. I haven't checked Tsai's examples, but
from his description, I am guessing he forces each color to end up on
a specific face.

One other thing I noticed is that in step 4, front and back face
layers are restricted to half-turns, but in step 5, quarter turns of
those layers are allowed again. (In the 8-step version, this applies
to right and left face layers as well, half-turns in step 3 and 4, but
quarter turns allowed again in step5.) So his method doesn't have the
property that every step uses only a subset of moves of prior steps,
although I think this is the only exception to that.

I think it should be possible to create a solver for the 4x4x4 using
only four stages, and perhaps only three stages, using an IDA* type of
search in each stage. It perhaps may be a challenge to get good
quality pruning tables for all stages to be compact enough to all fit
in memory at the same time. It might be interesting to know how much
memory is used for pruning tables in Tsai's program. Because of the
number of stages, I am guessing he doesn't need very large tables and
they all reside in memory at the same time.

As for solving by humans, Ryan Heise once looked at developing a
"human version" of the Thistlethwaite algorithm. See message 5113. So
it may be possible to extend that idea to the 4x4x4-specific steps of
Tsai's method (or my method as well). Of course, a computer can
calculate the parity of the edges faster than a human can, so avoiding
the parity issues may still be a problem as it seems to be with other
4x4x4 methods that simplify the 4x4x4 to a 3x3x3.

- Bruce
--- In speedsolvingrubikscube@yahoogroups.com, "ct" <c_w_tsai@...> wrote:
>
> > Very interesting methods. I will study them later. How do u go
> > solving each step? Trial and error only? Are they suitable for
> > speeding at all??
> >
>
> IDA*. I would guess they are not suitable for speeding.
>
>
> > >
> > > Hi everyone,
> > >
> > > I've worked out an algorithm for a computer solver for the 4x4x4
> > > (actually I've got 2 variations) They work by matching up the
> edges
> > > and solving the centers and then simply solving like a 3x3x3.
> They
> > > average slightly over 60 moves stm but the solutions can be made
> > even
> > > shorter by upgrading the Thistlethwaite portions to a Kociemba-
> style
> > > solution or possibly made optimal.
> > >
> > > Go here:
> > > http://www.geocities.com/c_w_tsai/solver4/
> > >
> > > for descriptions and sample solutions.
> > >
> >
>
• ... used ... very ... the ... solution ... this ... so ... step ... given ... have ... search ... up to ... Maybe. But it ends up solving like a 3x3x3, which I
Message 1 of 5 , Sep 1, 2006
View Source
> This is very similar in nature to my 4x4x4 computer method. Tsai
used
> 7 or 8 stages while I used only 5. Still he seems to be getting
very
> close to the typical number of moves that I get with my solver (in
the
> neighborhood of 60). While I decided to look at a multi-stage
solution
> ending with the "4x4x4 squares coset," it's interesting to see that
> someone else has looked into using a different set of stages. In
this
> case, the later stages eliminate the inner slice moves altogether,
so
> that these later stages are like solving a 3x3x3.
>
> I had suspected Tsai did something like an IDA* search for each
step
> since he didn't show any tables giving numbers of positions of a
given
> distance from the goal state for each step. It would be nice to
have
> worst-case number of moves for each step, but that would require
> carrying out a God's algorithm calculation, or running his IDA*
search
> for every effectively unique position of each step. I would have to
> believe that for the 7-stage (or 8-stage) method, they would add
up to
> more than 79, the value I got from my 5-stage method. Fewer stages
> should result in a lower worst case value.

Maybe. But it ends up solving like a 3x3x3, which I found really
attractive, and there has been extensive work done with that.

>
> I note that like the current version of my solver, it appears that
> Tsai's solver does not optimize across the stage boundaries. For
> instance, if the last move of one stage is F, and the first move of
> the next stage is F2, it does not combine the two moves to become
F'.
> This simple optimization technique could be used to make a small
> decrease in the number of moves used on average.
>

That's true. I didn't think it was worth the effort. :) Probably a
savings of 2 or 3 moves max.

> Since the 4x4x4 does not have fixed centers, step 1 would only
need to
> put the R and L centers on any opposite faces, not necessarily the
R
> and L faces. Of course, then either an explicit cube reorientation
> would need to be applied so that those faces become the R and L
faces,
> or the moves for the rest of solution must be remapped accordingly.
> That is, the solver could reorient the cube for its internal
workings,
> but would output the moves so that they correspond to the initial
> orientation of the cube. That is what my solver does. So the solved
> cube may end up with the colors in a different orientation, but
it's
> still considered solved. With my solver, the cube may end up in
any of
> the 24 possible orientations. I haven't checked Tsai's examples,
but
> from his description, I am guessing he forces each color to end up
on
> a specific face.

That's correct. My solver doesn't consider the cube solved unless
it's in a very specific orientation. You'd have to do it manually
for all 24 orientations. :S

>
> One other thing I noticed is that in step 4, front and back face
> layers are restricted to half-turns, but in step 5, quarter turns
of
> those layers are allowed again. (In the 8-step version, this
applies
> to right and left face layers as well, half-turns in step 3 and 4,
but
> quarter turns allowed again in step5.) So his method doesn't have
the
> property that every step uses only a subset of moves of prior
steps,
> although I think this is the only exception to that.

Yeah, I thought it was interesting that you could not allow certain
moves in a step and then allow it again later.

>
> I think it should be possible to create a solver for the 4x4x4
using
> only four stages, and perhaps only three stages, using an IDA*
type of
> search in each stage. It perhaps may be a challenge to get good
> quality pruning tables for all stages to be compact enough to all
fit
> in memory at the same time. It might be interesting to know how
much
> memory is used for pruning tables in Tsai's program. Because of the
> number of stages, I am guessing he doesn't need very large tables
and
> they all reside in memory at the same time.

For the 8-step algorithm, only about 80 kB. Several hundred kB for
the 7-step. But I still haven't got good tables for the 2nd step of
the 7-step (factor on the order of 10^11). I still need to think of
better tables for that... I found that sometimes it would find a
solution very quickly (like a second) while other times I could let
it search for an hour and still not find a solution (probably due to
my not-so-good tables and maybe the solution was too deep) What I
ended up doing was: limit the step 2 search to a maximum depth of 9
and if there was no solution found, it goes to the next step 1
solution. I liked how it worked so i did the same with the 8-step
algorithm with a max depth of 8. My 7-step solver takes about half a
minute, the 8-step one takes like 5 to 10 seconds.

>
> As for solving by humans, Ryan Heise once looked at developing a
> "human version" of the Thistlethwaite algorithm. See message 5113.
So
> it may be possible to extend that idea to the 4x4x4-specific steps
of
> Tsai's method (or my method as well). Of course, a computer can
> calculate the parity of the edges faster than a human can, so
avoiding
> the parity issues may still be a problem as it seems to be with
other
> 4x4x4 methods that simplify the 4x4x4 to a 3x3x3.
>

I also thought of Ryan's human thistlethwaite version :)

> - Bruce
• Hi :-) I feel that a 7/8 step solver would make up much smaller pruning tables, and it should be able to run on computers with less (normal) memory (?). A
Message 1 of 5 , Sep 2, 2006
View Source
Hi :-)

I feel that a 7/8 step solver would make up much smaller pruning
tables, and it should be able to run on computers with less (normal)
memory (?). A slightly longer solution on average should also
indicate a shorter solution time?

Also, letting the solver not solve optimally at each step will allow
increasingly better solutions to be found. I estimate that sub-100
solutions can be found rapidly :-)

Charles'methods are also somewhat closer in nature to the normal
pairing-up methods compared with Bruce's 5-stage method. How about
relaxing number of stages to an even higher number? Will we be able
to approach a "humanly doable" method with a "decent" maximum number
of moves overall ??

Cheers!

-Per

> --- In speedsolvingrubikscube@yahoogroups.com, "Bruce Norskog"
<brnorsk@...> wrote:
>
> This is very similar in nature to my 4x4x4 computer method. Tsai
used
> 7 or 8 stages while I used only 5. Still he seems to be getting
very
> close to the typical number of moves that I get with my solver (in
the
> neighborhood of 60). While I decided to look at a multi-stage
solution
> ending with the "4x4x4 squares coset," it's interesting to see that
> someone else has looked into using a different set of stages. In
this
> case, the later stages eliminate the inner slice moves altogether,
so
> that these later stages are like solving a 3x3x3.
>
> I had suspected Tsai did something like an IDA* search for each
step
> since he didn't show any tables giving numbers of positions of a
given
> distance from the goal state for each step. It would be nice to
have
> worst-case number of moves for each step, but that would require
> carrying out a God's algorithm calculation, or running his IDA*
search
> for every effectively unique position of each step. I would have to
> believe that for the 7-stage (or 8-stage) method, they would add
up to
> more than 79, the value I got from my 5-stage method. Fewer stages
> should result in a lower worst case value.
>
> I note that like the current version of my solver, it appears that
> Tsai's solver does not optimize across the stage boundaries. For
> instance, if the last move of one stage is F, and the first move of
> the next stage is F2, it does not combine the two moves to become
F'.
> This simple optimization technique could be used to make a small
> decrease in the number of moves used on average.
>
> Since the 4x4x4 does not have fixed centers, step 1 would only
need to
> put the R and L centers on any opposite faces, not necessarily the
R
> and L faces. Of course, then either an explicit cube reorientation
> would need to be applied so that those faces become the R and L
faces,
> or the moves for the rest of solution must be remapped accordingly.
> That is, the solver could reorient the cube for its internal
workings,
> but would output the moves so that they correspond to the initial
> orientation of the cube. That is what my solver does. So the solved
> cube may end up with the colors in a different orientation, but
it's
> still considered solved. With my solver, the cube may end up in
any of
> the 24 possible orientations. I haven't checked Tsai's examples,
but
> from his description, I am guessing he forces each color to end up
on
> a specific face.
>
> One other thing I noticed is that in step 4, front and back face
> layers are restricted to half-turns, but in step 5, quarter turns
of
> those layers are allowed again. (In the 8-step version, this
applies
> to right and left face layers as well, half-turns in step 3 and 4,
but
> quarter turns allowed again in step5.) So his method doesn't have
the
> property that every step uses only a subset of moves of prior
steps,
> although I think this is the only exception to that.
>
> I think it should be possible to create a solver for the 4x4x4
using
> only four stages, and perhaps only three stages, using an IDA*
type of
> search in each stage. It perhaps may be a challenge to get good
> quality pruning tables for all stages to be compact enough to all
fit
> in memory at the same time. It might be interesting to know how
much
> memory is used for pruning tables in Tsai's program. Because of the
> number of stages, I am guessing he doesn't need very large tables
and
> they all reside in memory at the same time.
>
> As for solving by humans, Ryan Heise once looked at developing a
> "human version" of the Thistlethwaite algorithm. See message 5113.
So
> it may be possible to extend that idea to the 4x4x4-specific steps
of
> Tsai's method (or my method as well). Of course, a computer can
> calculate the parity of the edges faster than a human can, so
avoiding
> the parity issues may still be a problem as it seems to be with
other
> 4x4x4 methods that simplify the 4x4x4 to a 3x3x3.
>
> - Bruce
> --- In speedsolvingrubikscube@yahoogroups.com, "ct" <c_w_tsai@>
wrote:
> >
> > > Very interesting methods. I will study them later. How do u go
> > > solving each step? Trial and error only? Are they suitable for
> > > speeding at all??
> > >
> >
> > IDA*. I would guess they are not suitable for speeding.
> >
> >
> > > >
> > > > Hi everyone,
> > > >
> > > > I've worked out an algorithm for a computer solver for the
4x4x4
> > > > (actually I've got 2 variations) They work by matching up
the
> > edges
> > > > and solving the centers and then simply solving like a
3x3x3.
> > They
> > > > average slightly over 60 moves stm but the solutions can be
> > > even
> > > > shorter by upgrading the Thistlethwaite portions to a
Kociemba-
> > style
> > > > solution or possibly made optimal.
> > > >
> > > > Go here:
> > > > http://www.geocities.com/c_w_tsai/solver4/
> > > >
> > > > for descriptions and sample solutions.
> > > >
> > >
> >
>
Your message has been successfully submitted and would be delivered to recipients shortly.
• Changes have not been saved
Press OK to abandon changes or Cancel to continue editing
• Your browser is not supported
Kindly note that Groups does not support 7.0 or earlier versions of Internet Explorer. We recommend upgrading to the latest Internet Explorer, Google Chrome, or Firefox. If you are using IE 9 or later, make sure you turn off Compatibility View.