At move generating depth 7, where ply-10 is being examined, I encounter positions that are proven to be 6 turns from a center-only solved state. That is looking ahead another 3-ply from the present depth. A 13-ply solution is found during move generation depth 7. This must be accounted for by some compounding measure where depth of solution = depth of center database + depth of game tree - depth of complete TFS database. 13 = 10 + 6 - 3 in this case. This is the exact formula I use to determine where in the PV to insert the move description for the solution that was found
OK, I understand now pretty much what your solver is doing.
You are checking for a special type of position (in this case, all corner and edge pieces solved), and then checking a database to see if it knows how to solve it (or at least knows its depth), and then, if that's the case, reports that solution. These databases for these special cases can be significantly deeper than TFS databases can be.
In your example, you have a goal depth of 10, and building a search tree out to depth 7 since at that point you can determine if a 10-move solution exists for any of the nodes at depth 7 from the scramble position. But you also check if the position is of the special type. For a certain node, you find this is the case, and know that it has a 6-move solution. So you are basically checking for a possible solution that is
deeper than the current goal depth. In this case, you find a solution that is 7 + 6 = 13 moves, while you haven't finished verifying if a 10-move solution exists. The solution you found
may be suboptimal. In this case, it is not. My solver found an 11-move solution in about 8 seconds:
R B U2 r l U2 B2 D2 R B2 b2.
Most optimal solvers don't bother spending any time looking for solutions deeper than the current goal depth. In doing so, there is a possibility you may be able to find a near-optimal solution much sooner than you would find a (guaranteed) optimal solution. On the other hand, you might simply spend extra time checking a lot of positions for such special cases without any success. You have to realize that the percentage of overall positions that have all corners and edges solved is miniscule. They may be somewhat over-represented among positions closed to solved, but you need to be careful in considering whether or not the possible benefit (and the likelihood of such benefit) outweighs the extra time spent.
There is such a thing as additive pruning heuristics, but you only assume pruning heuristics are additive if you have proven them to be. For instance, if you having a pruning table the says you need to make at least 6 outer layer turns (regardless of how many inner layer turns might also be needed) to arrive at the solved state, and another pruning table that says you need at least 4 inner layer turns (ignoring any outer layer turns are also needed) to arrive at the solved state, then you know that you must be at least 6+4 = 10 single-layer turns from solved.
Actually, I found out this is not true when I was first investigating solving the center databases. I started generating all the center positions that resulted from making only inner layer turns, adding them to a hash table in the order in which they occurred if they were unique, under the premise if the move sequences did not occur at a shallower depth, this must be the optimal path to the position. That was a faulty assumption. There are shortcuts to many inner-slice-only generated positions that involve turning the outer faces.
No, your "counterexample" does not directly relate to my point.
Let's say you found a position that can be solved either with 6 inner layer turns (no other turns). Let's say there is another ("shortcut") solution having 2 inner layer turns and 2 outer layer turns. The inner layer pruning heuristic would say at least 2 inner layer turns are required. The face turn heuristic will say you need at least zero face turns because a solution exists that doesn't use any face turns. You add the two heuristics and you get that at least 2 + 0 = 2 turns are required. In actuality, you really need 4 turns in this example. But the additive heuristic has not overestimated the distance to solved, so it is a valid heuristic.
Tossing out a position that was 11 moves from a candidate solution with no hope of being solved at the present level is almost always a good thing. Only now, we do a second test on the same node to make sure it is also out of range of the databases. Now imagine the multitude of 11-ply toss-outs and the resulting tree reduction. The subset of positions that get passed through might be soluble within the sum of the targeting ranges. That's 11 plies worth of "noise" that did not need to be waded through to hit upon it. I guess it can't be double-counted in this fashion.
I did
