Incremental update

[hgm]

If you sum all the incremental update costs in a 30+ ply search it can easily exceed the cost of computing something when you actually need it.

That reasoning seems flawed. It would only be correct for a non-branching tree. Even if the branching factor is just two, a 30-ply tree would have 2^30 leaf nodes and 2^31 - 2 MakeMoves. So there are only two MakeMoves for each leaf, not 30, and one should compare the cost for calculating from scratch in the leave to twice the cost of an incremental update in MakeMove. For larger branching factors the number of MakeMoves/leave gets even closer to 1.

[Sven]

Programs spend most of their time near the leaves of the search tree. A lot of times when you make a move, it is immediately cut off, for example because the static eval in the qsearch is too high. So you don't even get to use the attack information, or most of it. I only generate attacks as needed.

But that sounds just like a poor implementation. The trick is of course to only update the attack map when you are going to use it. Furthermore, the update can be split into a friendly and an enemy update (compared to the side that moved). To know if you have attacks that are worth following up in QS you only need the enemy update. Which is the cheapest one, as it does not include the altered moves of the mover, but just victim (which is taken care of by simply clearing a bit in the presence mask) and discovering of the enemy slidermoves (in typical positions much rarer than discovering of own pieces). And even the enemy update is only needed if the lazy evaluation did not cause a stand-pat cutoff.

My currently favored design doesn't really store the attackers info in board format, but in piece-list format, where each bit in a set represents an (attacker, victim) pair, sorted in MVV/LVA order, so that it can directly serve as (sorted)move list.

Has anyone ever tried an attack table approach like this in a non-bitboard engine?

a) Maintain an attack map only for attacks by pawns, knights, and kings.
b) Calculate sliding attacks on the fly whenever they are needed but do not store them.

Incrementally updating should be cheap for a) but is expensive for b), therefore it might be better to avoid the latter.

[AlvaroBegue]

Programs spend most of their time near the leaves of the search tree. A lot of times when you make a move, it is immediately cut off, for example because the static eval in the qsearch is too high. So you don't even get to use the attack information, or most of it. I only generate attacks as needed.

But that sounds just like a poor implementation. The trick is of course to only update the attack map when you are going to use it. Furthermore, the update can be split into a friendly and an enemy update (compared to the side that moved). To know if you have attacks that are worth following up in QS you only need the enemy update. Which is the cheapest one, as it does not include the altered moves of the mover, but just victim (which is taken care of by simply clearing a bit in the presence mask) and discovering of the enemy slidermoves (in typical positions much rarer than discovering of own pieces). And even the enemy update is only needed if the lazy evaluation did not cause a stand-pat cutoff.

My currently favored design doesn't really store the attackers info in board format, but in piece-list format, where each bit in a set represents an (attacker, victim) pair, sorted in MVV/LVA order, so that it can directly serve as (sorted)move list.

Has anyone ever tried an attack table approach like this in a non-bitboard engine?

a) Maintain an attack map only for attacks by pawns, knights, and kings.
b) Calculate sliding attacks on the fly whenever they are needed but do not store them.

Incrementally updating should be cheap for a) but is expensive for b), therefore it might be better to avoid the latter.

I haven't done it myself, but my understanding was the opposite: a) is cheap to do when you need it, but b) can benefit from incremental updates.

[ZirconiumX]

Would I be correct in saying that unless a king, knight or pawn moves, there are no situations that would change its attack set?

This would allow incremental update of those pieces, with sliding attack sets done when needed.

Matthew:out

[hgm]

What I like most about an attack map is that mobility evaluation sort of comes as a nearly free side effect of it. It is very easy to store the information on the number of moves on a per-piece basis, so that you only have to incrementally update mobility for the piece that is captured (subtract its contribution in one blow), that is moved (ditto for its old moves, and then add the number of moves from its new location), and the occasional blocked/unblocked slider.

This does sound a lot cheaper than calculating the mobility of all pieces from scratch (in a mailbox engine). Which you would probably need to do in any node (as nodes that would already fail high on the lazy eval, without the mobillity term, would already have been futility-pruned in the level below).

So you calculate the mobility for the purpose of eval,in the cheapest way you know (= incrementally), and the attack map is produced as a free side effect. And a major advantage of the attack map is that it would allow cheap beta pruning, where you lift eval so far above beta that all captures in the daughter node will be futile. For this you only have to look in the attackers map for your most valuable pieces (that would make non-futile victims), to see if there are attacks on them based on the current, unupdated map (verified by that the attack should not come from the piece that you just captured), plus possibly slider attacks over the evacuated from-square (which must have been attacks on that from-square before, and which in the common case would not be there).

Another advantage is easy staged move generation in MVV/LVA order: just run through the opponent piece list top-down, and search the captures on it by the attackers listed in the map. You can stop (to fail low or continue with dedicated check generation, if you do checks at that level) when you reach the futile victims.

All and all I can see so many time-saving applications that it would surprise me if it wasn't a big win.

[ZirconiumX]

What I like most about an attack map is that mobility evaluation sort of comes as a nearly free side effect of it. It is very easy to store the information on the number of moves on a per-piece basis, so that you only have to incrementally update mobility for the piece that is captured (subtract its contribution in one blow), that is moved (ditto for its old moves, and then add the number of moves from its new location), and the occasional blocked/unblocked slider.

This does sound a lot cheaper than calculating the mobility of all pieces from scratch (in a mailbox engine). Which you would probably need to do in any node (as nodes that would already fail high on the lazy eval, without the mobillity term, would already have been futility-pruned in the level below).

So you calculate the mobility for the purpose of eval,in the cheapest way you know (= incrementally), and the attack map is produced as a free side effect. And a major advantage of the attack map is that it would allow cheap beta pruning, where you lift eval so far above beta that all captures in the daughter node will be futile. For this you only have to look in the attackers map for your most valuable pieces (that would make non-futile victims), to see if there are attacks on them based on the current, unupdated map (verified by that the attack should not come from the piece that you just captured), plus possibly slider attacks over the evacuated from-square (which must have been attacks on that from-square before, and which in the common case would not be there).

Another advantage is easy staged move generation in MVV/LVA order: just run through the opponent piece list top-down, and search the captures on it by the attackers listed in the map. You can stop (to fail low or continue with dedicated check generation, if you do checks at that level) when you reach the futile victims.

All and all I can see so many time-saving applications that it would surprise me if it wasn't a big win.

It's probably a case of trying to offset the massive cost of the attack maps for sliders. Transposition tables would probably help in this regard.

Matthew:out

[hgm]

But what is so massive about the cost for sliders? Or are you still thinking of a situation where you also store attacks on empty squares? I think that indeed is a losing proposition.

Occasionally setting the end-point of a slider move from an evacuated square that it attacked to the next obstacle downstream can hardly be called expensive.

The idea to generate slider attacks when you need them seems to suffer from the problem that on average you would need them many times after the slider acquired them. And worse yet, that at the time where you need them, you would not really be aware that you needed the attacks of this particular slider, because you are facing qeastions like "is this piece attacked". So that you have to start generating attacks of all sliders, just to see if one of them happens to hit your piece. You might argue that this cost is ameliorated by the fact that you then also generate all attacks on all other pieces, but often you don't need those. (E.g. because only the capture of a Queen could bring you above alpha.)

[ZirconiumX]

But what is so massive about the cost for sliders? Or are you still thinking of a situation where you also store attacks on empty squares? I think that indeed is a losing proposition.

This is what I do so I can loop over all attacks for squares in move generation, although I'm reusing code from SecondChess to update the table. Maybe that should be switched out for mailbox/0x88.

Occasionally setting the end-point of a slider move from an evacuated square that it attacked to the next obstacle downstream can hardly be called expensive.

The idea to generate slider attacks when you need them seems to suffer from the problem that on average you would need them many times after the slider acquired them. And worse yet, that at the time where you need them, you would not really be aware that you needed the attacks of this particular slider, because you are facing qeastions like "is this piece attacked". So that you have to start generating attacks of all sliders, just to see if one of them happens to hit your piece. You might argue that this cost is ameliorated by the fact that you then also generate all attacks on all other pieces, but often you don't need those. (E.g. because only the capture of a Queen could bring you above alpha.)

Matthew:out

[hgm]

This is what I do so I can loop over all attacks for squares in move generation, although I'm reusing code from SecondChess to update the table. Maybe that should be switched out for mailbox/0x88.

That is a very inefficient way for generating non-captures, even if you already have the attack map. There are many more empty squares than there are own pieces. So it would be much faster to just loop over your pieces, and generate the moves they can make from the square they are on.

The attack map is only helpful for captures. They are inefficiently generated in the piece-based way, because for sliders the captures always come at the end of a stretch of non-captures. (Although keeping an incrementally-updated view-distance array would solve that.) And then the ray scan often hits a board edge, or an own piece, so that it was all in vain. Or a futile target.

So it is for capture generation that you would like to be able to see in one blow which moves capture your Queen (and then your Rooks, etc.). It is there that the attack map is useful.

[bob]

If you sum all the incremental update costs in a 30+ ply search it can easily exceed the cost of computing something when you actually need it.

That reasoning seems flawed. It would only be correct for a non-branching tree. Even if the branching factor is just two, a 30-ply tree would have 2^30 leaf nodes and 2^31 - 2 MakeMoves. So there are only two MakeMoves for each leaf, not 30, and one should compare the cost for calculating from scratch in the leave to twice the cost of an incremental update in MakeMove. For larger branching factors the number of MakeMoves/leave gets even closer to 1.

Think about this. You update attacks after a move at ply=1, then you update again after ply=3, then again after ply=5, and so on until ply=31. How much of the ply=1 stuff did you repeatedly undo as you went deeper? Then you only use the final product. Which (for me, anyway) was cheaper than the incremental stuff. You accumulate those costs throughout the tree. I find it cheaper to do things like "is this piece pinned?" at the point where the info is needed, rather than doing all the repeated checks and updates with the incremental code. With Magic, it is pretty trivial to answer that question. Generate attacks, AND with your own pieces, then ask "is any of those attacked own pieces move valuable than the piece I an testing? If so, is there an enemy piece in the opposite direction (that moves in the same direction (rank, file))? Yes? Problem.