I opened this thread to conduct a sort of blog on comparing the speed of
several experimental mailbox algorithms. The speed comparison of the various
techniques will be done for a toy 'model engine', which uses a fixed-depth search
plus capture-only quiescence (including delta pruning), with MVV/LVA sorting of the captures,
and an evaluation of PST plus (optionally) mobility.
No hash table, no killer or history heuristic,
so basically no particuar move ordering of the non-captures;
the time-to-depth is not really of interest here, we will be comparing nodes per second.
To not lose ourselves in details, promotion, castling and e.p. capture will be omitted.
The speed will be measured in a search of the KiwiPete position.

r3k2r/p1ppqpb1/bn2pnp1/3PN3/1p2P3/2N2Q1p/PPPBBPPP/R3K2R w KQkq - 0 1

The first design to be tested will be the 16x12 mailbox + piece list.
We should already have a rough idea how this works, because
Qperft* (*super fast perft by H.G. Muller - note by CMK) uses this design.
It does a perft(6) of KiwiPete in 45 sec, with bulk counting.
That means it has done move generation in perft(5) nodes (193M nodes), which translates to 4.26 Mnps.
But because that is perft there are two effects that slow it down compared to a search:
there is some legality testing (on King moves), which a search based on pseudo-legal moves would not do.
But, more importantly, in perft all nodes are 'full width', while in a search most nodes are QS nodes.
Refraining from putting the non-captures in a move list would speed up move generation appreciably.
And QS nodes that experience a stand-pat cutoff will not have to generate moves at all.
(At least, if the evaluation doesn't include mobility.)
So the search should be significantly faster, perhaps even double.

We will see shortly...
read more...

gcc -Ofast mailbox7.c -o mailbox7