hgm wrote:That makes a lot of assumptions. Smarter perft programs, e.g. incrementally calculating the number of moves in the last ply rather than generating them all, could easily speed up the calculation by a factor 30 compared to existing perft programs. The forelast move does not have that much effect on what the opponent can move. Many moves have no effect at all (if they do not happen to block or unblock enemy sliders, attack squares next to the king, or pin pieces), and their contribution would be equal to perft(1) after null move, which you could calculate once and then use for all such moves.
This is the theory behind the development version of gperft. In practice, I am not getting anywhere close to a factor of 30. Or even a factor of 2.
The problem is that last Makemove/Count/Unmakemove can be done quite quickly anyhow. I've had a specialized MCU() function just for this since the early versions; if you can quickly exclude certain moves then the M and U sections reduce to some quite simple code if the C section is modified to account for the fact that the M is cheating and not updating the entire board structure.
When you try to get smart and use a nullmove perft(1), or portions of it, the question becomes... how quickly can you figure out what needs recomputing? Yes, it is generally quicker than a MCU call, but it is not trivial. Is the move a checking move? Are you removing or adding pins? Are you blocking sliders, or removing blocks? Are you attacking or removing attacks on squares next to the king, changing king moves? etc.
There are a lot of different possibilities to try out though. Do you simply try to identify moves which have no effect at all so you can use the null move value directly? Or do you try to determine which pieces have a different move count and just update those pieces? And how accurate are those determinations? (i.e. if you find every case where a queen's moves don't change, it will probably take longer to decide than simply computing the queen moves. If you do a really fast check, you might only catch a small fraction of the times you can skip that queen.)
It depends a lot on the position. Some changes can speed one position up by 20% or more, and slow others by the same amount. My current version has a worst case speedup of about 5% for some pathalogical positions (things like the positions with 218 legal moves, for example), about 40% for the initial position, and about 25% for a typical opening position. This compared to the last release of gperft. I am still slowly testing out possibilities though, hopefully I can extract a little more speed.