[r-t] Exhausted search spaces

[Richard Smith]

Simon Humphrey wrote:

> Out of idle curiosity I just ran SMC on the sample search provided by
> MBD for extents of PB6, and stoppped it after 6 minutes.
> In that time it had produced 5.5 million compositions, occupying 344
> megabytes of disk space, and (it claimed) was 0.52% through the search.

I find this rate of progress astonishing.  I've coded up 
what I reckon is a pretty smart search algorithm, while not 
being too specific to PB6.  But my code only found 602,675 
methods in 6 minutes.  I can't believe hand coded assembler 
is a whole order of magnitude faster, so this suggests that 
I'm missing some tricks.  So, Mark, Graham, spill the beans. 
How do you do it?

I'm also curious as to how you estimate the proportion of 
the way through.  I'm guessing that you are pruning 
rotations as you do the search, as I've found this makes a 
big speed improvement.  But, in the obvious way of doing 
this, the part of the search tree is far deeper around the 
earlier branches.  For example, if you order the calls p, b, 
s, then the part of the search tree beginning pp includes 
all extents that have two consecutive plain leads in them 
(which must be the vast majority), while the pb and ps 
branches contain those extents that have no consecutive 
plains, and the b and s branches contain no extents as all 
extents include plain leads.  In other words, the last 67% 
of the search space can be pruned down so heavily that it 
can be searched in microseconds.

RAS