[r-t] Viking D Royal [was Exhausted search spaces]

[Mark Davies]

Don writes,

> This search required 13.05 seconds to actually search the graph I
> generated, though probably longer than that just setting up the graph
> to be searched and doing other pre-search optimizations. It visited
> 12.09 million nodes, and resulted in 6 distinct solutions.

The music pruning you do definitely gives you a big advantage over SMC32 
for this kind of search. I implemented a (fairly primitive) type of 
music pruner in Elf (which simply finds an upper bound on the amount of 
remaining music, rather than running a separate BFS) and this proved 
very effective. It's definitely on the to-do list for SMC32.

Pretty much any pruning you can do helps tree searches enormously. The 
agressive recursive false predecessor/successor node pruning you do at 
every stage in the search is good, too, despite what seems to be a large 
overhead in backtrack. Unfortunately this kind of thing is harder to 
implement in assembler, so any experimentation with that in SMC32 is 
probably going to have to wait for a change in language. I don't think 
it's true to say that you should not optimise your inner loop, though. 
What SMC32 considers to be the inner loop is very much an outer loop for 
you, but you still do have an inner loop - the recursive call in the 
falseness pruning bit.

Anyway, I've just run your search in SMC32, and it found what are 
presumably the same six solutions - certainly the top-scoring one 
matches the composition you printed. Total runtime was 39 minutes, so 
many times slower than yours. It's easy to see how the lack of pruning 
hurts - my code had to churn though 93.7 billion nodes to get the same 
results.

I'm interested how you knew that compositions existed matching your very 
tight criteria, though. Educated guess, or did you run a few preparatory 
searches first? That's one thing I really liked with the Elf music 
pruning I implemented - the minimum limits on music (as well as other 
factors such as COM) are set by the program as it runs; as better and 
better compositions are found, the limits are automatically raised, thus 
speeding up the search. Of course, this makes displaying an accurate 
percentage complete value even more difficult. It does make for a very 
user-friendly program though (which SMC32 most certainly isn't).

MBD