Question about Fruit 2.1 code

[hgm]

I am currently browsing the Fruit 2.1 code, in particular the code involved in evaluation, and there is something I don't understand:

There is an array PieceDeltaDelta[4][256][4] (declared in attack.cpp), indexed as PieceDeltaDelta[pieceType][boardStep], which seems to hold a list of squares where the moves of the piece would (first) intersect the neighborhood of the target square of the given board step. It is used in determining if a piece attacks a square next to the opponent's King. The target squares are also given relative to the position of the pieces, and the list is terminated by an invalid board step 'DeltaNone'.

Now what puzzles me is the maximum size of the list. I would say that with a Queen on d4, and an enemy King on e4, (i.e. board step +1) there would be 4 (or even 5) Queen rays that intersect the King neighborhood: at d5, e5, d3 and e3, and perhaps even e4 or f4. So it seems the array is too small to hold them all. Yet there is an ASSERT in the code filling the array (add_attack()), wich tests for the number of elements being always < 3. In fact even the code adding the sentinel DeltaNone to the list tests for size<3, which seems strange, as it would suggest the array elelment with i=3 can never be used (so why woud it be declared?), and that the sentinel can go into i=2 at the latest, so that there is room for only 2 intersections with the King neighborhood.

What am I overlooking?

[Aaron Becker]

I am currently browsing the Fruit 2.1 code, in particular the code involved in evaluation, and there is something I don't understand:

There is an array PieceDeltaDelta[4][256][4] (declared in attack.cpp), indexed as PieceDeltaDelta[pieceType][boardStep], which seems to hold a list of squares where the moves of the piece would (first) intersect the neighborhood of the target square of the given board step. It is used in determining if a piece attacks a square next to the opponent's King. The target squares are also given relative to the position of the pieces, and the list is terminated by an invalid board step 'DeltaNone'.

Now what puzzles me is the maximum size of the list. I would say that with a Queen on d4, and an enemy King on e4, (i.e. board step +1) there would be 4 (or even 5) Queen rays that intersect the King neighborhood: at d5, e5, d3 and e3, and perhaps even e4 or f4. So it seems the array is too small to hold them all. Yet there is an ASSERT in the code filling the array (add_attack()), wich tests for the number of elements being always < 3. In fact even the code adding the sentinel DeltaNone to the list tests for size<3, which seems strange, as it would suggest the array elelment with i=3 can never be used (so why woud it be declared?), and that the sentinel can go into i=2 at the latest, so that there is room for only 2 intersections with the King neighborhood.

What am I overlooking?

I remember being very confused by this code when I first read over it. Your observation is correct, there are 5 attacking rays in the scenario you described, and the array only holds 2. However, if you take a closer look at add_attack, you'll notice that it just adds the first two rays to the array and ignores the rest (the ray is only added if size < 2).

So, the question is: why does this work? Well, the intent of the array is to tell us which targets we need to check to find out if a piece attacks a given neighborhood. The key observation is that there are never more than two blockable rays from one square to the neighborhood of another square. It's ok to ignore any rays beyond 2, because checking two distinct rays will always tell us if the piece attacks the neighborhood or not.

So, for example with the queen on d4 and the king on e1, we need to check the queen's path to both d2 and f2 to see if they're blocked before we'll know the the queen attacks the king's neighborhood. If there are pieces on d3 and e3, then the queen doesn't attack the king's neighboorhood, but otherwise she does. But in your example with the queen adjacent to the king, it doesn't matter which ray we look at, because the queen always attacks the king's neighborhood.

There are no cases where a piece attacks a neighborhood along 3 or more independent rays with two different rays can be blocked. Therefore, just storing two distinct targets suffices, and the rest are ignored.

[hgm]

OK, I see, thanks. If there are more than two rays they must be all non-blockable, so it does not matter which two you store. So the only weirdness is really that the array reserves 4 places, while never more than 3 are used.

[Aaron Becker]

OK, I see, thanks. If there are more than two rays they must be all non-blockable, so it does not matter which two you store. So the only weirdness is really that the array reserves 4 places, while never more than 3 are used.

Yeah, the size of the array is a bit of a mystery to me. I think it's just bigger than it needs to be, which doesn't hurt anything. It does make me wonder if there's some subtlety that I'm missing, though.

[Sven]

OK, I see, thanks. If there are more than two rays they must be all non-blockable, so it does not matter which two you store. So the only weirdness is really that the array reserves 4 places, while never more than 3 are used.

Yeah, the size of the array is a bit of a mystery to me. I think it's just bigger than it needs to be, which doesn't hurt anything. It does make me wonder if there's some subtlety that I'm missing, though.

I guess using a size of [4][256][3] would slow down the array access a very tiny bit. Accessing element[p][s] translates into calculating the address "element + (((p << 8) + s) * 3 + i) * elementSize". If you replace 3 by 4 then the compiler can use "element + ((p << 10) + (s << 2) + i) * elementSize" which could execute slightly faster due to the "shift" instead of "* 3".

Whether the waste of (1024 * elementSize) bytes is compensated by that possible small speed advantage seems to be a very individual decision.

Sven