Attacks From table

[Edsel Apostol]

Which bitboard engines maintains an attack from tables here? How do you do it efficiently? I'm currently experimenting with adding attack tables and it slows down the engine a lot. I call the following function at the end of doMove/undoMove:

Code: Select all

void position_t::updateAttacksBB(uint64 toUpdate) {
	uint64 toUpdateSliders = 0;
	while (toUpdate) {
		int sq = popFirstBit(&toUpdate);
		attacksBB[sq] = pieceAttacksFromBB(pieces[sq], sq, occupiedBB);
		toUpdateSliders |= (piecesBB[ROOK] | piecesBB[QUEEN]) & rookAttacksBB(sq, occupiedBB);
		toUpdateSliders |= (piecesBB[BISHOP] | piecesBB[QUEEN]) & bishopAttacksBB(sq, occupiedBB);
	}
	while (toUpdateSliders) {
		int sq = popFirstBit(&toUpdateSliders);
		attacksBB[sq] = pieceAttacksFromBB(pieces[sq], sq, occupiedBB);
	}
}

toUpdate contains the bits of the source and destination of the moved piece, including rooks in castling and enpassant capture.

[Evert]

I think you can do better by testing for alignment first, and only then doing a lookup for the actual piece (your xxxAttacksBB functions) if there is alignment. You probably also want to do that in a ray-direction way, rather than by full rank/file/diagonal.
You can cache the attack information for at least the "from" square, so you don't have to do the full ray scan for that.

There are a number of posts by HGM about using attack tables. This is using a mailbox engine with some specific information on a large board, but it has a lot of very interesting ideas and suggestions. From what I recall, it'll be hard to make competitive on 8x8 though.

[pkumar]

I use attack tables. The following links are useful.

http://www.open-aurec.com/wbforum/viewtopic.php?t=171
http://www.open-aurec.com/wbforum/viewt ... f=4&t=1626
http://www.talkchess.com/forum/viewtopi ... 37&t=58628

I shall appreciate more references.

[Edsel Apostol]

So I put some criteria on when to add sliders to be considered for update and it is still too slow (factor 2 to 3 slow in perft. I even have implemented a way to save the before values of the updated squares so it will not be recomputed in undoMove. The problem here is that the update done in doMove/undoMove is useless at the last ply as the updated attacks table is not being used after that, but that is where the bulk of the nodes is.

I think that with a very fast bitboards attacks generator there is not much to gain with this. I may try again someday when the new engine already has a full eval. Thanks Evert and PKumar for the input.

[Gerd Isenberg]

Hi Edsel,

with magic or pext bitboards, most use "On the Fly" generation ...

For some references see
https://www.chessprogramming.org/Attack_and_Defend_Maps

Good luck,
Gerd

[bob]

Getting rid of that overhead is what drove me to the rotated bit board development. And then magic move generation came along as yet another alternative. The updates to maintain both attacks to and attacks from (slate/atkin chapter in Frey's "Chess Skill in Man and Machine") were pretty expensive. Computing the attacks from a square is a direct lookup nowadays with no loops at all.

[hgm]

I don't understand your code at all, in particular how it can be that you do the same thing for squares that got occupied and that get evacuated. Also I don't know what exactly you want to store in the attack map.

For a game with so few pieces as orthodox Chess it seems best to store for each square the set of pieces that attacks it. (One bit per piece.) When a piece moves you have to remove its old attacks and add its new attacks in all of the target squares. This can be a lot of work, and it cannot be avoided that the UnMake requires nearly as much work.

I have only used attack maps that only record attacks on occupied squares. This can save a lot of work on the update, especially for attacks by sliders. Obvious disadvantage is that you cannot use the map to test if non-capture moves go to a safe square (or whether your King moves into check). But I only use them for capture generation and SEE.

The attack map is also an aid for its own update: it lists the slider attacks on an evacuated square, and it are only these attacks that have to be displaced to a new target. Usually there are none or very few slider attacks on a square, so you don't have to displace any attacks.

A lot of work can also be saved by postponing the update until after it is sure that you need it. Even if the info is needed for evaluation, you would only need it in the comparatively rare cases where the evaluation is in or close to the search window (otherwise futility pruning or lazy eval do the job). In nodes where stand pat is futile, and there are no moves to search, you would only need the info to conclude there are no moves to search, and the only way you could have gotten new moves (not yet in the attack map) due to the preceding opponent move is by discovering one of your sliders (which is rare). So I usually split the update in two: discovery of own sliders, and the rest. The discovery of own sliders is always done (but cheap, as most moves do not discover any sliders). Then the map is good enough to be used for generating captures in MVV order: it would contain all attacks on enemy pieces (Perhaps also some that no longer exist, e.g. because the attacker was just captured, but these can be cheaply masked out of the set of attackers.) If I find a still-valid attack before reaching the futile victims I update the rest of the attack map before I search it. If there are no attacks I am in a true leaf node (the common case), and I only have to undo the update for discovery of own sliders before I return.

[Edsel Apostol]

I don't understand your code at all, in particular how it can be that you do the same thing for squares that got occupied and that get evacuated. Also I don't know what exactly you want to store in the attack map.

This code

Code: Select all

pieceAttacksFromBB(pieces[sq], sq, occupiedBB)

returns an empty bitboard when there is no piece in the sq, so it basically updates attacksBB with 0 when the sq is evacuated. So attacksBB[from] is assigned empty bitboard, etc. Note that this is done after all the pieces are moved in the internal board structure. To save the same process in the undomove, before the update in domove, one can save the relevant sq and attack bitboard into a vector/array and just restore the attack map from there. The toUpdateSliders are the discovered sliders. As suggested here, it can be optimized by checking for preconditions (checking for sliders by rank/file/diagonal/reverse-diagonal masks or per ray direction or a kogge stone method as suggested by Gerd).

The attack map is supposed to be used as a replacement for calls to the slider attack functions e.g. move generation, eval, etc. Since I only have perft working at the moment the attack map is not that useful. Besides the fact that the slider move generators are already fast (magic bitboards).

What I did is just a quick hack to experiment with using attack maps. In the future when I'm already done with the eval, I'll try it again and we will see if there is an improvement.

[Edsel Apostol]

Hi Edsel,

with magic or pext bitboards, most use "On the Fly" generation ...

For some references see
https://www.chessprogramming.org/Attack_and_Defend_Maps

Good luck,
Gerd

Hi Gerd,

Good to see the chess wiki moved to it's own page. The links to the CCC/WB forum that are related to the topic are so useful.

[Edsel Apostol]

Getting rid of that overhead is what drove me to the rotated bit board development. And then magic move generation came along as yet another alternative. The updates to maintain both attacks to and attacks from (slate/atkin chapter in Frey's "Chess Skill in Man and Machine") were pretty expensive. Computing the attacks from a square is a direct lookup nowadays with no loops at all.

Magic bitboards still has addition plus multiplication and shift. What I want to achieve is to replace them with direct table lookup from the attacks table. Since most of the time there are only a piece or two and some discovered sliders that has changed their attack information a lot can probably be saved by repeated calls to the slider attacks routine (in movegen and eval, and other attack utilities), especially if done as described by HG: to defer the update at all unless it is to be used by the next ply.