How does phase2 pruning work?

dwalton76 commented 6 years ago

Hi Chen, First of all let me say that your solver is amazing, the short solutions that it produces in such a short amount of time are very impressive. I have been trying to reverse engineer how your solver works so that I can implement what you've done in my solver at https://github.com/dwalton76/rubiks-cube-NxNxN-solver . I have the basics working but currently I only find one solution for phase1 because my phase2 is too slow for me to evaluate hundreds of phase1 solutions to find the best phase1 + phase2 combination. It works but I do not find solutions as short as your solver.

I forked your repo and have been adding debugs to figure out how things work, specifically how you are able to run 500 phase2 searches so quickly. One thing I have yet to figure out is how your phase2 pruning works, specifically this section: 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;
            }

So if the prun cost is the maxl we just continue to the next step (m++ in the for loop) but if it is above maxl it skips certain moves via skipAxis2. I looked at skipAxis2 but cannot follow what it is doing.

Any words of wisdom on how this works?

Thanks Daniel

cs0x7f commented 6 years ago

Well, it's a simple technique to reduce the number of nodes accessed. For example, we start at a position S whose pruning value is no more than maxl, otherwise, S will be pruned in previous searching. After a move X, we obtain position S', whose pruning value is larger than maxl, which means that X makes S farther from the solved state. In this case, we won't try X2 and X'.

BTW, I do not try to find hundreds of phase 2 solutions for each phase 1 solution. Instead, I collect 500 phase 1 solutions with minimum phase1+phase2prun, and try to find totally 100 phase 2 solutions for all these phase1 solutions as follows:

for depth1and2 = 1 to maximum for S in these 500 phase1 solutions search(S, depth1and2 - length1OfS)

For random position in phase 2, my solver does not run quickly enough. However, for filtered phase 1 solutions whose phase 2 pruning value is usually small, we are able to find phase 2 solutions quickly. This is because that a pruning table is always more efficient for small-depth positions than large-depth positions.

dwalton76 commented 6 years ago

After a move X, we obtain position S', whose pruning value is larger than maxl, which means that X makes S farther from the solved state.
In this case, we won't try X2 and X'.

Interesting...I will have to dig into this. Thanks!

cs0x7f / TPR-4x4x4-Solver

How does phase2 pruning work? #7