# For 5x5x5 Solving Programs

Status
Not open for further replies.

#### unsolved

##### Member
I'm just copying the ideas of earlier computer solvers like Thistlethwaite's algorithm, Kociemba's, Shuang Chen's, etc. where the pieces are just "partially solved" in an early stage and fully solved in the final stage; this strategy generally seems to lead to a low-ish move count.
What are the intermediate goals? I never fully understood what the objective was, other than reducing the number of moves spawned by the move generator by selectively getting certain pieces to certain locations so as to not ever have to worry about having to make those moves later.

This can be decomposed as [R' : [2D, F' D F]] (3-cycle of wings) with [D2, 3R2] (a pair of 2-cycles of midges) inserted to cancel one move.
It's amazing what brute force will uncover without any intelligence behind it though!

I coded the third phase over the past two days, and I expect to have the full solver done in a few more days. I'll describe it in more detail if my five-phase reduction algorithm doesn't turn out to be fatally flawed.
I'll have to take a look into these multi-phase reduction algorithms at one point.

#### xyzzy

##### Member
What are the intermediate goals? I never fully understood what the objective was, other than reducing the number of moves spawned by the move generator by selectively getting certain pieces to certain locations so as to not ever have to worry about having to make those moves later.
For my current approach, the first phase separates the UD centres to the UD faces (but possibly with U centres on the D face and vice versa), the second phase separates RL centres and FB centres as well as ensuring that the permutation of all the wing pieces is even. This prevents the occurrence of a parity case during the edge grouping step (which I've yet to code). The third phase (sort of) orients all the midges and wings, the fourth phase will fully solve some of the centres along with forming some tredges, and the fifth phase will complete the reduction to a 3x3x3 (with edges already oriented, as in the ZZ method).

And yeah, reducing the number of moves the move generator can spawn is part of the objective. Some of the benefits of using a multi-phase solver (in general, not just for reduction) are that it doesn't require storing an alg database, it doesn't constantly destroy progress built up in earlier stages only to rebuild it again, and it generally brings a lot of pieces "closer" (in a vague, air-quotes sense) to their solved locations at once.

On smaller puzzles, if we design our algorithm so that each of the phases isn't too large, we can do a breadth-first search for each phase and add up the maximum distances to get an upper bound on God's number. (This doesn't seem to be feasible with the phases I'm using for the 5x5x5, unfortunately.)

I'll have to take a look into these multi-phase reduction algorithms at one point.
Charles Tsai's four-phase reduction for the 4x4x4 is a good starting point, although the lack of fixed centres on the 4x4x4 may make it a bit confusing.

Edit (2016-05-18): Current progress on my solver:
R Dw2 L Uw B2 Fw Bw' Rw2 Uw2 F' Rw // phase 1
B Uw L Rw2 Uw' R2 F Dw // phase 2
Dw2 R F Uw2 L' Fw2 U F' L Rw2 F // phase 3.1
F Uw2 Dw2 Rw2 Lw2 F // phase 3.2
B2 Fw2 Lw2 Dw2 Bw2 D' Fw2 Rw2 Dw2 Bw2 Rw2 Bw2 // phase 4
// phase 5 (not implemented yet)
L2 U' F2 U2 R F R U' R U' R2 F' R2 U F U2 F U R B2 U2 D // phase 6 (3x3x3)

70 moves (68 not counting cancellations) in OBTM. I don't have a good intuitive feel for how many moves the fifth phase will take on average (my main big cube method is sandwich), but I expect it to be large enough that I can't just hit it with IDA*.

Edit (2016-05-19): Just finished coding the fifth phase. Had to spend just over an hour generating a pruning table for this particular phase (the rest of the initialisation time is probably 10 minutes, tops), and this is currently the only phase I have implemented any sort of symmetry reduction at all because I didn't want to spend two hours generating what's essentially the same table twice! Sample solve, with the same scramble as above.

R Dw2 L Uw B2 Fw Bw' Rw2 Uw2 F' Rw // phase 1
B Uw L Rw2 Uw' R2 F Dw // phase 2
Dw2 R F Uw2 L' Fw2 U F' L Rw2 F // phase 3.1
F Uw2 Dw2 Rw2 Lw2 F // phase 3.2
B2 Fw2 Lw2 Dw2 Bw2 D' Fw2 Rw2 Dw2 Bw2 Rw2 Bw2 // phase 4
R2 F2 D2 R' Uw2 F2 U R' Uw2 R Dw2 L2 Uw2 // phase 5.1
U D' F2 L' Dw2 R F2 B2 R' F2 B2 Dw2 // phase 5.2
R' B2 L D L F2 U2 R2 U' R2 F2 U2 F2 U2 F2 R U' R2 F2 U2 F2 U' R' // phase 6 (3x3x3)

There's still a lot of speed-related tweaking to be done, and this scramble was really an "easy" case (i.e. not representative) since phase 3 usually takes a lot more moves and time to find those moves. Phases 3, 5 and 6 are the only ones where I don't use IDA* for the whole phase, as optimally solving these phases quickly requires much larger pruning tables than I have RAM. Even with the subphases I'm using for these phases, the time taken is highly variable and can pretty much be summarised as "extremely slow on average, but occasionally fast".

The problem I'm facing now is that (other than the 3x3x3 phase) there's no obvious way to implement these problematic phases as "somewhat suboptimal but fast" algorithms, short of computing large alg databases or the like; I'm going to have to think a bit harder about this. I'll post more details about the phases at a later date, but just looking at the moves used in the sample solution above should provide enough information on what those phases are anyway.

Last edited: