4x4x4: tsai phase1 and phase2 needs more work

[dwalton76]

The "TPR solver" is referring to https://github.com/dwalton76/TPR-4x4x4-Solver I did not write this solver, it produces some very short solutions in just a second or two. I have been adding comments and debugs (thus my fork) to reverse engineer what it is doing.

Testing with the following

./usr/bin/rubiks-cube-solver.py --state DRFDFRUFDURDDLLUFLDLLBLULFBUUFRBLBFLLUDDUFRBURBBRBDLLDURFFBBRUFUFDRFURBUDLDBDUFFBUDRRLDRBLFBRRLB --cpu-tsai

The TPR solver reduces centers in 26 moves https://alg.cubing.net/?puzzle=4x4x4&setup=F2-_U-_F2-_D_U-_F2-_D_L2-_U2-_B-_D-_R_F-_D_B-_L-_B_F_L-_R_Uw_L-_B_D-_L_B-_Uw-_B-_Dw_B2-_L_U_D-_B2-_L-_Dw-_R_U-_B_R_D-_Rw_B2-_D_R-_B_D-_B_Rw-_F2-_D-_Fw2-_L_Dw2-_F_L_Bw2-_D-_Lw_U-_Lw-_Dw-_F-_Bw_U_Lw2-_Uw2-_R-_Uw&alg=Rw2_B_R-_Fw-_L-_Uw_Rw_%2F%2F_end_of_phase1%0AUw-_Rw2_B_R2_Uw_R-_%2F%2F_end_of_phase2%0AB-_F-_Fw2_R_B-_Uw2_R_U2_B-_Uw2_R-_Rw2_Uw2_x-_y2_%2F%2F_end_of_phase3

Where my --cpu-tsai takes 34 moves to reduce centers https://alg.cubing.net/?puzzle=4x4x4&setup=R2-_U_L2-_F2-_R2-_F2-_D-_F2-_R2-_U2-_R_B-_L_R-_B2-_U_L_R2-_U2-_B2-_Lw2-_B2-_Dw2-_F2-_D2-_Lw2-_U-_F-_Lw2-_L2-_D_Lw2-_B_Uw2-_F2-_U_R-_Rw-_Fw2-_Rw-_D2-_F-_Uw2-_B_L_Fw_B-_U-_Rw_Fw2-_R-_F2-_U2-_Fw&alg=Fw-_U2_F2_R_Fw2_Rw-_U_B_Fw-_L-__%2F%2F_end_of_phase1%0AB-_Uw2_F_D2_Rw_Fw2_Rw_R__%2F%2F_end_of_phase2%0AU-_F2_Uw2_B-_Lw2_D-_L2_Lw2_F_U_Lw2_D2_F2_Dw2_B2_Lw2_%2F%2F_end_of_phase3%0AB2_U2_R2_L-_U-_B2_R_L-_B_R-_U2_R2_F2_D_F2_R2_F2_L2_U-_R2

The difference is the TPR solver finds 10k phase1 solutions and keeps the best 500 (the ones with the lowest phase2 centers heuristic). It then searches for a phase2 solution for those 500 phase1 solutions, it does this by starting with a very low IDA threshold and incrementing it by one after trying to find a solution for all 500 scenarios. It then keeps the best 100 phase2 solutions and does the same basic process for finding the best phase2 + phase3 combo.

I am unable to get phase2 to run fast enough to do this though. TPR does some pruning that I do not understand. This is the skipAxis2 stuff...need to wrap my head around this.

https://github.com/dwalton76/TPR-4x4x4-Solver/blob/debug/src/Search.java#L318-L324

            if (prun >= maxl) {
                // TODO what is this doing?
                if (prun > maxl) {
                    m = skipAxis2[m];
                }
                continue;
            }

Note that my phase1 does EO where all edges are oriented correctly. I do this just to speed up phase2 where it is looking for edges to be EO but in any orientation.

Long term bidir IDA might be the way to go here, we could just combine phase 1 and phase 2 (which the TPR solver is somewhat doing)

[dwalton76]

Posted a question on the TPR repo asking about the mystery code above https://github.com/cs0x7f/TPR-4x4x4-Solver/issues/7

[cs0x7f]

Combining phase 1 and phase 2 is practical, Tom rokicki and I have both implemented such approach. However, I have no idea how to deal with EO efficiently. For a permutation of all 24 edges, there are 2048 different way to define edge orientation, since we only care about whether edges with same colours are separated into high/low positions.

[dwalton76]

yeah I haven't come up with anything good there either. Today I do not do any pruning based on EO, I just let phase2 run until it is lucky enough to find a solution that also accomplishes EO. Even with that I have phase1 also solve EO (it will be broken up as part of the phase2 search) in order to speed up phase2 search.

Brainstorming... option 1

• build all 2048 EO prune tables and all 2048 "phase1 + phase2" tables
• take your scrambled cube and IDA search for all 2048 possible EO orientations This would be very slow though. Perhaps there is some way to examine the edges and figure out which of the 2048 EOs would be the best one to aim for?

option 2

• build a single EO prune table and single "phase1 + phase2" table
• this wouldn't produce solutions as short as option 1 but maybe it would still be shorter than having separate phase1 and phase2

[dwalton76]

I tried option 2 in the tsai-combine-phase1-phase2 branch but it was very slow. I let the IDA search run for a few hours and eventually killed it.

[dwalton76]

Note that my phase1 does EO where all edges are oriented correctly. I do this just to speed up phase2

I did remove this part...just to simplify phase1.

[dwalton76]

closing for now