hgm wrote:Spartacus indeed has staged move generation. It generates captures victim by victim, starting from the MVV from the opponent piece list, running through the stm piece list and doing 0x88 attack tests. A stage encompasses generation of captures of all victims of the same (approximate) value, and is followed by a bubble sort by attacker value. (As the stm piece list is traversed LVA first, this never requires many steps.) Then follow two killer stages, then non-capture generation, and finally bad captures, which are captures that were postponed based on guaranteed negative SEE (protected victim, and victim +protector < attacker). In QS everything from the killer stages is skipped, as it also is at d=1 when non-captures are futile (or even during the capture stages when it encounters a futile victim). Hash move and null move are also separate stages, done before any move generation. But after generation of King captures and check test. (Some improvement is possible here, by checking for King captures in the parent node.)
I've been thinking about doing some sort of staged move generation, since it seems to me you could safe quite a bit of time that way. At the moment, I generate all moves, score them and then sort them (with quicksort). This gives hash move, winning captures, killer moves, losing captures, quiet moves. I'm experimenting with flipping the order of quiet moves and losing captures, but so far that doesn't seem to help much overall.
It's a lot of extra work that's ultimtely unnecessary if the hash move ends up causing a cutoff. In Jazz, I actually keep track of the move with the highest score, and I try it before sorting the rest of the list. This already speeds things up nicely.
Spartacus is also fast because there is virtually no evaluation. It is just PST + material table + Pawn hash.
Sjaak has material, PSQ, mobility and king safety. Mobility is a fairly expensive thing to calculate, but it helps a lot for playing strength. The obviously missing element is some notion of pawn structure.
It does not have particularly severe reductions. I use R=2 for null move, and reduce remaining non-captures by 1 ply.
Sjaak is actually more agressive than that: I prune after a null move fails high (except if it fails high with a mate score) and I reduce moves lower down on the list by 1 or 2 ply, depending on the type of move. I've wondered whether this is too much, but if I reduce less it seems to perform worse in practice...