sje wrote:bob wrote:
There are three levels of this...
(1) generate all moves and move captures to the front. We did this in Cray Blitz because we used the vector hardware to move things around, which was way fast.
(2) generate one at a time. I've never liked this. I tried it in early Crafty versions, as it is somewhat faster since you don't have to take the bit moves and unload them into an array. But you lose flexibility for ordering, if you want to do anything cute. Currently I don't do any ordering but used to use the history heuristic which doesn't translate very well to generating one at a time.
(3) The crafty approach, which is to generate captures only, and then to generate non-captures. The advantage of this is that the q-search doesn't need the non-captures, so not producing those saves time. Generating captures first also provides a ton of quick cutoffs and avoids the bigger job of generating non-captures. I've been doing this for many years because of the speed advantage it gives.
In the quiescence search it's a different story. The new Symbolic has a gainer generator (captures plus promotions) that's used there and this may be extended to include some special generators seen in the old Symbolic (gainers plus checks, gainer checks, checks, etc.) as appropriate.
The new Symbolic, like the old one, has a gainer generator and a holder generator (like its predecessor Spector and like Crafty) along with a separate all-moves generator. The all-moves generator call is always faster than a gainer generation call followed by a holder generation call. So if at least one holder move needs searched, then the all-moves mode is a win. And because of the factors mentioned earlier along with the program's bitboard database implementation, the all-moves call is pretty much a win everywhere else. Even in the endgame where the transposition table hit rate is high and the cutoff rate is also high, the all-moves call wins because there are usually fewer moves and they are generated quickly.
I'm not convinced. I did a ton of testing before I decided to split the move generator into two parts. The q-search is obviously a no-brainer. But the normal search has a majority of its nodes where a capture is the best move to refute a stupid move at the previous ply.
I have four generators.
GenerateCaptures()
GenerateNonCaptures()
GenerateChecks()
GenerateCheckEvasions()
To generate all moves you have to call the first two in succession. Since captures are so often the best move, I do that first, and after having exhausted the good-looking captures, I generate the rest, saving that effort if a capture is good enough.
GenerateCheckEvasions() is a legal-move generator and is only used when a node starts off with the side to move in check. GenerateChecks() is used in the first level of the q-search only to include checking moves there.
The only real downside to the all-moves approach is the processing time incurred for incremental updating of the bitboard database. This is significant in Symbolic to be sure. But it pays off in many other areas of the program including move generation, evaluation, pins (detection and effects), swap analysis, and move ordering. Also, Symbolic never has to test for a pseudolegal move or an insane move from a table.
Perhaps the biggest gains from the all-moves approach will be seen in move ordering. One idea taken from Chess 4.x is to search all moves, both gainer and holder, by a particular piece. Tough to do in some modes, but easy with all-moves in play. Similar: all moves that attack a given piece, all moves that defend a given piece, etc.
If I were doing any of that, I would agree. However Crafty is still "brute force" and doesn't try targeted generation for anything at all, nor is it likely to do so in the near future if at all.