Incremental update

[abulmo]

How do you know there will be no good captures at ply=N+1 and therefore you can avoid the incremental update stuff?

This is not difficult/expensive at all. Captures you have at ply N+1 must already be in the old attack map, or must be discovered slider moves, which are in the old attack map as enemy slider attacks to the from-square. The latter are rare: in typical chess positions most moves will not discover any sliders at all. Existing attacks in the old attack map can have disappeared, because the attacker was captured with the last move, but these are easily filtered out.

Do you have an example code of a working and efficient incremental attack map for a bitboard representation of the chessboard? I tried it recently and came to the same conclusion as Robert Hyatt, ie computing directly the attack is faster than using an incremental attack map.

[hgm]

I did publish a somewhat detailed example here some time ago. It was not bitboard, of course; I wanted it to be fast.

[Harald]

Could it be that the rotating indices approach has something to do woth this discussion?
There is the updateRotatedIndices() function and the method was fast.

I found an old post with this topic:

http://www.talkchess.com/forum/viewtopi ... 55&t=16002
from this thread
http://www.talkchess.com/forum/viewtopi ... 93&t=16002

There must be an even older thread that I could not find.

Harald

[Sven]

I did publish a somewhat detailed example here some time ago. It was not bitboard, of course; I wanted it to be fast.

This comment shows that Bob and you are talking about completely different things (first time ever ). As everyone knows Bob is talking about a bitboard program while you are talking about a mailbox representation. And obviously both of you are right, each one from his perspective. An incrementally updated attack map, efficiently implemented in the way you are describing, is most probably the way to go for a mailbox program since on-the-fly recalculation of all attacks from or to a given square is quite expensive there (and there may be more reasons for that). However, for a bitboard program the opposite seems to be true: maintaining an attack map, even with incremental update, is mostly redundant here due to the relatively low costs of generating sliding attacks.

As always, this thread would lack a lot of its entertaining ingredients if the two of you would agree to each other

[hgm]

I don't think that is the problem. My claim is that on-the-fly bitboard move generation is far more expensive than incrementally updating the move list. The claim that it is inefficient to do things you don't need the result of is hardly dependent on the underlying implementation. Neither is the claim that the (lack of) speed of an implementation that does such unnecessesary updates hardly can serve as proof for inferiority of the method.

Note, however, that attack maps are inherently mailbox structures. There is no way to represent an attackers set as a single bit, and cram 64 of them in a word.

Incremental update of the move list / attack map can be done both with mailbox and bitboard design. I would of course never touch bitboards, because they are never competitive with boards of 80, 81 or 144 squares, and I think even on 8x8 boards mailbox would in this case be faster. The one thing bitboard is good at, generation of slidr moves, would hardly ever have to be done anymore.

[Sven]

I don't think that is the problem. My claim is that on-the-fly bitboard move generation is far more expensive than incrementally updating the move list.

But the main focus is not necessarily on updating the move list. For the purpose of static evaluation, but possibly also for legality and in-check detection both "attacksFrom(square)" and "attacksTo(square)" maps may be of major interest.

Note, however, that attack maps are inherently mailbox structures. There is no way to represent an attackers set as a single bit, and cram 64 of them in a word.

When has representing a set of anything with one single bit (??!) ever been a requirement?

[bob]

I don't think that is the problem. My claim is that on-the-fly bitboard move generation is far more expensive than incrementally updating the move list. The claim that it is inefficient to do things you don't need the result of is hardly dependent on the underlying implementation. Neither is the claim that the (lack of) speed of an implementation that does such unnecessesary updates hardly can serve as proof for inferiority of the method.

Note, however, that attack maps are inherently mailbox structures. There is no way to represent an attackers set as a single bit, and cram 64 of them in a word.

Incremental update of the move list / attack map can be done both with mailbox and bitboard design. I would of course never touch bitboards, because they are never competitive with boards of 80, 81 or 144 squares, and I think even on 8x8 boards mailbox would in this case be faster. The one thing bitboard is good at, generation of slidr moves, would hardly ever have to be done anymore.

Not necessarily. Slate/Atkin did "attacks-to" and "attacks-from". The first gives all squares that attack square X, the latter gives all attacks from square X to other squares. With magic bit boards, the cost for generating attacks is really minimal.

For bit boards, incrementally updating is not exactly cheap. When you move any piece, you have to look at the square you vacate, and look down the ranks/files/diagonals to see if you were blocking a slider, and if so, update that ray. Then you have to look at the square you landed on and see if you now block any sliders on rays through that square and update those.

Magic is just an and, multiply and shift and voila... Current Crafty has total move generation time taking under 10% of total search time. Non-captures only is a paltry 1% via profiling. Most of the work is in generating captures in the q-search. Your incremental update is going to have to be done in almost zero time to make it profitable, and the savings is not even 10% if you can completely eliminate move generation and incur zero cost in Make/Unmake. And you almost have to go back to copy/make, as the unmake is just as expensive as the make for incremental updates. Copy/Make definitely has a cost. I tried it sometime during the past year, just to see, and it was less efficient. Adding incremental attacks adds another 4K bytes of state to copy (64 squares x 64 bits per square for attacks).

I don't have the data from so long back, but I did incremental attack updates for maybe a year before going to direct computation via rotated bit boards. The savings was not just a few percent.

I did not think you were talking about just mailbox approaches, however. Bruce Moreland did a mailbox approach in Ferret and he used incremental piece lists.

For your claim for bit boards, consider this: an AND, a Multiply, and a shift and I have generated attacks for any sliding piece except the queen. For the queen I have to do two of each (bishop + rook). For knights, pawns and kings, it is a direct lookup, access memory once and I have the squares attacked by those three. So for a starting board position with all 32 pieces still on the board, I have 8 pawn accesses, plus two knights and the king, and then for bishops, rooks and queens, I have a total of 6 ands, 6 multiplies and 6 shifts and my move generation for all pieces are done. You are going to have a real struggle to get an incremental update done in 29 instructions (I am ignoring array references since mailbox has plenty of that as well). I get a complete move generation for all pieces in 29 operations.

Just take moving a rook from e3 to e5. You vacate e3 so you have to look down all four directions. If you encounter a rook or queen, you have to update their attacks. Then you have to look down all four diagonal directions and do the same thing. Then you have to look at the destination and repeat. And you have to do that for any single piece that moves.

So for that rook, I have to do a move generation from the original square (the original attacks board, just a lookup) and intersect with all rooks, bishops and queens. Now I know where the pieces are that attack the original square. For each one, I have to update the attacks accordingly. Anywhere from zero to 8 max. Repeat for destination. I'm not even remotely convinced I could do that in 29 instructions or less.

[Aleks Peshkov]

Do you have an example code of a working and efficient incremental attack map for a bitboard representation of the chessboard? I tried it recently and came to the same conclusion as Robert Hyatt, ie computing directly the attack is faster than using an incremental attack map.

I have https://bitbucket.org/alekspeshkov/petrel
Sure it is not typical bitboard representation because I need unique identity for each piece.

[hgm]

Not necessarily. Slate/Atkin did "attacks-to" and "attacks-from". The first gives all squares that attack square X, the latter gives all attacks from square X to other squares. With magic bit boards, the cost for generating attacks is really minimal.

I suppose this refers to being mailbox. What I meant is that info on different squares would be in different memory words, and that is mailbox. One can see the move set as a 64x64 bit array indexed by from- and to-square, and there is the choice to store it by row or by column. If all moves that have the same from-square reside in the same word I would call it a bitboard move set, if all moves that have the same to-square would be in a word, I would call it an attack map.

For bit boards, incrementally updating is not exactly cheap. When you move any piece, you have to look at the square you vacate, and look down the ranks/files/diagonals to see if you were blocking a slider, and if so, update that ray. Then you have to look at the square you landed on and see if you now block any sliders on rays through that square and update those.

The point is that in the common case there are no discoveries. You just look at the attack map for the from-square, conclude there are no slider attacks on it, and are done. That is cheap, just an array access plus AND instruction. For blocking the common case is a capture, which never blocks anything.

Magic is just an and, multiply and shift and voila...

Times 32 pieces...

Current Crafty has total move generation time taking under 10% of total search time. Non-captures only is a paltry 1% via profiling. Most of the work is in generating captures in the q-search. Your incremental update is going to have to be done in almost zero time to make it profitable, and the savings is not even 10% if you can completely eliminate move generation and incur zero cost in Make/Unmake.

The reason for wanting an attack map is that it is helpfull in speeding up many parts of the engine. I don't know what the other 90% in Crafty is, but mobility calculation should become an almost free side effct of the attack-map update, SEE would become nearly free, move sorting would mostly disappear... So comparing to just the 10% of move-generation cost is a bit misleading.

And you almost have to go back to copy/make, as the unmake is just as expensive as the make for incremental updates. Copy/Make definitely has a cost. I tried it sometime during the past year, just to see, and it was less efficient. Adding incremental attacks adds another 4K bytes of state to copy (64 squares x 64 bits per square for attacks).

Yes, unmake is relatively more expensive. It can be better than copy-make, however. For instance, you can assign new bits to moved pieces in the attackers sets, so that you can leave their old moves, and those of captured piece, in the attack map. So they won't have to be put back on unmake.

For your claim for bit boards, consider this: an AND, a Multiply, and a shift and I have generated attacks for any sliding piece except the queen. For the queen I have to do two of each (bishop + rook). For knights, pawns and kings, it is a direct lookup, access memory once and I have the squares attacked by those three. So for a starting board position with all 32 pieces still on the board, I have 8 pawn accesses, plus two knights and the king, and then for bishops, rooks and queens, I have a total of 6 ands, 6 multiplies and 6 shifts and my move generation for all pieces are done. You are going to have a real struggle to get an incremental update done in 29 instructions (I am ignoring array references since mailbox has plenty of that as well). I get a complete move generation for all pieces in 29 operations.

And then you still have to extract the moves or captures, and sort them... The idea of incremental update is that in the common case you would only have to do that for a single piece (the one that moved), rather than 16. There would also be moving of the work one ply level towards the root, so it could be shared. With on-the-fly move generation you would be generating moves in all leaves, to conclude there are none you want to make. The incremental update would only have to be done when you do want to make moves, which you can cheaply conclude without doing the update. Most of the time you only need the attackers map of the parent node.

Just take moving a rook from e3 to e5. You vacate e3 so you have to look down all four directions. If you encounter a rook or queen, you have to update their attacks. Then you have to look down all four diagonal directions and do the same thing. Then you have to look at the destination and repeat. And you have to do that for any single piece that moves.

No. What you in fact do is look at the attackers map for e3, AND with the 'present sliders' set, conclude the intersection is empty, and be done. The crux is that the attackers map also contains info that is of great help with its own update. Then you look at e5, conclude that there was a piece there that was captured, so that nothing is blocked that was not blocked before.

[bob]

Not necessarily. Slate/Atkin did "attacks-to" and "attacks-from". The first gives all squares that attack square X, the latter gives all attacks from square X to other squares. With magic bit boards, the cost for generating attacks is really minimal.

I suppose this refers to being mailbox. What I meant is that info on different squares would be in different memory words, and that is mailbox. One can see the move set as a 64x64 bit array indexed by from- and to-square, and there is the choice to store it by row or by column. If all moves that have the same from-square reside in the same word I would call it a bitboard move set, if all moves that have the same to-square would be in a word, I would call it an attack map.

For bit boards, incrementally updating is not exactly cheap. When you move any piece, you have to look at the square you vacate, and look down the ranks/files/diagonals to see if you were blocking a slider, and if so, update that ray. Then you have to look at the square you landed on and see if you now block any sliders on rays through that square and update those.

The point is that in the common case there are no discoveries. You just look at the attack map for the from-square, conclude there are no slider attacks on it, and are done. That is cheap, just an array access plus AND instruction. For blocking the common case is a capture, which never blocks anything.

Magic is just an and, multiply and shift and voila...

Times 32 pieces...

No, just for 5 pieces. The rest are just direct lookups that are computed before the game starts. Only sliders use the magic stuff.

Current Crafty has total move generation time taking under 10% of total search time. Non-captures only is a paltry 1% via profiling. Most of the work is in generating captures in the q-search. Your incremental update is going to have to be done in almost zero time to make it profitable, and the savings is not even 10% if you can completely eliminate move generation and incur zero cost in Make/Unmake.

The reason for wanting an attack map is that it is helpfull in speeding up many parts of the engine. I don't know what the other 90% in Crafty is, but mobility calculation should become an almost free side effct of the attack-map update, SEE would become nearly free, move sorting would mostly disappear... So comparing to just the 10% of move-generation cost is a bit misleading.

My mobility is as cheap as the magic stuff. I pre-compute mobility per square, then use the same magic math, but instead of looking up a 64 bit attack set for the piece, I look up a 1 byte mobility score for the piece, since this includes just squares the piece can reach anyway.

And you almost have to go back to copy/make, as the unmake is just as expensive as the make for incremental updates. Copy/Make definitely has a cost. I tried it sometime during the past year, just to see, and it was less efficient. Adding incremental attacks adds another 4K bytes of state to copy (64 squares x 64 bits per square for attacks).

Yes, unmake is relatively more expensive. It can be better than copy-make, however. For instance, you can assign new bits to moved pieces in the attackers sets, so that you can leave their old moves, and those of captured piece, in the attack map. So they won't have to be put back on unmake.

For your claim for bit boards, consider this: an AND, a Multiply, and a shift and I have generated attacks for any sliding piece except the queen. For the queen I have to do two of each (bishop + rook). For knights, pawns and kings, it is a direct lookup, access memory once and I have the squares attacked by those three. So for a starting board position with all 32 pieces still on the board, I have 8 pawn accesses, plus two knights and the king, and then for bishops, rooks and queens, I have a total of 6 ands, 6 multiplies and 6 shifts and my move generation for all pieces are done. You are going to have a real struggle to get an incremental update done in 29 instructions (I am ignoring array references since mailbox has plenty of that as well). I get a complete move generation for all pieces in 29 operations.

And then you still have to extract the moves or captures, and sort them... The idea of incremental update is that in the common case you would only have to do that for a single piece (the one that moved), rather than 16. There would also be moving of the work one ply level towards the root, so it could be shared. With on-the-fly move generation you would be generating moves in all leaves, to conclude there are none you want to make. The incremental update would only have to be done when you do want to make moves, which you can cheaply conclude without doing the update. Most of the time you only need the attackers map of the parent node.

Don't follow you there. When I was using incremental update, all I got were attack bitmaps just as I do with magic. With either approach I had to "unroll" the bitmap into a set of from/to/etc actual moves.

{quote]

Just take moving a rook from e3 to e5. You vacate e3 so you have to look down all four directions. If you encounter a rook or queen, you have to update their attacks. Then you have to look down all four diagonal directions and do the same thing. Then you have to look at the destination and repeat. And you have to do that for any single piece that moves.

No. What you in fact do is look at the attackers map for e3, AND with the 'present sliders' set, conclude the intersection is empty, and be done. The crux is that the attackers map also contains info that is of great help with its own update. Then you look at e5, conclude that there was a piece there that was captured, so that nothing is blocked that was not blocked before.[/quote]