Idea: Incremental Attack Tables Using "Bitwise Addition

[Lykos]

Hi all,

I recently started writing a chess engine and I was looking a bit at the literature. It seems as if incremental attack tables have gone out of fashion because updating them is complicated and they don't provide enough value to compensate for that.

I have a different idea on how to do incremental attack tables. I haven't seen this one in the literature, so I see three options (in the order of likelyhood):

- This idea has been tried out, I just didn't find it.
- Nobody tried it because it is stupid.
- It is indeed a useful new approach.

I called the approach "bitwise addition". It works as follows. The incremental attack table consists of 4 64-bit integers a0, a1, a2, a3 per color. Let x be the ith bit of x. To get the number of attacks of square i for a given color (numbered from 0 to 63) we interpret the ith bits of the stored numbers a0..a4 as a number. I.e. we use:

Code: Select all

a0[i] + 2 * a1[i] + 4 * a2[i] + 8 * a3[i]

If we just need a bitboard which tells us which squares are attacked, we can use bitwise or, i.e.

Code: Select all

a0 | a1 | a2 | a3.

Even though the idea sounds quite complicated, updating is quite efficient. If we move a piece, we just remove the pieces it attacks from the old square using "bitwise subtraction" and add the pieces it attacks from the new square using "bitwise addition". We pretend to implement addition for single booleans as we know it from digital circuits (reference: http://en.wikipedia.org/wiki/Adder_%28electronics%29) but instead of using single booleans, we use 64 bit words and bitwise operations. So it works as follows for our application (This is addition, subtraction works similarly):

Code: Select all

carry = attack_board_for_new_square

new_a0 = a0 ^ carry
carry = a0 & carry
a0 = new_a0

new_a1 = a1 ^ carry
carry = a1 & carry
a1 = new_a1

new_a1 = a1 ^ carry
carry = a1 & carry
a1 = new_a1

a3 = a3 ^ carry
// Note that we don't need to update the carry here any more. It is guaranteed to be 0 since it is not possible that one color attacks a square 16 (or more) times.

The advantage of storing the number of attacks and not only the attack set is that updating gets easier. If we remove a piece, we don't have to check who else is attacking those squares. At the same time, it is far more efficient than having an array of 64 bytes where we store the number of attacks for each square separately. That approach seems more intuitive, but updating it is much less efficient and that attack table is also far less nicely compatible to bitboards.

What are your opinions? Did I miss something and this just sucks? Has it been done already? Is it maybe even an interesting idea?

[vittyvirus]

I see you haven't provided the pseudo-code enough. For example, how do yiou generate bishop attacks with your idea?
But I must say that it seems interesting!

[Lykos]

My idea is only about a new way to implement incremental attack tables on top of existing tools. I do NOT want to create a new way of doing move generation. I would certainly rely on an existing move generation method (I am using magic bitboards) to generate the possible moves of a piece. Maybe I should have stated this more clearly. Sadly editing is not possible any more.

More direct answer: After a move, I would create a bitboard containing the attacks of the moved piece using magic bitboards. Then, I use the described algorithm to update my attack table.

[vittyvirus]

My idea is only about a new way to implement incremental attack tables on top of existing tools. I do NOT want to create a new way of doing move generation. I would certainly rely on an existing move generation method (I am using magic bitboards) to generate the possible moves of a piece. Maybe I should have stated this more clearly. Sadly editing is not possible any more.

More direct answer: After a move, I would create a bitboard containing the attacks of the moved piece using magic bitboards. Then, I use the described algorithm to update my attack table.

If it'd be possible, fine. But the problem is, it can't be updated during makeMove().

[kbhearn]

The table itself is not really the drawback to an incrementally updated attack table, but the work to keep it accurate vs how much it winds up being used.

I'm not clear how you think you wouldn't need to look up 'what else is attacking this square' when a piece is moved away from it:

i.e. a rather extreme example of the possible updates needed to an attack table:

[d] 1n1qkb1r/1bp2p1p/1p3np1/r2P2B1/p3B3/P1N2QP1/1PPR1P1P/4K1NR w Kk - 0 13

if white moves d5-d6 here:
For black:
The Bf8 is blocked. The Qd8 is blocked.
The Bb7 is unblocked, the Ra5 is unblocked.
For white:
The Be4+Qf3 battery is unblocked (is that 1 attack or 2 on the relevant squares)
The Rd2 is unblocked.

In short you need to scan each of 8 directions for potential discoveries on an unblock, and each of 8 directions for potential new blocks on the new location of the piece. You may need to scan further in that direction to discovery a battery if that's something you wish to cover. You also then need to look in the opposite direction to find out exactly which squares are now blocked/unblocked that weren't before. All of this is of course doable, but it's significantly more operations than the table.

And then the question is: just what are you going to use this count of attacks for? If you're only using it in one or two places or the places you use it aren't called frequently, it's simpler and quite possibly faster to do a superpiece move generation on the square you want to know 'what's attacking this?' whenever it comes up than an incremental update you have to do in every makemove. If this is something you're planning to use heavily, then by all means, your method for keeping track of the tables is fine.

[hgm]

It seems to me you don't account for discovered and blocked attacks.

[Lykos]

You are right. I got so stuck in my funny idea of implementing my weird bitwise addition that I missed the obvious: I would need special treatment for blocked and discovered attacks. And that makes the idea kind of pointless because I still need to do a lot of work for updating...

Thank you for your answers.