50-move counter update

[hgm]

I have started building an engine that I want to be absolutely standard (except that it plays on 10x10, rather than 8x8...), so I also wants to add a 50-move counter.

I did find a very efficient way to update it, namely in combination with the castling rights:

Code: Select all

int revMovesAndCastlRights = 0xF;
char spoiler[];
revMovesAndCastlRights &= (char) (spoiler[piece] + 64) | spoiler[victim];

this replaces the old code

Code: Select all

int CastlingRights = 0xF;
char spoiler[];
CastlingRights &= spoiler[piece] | spoiler[victim];

which used the low-order 4 bits of the spoiler array to clear the castling rights when a Rook or King were moved or captured. (So all other pieces p, plus the EMPTYSQR had spoiler[p] = 15.)

In the new code, all non-Pawns get 0x40 (=64) added to their spoiler. After adding the 64 for the piece that moved, this becomes 0x8F (which is then sign-extended to 0xFFFFFF8F). Pawns that move get to 0x4F = 0x0000004F. The first mask preserves the three high-order bytes of revMovesAndCastlRights, the second clears them. These 3 bytes then contain the reversible move count. All pieces have the sign bit of their byte-size spoiler at zero, and are tus sign-extended to a mask that clears the move counter when tey are captured. The EMPTYSQR pseudo-piece gets a castling spoiler 0xCF: this sign-extends to 0xFFFFFFFCF and thus leaves the move counter alone if it is victim (i.e. the move was a non-capture), but adding 64 turns it into 0x0F, which clears the move counter if EMPTYSQR is moved (assuming that null moves are encoded by moving from and to a dummy square which is always empty).

To increment the move counter we add 256 to revMovesAndCastlRights. For UnMake the original value, which was saved, is copied back. As it had to be done before anyway, for the benefit of the castling rights. The only extra work involved is the add instruction needed to make pieces that are moved have a different effect than pieces that are captured. This could be eliminated by having a second array of spoilers, with the 64 already added, but it is questionable if the extra demand on L1 cache space by such table would not be more detrimental to performance than having the add instruction.

[Zach Wegner]

Interesting, but it doesn't seem like it would be much of a gain. Seems to me like this might be easier:

Code: Select all

int CastlingRights = 0xF;
char spoiler[];
CastlingRights &= spoiler[piece] | spoiler[victim];

int revMoves = 0;
char revspoiler[];
revMoves += revspoiler[piece] & revspoiler[victim];

So, total instruction breakdown, in rough chronological order:
Yours:
1 add (revMovesAndCastlRights += 256)
2 loads
1 add
1 and (signed char cast)
1 sign extend
1 or
1 and
=8 total


Mine:
2 loads
1 or
1 and
2 loads
1 and
1 add
=8 total

So just about equal. Yours uses a tiny bit less memory (something like 16 bytes) but with both counters combined into one, which even though shouldn't cost anything extra later on, is much less clear IMO. So the tiebreaker goes to... mine, because it should have higher IPC.

[hgm]

Sorry, my code contains typos: the '|' should have been '&' in all cases. That does not affect the efficiency, of course.

I don't see how your code works at all. In the first place, victims reset the 50-move counter in a different way than the moving piece: captring non-Pawns clears the counter, but moving non-Pawns doesn't. That can of course be solved by having two tables of revSpoilers, like it could be in my case to eliminate the add.

But adding something to the move counter that depends only on the spoilers cannot work at all. You dount know what you have to add to zero the counter, as it could have any value. You need an irreversible operaton like &, with a fixed outcome, to clear the counter, while for incrementing you need a reversible operation, the outcome of which depends in 1-to-1 correspondence on the previous value.

As for counting the instructions: the sign extends or zero extends are automatic, and a consequence using byte-size spoilers. I think the cache space this saves is a winning del compared to one or two instructions. But even if you have infinite cache, a similar trick is possible with int-size spoilers. If you are prepared to make 2 tables (as your method does anyway, as you need separate tables for castling spoilers and 50-move spoilers), you ould simply do:

Code: Select all

int moveSpoiler[NRPIECE], victimSpoiler[NRPIECE];
revMoveCounterAndCstlRights &= moveSpoiler[piece] & victimSpoiler[victim];

Where only the moveSpoilers for non-Pawns and the victimSpoiler for EMPTRYSQR would have 0xFFFFFF.. in their 3 high-order bytes. You still would need to increment the move counter elsewhere, though (by 256).

[Zach Wegner]

Sorry, my code contains typos: the '|' should have been '&' in all cases. That does not affect the efficiency, of course.

I don't see how your code works at all. In the first place, victims reset the 50-move counter in a different way than the moving piece: captring non-Pawns clears the counter, but moving non-Pawns doesn't. That can of course be solved by having two tables of revSpoilers, like it could be in my case to eliminate the add.

But adding something to the move counter that depends only on the spoilers cannot work at all. You dount know what you have to add to zero the counter, as it could have any value. You need an irreversible operaton like &, with a fixed outcome, to clear the counter, while for incrementing you need a reversible operation, the outcome of which depends in 1-to-1 correspondence on the previous value.

OK, I wrote that way too fast. You are right on both counts. Here's something a bit more realistic, which does add a few instructions:

Code: Select all

int revMoves = 0;
char revspoiler[];
revMoves++;
revMoves &= revspoiler[piece] & -(victim != EMPTYSQR);

2 loads
1 or
1 and
1 add
1 load
1 cmp
1 neg
2 ands
=10 total

Anyways, my main point is that the savings are very small, and not worth the added complexity IMO. I doubt my fifty move counter causes any slowdown at all actually, because the increment and zeroing are within larger blocks of code where the instructions are hidden in the pipeline. The conditionals don't cost any extra when you're doing them anyway.

[hgm]

If you are latency bound on other things, then indeed what you do next to it is free. (Except of course, that it precludes you from drawing an advantage from hyperthreading, which gives you a free extra CPU on latency-bound code...)

I don't completely understand your counting (I see no 'or', and don't know what you suppose to be already in registers for determining load count). The code is not complete anyway: you would also have to save and restore the castling rights and move counter.

The main reason I like this is not so much because of the number of instructions, but because of the rduced L1 footprint of my engine's kernel data. My piece lists have 64 entires, so I need only 64 bytes of spoiler tables this way. This is why I prefer to throw in an extra add over having a separate victim spoiler table. Your comparison victim != EMPTYSQR might also achieve that.

[Gerd Isenberg]

Your code is somehow hard to read at the first glance. Do you mean that?

Code: Select all

// revMoves++ 
// revMoves &= pawnMove Or Capture ? 00 : 0xff
revMovesAndCastlRights +=  256; 
revMovesAndCastlRights &=  (int) ( (char) (spoiler[piece] + 64) & spoiler[victim] );

By the way, if a rook moves or is captured, how do you distinguish which castling wing is affected? Or do you have distinct piece codes for both rooks?

I use distinct "spoilers" for from- and to-aspects of a move for a swar-wise add/and for the same purpose plus ep-target update and piece nibble counters (all inside misc).

Code: Select all

quadbb ^= fromUpdate[fromAspects].qbb   ^ toUpdate[toAspects].qbb;   // 32 bytes
hkeys  ^= fromUpdate[fromAspects].hkeys ^ toUpdate[toAspects].hkeys; // 16 bytes
misc   += fromUpdate[fromAspects].inc   + toUpdate[toAspects].inc;   // 8 bytes
misc   &= fromUpdate[fromAspects].msk   & toUpdate[toAspects].msk;   // 8 bytes

[bob]

Your code is somehow hard to read at the first glance. Do you mean that?

Code: Select all

// revMoves++ 
// revMoves &= pawnMove Or Capture ? 00 : 0xff
revMovesAndCastlRights +=  256; 
revMovesAndCastlRights &=  (int) ( (char) (spoiler[piece] + 64) & spoiler[victim] );

By the way, if a rook moves or is captured, how do you distinguish which castling wing is affected? Or do you have distinct piece codes for both rooks?

I use distinct "spoilers" for from- and to-aspects of a move for a swar-wise add/and for the same purpose plus ep-target update and piece nibble counters (all inside misc).

Code: Select all

quadbb ^= fromUpdate[fromAspects].qbb   ^ toUpdate[toAspects].qbb;   // 32 bytes
hkeys  ^= fromUpdate[fromAspects].hkeys ^ toUpdate[toAspects].hkeys; // 16 bytes
misc   += fromUpdate[fromAspects].inc   + toUpdate[toAspects].inc;   // 8 bytes
misc   &= fromUpdate[fromAspects].msk   & toUpdate[toAspects].msk;   // 8 bytes

I do it even more differently, because when I give up castling rights in the search, I want to know "did I castle?" or "did I move a rook?" or "did I move the king?" and I evaluate each of those differently. My castling status is normally a 2 bit value. When a rook moves, the corresponding bit is cleared. When the king moves both are cleared. Except that when castling is actually done, I set the castling status to -ply. A - value tells me that I castled rather than just gave up castling rights, and the "ply" tells me where I castled (I don't use that any longer, but did in older versions). If the castling status is < 0, I castled, = 0 means I gave up the right by moving either the last rook or the king... When I castle at the root, the status is set to zero since it no longer matters how castle privilege was lost.

[Gerd Isenberg]

I do it even more differently, because when I give up castling rights in the search, I want to know "did I castle?" or "did I move a rook?" or "did I move the king?" and I evaluate each of those differently. My castling status is normally a 2 bit value. When a rook moves, the corresponding bit is cleared. When the king moves both are cleared. Except that when castling is actually done, I set the castling status to -ply. A - value tells me that I castled rather than just gave up castling rights, and the "ply" tells me where I castled (I don't use that any longer, but did in older versions). If the castling status is < 0, I castled, = 0 means I gave up the right by moving either the last rook or the king... When I castle at the root, the status is set to zero since it no longer matters how castle privilege was lost.

Interesting, but I guess considering ply-diff from castling in eval terms introduces some problems considering todays depths, if after castling, an immediate "unmake" with Kf2 (Rh1) Ke1 occurs

[hgm]

By the way, if a rook moves or is captured, how do you distinguish which castling wing is affected? Or do you have distinct piece codes for both rooks?

Indeed, piece and victim are indexes in the piece list, not the piece types themselves.

Counting the captured pieces might indeed be combined with incrementing the move counter. Unfortunately the number of pieces that can be captured of each type is very unfavorable for packing them: it runs upto 2, 4 or 18, so that I run out of bits pretty quickly.

[bob]

I do it even more differently, because when I give up castling rights in the search, I want to know "did I castle?" or "did I move a rook?" or "did I move the king?" and I evaluate each of those differently. My castling status is normally a 2 bit value. When a rook moves, the corresponding bit is cleared. When the king moves both are cleared. Except that when castling is actually done, I set the castling status to -ply. A - value tells me that I castled rather than just gave up castling rights, and the "ply" tells me where I castled (I don't use that any longer, but did in older versions). If the castling status is < 0, I castled, = 0 means I gave up the right by moving either the last rook or the king... When I castle at the root, the status is set to zero since it no longer matters how castle privilege was lost.

Interesting, but I guess considering ply-diff from castling in eval terms introduces some problems considering todays depths, if after castling, an immediate "unmake" with Kf2 (Rh1) Ke1 occurs

I'm not using that any longer as I mentioned, as it was problematic with hashing. But the idea of castling or not castling is a measurable gain, as "castling by hand" wastes many moves that are usually critical in the opening.

Once the king moves, it is penalized unless it actually castled. Ditto for rook moves until castling has occurred.