Announcing: New 4x4x4 Brute Force Solver

Status
Not open for further replies.
Carrot said:
If the heavy pruning is supposed to find at least one optimal solution, then it doesn't work :)
Click to expand...

It looks like the TFS database at the end is just "undoing" the last 3 moves made. So... it does and it doesn't. This "overshoot problem" is a known issue. Somehow the TFS is finding the solve at a greater depth to give a solution = to the nominal search depth. So a 23-ply search, with the last 3 plies in the database undoing the last 3 moves made, gives you a 20-ply solution. I know, crazy, right? It's supposed to be the other way around, finding a 20-ply solution after 17 plies of search.

kjnISye.png
 
Last edited:
unsolved said:
It looks like the TFS database at the end is just "undoing" the last 3 moves made. So... it does and it doesn't. This "overshoot problem" is a known issue. Somehow the TFS is finding the solve at a greater depth to give a solution = to the nominal search depth. So a 23-ply search, with the last 3 plies in the database undoing the last 3 moves made, gives you a 20-ply solution. I know, crazy, right? It's supposed to be the other way around, finding a 20-ply solution after 17 plies of search.

http://i.imgur.com/kjnISye.png
Click to expand...

the last 3 moves are not canceling.

however, R' r' l could just have been written as L'
 
Yeah, it's not undoing the moves, those last 7 or so moves are just a PLL parity algorithm. But as Bruce said, you are pruning positions that could be part of optimal solutions. So sometimes you will find the optimal solutions, but sometimes you will not see them.

Pruning too many positions can be a really strong technique for suboptimal solvers - I have used it for a puzzle game solver I made, where I took the 'best' N positions from each depth so as to get very deep without running out of memory. But for optimal solving you need an admissible heuristic, which means you only throw out positions when you can guarantee they will not lead to a solution of the given length.
 
Carrot said:
the last 3 moves are not canceling.
Click to expand...

Ah, you are correct. I spoke too soon. I was so used to seeing moves being undone in some of my own testing.

cuBerBruce said:
A solver that guarantees optimality of solutions always uses admissible heuristics for pruning. Since you choose not to use admissible heuristics, you should not be surprised that optimal solutions are missed.
Click to expand...

It's called experimenting Bruce. Sometimes you have to try new things to see how they work out.

The algorithm shows great promise. With a deeper understanding and some fine tuning, it could be perfected.

qqwref said:
But for optimal solving you need an admissible heuristic, which means you only throw out positions when you can guarantee they will not lead to a solution of the given length.
Click to expand...

Indeed :) Let's just say I am working on trying to make this one admissible then.
 
Last edited:
unsolved said:
It's called experimenting Bruce. Sometimes you have to try new things to see how they work out.
Click to expand...

You generally do not get an admissable heuristic through "experimenting" or ad hoc trial and error techniques. You get an admissible heuristic through using techniques that provably give you admissible heuristics. One of the most common ways is using a subset of pieces, and building a table of how many moves are required to solve each of the various arrangements of those pieces.

I'm not saying that it's necessarily bad to experiment with non-admissible heuristics. If you can create a solver that will solve "random" positions in under 40 moves fairly quickly, even if the solutions are not necessarily optimal, that would probably be considered very useful. As qqwref mentioned, you might be able to find solutions for deep positions faster with non-admmissible pruining, you just can't expect to necessarily get the optimal solutions.
 
cuBerBruce said:
You generally do not get an admissable heuristic through "experimenting" or ad hoc trial and error techniques.
Click to expand...

A PV that leads to a solution must start to converge at one point in time. I can guarantee, if you are 1 move away from a solution, you must have at least 2 opposite sides of the cube solved. It's very easy to test for, and if depth == 1 and that condition is absent, there is no move, real or imagined, that will solve the cube.

If you are 2 moves away, and any one of your 6 sides has 4 different colors for centers, you'll never solve it in 2 moves.

These are the types of heuristics I am discovering through Karnaugh Map reductions of the entire n-move domain.

Sometimes I am not implementing them properly, and I prune a node that would converge on a solution. Or sometimes the heuristic is "off by 1" in the depth at which it is applied, then I have to reconfirm it (takes over a hundred hours for some of the more complex ones).

Once I get all the kinks out, these will be what you call admissible.

You have to admit, finding a few 22-ply solves in under a minute is pretty cool.

fastest_snake_solve_ever.jpg
 
Last edited:
qqwref said:
I don't know if they're optimal, but 14 btm is pretty cool.
Click to expand...
Not in btm, but close.:) y f' 2L' f r2 f' 2L f' 2D' f2 r2 u 2R2 u' (but in single slice turns, his algs are optimal, and therefore his solver "did its job").

@unsolved, I just grabbed these from one of my old (long) posts which might be of interest to you.
I believe these are all possible 8 BQTM 1x2x2 block 3-cycle algorithms. The algorithm I used to create the 13 btm solution above is 10 BQTM, but 8 btm: Rw2 Uw' l' Uw Rw2 Uw' l Uw.

Case 1
Alg 1.
Rw' Fw' Rw b' Rw' Fw Rw b
Wide Turn Equivalences (3)
Rw' Bw' Dw b' Dw' Bw Rw b
Lw' Uw' Lw b' Lw' Uw Lw b
Lw' Dw' Bw r' Bw' Dw Lw b
Alg 2.
b Lw Fw' Lw' b' Lw Fw Lw'
Wide Turn Equivalences (3)
b Lw Bw' Uw' b' Uw Bw Lw'
b Rw Uw' Rw' b' Rw Uw Rw'
b Rw Dw' Fw' r' Fw Dw Rw'

Case 2
Lw' b Lw Fw' Lw' b' Lw Fw
Wide Turn Equivalences (3)
Lw' b Lw Bw' Uw' b' Uw Bw
Rw' u Rw Fw' Rw' u' Rw Fw
Rw' u Rw Bw' Dw' r' Dw Bw

Case 3
r' Dw r Uw r' Dw' r Uw'
Wide Turn Equivalences (3)
r' Uw f Uw f' Uw' r Uw'
r' Dw r Dw b' Dw' b Dw'
r' Uw f Dw r' Uw' b Dw'

Case 4
Uw' Rw d' Rw' Uw Rw d Rw'
Wide Turn Equivalences (3)
Dw' Fw d' Fw' Dw Rw d Rw'
Uw' Lw b' Lw' Uw Lw b Lw'
Dw' Bw r' Bw' Dw Lw b Lw'

Case 5
Alg 1.
Rw' Fw' Rw b Rw' Fw Rw b'
Wide Turn Equivalences (3)
Rw' Bw' Dw b Dw' Bw Rw b'
Lw' Uw' Lw b Lw' Uw Lw b'
Lw' Dw' Bw r Bw' Dw Lw b'
Alg 2.
Uw' Rw d Rw' Uw Rw d' Rw'
Wide Turn Equivalences (3)
Dw' Fw d Fw' Dw Rw d' Rw'
Uw' Lw b Lw' Uw Lw b' Lw'
Dw' Bw r Bw' Dw Lw b' Lw'

Case 6
Alg 1.
Fw d Fw' Uw Fw d' Fw' Uw'
Wide Turn Equivalences (3)
Fw d Fw' Dw Rw d' Rw' Dw'
Bw r Bw' Uw Bw r' Bw' Uw'
Bw r Bw' Dw Lw b' Lw' Dw'
Alg 2.
Uw' b' Dw b Uw b' Dw' b
Wide Turn Equivalences (3)
Dw' r' Dw r Dw b' Dw' b
Uw' b' Uw r Uw r' Uw' b
Dw' r' Uw f Dw r' Uw' b

Case 7
Uw Lw' Uw' r' Uw Lw Uw' r
Wide Turn Equivalences (3)
Uw Rw' Fw' r' Fw Rw Uw' r
Dw Fw' Dw' r' Dw Fw Dw' r
Dw Bw' Lw' d' Lw Bw Dw' r
I found all of those with the hope of finding a shorter single dedge flip algorithm (in BQTM) than 19, but I didn't succeed.

Here's a 19 btm single dedge flip algorithm from your first solution. :)
r' U' 2B u2 f2 2D f2 2D' f2 2U f2 2U' r2 2D r2 u2 2B' U r
 
Last edited:
cmowla said:
Not in btm, but close.:) y f' 2L' f r2 f' 2L f' 2D' f2 r2 u 2R2 u' (but in single slice turns, his algs are optimal, and therefore his solver "did its job").

@unsolved, I just grabbed these from one of my old (long) posts which might be of interest to you.

...


Here's a 19 btm single dedge flip algorithm from your first solution. :)
r' U' 2B u2 f2 2D f2 2D' f2 2U f2 2U' r2 2D r2 u2 2B' U r
Click to expand...

Yes, that is like my favorite alg for the single dedge flip! I guess if this version of OO_4x4x4 proves to be stable, it will be time to start working on a Block Turn version. As for the latest developments:


I am hopeful now. Every time Bruce gives me a kick in the pants, I end up staying awake all night and retasking about 30 CPUs to bang on stuff :)

So here is what I did:

1. I eliminated EVERY heuristic in the Inexact Pattern Singular Distance Heuristic Database that did not have a 100% tautology table matchup in the Karnaugh Map Database. That is a real shame, because some were at 88% to 95% and would prune like a hot knife through butter. But, the ones that remain are what Bruce would have to call admissible. The beauty of a Bitmap Move Generator is you can perform bit-ANDs across every cube from every possible position in a given depth, and the resulting pattern masks are those that did not occur. Pass these patterns into a Karnaugh Map analyzer, and you get a "logical expression" that precipitates out. So one line of code has the power to determine what cubes can't possibly be in a solution set bounded by a certain range of depths. I am keeping my fingers crossed that version 2.0.7 is working properly.

2. I stratified my databases by function. There are 3 types: Exact Pattern Complete Solution Database, which is what I used to call the Turns From Solved databases. Match a pattern in here, and not only do you not have to search, you get the solution returned. A Partial Pattern Minimal Distance Database is one that is populated with "Ghost Squares," or what are called "Don't Care" conditions in Karnaugh Maps. As long as the unghosted squares match, then the minimum distance for a solution is known with 100% certainty. If you are 3 plies away and in a Minimal Distance of 4 or more to solve the cube, you can prune the branch, not just the node. Lastly, the Inexact Pattern Singular Minimal Distance database, which contains the opposite kind of information. It pulls data from a corner-pruner and center-pruner, so there is some "inexactness" here. In such a position, you know there is a solution either in the next n - m bounded moves, or there can't be a solution before n moves. So you take a "wait and see" approach. The cutoff becomes conditional.

3. Lastly, I built a 1 GB + massive Solution Transposition Filter mechanism. Beyond two pairs of transposing opposite face moves appearing in conjunction in a solution, all rotated and flipped versions are pruned. This means you will need about 2 GB of RAM to use version 2.0.7 or later. The results of this seem to be good so far. It can still crank out many solutions, as shown below:

Code: 
Omnia Obtorquebantur 4x4x4 Version 2.0.7 [with Partial Pattern Minimal Distance Pruning] compiled on December 07, 2014.



                          TOP
                          ---------------------
                          |####|####|####|####|
                          ---------------------
                          |####|####|####|####|
                          ---------------------
                          |####|####|####|####|
                          ---------------------
                          |####|####|####|####|
                          ---------------------

  LEFT                    FRONT                   RIGHT                   BACK
  ---------------------   ---------------------   ---------------------   ---------------------
  |&&&&|^^^^|^^^^|&&&&|   |OOOO|&&&&|&&&&|OOOO|   |XXXX|OOOO|OOOO|XXXX|   |^^^^|XXXX|XXXX|^^^^|
  ---------------------   ---------------------   ---------------------   ---------------------
  |&&&&|&&&&|&&&&|&&&&|   |OOOO|OOOO|OOOO|OOOO|   |XXXX|XXXX|XXXX|XXXX|   |^^^^|^^^^|^^^^|^^^^|
  ---------------------   ---------------------   ---------------------   ---------------------
  |&&&&|&&&&|&&&&|&&&&|   |OOOO|OOOO|OOOO|OOOO|   |XXXX|XXXX|XXXX|XXXX|   |^^^^|^^^^|^^^^|^^^^|
  ---------------------   ---------------------   ---------------------   ---------------------
  |&&&&|&&&&|&&&&|&&&&|   |OOOO|OOOO|OOOO|OOOO|   |XXXX|XXXX|XXXX|XXXX|   |^^^^|^^^^|^^^^|^^^^|
  ---------------------   ---------------------   ---------------------   ---------------------

                          BOTTOM
                          ---------------------
                          |~~~~|~~~~|~~~~|~~~~|
                          ---------------------
                          |~~~~|~~~~|~~~~|~~~~|
                          ---------------------
                          |~~~~|~~~~|~~~~|~~~~|
                          ---------------------
                          |~~~~|~~~~|~~~~|~~~~|
                          ---------------------


 
  Solutions To Scramble = u2 b2 l2 D f2 D2 r2 D' r2 D2 b2 l2 u2 
 
  Solution [0001] =  u2 l2 b2 U  l2 D2 f2 U' f2 U2  [inside 3-TFS] --->  r2 f2 d2  @ 000000031166759 nodes [time = 01:25]
  Solution [0002] =  u2 l2 b2 U  l2 D2 f2 U' f2 D2  [inside 3-TFS] --->  l2 b2 u2  @ 000000031166768 nodes [time = 01:25]
  Solution [0003] =  u2 l2 b2 U' b2 U2 l2 U  b2 U2  [inside 3-TFS] --->  l2 b2 u2  @ 000000031298258 nodes [time = 01:25]
  Solution [0004] =  u2 l2 b2 U' b2 U2 l2 U  b2 D2  [inside 3-TFS] --->  r2 f2 d2  @ 000000031298267 nodes [time = 01:25]
  Solution [0005] =  u2 l2 b2 U' b2 D2 r2 U  f2 U2  [inside 3-TFS] --->  r2 f2 d2  @ 000000031300909 nodes [time = 01:25]
  Solution [0006] =  u2 l2 b2 U' b2 D2 r2 U  f2 D2  [inside 3-TFS] --->  l2 b2 u2  @ 000000031300918 nodes [time = 01:25]
  Solution [0007] =  u2 l2 b2 U2 l2 U  b2 U2 l2 U'  [inside 3-TFS] --->  l2 b2 u2  @ 000000031322138 nodes [time = 01:25]
  Solution [0008] =  u2 l2 b2 U2 l2 U  b2 D2 r2 U'  [inside 3-TFS] --->  r2 f2 d2  @ 000000031323644 nodes [time = 01:25]
  Solution [0009] =  u2 l2 b2 U2 l2 U' l2 U2 b2 U   [inside 3-TFS] --->  l2 b2 u2  @ 000000031323908 nodes [time = 01:25]
  Solution [0010] =  u2 l2 b2 U2 l2 U' l2 D2 f2 U   [inside 3-TFS] --->  r2 f2 d2  @ 000000031323964 nodes [time = 01:25]
  Solution [0011] =  u2 l2 b2 U2 l2 D' b2 U2 r2 D   [inside 3-TFS] --->  l2 b2 u2  @ 000000031359641 nodes [time = 01:25]
  Solution [0012] =  u2 l2 b2 U2 l2 D' b2 D2 l2 D   [inside 3-TFS] --->  r2 f2 d2  @ 000000031359801 nodes [time = 01:25]
  Solution [0013] =  u2 l2 b2 U2 l2 D  l2 U2 f2 D'  [inside 3-TFS] --->  l2 b2 u2  @ 000000031361702 nodes [time = 01:25]
  Solution [0014] =  u2 l2 b2 U2 l2 D  l2 D2 b2 D'  [inside 3-TFS] --->  r2 f2 d2  @ 000000031362974 nodes [time = 01:25]
  Solution [0015] =  u2 l2 b2 D' r2 D2 f2 D  f2 U2  [inside 3-TFS] --->  r2 f2 d2  @ 000000031525567 nodes [time = 01:25]
  Solution [0016] =  u2 l2 b2 D' r2 D2 f2 D  f2 D2  [inside 3-TFS] --->  l2 b2 u2  @ 000000031525576 nodes [time = 01:25]
  Solution [0017] =  u2 l2 b2 D  f2 U2 l2 D' b2 U2  [inside 3-TFS] --->  l2 b2 u2  @ 000000031548275 nodes [time = 01:25]
  Solution [0018] =  u2 l2 b2 D  f2 U2 l2 D' b2 D2  [inside 3-TFS] --->  r2 f2 d2  @ 000000031548284 nodes [time = 01:25]
  Solution [0019] =  u2 l2 b2 D  f2 D2 r2 D' f2 U2  [inside 3-TFS] --->  r2 f2 d2  @ 000000031550333 nodes [time = 01:25]
  Solution [0020] =  u2 l2 b2 D  f2 D2 r2 D' f2 D2  [inside 3-TFS] --->  l2 b2 u2  @ 000000031550342 nodes [time = 01:25]
  Solution [0021] =  u2 l2 b2 D2 r2 U  f2 U2 r2 U'  [inside 3-TFS] --->  r2 f2 d2  @ 000000031590045 nodes [time = 01:26]
  Solution [0022] =  u2 l2 b2 D2 r2 U  f2 D2 l2 U'  [inside 3-TFS] --->  l2 b2 u2  @ 000000031591614 nodes [time = 01:26]
  Solution [0023] =  u2 l2 b2 D2 r2 U' r2 U2 f2 U   [inside 3-TFS] --->  r2 f2 d2  @ 000000031592048 nodes [time = 01:26]
  Solution [0024] =  u2 l2 b2 D2 r2 U' r2 D2 b2 U   [inside 3-TFS] --->  l2 b2 u2  @ 000000031592168 nodes [time = 01:26]
  Solution [0025] =  u2 l2 b2 D2 r2 D' f2 U2 l2 D   [inside 3-TFS] --->  r2 f2 d2  @ 000000031606094 nodes [time = 01:26]
  Solution [0026] =  u2 l2 b2 D2 r2 D' f2 D2 r2 D   [inside 3-TFS] --->  l2 b2 u2  @ 000000031606269 nodes [time = 01:26]
  Solution [0027] =  u2 l2 b2 D2 r2 D  r2 U2 b2 D'  [inside 3-TFS] --->  r2 f2 d2  @ 000000031612317 nodes [time = 01:26]
  Solution [0028] =  u2 l2 b2 D2 r2 D  r2 D2 f2 D'  [inside 3-TFS] --->  l2 b2 u2  @ 000000031615566 nodes [time = 01:26]
  Solution [0029] =  d2 l2 b2 U  l2 U2 b2 U' b2 U2  [inside 3-TFS] --->  l2 b2 d2  @ 000000039898690 nodes [time = 01:44]
  Solution [0030] =  d2 l2 b2 U  l2 U2 b2 U' b2 D2  [inside 3-TFS] --->  r2 f2 u2  @ 000000039898699 nodes [time = 01:44]
  Solution [0031] =  d2 l2 b2 U' b2 U2 l2 U  b2 U2  [inside 3-TFS] --->  l2 b2 d2  @ 000000040032252 nodes [time = 01:45]
  Solution [0032] =  d2 l2 b2 U' b2 U2 l2 U  b2 D2  [inside 3-TFS] --->  r2 f2 u2  @ 000000040032261 nodes [time = 01:45]
  Solution [0033] =  d2 l2 b2 U' b2 D2 r2 U  f2 U2  [inside 3-TFS] --->  r2 f2 u2  @ 000000040034539 nodes [time = 01:45]
  Solution [0034] =  d2 l2 b2 U' b2 D2 r2 U  f2 D2  [inside 3-TFS] --->  l2 b2 d2  @ 000000040034548 nodes [time = 01:45]
  Solution [0035] =  d2 l2 b2 U2 l2 U  b2 U2 l2 U'  [inside 3-TFS] --->  l2 b2 d2  @ 000000040079858 nodes [time = 01:45]
  Solution [0036] =  d2 l2 b2 U2 l2 U  b2 D2 r2 U'  [inside 3-TFS] --->  r2 f2 u2  @ 000000040081408 nodes [time = 01:45]
  Solution [0037] =  d2 l2 b2 U2 l2 U' l2 U2 b2 U   [inside 3-TFS] --->  l2 b2 d2  @ 000000040081739 nodes [time = 01:45]
  Solution [0038] =  d2 l2 b2 U2 l2 U' l2 D2 f2 U   [inside 3-TFS] --->  r2 f2 u2  @ 000000040081848 nodes [time = 01:45]
  Solution [0039] =  d2 l2 b2 U2 l2 D' b2 U2 r2 D   [inside 3-TFS] --->  l2 b2 d2  @ 000000040095844 nodes [time = 01:45]
  Solution [0040] =  d2 l2 b2 U2 l2 D' b2 D2 l2 D   [inside 3-TFS] --->  r2 f2 u2  @ 000000040096032 nodes [time = 01:45]
  Solution [0041] =  d2 l2 b2 U2 l2 D  l2 U2 f2 D'  [inside 3-TFS] --->  l2 b2 d2  @ 000000040102735 nodes [time = 01:45]
  Solution [0042] =  d2 l2 b2 U2 l2 D  l2 D2 b2 D'  [inside 3-TFS] --->  r2 f2 u2  @ 000000040106130 nodes [time = 01:45]
  Solution [0043] =  d2 l2 b2 D' r2 U2 b2 D  b2 U2  [inside 3-TFS] --->  l2 b2 d2  @ 000000040321939 nodes [time = 01:46]
  Solution [0044] =  d2 l2 b2 D' r2 U2 b2 D  b2 D2  [inside 3-TFS] --->  r2 f2 u2  @ 000000040321948 nodes [time = 01:46]
  Solution [0045] =  d2 l2 b2 D  f2 U2 l2 D' b2 U2  [inside 3-TFS] --->  l2 b2 d2  @ 000000040333910 nodes [time = 01:46]
  Solution [0046] =  d2 l2 b2 D  f2 U2 l2 D' b2 D2  [inside 3-TFS] --->  r2 f2 u2  @ 000000040333919 nodes [time = 01:46]
  Solution [0047] =  d2 l2 b2 D  f2 D2 r2 D' f2 U2  [inside 3-TFS] --->  r2 f2 u2  @ 000000040336240 nodes [time = 01:46]
  Solution [0048] =  d2 l2 b2 D  f2 D2 r2 D' f2 D2  [inside 3-TFS] --->  l2 b2 d2  @ 000000040336249 nodes [time = 01:46]
  Solution [0049] =  d2 l2 b2 D2 r2 U  f2 U2 r2 U'  [inside 3-TFS] --->  r2 f2 u2  @ 000000040351316 nodes [time = 01:46]
  Solution [0050] =  d2 l2 b2 D2 r2 U  f2 D2 l2 U'  [inside 3-TFS] --->  l2 b2 d2  @ 000000040352865 nodes [time = 01:46]
  Solution [0051] =  d2 l2 b2 D2 r2 U' r2 U2 f2 U   [inside 3-TFS] --->  r2 f2 u2  @ 000000040353284 nodes [time = 01:46]
  Solution [0052] =  d2 l2 b2 D2 r2 U' r2 D2 b2 U   [inside 3-TFS] --->  l2 b2 d2  @ 000000040353350 nodes [time = 01:46]
  Solution [0053] =  d2 l2 b2 D2 r2 D' f2 U2 l2 D   [inside 3-TFS] --->  r2 f2 u2  @ 000000040389180 nodes [time = 01:46]
  Solution [0054] =  d2 l2 b2 D2 r2 D' f2 D2 r2 D   [inside 3-TFS] --->  l2 b2 d2  @ 000000040389328 nodes [time = 01:46]
  Solution [0055] =  d2 l2 b2 D2 r2 D  r2 U2 b2 D'  [inside 3-TFS] --->  r2 f2 u2  @ 000000040391295 nodes [time = 01:46]
  Solution [0056] =  d2 l2 b2 D2 r2 D  r2 D2 f2 D'  [inside 3-TFS] --->  l2 b2 d2  @ 000000040392453 nodes [time = 01:46]

perm.jpg


But on a side note, the 22-move "snake" positions are now effectively out of range. Those heavy pruning algos that were not 100% admissible are now out of version 2.0.7, so it looks like 15-plies is a functional limit of what it can do in a about 2-3 minutes.
 
Last edited:
15 move solutions in 2-3 minutes? Wow, that's impressive! These solutions are impressive as well (as are all solutions you have found with your solver so far!). :)
 
I tried the UF dedge flip position, and it clearly is not generating all optimal solutions. It only generates three solutions. All of them start with r2. None of them start with l2. Also, none start with r2 U2 B2 (although all 3 solutions found end with B2 U2 r2). Also, none started with r2 D2 F2.

It spent several minutes searching for solutions starting with r2. It spent little or no time searching for solutions starting with l2.

What's worse, I tried the scramble: r2 B2 U2 l U2 r' U2 r U2 F2 r F2 l' B2 D2 F2 which can be solved in 12 moves. It is 3 moves away from the UF dedge flip position. Version 2.0.7 didn't even solve this in its "depth 12-15" search. (I tried this based upon the lack of solutions starting with r2 D2 F2 for the dedge flip.)

Clearly there is still over-aggressive pruning going on (at least if you're expecting to get optimal solutions).
 
cuBerBruce said:
I tried the UF dedge flip position, and it clearly is not generating all optimal solutions. It only generates three solutions. All of them start with r2. None of them start with l2. Also, none start with r2 U2 B2 (although all 3 solutions found end with B2 U2 r2). Also, none started with r2 D2 F2.

It spent several minutes searching for solutions starting with r2. It spent little or no time searching for solutions starting with l2.

What's worse, I tried the scramble: r2 B2 U2 l U2 r' U2 r U2 F2 r F2 l' B2 D2 F2 which can be solved in 12 moves. It is 3 moves away from the UF dedge flip position. Version 2.0.7 didn't even solve this in its "depth 12-15" search. (I tried this based upon the lack of solutions starting with r2 D2 F2 for the dedge flip.)

Clearly there is still over-aggressive pruning going on (at least if you're expecting to get optimal solutions).
Click to expand...

Well I am going to have to write the most detailed chronicling tool ever to debug this one. I highly suspect the transposition code based on what you said. I wanted to avoid the "large dump" of solutions that some scrambles produce, such as:

l2 R2 [ROTATE z'] l2 R2 [ROTATE x'] [ROTATE z'] [ROTATE x] l2 R2 [ROTATE y] [ROTATE x] l2 R2 [ROTATE y] and u2 l2 b2 U l2 D2 f2 U' f2 U2 There are so many mirrors/rotations that the complete set of solutions borders on ridiculous. So I started hashing cubes already generated during the searching process, rotated each of them to the other 23 states, and hashed them as well. Should they ever arise again during the search, I pruned them. But as the hash table fills up, I used an aging mechanism to determine which entries to overwrite. Oldest entries are overwritten first. I suspect therein lies the culprit, so I'll start there.

Good detective work Bruce.
 
Ah, but wouldn't the pruning cubes you have already seen make it pretty much impossible to generate all optimal solutions? All you can really be sure of is that solutions won't have rotations in them. That said, you can certainly prune an already-known state if you know it can be reached in fewer moves than what you just did.
 
qqwref said:
Ah, but wouldn't the pruning cubes you have already seen make it pretty much impossible to generate all optimal solutions? All you can really be sure of is that solutions won't have rotations in them. That said, you can certainly prune an already-known state if you know it can be reached in fewer moves than what you just did.
Click to expand...

I wanted to avoid output like this:

Code: 
Omnia Obtorquebantur 4x4x4 Version 2.0.5 compiled on December 05, 2014. Copyright (c) 2014 by Ed Trice.



                          TOP
                          ---------------------
                          |^^^^|OOOO|^^^^|OOOO|
                          ---------------------
                          |OOOO|^^^^|OOOO|^^^^|
                          ---------------------
                          |^^^^|OOOO|^^^^|OOOO|
                          ---------------------
                          |OOOO|^^^^|OOOO|^^^^|
                          ---------------------

  LEFT                    FRONT                   RIGHT                   BACK
  ---------------------   ---------------------   ---------------------   ---------------------
  |&&&&|&&&&|&&&&|&&&&|   |~~~~|####|~~~~|####|   |XXXX|XXXX|XXXX|XXXX|   |####|~~~~|####|~~~~|
  ---------------------   ---------------------   ---------------------   ---------------------
  |&&&&|&&&&|&&&&|&&&&|   |####|~~~~|####|~~~~|   |XXXX|XXXX|XXXX|XXXX|   |~~~~|####|~~~~|####|
  ---------------------   ---------------------   ---------------------   ---------------------
  |&&&&|&&&&|&&&&|&&&&|   |~~~~|####|~~~~|####|   |XXXX|XXXX|XXXX|XXXX|   |####|~~~~|####|~~~~|
  ---------------------   ---------------------   ---------------------   ---------------------
  |&&&&|&&&&|&&&&|&&&&|   |####|~~~~|####|~~~~|   |XXXX|XXXX|XXXX|XXXX|   |~~~~|####|~~~~|####|
  ---------------------   ---------------------   ---------------------   ---------------------

                          BOTTOM
                          ---------------------
                          |OOOO|^^^^|OOOO|^^^^|
                          ---------------------
                          |^^^^|OOOO|^^^^|OOOO|
                          ---------------------
                          |OOOO|^^^^|OOOO|^^^^|
                          ---------------------
                          |^^^^|OOOO|^^^^|OOOO|
                          ---------------------


 
  Solutions To Scramble = l2 R2 [ROTATE z'] l2 R2 [ROTATE x'] [ROTATE z'] [ROTATE x] l2 R2 [ROTATE y] [ROTATE x] l2 R2 [ROTATE y] 
 
  Solution [0001] =  R2 l2 U2 d2 F2  [inside 3-TFS] --->  b2 d2 U2  @ 000000002423835 nodes [time = 00:01]
  Solution [0002] =  R2 l2 U2 d2 f2  [inside 3-TFS] --->  B2 d2 U2  @ 000000002423838 nodes [time = 00:01]
  Solution [0003] =  R2 l2 U2 d2 b2  [inside 3-TFS] --->  F2 d2 U2  @ 000000002423841 nodes [time = 00:01]
  Solution [0004] =  R2 l2 U2 d2 B2  [inside 3-TFS] --->  f2 d2 U2  @ 000000002423844 nodes [time = 00:01]
  Solution [0005] =  R2 l2 u2 D2 F2  [inside 3-TFS] --->  b2 D2 u2  @ 000000002426418 nodes [time = 00:01]
  Solution [0006] =  R2 l2 u2 D2 f2  [inside 3-TFS] --->  B2 D2 u2  @ 000000002426421 nodes [time = 00:01]
  Solution [0007] =  R2 l2 u2 D2 b2  [inside 3-TFS] --->  F2 D2 u2  @ 000000002426424 nodes [time = 00:01]
  Solution [0008] =  R2 l2 u2 D2 B2  [inside 3-TFS] --->  f2 D2 u2  @ 000000002426427 nodes [time = 00:01]
  Solution [0009] =  R2 l2 F2 b2 U2  [inside 3-TFS] --->  d2 b2 F2  @ 000000002433786 nodes [time = 00:01]
  Solution [0010] =  R2 l2 F2 b2 u2  [inside 3-TFS] --->  D2 b2 F2  @ 000000002433789 nodes [time = 00:01]
  Solution [0011] =  R2 l2 F2 b2 d2  [inside 3-TFS] --->  U2 b2 F2  @ 000000002433792 nodes [time = 00:01]
  Solution [0012] =  R2 l2 F2 b2 D2  [inside 3-TFS] --->  u2 b2 F2  @ 000000002433795 nodes [time = 00:01]
  Solution [0013] =  R2 l2 f2 B2 U2  [inside 3-TFS] --->  d2 B2 f2  @ 000000002436372 nodes [time = 00:01]
  Solution [0014] =  R2 l2 f2 B2 u2  [inside 3-TFS] --->  D2 B2 f2  @ 000000002436375 nodes [time = 00:01]
  Solution [0015] =  R2 l2 f2 B2 d2  [inside 3-TFS] --->  U2 B2 f2  @ 000000002436378 nodes [time = 00:01]
  Solution [0016] =  R2 l2 f2 B2 D2  [inside 3-TFS] --->  u2 B2 f2  @ 000000002436381 nodes [time = 00:01]
  Solution [0017] =  R2 U2 d2 F2 b2  [inside 3-TFS] --->  d2 U2 l2  @ 000000002564628 nodes [time = 00:01]
  Solution [0018] =  R2 U2 d2 f2 B2  [inside 3-TFS] --->  d2 U2 l2  @ 000000002564721 nodes [time = 00:01]
  Solution [0019] =  R2 u2 D2 F2 b2  [inside 3-TFS] --->  D2 u2 l2  @ 000000002637312 nodes [time = 00:01]
  Solution [0020] =  R2 u2 D2 f2 B2  [inside 3-TFS] --->  D2 u2 l2  @ 000000002637405 nodes [time = 00:01]
  Solution [0021] =  R2 F2 b2 U2 d2  [inside 3-TFS] --->  b2 F2 l2  @ 000000002844453 nodes [time = 00:01]
  Solution [0022] =  R2 F2 b2 u2 D2  [inside 3-TFS] --->  b2 F2 l2  @ 000000002844546 nodes [time = 00:01]
  Solution [0023] =  R2 f2 B2 U2 d2  [inside 3-TFS] --->  B2 f2 l2  @ 000000002917209 nodes [time = 00:01]
  Solution [0024] =  R2 f2 B2 u2 D2  [inside 3-TFS] --->  B2 f2 l2  @ 000000002917302 nodes [time = 00:01]
  Solution [0025] =  r2 L2 U2 d2 F2  [inside 3-TFS] --->  b2 d2 U2  @ 000000004467789 nodes [time = 00:02]
  Solution [0026] =  r2 L2 U2 d2 f2  [inside 3-TFS] --->  B2 d2 U2  @ 000000004467792 nodes [time = 00:02]
  Solution [0027] =  r2 L2 U2 d2 b2  [inside 3-TFS] --->  F2 d2 U2  @ 000000004467795 nodes [time = 00:02]
  Solution [0028] =  r2 L2 U2 d2 B2  [inside 3-TFS] --->  f2 d2 U2  @ 000000004467798 nodes [time = 00:02]
  Solution [0029] =  r2 L2 u2 D2 F2  [inside 3-TFS] --->  b2 D2 u2  @ 000000004470372 nodes [time = 00:02]
  Solution [0030] =  r2 L2 u2 D2 f2  [inside 3-TFS] --->  B2 D2 u2  @ 000000004470375 nodes [time = 00:02]
  Solution [0031] =  r2 L2 u2 D2 b2  [inside 3-TFS] --->  F2 D2 u2  @ 000000004470378 nodes [time = 00:02]
  Solution [0032] =  r2 L2 u2 D2 B2  [inside 3-TFS] --->  f2 D2 u2  @ 000000004470381 nodes [time = 00:02]
  Solution [0033] =  r2 L2 F2 b2 U2  [inside 3-TFS] --->  d2 b2 F2  @ 000000004477740 nodes [time = 00:02]
  Solution [0034] =  r2 L2 F2 b2 u2  [inside 3-TFS] --->  D2 b2 F2  @ 000000004477743 nodes [time = 00:02]
  Solution [0035] =  r2 L2 F2 b2 d2  [inside 3-TFS] --->  U2 b2 F2  @ 000000004477746 nodes [time = 00:02]
  Solution [0036] =  r2 L2 F2 b2 D2  [inside 3-TFS] --->  u2 b2 F2  @ 000000004477749 nodes [time = 00:02]
  Solution [0037] =  r2 L2 f2 B2 U2  [inside 3-TFS] --->  d2 B2 f2  @ 000000004480326 nodes [time = 00:02]
  Solution [0038] =  r2 L2 f2 B2 u2  [inside 3-TFS] --->  D2 B2 f2  @ 000000004480329 nodes [time = 00:02]
  Solution [0039] =  r2 L2 f2 B2 d2  [inside 3-TFS] --->  U2 B2 f2  @ 000000004480332 nodes [time = 00:02]
  Solution [0040] =  r2 L2 f2 B2 D2  [inside 3-TFS] --->  u2 B2 f2  @ 000000004480335 nodes [time = 00:02]
  Solution [0041] =  r2 U2 d2 F2 b2  [inside 3-TFS] --->  d2 U2 L2  @ 000000004550910 nodes [time = 00:02]
  Solution [0042] =  r2 U2 d2 f2 B2  [inside 3-TFS] --->  d2 U2 L2  @ 000000004551003 nodes [time = 00:02]
  Solution [0043] =  r2 u2 D2 F2 b2  [inside 3-TFS] --->  D2 u2 L2  @ 000000004623594 nodes [time = 00:02]
  Solution [0044] =  r2 u2 D2 f2 B2  [inside 3-TFS] --->  D2 u2 L2  @ 000000004623687 nodes [time = 00:02]
  Solution [0045] =  r2 F2 b2 U2 d2  [inside 3-TFS] --->  b2 F2 L2  @ 000000004830735 nodes [time = 00:02]
  Solution [0046] =  r2 F2 b2 u2 D2  [inside 3-TFS] --->  b2 F2 L2  @ 000000004830828 nodes [time = 00:02]
  Solution [0047] =  r2 f2 B2 U2 d2  [inside 3-TFS] --->  B2 f2 L2  @ 000000004903491 nodes [time = 00:02]
  Solution [0048] =  r2 f2 B2 u2 D2  [inside 3-TFS] --->  B2 f2 L2  @ 000000004903584 nodes [time = 00:02]
  Solution [0049] =  l2 U2 d2 F2 b2  [inside 3-TFS] --->  d2 U2 R2  @ 000000006345708 nodes [time = 00:03]
  Solution [0050] =  l2 U2 d2 f2 B2  [inside 3-TFS] --->  d2 U2 R2  @ 000000006345801 nodes [time = 00:03]
  Solution [0051] =  l2 u2 D2 F2 b2  [inside 3-TFS] --->  D2 u2 R2  @ 000000006418392 nodes [time = 00:03]
  Solution [0052] =  l2 u2 D2 f2 B2  [inside 3-TFS] --->  D2 u2 R2  @ 000000006418485 nodes [time = 00:03]
  Solution [0053] =  l2 F2 b2 U2 d2  [inside 3-TFS] --->  b2 F2 R2  @ 000000006625533 nodes [time = 00:03]
  Solution [0054] =  l2 F2 b2 u2 D2  [inside 3-TFS] --->  b2 F2 R2  @ 000000006625626 nodes [time = 00:03]
  Solution [0055] =  l2 f2 B2 U2 d2  [inside 3-TFS] --->  B2 f2 R2  @ 000000006698289 nodes [time = 00:03]
  Solution [0056] =  l2 f2 B2 u2 D2  [inside 3-TFS] --->  B2 f2 R2  @ 000000006698382 nodes [time = 00:03]
  Solution [0057] =  L2 U2 d2 F2 b2  [inside 3-TFS] --->  d2 U2 r2  @ 000000007967490 nodes [time = 00:03]
  Solution [0058] =  L2 U2 d2 f2 B2  [inside 3-TFS] --->  d2 U2 r2  @ 000000007967583 nodes [time = 00:03]
  Solution [0059] =  L2 u2 D2 F2 b2  [inside 3-TFS] --->  D2 u2 r2  @ 000000008040174 nodes [time = 00:03]
  Solution [0060] =  L2 u2 D2 f2 B2  [inside 3-TFS] --->  D2 u2 r2  @ 000000008040267 nodes [time = 00:03]
  Solution [0061] =  L2 F2 b2 U2 d2  [inside 3-TFS] --->  b2 F2 r2  @ 000000008247315 nodes [time = 00:03]
  Solution [0062] =  L2 F2 b2 u2 D2  [inside 3-TFS] --->  b2 F2 r2  @ 000000008247408 nodes [time = 00:03]
  Solution [0063] =  L2 f2 B2 U2 d2  [inside 3-TFS] --->  B2 f2 r2  @ 000000008320071 nodes [time = 00:03]
  Solution [0064] =  L2 f2 B2 u2 D2  [inside 3-TFS] --->  B2 f2 r2  @ 000000008320164 nodes [time = 00:03]
  Solution [0065] =  U2 d2 F2 b2 U2  [inside 3-TFS] --->  d2 l2 R2  @ 000000010305123 nodes [time = 00:04]
  Solution [0066] =  U2 d2 F2 b2 u2  [inside 3-TFS] --->  D2 L2 r2  @ 000000010305126 nodes [time = 00:04]
  Solution [0067] =  U2 d2 F2 b2 d2  [inside 3-TFS] --->  U2 l2 R2  @ 000000010305129 nodes [time = 00:04]
  Solution [0068] =  U2 d2 F2 b2 D2  [inside 3-TFS] --->  u2 L2 r2  @ 000000010305132 nodes [time = 00:04]
  Solution [0069] =  U2 d2 f2 B2 U2  [inside 3-TFS] --->  d2 L2 r2  @ 000000010307709 nodes [time = 00:04]
  Solution [0070] =  U2 d2 f2 B2 u2  [inside 3-TFS] --->  D2 l2 R2  @ 000000010307712 nodes [time = 00:04]
  Solution [0071] =  U2 d2 f2 B2 d2  [inside 3-TFS] --->  U2 L2 r2  @ 000000010307715 nodes [time = 00:04]
  Solution [0072] =  U2 d2 f2 B2 D2  [inside 3-TFS] --->  u2 l2 R2  @ 000000010307718 nodes [time = 00:04]
  Solution [0073] =  u2 D2 F2 b2 U2  [inside 3-TFS] --->  d2 l2 R2  @ 000000012349077 nodes [time = 00:05]
  Solution [0074] =  u2 D2 F2 b2 u2  [inside 3-TFS] --->  D2 L2 r2  @ 000000012349080 nodes [time = 00:05]
  Solution [0075] =  u2 D2 F2 b2 d2  [inside 3-TFS] --->  U2 l2 R2  @ 000000012349083 nodes [time = 00:05]
  Solution [0076] =  u2 D2 F2 b2 D2  [inside 3-TFS] --->  u2 L2 r2  @ 000000012349086 nodes [time = 00:05]
  Solution [0077] =  u2 D2 f2 B2 U2  [inside 3-TFS] --->  d2 L2 r2  @ 000000012351663 nodes [time = 00:05]
  Solution [0078] =  u2 D2 f2 B2 u2  [inside 3-TFS] --->  D2 l2 R2  @ 000000012351666 nodes [time = 00:05]
  Solution [0079] =  u2 D2 f2 B2 d2  [inside 3-TFS] --->  U2 L2 r2  @ 000000012351669 nodes [time = 00:05]
  Solution [0080] =  u2 D2 f2 B2 D2  [inside 3-TFS] --->  u2 l2 R2  @ 000000012351672 nodes [time = 00:05]
  Solution [0081] =  F2 b2 U2 d2 F2  [inside 3-TFS] --->  b2 l2 R2  @ 000000018174069 nodes [time = 00:08]
  Solution [0082] =  F2 b2 U2 d2 f2  [inside 3-TFS] --->  B2 l2 R2  @ 000000018174072 nodes [time = 00:08]
  Solution [0083] =  F2 b2 U2 d2 b2  [inside 3-TFS] --->  F2 l2 R2  @ 000000018174075 nodes [time = 00:08]
  Solution [0084] =  F2 b2 U2 d2 B2  [inside 3-TFS] --->  f2 l2 R2  @ 000000018174078 nodes [time = 00:08]
  Solution [0085] =  F2 b2 u2 D2 F2  [inside 3-TFS] --->  b2 L2 r2  @ 000000018176652 nodes [time = 00:08]
  Solution [0086] =  F2 b2 u2 D2 f2  [inside 3-TFS] --->  B2 L2 r2  @ 000000018176655 nodes [time = 00:08]
  Solution [0087] =  F2 b2 u2 D2 b2  [inside 3-TFS] --->  F2 L2 r2  @ 000000018176658 nodes [time = 00:08]
  Solution [0088] =  F2 b2 u2 D2 B2  [inside 3-TFS] --->  f2 L2 r2  @ 000000018176661 nodes [time = 00:08]
  Solution [0089] =  f2 B2 U2 d2 F2  [inside 3-TFS] --->  b2 L2 r2  @ 000000020220075 nodes [time = 00:09]
  Solution [0090] =  f2 B2 U2 d2 f2  [inside 3-TFS] --->  B2 L2 r2  @ 000000020220078 nodes [time = 00:09]
  Solution [0091] =  f2 B2 U2 d2 b2  [inside 3-TFS] --->  F2 L2 r2  @ 000000020220081 nodes [time = 00:09]
  Solution [0092] =  f2 B2 U2 d2 B2  [inside 3-TFS] --->  f2 L2 r2  @ 000000020220084 nodes [time = 00:09]
  Solution [0093] =  f2 B2 u2 D2 F2  [inside 3-TFS] --->  b2 l2 R2  @ 000000020222658 nodes [time = 00:09]
  Solution [0094] =  f2 B2 u2 D2 f2  [inside 3-TFS] --->  B2 l2 R2  @ 000000020222661 nodes [time = 00:09]
  Solution [0095] =  f2 B2 u2 D2 b2  [inside 3-TFS] --->  F2 l2 R2  @ 000000020222664 nodes [time = 00:09]
  Solution [0096] =  f2 B2 u2 D2 B2  [inside 3-TFS] --->  f2 l2 R2  @ 000000020222667 nodes [time = 00:09]

but I thought this was an appropriate level of pruning:

Code: 
Omnia Obtorquebantur 4x4x4 Version 2.0.7 [with Partial Pattern Minimal Distance Pruning] compiled on December 07, 2014.



                          TOP
                          ---------------------
                          |^^^^|OOOO|^^^^|OOOO|
                          ---------------------
                          |OOOO|^^^^|OOOO|^^^^|
                          ---------------------
                          |^^^^|OOOO|^^^^|OOOO|
                          ---------------------
                          |OOOO|^^^^|OOOO|^^^^|
                          ---------------------

  LEFT                    FRONT                   RIGHT                   BACK
  ---------------------   ---------------------   ---------------------   ---------------------
  |&&&&|&&&&|&&&&|&&&&|   |~~~~|####|~~~~|####|   |XXXX|XXXX|XXXX|XXXX|   |####|~~~~|####|~~~~|
  ---------------------   ---------------------   ---------------------   ---------------------
  |&&&&|&&&&|&&&&|&&&&|   |####|~~~~|####|~~~~|   |XXXX|XXXX|XXXX|XXXX|   |~~~~|####|~~~~|####|
  ---------------------   ---------------------   ---------------------   ---------------------
  |&&&&|&&&&|&&&&|&&&&|   |~~~~|####|~~~~|####|   |XXXX|XXXX|XXXX|XXXX|   |####|~~~~|####|~~~~|
  ---------------------   ---------------------   ---------------------   ---------------------
  |&&&&|&&&&|&&&&|&&&&|   |####|~~~~|####|~~~~|   |XXXX|XXXX|XXXX|XXXX|   |~~~~|####|~~~~|####|
  ---------------------   ---------------------   ---------------------   ---------------------

                          BOTTOM
                          ---------------------
                          |OOOO|^^^^|OOOO|^^^^|
                          ---------------------
                          |^^^^|OOOO|^^^^|OOOO|
                          ---------------------
                          |OOOO|^^^^|OOOO|^^^^|
                          ---------------------
                          |^^^^|OOOO|^^^^|OOOO|
                          ---------------------


 
  Solutions To Scramble = l2 R2 [ROTATE z'] l2 R2 [ROTATE x'] [ROTATE z'] [ROTATE x] l2 R2 [ROTATE y] [ROTATE x] l2 R2 [ROTATE y] 
 
  Solution [0001] =  R2 U2 d2 F2 b2  [inside 3-TFS] --->  d2 U2 l2  @ 000000000450649 nodes [time = 00:04]
  Solution [0002] =  R2 U2 d2 f2 B2  [inside 3-TFS] --->  d2 U2 l2  @ 000000000450684 nodes [time = 00:04]
  Solution [0003] =  R2 u2 D2 F2 b2  [inside 3-TFS] --->  D2 u2 l2  @ 000000000451845 nodes [time = 00:04]
  Solution [0004] =  R2 u2 D2 f2 B2  [inside 3-TFS] --->  D2 u2 l2  @ 000000000451880 nodes [time = 00:04]
  Solution [0005] =  R2 F2 b2 U2 d2  [inside 3-TFS] --->  b2 F2 l2  @ 000000000454484 nodes [time = 00:04]
  Solution [0006] =  R2 F2 b2 u2 D2  [inside 3-TFS] --->  b2 F2 l2  @ 000000000454519 nodes [time = 00:04]
  Solution [0007] =  R2 f2 B2 U2 d2  [inside 3-TFS] --->  B2 f2 l2  @ 000000000455752 nodes [time = 00:04]
  Solution [0008] =  R2 f2 B2 u2 D2  [inside 3-TFS] --->  B2 f2 l2  @ 000000000455787 nodes [time = 00:04]
  Solution [0009] =  U2 d2 F2 b2 U2  [inside 3-TFS] --->  d2 l2 R2  @ 000000000638472 nodes [time = 00:04]
  Solution [0010] =  U2 d2 F2 b2 u2  [inside 3-TFS] --->  D2 L2 r2  @ 000000000638475 nodes [time = 00:04]
  Solution [0011] =  U2 d2 F2 b2 d2  [inside 3-TFS] --->  U2 l2 R2  @ 000000000638478 nodes [time = 00:04]
  Solution [0012] =  U2 d2 F2 b2 D2  [inside 3-TFS] --->  u2 L2 r2  @ 000000000638481 nodes [time = 00:04]
  Solution [0013] =  U2 d2 f2 B2 U2  [inside 3-TFS] --->  d2 L2 r2  @ 000000000638683 nodes [time = 00:05]
  Solution [0014] =  U2 d2 f2 B2 u2  [inside 3-TFS] --->  D2 l2 R2  @ 000000000638686 nodes [time = 00:05]
  Solution [0015] =  U2 d2 f2 B2 d2  [inside 3-TFS] --->  U2 L2 r2  @ 000000000638689 nodes [time = 00:05]
  Solution [0016] =  U2 d2 f2 B2 D2  [inside 3-TFS] --->  u2 l2 R2  @ 000000000638692 nodes [time = 00:05]
  Solution [0017] =  u2 D2 F2 b2 U2  [inside 3-TFS] --->  d2 l2 R2  @ 000000000690182 nodes [time = 00:05]
  Solution [0018] =  u2 D2 F2 b2 u2  [inside 3-TFS] --->  D2 L2 r2  @ 000000000690185 nodes [time = 00:05]
  Solution [0019] =  u2 D2 F2 b2 d2  [inside 3-TFS] --->  U2 l2 R2  @ 000000000690188 nodes [time = 00:05]
  Solution [0020] =  u2 D2 F2 b2 D2  [inside 3-TFS] --->  u2 L2 r2  @ 000000000690191 nodes [time = 00:05]
  Solution [0021] =  u2 D2 f2 B2 U2  [inside 3-TFS] --->  d2 L2 r2  @ 000000000690393 nodes [time = 00:05]
  Solution [0022] =  u2 D2 f2 B2 u2  [inside 3-TFS] --->  D2 l2 R2  @ 000000000690396 nodes [time = 00:05]
  Solution [0023] =  u2 D2 f2 B2 d2  [inside 3-TFS] --->  U2 L2 r2  @ 000000000690399 nodes [time = 00:05]
  Solution [0024] =  u2 D2 f2 B2 D2  [inside 3-TFS] --->  u2 l2 R2  @ 000000000690402 nodes [time = 00:05]
  Solution [0025] =  F2 b2 U2 d2 F2  [inside 3-TFS] --->  b2 l2 R2  @ 000000001097301 nodes [time = 00:05]
  Solution [0026] =  F2 b2 U2 d2 f2  [inside 3-TFS] --->  B2 l2 R2  @ 000000001097304 nodes [time = 00:05]
  Solution [0027] =  F2 b2 U2 d2 b2  [inside 3-TFS] --->  F2 l2 R2  @ 000000001097307 nodes [time = 00:05]
  Solution [0028] =  F2 b2 U2 d2 B2  [inside 3-TFS] --->  f2 l2 R2  @ 000000001097310 nodes [time = 00:05]
  Solution [0029] =  F2 b2 u2 D2 F2  [inside 3-TFS] --->  b2 L2 r2  @ 000000001099884 nodes [time = 00:05]
  Solution [0030] =  F2 b2 u2 D2 f2  [inside 3-TFS] --->  B2 L2 r2  @ 000000001099887 nodes [time = 00:05]
  Solution [0031] =  F2 b2 u2 D2 b2  [inside 3-TFS] --->  F2 L2 r2  @ 000000001099890 nodes [time = 00:05]
  Solution [0032] =  F2 b2 u2 D2 B2  [inside 3-TFS] --->  f2 L2 r2  @ 000000001099893 nodes [time = 00:05]
  Solution [0033] =  f2 B2 U2 d2 F2  [inside 3-TFS] --->  b2 L2 r2  @ 000000001216978 nodes [time = 00:05]
  Solution [0034] =  f2 B2 U2 d2 f2  [inside 3-TFS] --->  B2 L2 r2  @ 000000001216981 nodes [time = 00:05]
  Solution [0035] =  f2 B2 U2 d2 b2  [inside 3-TFS] --->  F2 L2 r2  @ 000000001216984 nodes [time = 00:05]
  Solution [0036] =  f2 B2 U2 d2 B2  [inside 3-TFS] --->  f2 L2 r2  @ 000000001216987 nodes [time = 00:05]
  Solution [0037] =  f2 B2 u2 D2 F2  [inside 3-TFS] --->  b2 l2 R2  @ 000000001219561 nodes [time = 00:05]
  Solution [0038] =  f2 B2 u2 D2 f2  [inside 3-TFS] --->  B2 l2 R2  @ 000000001219564 nodes [time = 00:05]
  Solution [0039] =  f2 B2 u2 D2 b2  [inside 3-TFS] --->  F2 l2 R2  @ 000000001219567 nodes [time = 00:05]
  Solution [0040] =  f2 B2 u2 D2 B2  [inside 3-TFS] --->  f2 l2 R2  @ 000000001219570 nodes [time = 00:05]

The difference is, one program can take 15 minutes to finish ply 10, and the other can solve the Single Dedge flip in less time. I thought it was an acceptable tradeoff. But it's not acceptable if the transposition filter removes all of the optimal solutions at the proper depth.
 
Last edited:
I don't know how relevant this is, based on how you did things, but perhaps you could reduce the number of solutions by only considering one way to write each move on a given axis. For instance, R2 l2 and l2 R2 are the same (up to a rotation), as are U u and D d. Then you would at least not be printing 96 solutions.

Actually, with the current setup, you would never print every solution anyway - once you find a position inside your TFS database, you only produce one solution, right? There may be more than one.
 
qqwref said:
I don't know how relevant this is, based on how you did things, but perhaps you could reduce the number of solutions by only considering one way to write each move on a given axis. For instance, R2 l2 and l2 R2 are the same (up to a rotation), as are U u and D d. Then you would at least not be printing 96 solutions.

Actually, with the current setup, you would never print every solution anyway - once you find a position inside your TFS database, you only produce one solution, right? There may be more than one.
Click to expand...

The attempt was made to reduce the size of the game tree, and the result was the reduction of the solution count in exchange for searching much deeper and much faster. Did you see the 22-ply "snake" solve in under 1 minute?

fastest_snake_solve_ever.jpg


That was just too incredible to fathom. In scrambles where there are so many symmetrical solutions, pruning away even one set early enough in the move generation phase has tremendous impact on tree reduction. Look at one of the solutions starting out F2 f2.... Everyone one of the permutations with f2 F2 and r2 R2 that are ignored alone will make the tree 64 times smaller. Now multiply that by each rotation state, and aggregate the node reduction from each early stage of the tree on out to the final depth, and it's like taking a chainsaw to the game tree.

The problem is, in scrambles where this symmetry reduction happens to factor out even a single node that was necessary to examine en route to an optimal solution will have the potential to miss that solution entirely.
 
I'm not completely sure what you're talking about, as the example you posted doesn't quite do what I mean. You have solutions beginning with both F2 f2 and b2 B2, whereas I'm suggesting that since those positions are the same (up to a rotation) you only allow one of the two sequences.
 
Status
Not open for further replies.

Similar threads

P
Announcing: Competition Cubes - A Ranked Speedcubing Website
Replies
4
Views
1,279
Phantom37
P
E
Announcing the United States School Cubing League (USSCL) Season 3!
Replies
4
Views
792
ea99
E
Calode
Announcing LetsCube! A real-time racing website
Replies
6
Views
3,119
abunickabhi
abunickabhi
M
Announcing: Vintage Cube Sale/Store
Replies
3
Views
1,102
herbs1685
H
penguinz7
Announcing our new Canadian collab channel, Cubing Province
Replies
1
Views
944
penguinz7
penguinz7
Back
Top