How to incrementally update attack tables?

[maksimKorzh]

Hi guys! I want to implement attack tables in order to reduce is_square_attacked() function's execution time. I use 0x88 board representation and keep track of the piece lists. I DO NOT want to use bitboards and any kind of pre-calculated attack tables for all pieces, for that takes lot's of amount of code and I want to keep my engine as small as possible. So I came up with an idea to use unused right part of the board array to represent the attacks. In my dreams it has to work as follows - say I need to know whether a given square is attacked or not - I'll add 8 to sq and bitwise it with 1, like so
board[sq + 8] & 1.

I've already initialized the right part of the board via bitwise OR'ing sq + 8 with the side(8th bit for white, 16th bit for black), so that square may be equal to 8 if attacked by white, to 16 - if attacked by black, 8 + 16 or 8 | 16 - if attacked by both sides, or 0 if not attacked.

My problem is that I have no idea how to proceed with incremental updates of attack board? Is it possible without using bitboards? And is it done? Chess programming wiki says something like "some programmers use incremental updates of attack maps..." but no implementations. Where can I get some code examples or any resources at this subject. Appreciate your help.

[hgm]

Incrementally updating attack maps is a very complex issue, as you have to take care of slider bocking/discovering, piece displacement and capture. I once posted a long monologue here how I did it for Tenjiku Shogi (where incremental methods are very competitive, as the board is 16x16 with 78 pieces each, so that generating everything from scratch in each position is very costly). Search for 'The Inferno thread'.

In Chess calculating things from scratch is orders of magnitude cheaper than in Tenjiku Shogi, so you are not automatically superior with an incremental method, but must use a really good one. Key is to not update the map unless you need it; it is often possible to postpone the update, or the major part of it. The point is that the move leading to the position was made by the opponent of the side to move, and could only affect the moves (and thus attacks) of the latter by discovering a slider ('pin punish'), blocking one, or capturing a piece. The second case can only happen on non-captures (don't put e.p. capture in the map, but treat it separately), and these are rare, as most of your search is QS. Capture just makes moves disappear; if you give each piece its own bit in the attack map, you can AND the map elements with a 'presence map' before you use them, and you would only have to clear the bit for the captured piece in that mask to take the capture into account.

So what you should do is first update the map for opponent slider discovery; the map itself tells you which sliders attacked the piece that moved away, (usually none!) and you can then just displace those attacks to the next target down-stream. (Use a 10x10 board with uncapturable 'edge guards' around it, so that attacks can also be displaced to these guards when there was nothing behind the moved piece.) There could be new attacks on the moved piece, but after a capture (the common case) these are simply inherited from the piece that was captured, as the map holds the attacks per square rather than per victim. (Only after the occasional non-capture you have to do much work to collect the attackers.)

So after the enemy slider discovery and presence mask your map is usually updated good enough to generate your own capture moves from it, in MVV order. If (at d <= 1) the MVV cannot bring you above alpha, there is nothing to search in that move (futility pruning), and also no reason to update the map for opponent moves: you undo the slider discovery, and return a fail low. Only when you find an attack on a non-futile victim, you must finish the update of the map before actually searching any of the moves. Which means you have to remove the attacks by the moved piece from its previous location, and add its attacks from its new location. This is most of the work, especially since you have to undo it before you return from the node.

I usually update the attack map in combination with an auxiliary data structure, the 'neighbor' or 'view-distance' map. This keeps for each occupied square the nearest occupied square in each of the eight directions. This is easy to update, and helps a lot to quickly displace attacks 'downstream' after slider discovery. For sliders I let the map only keep track of attacks on occupied squares, because sliders tend to attack many empty squares for each occupied square they attack. And updating all that info is a waste of time in QS, as only non-captures would need it. For leapers it is usually better to keep all their attacks; this actually saves you time, because you only need to update one square in each direction, and just doing it is already less work than testing if it should be done. (For sliders you save time by not looking at the empty squares at all, but using the neighbor table to directly skip to the nearest occupied square.)

[maksimKorzh]

Thank you for such a detailed answer, mr. Muller, I feel a bit confused. It seems to be a really tough work. Probably magic bitboards are much easier to implement even if writing the routine of generating magic numbers your own which I did once...

I've modified micro-Max's move generator by adding is_square_attacked function, so it's not a king capture based anymore and now seem to be faster according to gprof profiler, but the attack function takes 2 times more time compare to all others...

Yesterday I was playing around with storing attack map in one bitboard, but didn't invent anything to update it - one idea was erase entire bitboard before move generation and later exploit the similarity of generated moves and attacked squares via setting bits in all the target squares, but avoiding straight pawn moves and castling, but then I realized that after the move is made it causes completely new attack map, so it won't work.

Which approach is faster - precalculated bitboard attacks or incremental update of attack tables?

[hgm]

I expect incrementally updated attack maps to be faster, if it is really well integrated with the rest of the engine. E.g. mobility can be kept track of as an almost free side effect of the attack map. But it is not a minimalistic method. It requires a lot of code, most of it not executed very often, but still necessary.

In Chess the number of pieces is sufficiently small that you could also consider another organization of the attack map, where you store the set of attackers per piece rather than per square. The downside is that the inheritence of the attacks on a piece that is captured by its capturer is no longer aitomatic, but requires a data move. But the advantage is that the attack map then doubles duty as the list of possible captures, each bit corresponding to an (attacker, victim) pair. By assigning the bits so that they can be extracted in MVV/LVA order, you completely by pass the need of creating and sorting a move list in QS.

[Aleks Peshkov]

Board representation for incremental attack tables should be build from scratch.
It is not a efficient idea to add attacks as extra weight to well-known representations.

[maksimKorzh]

Board representation for incremental attack tables should be build from scratch.
It is not a efficient idea to add attacks as extra weight to well-known representations.

That's really good advise, thanks!