7x7x7: step80 avoid solving LR and FB prior to solving LRFB

[dwalton76]

We spend 40+ moves in this phase because we solve LR, then solve FB (which partially breaks up the LR we just solved) and then we solve LFRB. The step80 table is only 5-deep, if we build it 6-deep can we avoid solving LR then FB and just jump straight to solving LFRB?

• build the step80 table out to 6-deep
• convert this table to hex to make it much smaller
• chop the outer x-centers, these are not needed and will make the table smaller
• build a 24 million entry prune table? Today all of the prune tables are 343,000
• ./usr/bin/rubiks-cube-solver.py --state LLDBLFDRRFDUBFLLLFLLDFLDUBRULFLFDRDRUBBUDBFLFRUBFLDBFRDRFLLRBDUUFRFURDDDBRRLDUDUBLRLLBUDRUDBUUUUBUUDLDFRURFFUFURRRDLBRFLLUFUULRUBRRURULFUBUURLDBRBDBFRLULLFLDLFRRDLRBFDBBFDDUDRBBUUFLBFBLRDDDBRFLBURFDDRBDRBRLURFUDDUFBBFBFLLRFFLLRDFDBBFBRFDLLURUFDDFLFDFBDFFUBDBRBUDDDBLFBLBRBRURFLBBULLDFURUBBLURFU

[dwalton76]

Did the following:

• converted the table to hex
• chopped the outer x-centers
• I built it out to 6-deep but only for the first 100 of 4900 tables (went 5-deep for the other 4800). That got the table to 53 million entries and was 400M zipped. Going to 6-deep for all 4900 tables would produce a table much too large to check into the repo.
• chopped the "solve FB" call prior to calling "solve LFRB"

What I didn't do:

• I did not drop the "solve LR" call prior to calling "solve LFRB". When we solve LR and then LFRB, the solving of LFRB does not do any L or R turns so it doesn't scramble them that much anyway.
• I did not build a 24 million entry prune table. I've built these in the past but they don't go deep enough in move count to make a "do step80 without first solving LR" IDA search finish in a reasonable amount of time.

[dwalton76]

I built the step80 table out to 6-deep, it had 326,593,093 entries

-rw-rw-r-- 1 dwalton dwalton  15G Jan 20 16:58 lookup-table-7x7x7-step80-LFRB-solve-inner-center-and-oblique-edges.txt.6-deep
-rw-rw-r-- 1 dwalton dwalton 1.9G Jan 20 16:58 lookup-table-7x7x7-step80-LFRB-solve-inner-center-and-oblique-edges.txt.6-deep.gz

baseline with normal step80 table

2018-01-21 06:47:52,869 RubiksCube777.py     INFO: UD inner-centers solved, UD oblique edges paired, 87 steps in
2018-01-21 06:47:52,875   LookupTable.py     INFO: 7x7x7-step60-LR-solve-inner-center-and-oblique-edges: IDA threshold range 7->99
2018-01-21 06:47:52,936   LookupTable.py     INFO: 7x7x7-step60-LR-solve-inner-center-and-oblique-edges: IDA found match 4 steps in, f_cost 8 (4 + 4)
2018-01-21 06:47:52,936   LookupTable.py     INFO: 7x7x7-step60-LR-solve-inner-center-and-oblique-edges: IDA threshold 7, explored 98 branches, took 60ms (65ms total)
2018-01-21 06:47:52,936 RubiksCube777.py     INFO: LR inner-centers solved and oblique edges paired, 99 steps in

2018-01-21 06:47:52,940   LookupTable.py     INFO: 7x7x7-step80-LFRB-solve-inner-center-and-oblique-edges: IDA threshold range 8->99
2018-01-21 06:47:52,945   LookupTable.py     INFO: 7x7x7-step80-LFRB-solve-inner-center-and-oblique-edges: IDA threshold 8, explored 17 branches, took 5ms
2018-01-21 06:47:52,971   LookupTable.py     INFO: 7x7x7-step80-LFRB-solve-inner-center-and-oblique-edges: IDA threshold 9, explored 118 branches, took 25ms
2018-01-21 06:47:53,187   LookupTable.py     INFO: 7x7x7-step80-LFRB-solve-inner-center-and-oblique-edges: IDA threshold 10, explored 1150 branches, took 216ms
2018-01-21 06:47:54,268   LookupTable.py     INFO: 7x7x7-step80-LFRB-solve-inner-center-and-oblique-edges: IDA threshold 11, explored 9237 branches, took 1080ms
2018-01-21 06:47:56,513   LookupTable.py     INFO: 7x7x7-step80-LFRB-solve-inner-center-and-oblique-edges: IDA found match 8 steps in, f_cost 13 (8 + 5)
2018-01-21 06:47:56,513   LookupTable.py     INFO: 7x7x7-step80-LFRB-solve-inner-center-and-oblique-edges: IDA threshold 12, explored 25194 branches, took 0:00:02.244645 (0:00:03.576306 total)
2018-01-21 06:47:56,513 RubiksCube777.py     INFO: LFRB centers reduced to 5x5x5 centers, 113 steps in

143 steps to solve centers
108 steps to group edges
18 steps to solve 3x3x3
269 steps total

numbers with the huge step80 table

• no longer solving LR ahead of time

  
  2018-01-20 17:14:00,356 RubiksCube777.py     INFO: UD inner-centers solved, UD oblique edges paired, 87 steps in
  2018-01-20 17:14:00,356 RubiksCube777.py     INFO: 
  2018-01-20 17:14:00,357   LookupTable.py     INFO: 7x7x7-step80-LFRB-solve-inner-center-and-oblique-edges: IDA threshold range 8->99
  2018-01-20 17:14:00,378   LookupTable.py     INFO: 7x7x7-step80-LFRB-solve-inner-center-and-oblique-edges: IDA threshold 8, explored 42 branches, took 21ms
  2018-01-20 17:14:00,558   LookupTable.py     INFO: 7x7x7-step80-LFRB-solve-inner-center-and-oblique-edges: IDA threshold 9, explored 569 branches, took 180ms
  2018-01-20 17:14:01,637   LookupTable.py     INFO: 7x7x7-step80-LFRB-solve-inner-center-and-oblique-edges: IDA threshold 10, explored 5959 branches, took 1078ms
  2018-01-20 17:14:08,544   LookupTable.py     INFO: 7x7x7-step80-LFRB-solve-inner-center-and-oblique-edges: IDA threshold 11, explored 58727 branches, took 0:00:06.906547
  2018-01-20 17:14:58,383   LookupTable.py     INFO: 7x7x7-step80-LFRB-solve-inner-center-and-oblique-edges: IDA threshold 12, explored 529179 branches, took 0:00:49.839114
  2018-01-20 17:21:32,852   LookupTable.py     INFO: 7x7x7-step80-LFRB-solve-inner-center-and-oblique-edges: IDA threshold 13, explored 4558464 branches, took 0:06:34.468393
  2018-01-20 17:34:54,652   LookupTable.py     INFO: 7x7x7-step80-LFRB-solve-inner-center-and-oblique-edges: IDA found match 11 steps in, f_cost 15 (11 + 4)
  2018-01-20 17:34:54,653   LookupTable.py     INFO: 7x7x7-step80-LFRB-solve-inner-center-and-oblique-edges: IDA threshold 14, explored 9818546 branches, took 0:13:21.800651 (0:20:54.296004 total)
  2018-01-20 17:34:54,653 RubiksCube777.py     INFO: LFRB centers reduced to 5x5x5 centers, 104 steps in
             U B L B R D L 
             B F D D D L D 
             B U U U U D F 
             L U U U U D L 
             B U U U U D B 
             R U U U U R D 
             R L R R U R U 

R L L B D F F D F D F B B R B B D D L R U B L U R F L F L U R R R B U B F B B B D L U B R R R R D F R F F F D D D R L L L L F U B F F F B U L L R R R R F D F B B B F L L R L L L L U B B F F F B D B L R R R R R U F B B B F F R R L L L L B R B F F F B R F L R R R R R B F B B B F D U U L L L L U R L B B B R R U F L L L F F L D F F F D L R R L L R B L F U F R B R U F F U U R F D B B F D D F D

           D B U D U D L 
           R B D D D L U 
           F U D D D U L 
           U U D D D U F 
           B U D D D U U 
           F U D D D B U 
           B D L F D D L 

2018-01-20 17:34:54,653 RubiksCube777.py INFO: 2018-01-20 17:34:54,653 RubiksCube777.py INFO: 2018-01-20 17:34:54,653 RubiksCube777.py INFO:

135 steps to solve centers 104 steps to group edges 21 steps to solve 3x3x3 260 steps total

So it took us 17 steps instead of 26 steps but it also took 20 minutes vs 3s!  We could build a 70^4 or 24,010,000 prune table but we would have to build 70 of them and merge them.  Even then we would probably have to build several different 24,010,000 types of prune tables.  Maybe someday but for now that doesn't feel worth the trouble.  

[dwalton76]

The LFRB inner centers prune table only had one starting point (not 70) so I built that one, it is a good one:

    lookup-table-7x7x7-step81-LFRB-solve-inner-centers.txt
    ======================================================
    1 steps has 3 entries (0 percent, 0.00x previous step)
    2 steps has 25 entries (0 percent, 8.33x previous step)
    3 steps has 146 entries (0 percent, 5.84x previous step)
    4 steps has 544 entries (0 percent, 3.73x previous step)
    5 steps has 2,772 entries (0 percent, 5.10x previous step)
    6 steps has 13,681 entries (0 percent, 4.94x previous step)
    7 steps has 57,790 entries (0 percent, 4.22x previous step)
    8 steps has 227,221 entries (0 percent, 3.93x previous step)
    9 steps has 797,842 entries (3 percent, 3.51x previous step)
    10 steps has 2,318,392 entries (9 percent, 2.91x previous step)
    11 steps has 5,327,072 entries (22 percent, 2.30x previous step)
    12 steps has 7,922,750 entries (32 percent, 1.49x previous step)
    13 steps has 5,770,345 entries (24 percent, 0.73x previous step)
    14 steps has 1,498,471 entries (6 percent, 0.26x previous step)
    15 steps has 71,950 entries (0 percent, 0.05x previous step)
    16 steps has 998 entries (0 percent, 0.01x previous step)
    17 steps has 3 entries (0 percent, 0.00x previous step)

    Total: 24,010,005 entries
    Average: 11.805268 moves

With the step81 table...much faster

2018-01-21 23:53:46,036   LookupTable.py     INFO: 7x7x7-step80-LFRB-solve-inner-center-and-oblique-edges: IDA threshold range 12->99
2018-01-21 23:53:47,408   LookupTable.py     INFO: 7x7x7-step80-LFRB-solve-inner-center-and-oblique-edges: IDA threshold 12, explored 2878 branches, took 1371ms
2018-01-21 23:53:56,526   LookupTable.py     INFO: 7x7x7-step80-LFRB-solve-inner-center-and-oblique-edges: IDA threshold 13, explored 46942 branches, took 0:00:09.118542
2018-01-21 23:55:17,290   LookupTable.py     INFO: 7x7x7-step80-LFRB-solve-inner-center-and-oblique-edges: IDA threshold 14, explored 560072 branches, took 0:01:20.763717
2018-01-21 23:57:58,695   LookupTable.py     INFO: 7x7x7-step80-LFRB-solve-inner-center-and-oblique-edges: IDA found match 11 steps in, f_cost 15 (11 + 4)
2018-01-21 23:57:58,696   LookupTable.py     INFO: 7x7x7-step80-LFRB-solve-inner-center-and-oblique-edges: IDA threshold 15, explored 1257043 branches, took 0:02:41.405338 (0:04:12.666662 total)
2018-01-21 23:57:58,696 RubiksCube777.py     INFO: LFRB centers reduced to 5x5x5 centers, 104 steps in

With LR and FB IDA tables as prune tables

2018-01-22 00:32:41,477   LookupTable.py     INFO: 7x7x7-step80-LFRB-solve-inner-center-and-oblique-edges: IDA threshold range 12->99
2018-01-22 00:32:41,959   LookupTable.py     INFO: 7x7x7-step80-LFRB-solve-inner-center-and-oblique-edges: IDA threshold 12, explored 1330 branches, took 482ms
2018-01-22 00:32:45,518   LookupTable.py     INFO: 7x7x7-step80-LFRB-solve-inner-center-and-oblique-edges: IDA threshold 13, explored 19485 branches, took 0:00:03.558684
2018-01-22 00:33:15,783   LookupTable.py     INFO: 7x7x7-step80-LFRB-solve-inner-center-and-oblique-edges: IDA threshold 14, explored 205661 branches, took 0:00:30.264428
2018-01-22 00:34:20,607   LookupTable.py     INFO: 7x7x7-step80-LFRB-solve-inner-center-and-oblique-edges: IDA found match 11 steps in, f_cost 16 (11 + 5)
2018-01-22 00:34:20,608   LookupTable.py     INFO: 7x7x7-step80-LFRB-solve-inner-center-and-oblique-edges: IDA threshold 15, explored 457986 branches, took 0:01:04.824854 (0:01:39.136239 total)
2018-01-22 00:34:20,608 RubiksCube777.py     INFO: LFRB centers reduced to 5x5x5 centers, 104 steps in

So I'm down to 1m 39s, maybe if I use symmetry and build the step80 table out to 7-deep that will make this fast enough to avoid the "solving LR" step

[dwalton76]

I tried but symmetry won't make this table small enough to build to 7-deep.