[r-t] Exhausted search spaces

[Mark Davies]

Simon writes,

> Just ran it again using exactly these parameters: run time now
> 1h03m04s.

That's truly superb.

Whilst in general methods with a high degree of falseness are more 
amenable to brute-force searching, because the falseness prunes the 
search tree, in practice there are still plenty of examples where the 
search space is disappointingly large - like the Full Monty for 
Cambridge Major. For searches like this, a large proportion of the 
runtime is spent checking and marking false nodes.

The "bittruth" optimisation uses a bitwise table to hold the node truth 
flags, and this is accessed using 32-bit words in order to allow 
multiple false nodes to be checked and marked simultaneously. For this 
search, there are an average of 10.6 false nodes per node, but the 
bitwise approach allows these to be checked or marked in an average of 
5.4 operations, hence reducing the time taken for checking falseness, 
and giving a useful percentage reduction in overall search time.

With the later SSE instructions sets, it would be possible to do the 
same thing, but using 128-bit words. Since there are only 600 nodes in 
this search space, the whole truth table would fit in five words, and 
the average number of words to be processed per node would likely halve 
again. (If the truthtable is in L1 cache, a 128-bit operation is just as 
fast as a 32-bit one.)

What's more, I see that forthcoming versions of SSE will include 256-bit 
operations. Those ten false nodes per node could in theory reduce down 
to not much more than one checking operation per node - the same as a 
CPS search. That would definitely bring the FM down to less than an hour.

MBD