Kociemba explained verbally?

[Dapianokid]

Thank you so much Lucas. I like math, so I expected these methods to be easy to grasp. When they weren't, I gave up in frustration. I love this basic introduction to group theory and cube math. It makes so much more sense when explained like that.

 

[Stefan]

I love this basic introduction to group theory and cube math. It makes so much more sense when explained like that.

Where do you see an introduction to group theory?

 

[Lucas Garron]

But in Kociemba, you also need to enumerate a lot of phase 1 solutions. Maybe not at the shortest phase 1 lengths, but then later when you're trying longer phase 1 lengths. And I don't see why that's easily possible but with F2L it's impossible. Let's say the whole given cube can be solved in x moves and you're looking for phase 1 solutions of length x, aren't then both versions pretty much even enumerating all whole cube solutions?

You can't start pruning the search aggressively until you've found a few solutions. Kociemba starts finding solutions with about 10 moves in phase one. I don't know God's number to solve F2L on average, but I'd guess it's significantly higher -- enough to make the initial BFS really impractical (at least, when "real" Kociemba is an option).

Btw, would we ever really "Try all the solutions that take 25 moves for F2L", given that the whole cube can always be solved in 20 moves so at phase 1 length 20 we'd find a phase 2 solution of length 0 and stop?

In fact, we can extend this and keep looking. Here's our plan:
...
We abort the original 26-plan and continue our search wtih a new upper bound:
...
For 3x3x3, we happen to know that the optimal solution must be at most 20 moves... but that's only because we know God's number. The approach works even if we don't know God's number.

You should stick to "fewer than" (or subtract 1).
And you have "1 + 8 = 25" and "28 moves for F2L" and "25 - 25 = 7" typos.

Yeah, I do have a few consistency issues. I'll fix those.

 

[Lucas Garron]

But it really does 5-8 as 2 phases, right?

Yeah, it uses min2phase. ;-)
The name is technically "TPR-4x4x4-Solver", which is "Three-Phase-Reduction Solver + 3x3x3 Solver". From the perspective of the algorithm, though, the 3x3x3 stage is a 1-phase black box. You could call it a 5-phase solution overall, but I'm not sure if that's much more accurate.

 

[cuBerBruce]

The name is technically "TPR-4x4x4-Solver", which is "Three-Phase-Reduction Solver + 3x3x3 Solver". From the perspective of the algorithm, though, the 3x3x3 stage is a 1-phase black box. You could call it a 5-phase solution overall, but I'm not sure if that's much more accurate.

But if the pseudo 3x3x3 phase actually used a conventional single-phase solver, you would get slightly shorter solutions (gnerally speaking) and execution time could be quite lengthy (based on the performance of available 3x3x3 single-phase solvers). So even though the pseudo 3x3x3 phase may be viewed as a black box from a point of view of coding the 4x4x4 solver, as far as how the solver works internally, I think it's clearly a 5-phase solver. I would say it's a 5-phase solver where optimization is performed across the last two stages, but not across any of the other phases.

I suppose you can be more general about what you might consider a "phase" to consist of. Although the pseudo 3x3x3 portion of the solve is internally implemented as two phases, the fact that the 4x4x4 solver treats it as a black box means that the two Kociemba phases have to be treated as a single "phase" from the point of view of trying to do any optimizations across phases. So in that sense it may make some sense to talk about it as 4 phases. But the fact that the code treats the 3x3x3 phase as a black box doesn't really change the fact that a total of 5 phases are actually used in producing the solution (which is inverted to create the scramble).

 

[bcube]

If we keep going, we reach a point where any solution we haven't considered must be longer than the one we have -- so our solution is optimal.

I think this part deserves a bit of clarification.

Quoting Herbert himself: "In principle you can run the [Kociemba's two-phase] algorithm until it finds a phase 1 suboptimal solution for which the phase 2 solution has length 0. In this case you have found the optimal solution.

But this is not the intention of the algorithm. Usually you just run it until the desired total length (phase 1 length + phase 2 length) is below a certain treshhold." but without any guarantee that the solution found is optimal.

Also by Herbert himself: "My two phase algorithm was not designed to solve the cube optimally, only suboptimally with decent computational expense."

So yes, in principle you are right, but in practice that is not how Kociemba's two-phase algorithm usually works.

P.S. maybe by "our solution is optimal" you meant "our solution is optimal but not proved to be optimal" - but then I would ask how do you know that our solution is optimal?

P.S.2 for those who didn't know: how optimal solver in Cube Explorer works, link 2