Jan Brouwer wrote:bob wrote:hgm wrote:I want to try an approach in the engine that I am currently building where I update a list (or perhaps bitmap) of attackers only for occupied squares. That cuts down a lot on the effort needed to do the update. For one, only captures and pseudo-captures (= defending your own piece) have to be in the tables, and when a piece moves you only have to remove its captures from the old square (which might be an empty set, and in general only has very few elements), and add those that can be made from the new square (which unavoidably require some move generation, as these depend on the piece type of the mover). And you have to continue all slider moves that went to the from square, as these were discovered. But also there, you have the list available (as the from square was occupied), and the list is usually empty.
And if the move is a capture, that is really all you have to do: captures don't block any slider moves that were not already blocked by the victim. The piece just inherits the attacks and defenses on it from its victim. Which is automatic, as the lists are tied to the squares, and not to the pieces. And almost all moves made are captures, as almost all nodes searched are QS nodes. Only in the MakeMove of the full-width search you have to worry about non-captures blocking slider moves on a square you have no information on (as it was empty, and the lists of attacks tied to it miht be stale). So there you have to go through the tedious process of viguring out which sliders of both sides attacked it, by running through the slider lists and doing 0x88 attack test. But who cares what you do in the full-width search? That is only a small fraction of the nodes, and most of those do not get to the point where non-captures are searched, as null move or aptures are search earlier and will typically cause a cutoff.
Of course you do the update of the attacker lists in QS only after having decided you are going to search a move: if there is a stand-pat cutoff, or no captures, or only captures with negative SEE, or only futile captures, there is no reason to do it (so that you also don't have to undo it). you then simply return the eval. Of course generating the moves is now only running through the list of non-futile victims, to check if you have attacks on them.
That was the basic chess 4.x idea. And it was where I started in Crafty. But there is a fly in the ointment. Those incremental updates are expensive. And at today's speeds, you make 20 moves or more to reach an endpoint position. At which point you might use some of that info or not. Ditto for any CUT node in the tree. All the incremental update cost is amortized over a single move that causes a cutoff and then you get to un-update (or you can try copy/make which will kill a PC) the stuff and start over. If you look at crafty's source, you can see where I stopped the incremental update stuff and went to on-demand computations. And speeded things up significantly. If you have something that is very costly to compute from scratch, and easy to incrementally update it, this will be a good approach. But if not, it is beyond expensive.
Did you do incremental updates for all squares, or only for occupied squares?
It seems that if you do it only for occupied squares, and only maintain a list of squares that attack an occupied square (and not a list of squares that the piece on the occupied square attacks), this might still be quite fast. For capture moves you basically have to perform twice the capture move generation of the moving piece, plus scanning a few extra rays and updating a few small lists. And if you do the update lazily, it only has to be done for roughly half the nodes.
Still, there might be too many unpredictable branches involved in the list manipulation for this to work out I guess.
I only incrementally updated what actually could change. For example, chess 4.x mentions the attacks_to and attacks_from bitmaps. They kept two sets of things, a bitmap showing attacks from a given occupied square, and a bitmap showing attacks to any given square. I updated only what was necessary. For example, attacks_from square X was only affected by another piece moving if the piece on square X was a slider, and if the piece being moved was on one of the "rays" from that square. So I very carefully only updated exactly what was changed.
Note that this was prior to rotated bitboards. The problem with the above was that each make/unmake had a significant amount of work to do, and the fastest way was to use the copy/make approach so that the unmake operation was not needed. When I went to rotated bitboards, I went to make/unmake at the same time since the PC has very poor memory bandwidth, and the incremental update was dropped at the same time since it was not faster to calculate these attacks on demand rather than maintaining them incrementally. And my speed went way up as a result.
I incrementally update the material count, presently, since it only needs adjusting on a capture or promotion, but that is all that I currently do. If you only search 7-8-9 plies deep as we did in the Cray Blitz days, incremental updating makes sense. But when you start averaging 20+ plies, with extensions taking you to 30-40 plies deep overall, incremental update begins to become more expensive than on-demand computation. For material, this doesn't happen, but imagine doing 40 incremental updates, where half of the updates are done and undone more than once as pieces move on and off of a blocked diagonal for a bishop. You do the update multiple times, you use it once. Not a good deal. So done right, it can be useful. But I have seen lots of examples where it is done because it is thought to be good, when in reality it is actually hurting performance...
