[r-t] Exhausted search spaces
mark at snowtiger.net
Sat Mar 6 12:01:31 UTC 2010
> Just ran it again using exactly these parameters: run time now
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.
More information about the ringing-theory