Excellent, so now we have a position that we know is at least 13 moves from
the start (if I interpret your screenshot correctly). Do you agree? This is a
start.
The program is still searching the 13th ply. So we can say with certainty it is at least 12 moves from a solved state. You can see
(08/36) right before the PV. That means it is on move number 8 of 36 in the current depth.
Can we find positions that we know are at least 14 moves from start? 15?
(I think we have some from an earlier investigation, but it would be nice
to give them here.)
Do you mean other positions, or "play into the line" one ply at a time and do 13-ply searches to functionally test for a depth of "13 + d" where d is the number of plies we advance manually?
For example, from the scrambled position, if I play the move
F, then search 13-ply, we have functionally searched 1 out of the 36 moves to a depth of 14.
If we recreate the scramble, then play the move
F', then repeat the 13-ply search, we have no searched 2 out of the 36 moves to a depth of 14. Etc., Etc.
While these are clearly not proof of antipodal positions, the fact that we've
actually proved a concrete position to be at least a particular distance away
is progress.
Yes but that branching factor of 36 is a real killer.
If we find a symmetric position and use symmetry to reduce the search, we
can probably get another ply deeper (maybe even two plys).
I am on a 16-core machine but I have parallel searching off. My earlier parallel implementations were very fast, but ultimately flawed, as the intrepid Bruce Norskog was able to demonstrate. I disabled all of the parallel code and stripped out a great deal of the dead wood. If someone wants to take a crack at parallelizing the code, I'm willing to donate the code.
By the way, my move generator only executes 6 lines of C-code to generate a legal 4x4x4 move. It is slowed down by probing the 16 GB hash tables and generating 64-bit hash numbers and resolving hash conflicts. Otherwise it's speed is in the 50 million moves per second range using a single CPU core.
Long term, in order to raise the lower bound, we need to prove a particular
position to be deeper than the simple pigeonhole argument (or else use
another technique). For instance, some of the subgroup DP approaches
(to calculate counts of canonical move sequences for cosets of subgroups)
may be able to increase the lower bound without finding a concrete position.
Some may argue we are so far from being able to solve a random position
optimally, that this is a fool's errand. But I think there is a lot to be
learned from the attempt.
I have a few ideas regarding optimal solutions as well. Are you familiar with so-called "Dropout Expansion" by Thomas Lincke? Programmers Martin Fierz and Edward Gilbert used this technique to develop automated opening books for their checkers programs using this technique. Their implementation was very effective, making their programs virtually bullet proof in the opening.
http://www.fierz.ch/strategy4.htm
I am convinced this approach would work well for scrolling into a solution-attack line, then backing up as needed. All that is required is an evaluation function, which can be as simple as an enumeration of correct colors per cube side, maybe with goal-directed bonuses for centers to be prefered over edges, and so on. Fixed depth searches with conspiracy numbers to guide the way will insure that positions with color counts improving get searched more deeply than those positions where there is little to no progress, or worse, lost progress.
