[r-t] Viking D Royal [was Exhausted search spaces]
mark at snowtiger.net
Sun Feb 7 16:42:11 UTC 2010
> 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
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).
More information about the ringing-theory