Recently, for some reason, I decided to write a program to solve Rubic
(I thought it is too easy, I was wrong). My approach is using normal depth-first
search + 'normal evaluator'.
I found such kind of 'normal evaluator' (evaluates the game by heuristic) should unavoidably result into searching in a local maxima, because the depth the
solver can reach is so much (in my case, 7). For exampe:
https://rubiks-cube-solver.com/solution.php?cube=0111111113222222222334333334144444644555555555663666666
This rubic example to solve has only two mismatched dices (smaller cubic), but
it takes 17 steps to solve!

Is there feasible strategy of the evaluator that can guide the search to the goa
l?

(Analogy of this phenomenon to me: like many problems we encountered, we may be
trapped in a local min/max. No matter how close it appears to the goal, the real
answer is no where near what we thought due to our ability to think deeper)

On 03/08/2022 14:29, wij wrote:
> Recently, for some reason, I decided to write a program to solve Rubic
> (I thought it is too easy, I was wrong). My approach is using normal depth-first
> search + 'normal evaluator'.
> I found such kind of 'normal evaluator' (evaluates the game by heuristic) should unavoidably result into searching in a local maxima, because the depth the
> solver can reach is so much (in my case, 7). For exampe:
> https://rubiks-cube-solver.com/solution.php?cube=0111111113222222222334333334144444644555555555663666666
> This rubic example to solve has only two mismatched dices (smaller cubic), but
> it takes 17 steps to solve!
>
> Is there feasible strategy of the evaluator that can guide the search to the goa
> l?
>
> (Analogy of this phenomenon to me: like many problems we encountered, we may be
> trapped in a local min/max. No matter how close it appears to the goal, the real
> answer is no where near what we thought due to our ability to think deeper)
>

As you realise, a local max may be some way from the global max (fully solved). Just off the top of
my head, it seems:

- moving 3 corners = around 8 moves +
twice a number of required conjugation moves
- moving 3 edges = around 6 moves +
twice a number of required conjugation moves
- so 2 wrong corners will be around 16 moves +
twice a number of required conjugation moves
- and 2 wrong edges will be around 12 moves +
twice a number of required conjugation moves

Not sure what the max number of conjugation moves - I think 5 should be safe, so if your look ahead
covers 26 moves, that should be enough to ensure any local max can be moved on to another improved
max, and eventually the cube will be solved.

But that's a daft strategy, since I've read that any cube can be unscrambled in max 20 moves - so if
you can look that far ahead, just search 20 moves deep until you solve it! (That will not be a good
way of solving the cube - I expect it is computationally unfeasible!?)

Otherwise, you need to do what humans do - identify sequences of moves that move just a small subset
of the blocks, and combine these successively to improve the state of the cube until it is solved.
My solution is to first solve edges (ignoring corners) then solve corners (keeping edges solved).
This is still going to take a lot of time, investigating the specifics of the cube puzzle, which I
don't think really interest you, so be warned! :)

Regards,
Mike.

On Wednesday, 3 August 2022 at 22:26:36 UTC+8, Mike Terry wrote:
> On 03/08/2022 14:29, wij wrote:
> > Recently, for some reason, I decided to write a program to solve Rubic
> > (I thought it is too easy, I was wrong). My approach is using normal depth-first
> > search + 'normal evaluator'.
> > I found such kind of 'normal evaluator' (evaluates the game by heuristic) should unavoidably result into searching in a local maxima, because the depth the
> > solver can reach is so much (in my case, 7). For exampe:
> > https://rubiks-cube-solver.com/solution.php?cube=0111111113222222222334333334144444644555555555663666666
> > This rubic example to solve has only two mismatched dices (smaller cubic), but
> > it takes 17 steps to solve!
> >
> > Is there feasible strategy of the evaluator that can guide the search to the goa
> > l?
> >
> > (Analogy of this phenomenon to me: like many problems we encountered, we may be
> > trapped in a local min/max. No matter how close it appears to the goal, the real
> > answer is no where near what we thought due to our ability to think deeper)
> >

Correction: 'Rubic' should be Rubik.
I misspelled it (In correcting my files, I lost some files. Damn it)

> As you realise, a local max may be some way from the global max (fully solved). Just off the top of
> my head, it seems:
>
> - moving 3 corners = around 8 moves +
> twice a number of required conjugation moves
> - moving 3 edges = around 6 moves +
> twice a number of required conjugation moves
> - so 2 wrong corners will be around 16 moves +
> twice a number of required conjugation moves
> - and 2 wrong edges will be around 12 moves +
> twice a number of required conjugation moves
>
> Not sure what the max number of conjugation moves - I think 5 should be safe, so if your look ahead
> covers 26 moves, that should be enough to ensure any local max can be moved on to another improved
> max, and eventually the cube will be solved.
What is "conjugation moves"? Some 'algebraic property' may also be very helpful.

> But that's a daft strategy, since I've read that any cube can be unscrambled in max 20 moves - so if
> you can look that far ahead, just search 20 moves deep until you solve it! (That will not be a good
> way of solving the cube - I expect it is computationally unfeasible!?)

"any cube can be unscrambled in max 20 moves" means to me that no rigor proof
is available and no computer has proved it.
If there is no good strategy, me thinks, searching 20 levels is in general not feasible for all computers.

> Otherwise, you need to do what humans do - identify sequences of moves that move just a small subset
> of the blocks, and combine these successively to improve the state of the cube until it is solved.
> My solution is to first solve edges (ignoring corners) then solve corners (keeping edges solved).
> This is still going to take a lot of time, investigating the specifics of the cube puzzle, which I
> don't think really interest you, so be warned! :)
>
> Regards,
> Mike.

In the example shown (only 2 corner mismatches. 'edges' are all solved), it may still need 17 moves.

On 03/08/2022 16:59, wij wrote:
> On Wednesday, 3 August 2022 at 22:26:36 UTC+8, Mike Terry wrote:
>> On 03/08/2022 14:29, wij wrote:
>>> Recently, for some reason, I decided to write a program to solve Rubic
>>> (I thought it is too easy, I was wrong). My approach is using normal depth-first
>>> search + 'normal evaluator'.
>>> I found such kind of 'normal evaluator' (evaluates the game by heuristic) should unavoidably result into searching in a local maxima, because the depth the
>>> solver can reach is so much (in my case, 7). For exampe:
>>> https://rubiks-cube-solver.com/solution.php?cube=0111111113222222222334333334144444644555555555663666666
>>> This rubic example to solve has only two mismatched dices (smaller cubic), but
>>> it takes 17 steps to solve!
>>>
>>> Is there feasible strategy of the evaluator that can guide the search to the goa
>>> l?
>>>
>>> (Analogy of this phenomenon to me: like many problems we encountered, we may be
>>> trapped in a local min/max. No matter how close it appears to the goal, the real
>>> answer is no where near what we thought due to our ability to think deeper)
>>>
>
> Correction: 'Rubic' should be Rubik.
> I misspelled it (In correcting my files, I lost some files. Damn it)
>
>> As you realise, a local max may be some way from the global max (fully solved). Just off the top of
>> my head, it seems:
>>
>> - moving 3 corners = around 8 moves +
>> twice a number of required conjugation moves
>> - moving 3 edges = around 6 moves +
>> twice a number of required conjugation moves
>> - so 2 wrong corners will be around 16 moves +
>> twice a number of required conjugation moves
>> - and 2 wrong edges will be around 12 moves +
>> twice a number of required conjugation moves
>>
>> Not sure what the max number of conjugation moves - I think 5 should be safe, so if your look ahead
>> covers 26 moves, that should be enough to ensure any local max can be moved on to another improved
>> max, and eventually the cube will be solved.
>
> What is "conjugation moves"? Some 'algebraic property' may also be very helpful.

Conjugation is a term from algebra (from group theory). If we have a transformation T, then we can
get new transformations from it, by "conjugating" it with other transforms as follows:

If A is some other transform:
- first apply A
- then apply T
- then apply the inverse of A.

the new transformation is written ATA^(-1).

Here is a cube example: suppose we have a series of moves T on a Rubik's cube that swap two
adjacent corners. But... we find ourselves wanting to swap two /opposite/ corners on the red face!
What can we do? The answer is

- first do a single twist to bring the two corners we want to act on together
- then apply T on those two (now adjacent) corners
- then we have to undo the original single twist to get the cube
back to its original condition (aside from the swapped corners)

We have performed a "conjugation" of T! The A in ATA^(-1) is the single twist - a kind of
preparation move before we applied T. The effect of conjugating T was broadly like the original T:
just two corners are swapped, except that it is like T has been made to act on different corners.

This is how conjugations are used generally in solving the cube. We have, say, a sequence of moves
that swap 3 corners which are in a particular relation to each other. Very rarely will be faced
with a cube that has corners we want to swap in /exactly/ the right orientation etc., but by using
suitable conjugation moves we can use our sequence in a wide variety of scenarios. (Typically we
can use it to solve 2 of the outstanding wrong corners in the puzzle.)

>
>> But that's a daft strategy, since I've read that any cube can be unscrambled in max 20 moves - so if
>> you can look that far ahead, just search 20 moves deep until you solve it! (That will not be a good
>> way of solving the cube - I expect it is computationally unfeasible!?)
>
> "any cube can be unscrambled in max 20 moves" means to me that no rigor proof
> is available and no computer has proved it.
> If there is no good strategy, me thinks, searching 20 levels is in general not feasible for all computers.

No, I think that is a proved result - search for "Rubik's cube maximum moves" or similar.

>
>> Otherwise, you need to do what humans do - identify sequences of moves that move just a small subset
>> of the blocks, and combine these successively to improve the state of the cube until it is solved.
>> My solution is to first solve edges (ignoring corners) then solve corners (keeping edges solved).
>> This is still going to take a lot of time, investigating the specifics of the cube puzzle, which I
>> don't think really interest you, so be warned! :)
>>
>> Regards,
>> Mike.
>
> In the example shown (only 2 corner mismatches. 'edges' are all solved), it may still need 17 moves.

Yes that sounds plausible, depending on how you count moves etc.. If I had that position I would
have to swap 3 corner (roughly 8 moves) and then swap them back slightly differently (another 8
moves or so).

Note: I'm not a cube record speed solver or memory solver - my interest is more /how/ to solve the
cube rather than doing it in minimum time. To do it in minimum time or number of moves, you would
memorise many more specific transforms than I use, each doing more specialised jobs in moving things
around. (I have just a basic 3-edge transform (4 moves) and 3-corner transform (8 moves), which is
enough with suitable conjugations.)

Mike.

On 03/08/2022 16:59, wij wrote:
> What is "conjugation moves"? [...]

If you're having to ask that, then I suggest that some preliminary
reading would be useful. Wiki:

https://en.wikipedia.org/wiki/Rubik%27s_Cube

is helpful and gives references, inc "how to" guides. [I have and can
commend the Singmaster and Berlekamp/Conway/Guy books, both very good
but out of date esp in respect of optimal solutions.]

> "any cube can be unscrambled in max 20 moves" means to me that no
> rigor proof is available and no computer has proved it.

In fact, a rigorous proof has been produced, partly with the aid
of computers; see, for example, the Wiki article just referenced. See
also

https://en.wikipedia.org/wiki/Optimal_solutions_for_Rubik%27s_Cube

....

> If there is
> no good strategy, me thinks, searching 20 levels is in general not
> feasible for all computers.

... and

http://www.cube20.org

They estimate approximately three seconds on a decent PC for a random
starting configuration to find an optimal solution, ~256 microseconds
to find a solution of no more than 20 moves [see the table about
half-way down the page]. Note that the time taken to prove the 20-
move limit for all configurations took rather longer; see the
discussion just below the table.

--
Andy Walker, Nottingham.
Andy's music pages: www.cuboid.me.uk/andy/Music
Composer of the day: www.cuboid.me.uk/andy/Music/Composers/Rubinstein

On Thursday, 4 August 2022 at 02:26:57 UTC+8, Andy Walker wrote:
> On 03/08/2022 16:59, wij wrote:
> > What is "conjugation moves"? [...]
>
> If you're having to ask that, then I suggest that some preliminary
> reading would be useful. Wiki:
>
> https://en.wikipedia.org/wiki/Rubik%27s_Cube
>
> is helpful and gives references, inc "how to" guides. [I have and can
> commend the Singmaster and Berlekamp/Conway/Guy books, both very good
> but out of date esp in respect of optimal solutions.]
> > "any cube can be unscrambled in max 20 moves" means to me that no
> > rigor proof is available and no computer has proved it.
> In fact, a rigorous proof has been produced, partly with the aid
> of computers; see, for example, the Wiki article just referenced. See
> also
>
> https://en.wikipedia.org/wiki/Optimal_solutions_for_Rubik%27s_Cube
>
> ...
> > If there is
> > no good strategy, me thinks, searching 20 levels is in general not
> > feasible for all computers.
> ... and
>
> http://www.cube20.org
>
> They estimate approximately three seconds on a decent PC for a random
> starting configuration to find an optimal solution, ~256 microseconds
> to find a solution of no more than 20 moves [see the table about
> half-way down the page]. Note that the time taken to prove the 20-
> move limit for all configurations took rather longer; see the
> discussion just below the table.
>
> --
> Andy Walker, Nottingham.
> Andy's music pages: www.cuboid.me.uk/andy/Music
> Composer of the day: www.cuboid.me.uk/andy/Music/Composers/Rubinstein

Thanks Andy Walker. The info. provided should be enough for quick start.