search

dwalton76 / rubiks-cube-NxNxN-solver

A generic rubiks cube solver
MIT License
93 stars 25 forks source link

6x6x6: step20 remove fake_move #43

Closed dwalton76 closed 6 years ago

dwalton76 commented 6 years ago

This adds a lot of steps...need to use symmetry so we can build this table out deep enough to not need fake_move.

dwalton76 commented 6 years ago

I still don't have my head wrapped around symmetry and don't feel like fighting that battle right now. The other option is to just build the table deep enough for us to be able to remove the fake_move. The deepest I can realistically build this is 7-deep

dwalton@laptop ~/l/rubiks-cube-NxNxN-solver> ls -lh lookup-table-6x6x6-step20-UD-oblique-edge-pairing.txt.7-deep.one-step lookup-table-6x6x6-step20-UD-oblique-edge-pairing.txt.7-deep.one-step.gz
-rw-rw-r-- 1 dwalton dwalton 2.1G Jan 27 16:55 lookup-table-6x6x6-step20-UD-oblique-edge-pairing.txt.7-deep.one-step
-rw-rw-r-- 1 dwalton dwalton 470M Jan 27 16:55 lookup-table-6x6x6-step20-UD-oblique-edge-pairing.txt.7-deep.one-step.gz
dwalton@laptop ~/l/rubiks-cube-NxNxN-solver>

With distribution:

    lookup-table-6x6x6-step20-UD-oblique-edge-pairing.txt
    =====================================================
    1 steps has 5 entries (0 percent, 0.00x previous step)
    2 steps has 82 entries (0 percent, 16.40x previous step)
    3 steps has 1,434 entries (0 percent, 17.49x previous step)
    4 steps has 24,198 entries (0 percent, 16.87x previous step)
    5 steps has 405,916 entries (0 percent, 16.77x previous step)
    6 steps has 6,839,392 entries (5 percent, 16.85x previous step)
    7 steps has 116,031,874 entries (94 percent, 16.97x previous step)

    Total: 123,302,901 entries
    Average: 6.937309 moves

so 470M zipped at 7-deep and growing at 17x...so 8-deep would be 7.9G zipped!! Using the 7-deep table (and removing fake_move) brings the number of moves required to solve the centers from 100.74 down to 93.8. The problem is the IDA is very slow for some cubes, this one takes 2m 36s :(

dwalton@laptop ~/l/rubiks-cube-NxNxN-solver> ./usr/bin/rubiks-cube-solver.py --state UBULRLBDLDBDDLLDBBRRBFDRFRLLRLBUDUBBUFFUBBFUURDBDUFRDLDLUDBFLBRUFLUFUUBDDRLLLLULFDLLDRFDFBDFLUUFLBFRDBFUBRDRLLUFFBRDBDLUUFRFDRDDBLBRRRBBRRLLLBRRRRRBRRDUUFBFBLDBUFBLULRBUUBDLDDFRFDUDUDFUFDFFUFFUUBRRLLBRULLUFFRUBFDRFDF

2018-01-27 17:25:23,123      __init__.py     INFO: 
2018-01-27 17:25:23,123      __init__.py     INFO: 
2018-01-27 17:25:23,123      __init__.py     INFO: 
2018-01-27 17:25:23,137 RubiksCube666.py     INFO: UD inner x-centers staged, 5 steps in
2018-01-27 17:25:23,138   LookupTable.py     INFO: 6x6x6-step20-UD-oblique-edge-pairing: IDA threshold range 6->99
2018-01-27 17:25:23,145   LookupTable.py     INFO: 6x6x6-step20-UD-oblique-edge-pairing: IDA threshold 6, explored 42 branches, took 7ms
2018-01-27 17:25:23,296   LookupTable.py     INFO: 6x6x6-step20-UD-oblique-edge-pairing: IDA threshold 7, explored 1108 branches, took 151ms
2018-01-27 17:25:26,979   LookupTable.py     INFO: 6x6x6-step20-UD-oblique-edge-pairing: IDA threshold 8, explored 28404 branches, took 0:00:03.682082
2018-01-27 17:26:51,293   LookupTable.py     INFO: 6x6x6-step20-UD-oblique-edge-pairing: IDA threshold 9, explored 755480 branches, took 0:01:24.313916
2018-01-27 17:27:59,278   LookupTable.py     INFO: 6x6x6-step20-UD-oblique-edge-pairing: IDA found match 8 steps in, f_cost 11 (8 + 3)
2018-01-27 17:27:59,279   LookupTable.py     INFO: 6x6x6-step20-UD-oblique-edge-pairing: IDA threshold 10, explored 715517 branches, took 0:01:07.985805 (0:02:36.141086 total)
2018-01-27 17:27:59,279 RubiksCube666.py     INFO: UD oblique edges paired, 20 steps in

Things that won't work

conclusion? Keep the fake move