Bitboard of Pinned Pieces

[grant]

Hi

Thanks for your comments.

Taking a closer look at the table size, it would more likely be about 200Kb from my calculations.
The lookup and magic multiplication for this table need only be done on the few occasions that there are pinned pieces, since pinners is only non-zero when it is pinning a piece to the king.

Are we still saying, in this case, that the extra work involved to retrieved the pinned pieces bitboard on these few occasions is going hurt performance?

Grant

[Gerd Isenberg]

Hi

Thanks for your comments.

Taking a closer look at the table size, it would more likely be about 200Kb from my calculations.
The lookup and magic multiplication for this table need only be done on the few occasions that there are pinned pieces, since pinners is only non-zero when it is pinning a piece to the king.

Are we still saying, in this case, that the extra work involved to retrieved the pinned pieces bitboard on these few occasions is going hurt performance?

Grant

If you do it conditionally, it might be fine. But I would not do it for < 0.00x percent of runtime to introduce such a huge array only for that purpose. For the most common case of one pinner (if any), I even suspect bsf, obstructed lookup reset lb1b by btr or bb & bb-1 still faster (on core2, K10) than magic mul/shift plus lookup. Obstructed lookup is likely used elsewhere inside the program, while the pinned lookup table is likely more often fetched from L2 than the obstructed table.

[bob]

Well I think you are right. The infrequent occasion is not worth the extra work and big table.

By the way, I'm using Matt Taylor's folded bitscan approach.

Can you elaborate further on this?

And there are easier ways to either (a) check for legality or (b) just generate legal moves. I do both in Crafty in fact, depending on whether I start off at a given node in check or not...

In my engine I used the return value from the pinnedPieces in determining move legality. I passed it to my sorting routine that does a lazy move generation in the move loop.

In Crafty, I handle two distinct cases:

(1) If I start off not in check at a node, I generate pseudo-legal moves and make 'em one at a time using normal ordering. After selecting the next move and making it, I ask "is my king in check?" and if so, discard the move as illegal. This is very fast since most moves are legal.

(2) If I start off in check at a node, I then generate moves with a special move generator that only produces legal moves. how? It is actually simple. If you are in check, you only have three options... (1) capture the checking piece, unless there are two pieces giving check as in a in a double-discovered-check; (2) interpose if the checking piece is a sliding piece; (3) else move the king out of check. If you look at GenerateCheckEvasions() in Crafty, you will see that I do exactly the above. The plus is that it is slightly faster since I don't need to check for legality and also I know how many legal moves there are instantly which makes the one-reply-to-check extension easier to deal with.

[Edsel Apostol]

In Crafty, I handle two distinct cases:

(1) If I start off not in check at a node, I generate pseudo-legal moves and make 'em one at a time using normal ordering. After selecting the next move and making it, I ask "is my king in check?" and if so, discard the move as illegal. This is very fast since most moves are legal.

(2) If I start off in check at a node, I then generate moves with a special move generator that only produces legal moves. how? It is actually simple. If you are in check, you only have three options... (1) capture the checking piece, unless there are two pieces giving check as in a in a double-discovered-check; (2) interpose if the checking piece is a sliding piece; (3) else move the king out of check. If you look at GenerateCheckEvasions() in Crafty, you will see that I do exactly the above. The plus is that it is slightly faster since I don't need to check for legality and also I know how many legal moves there are instantly which makes the one-reply-to-check extension easier to deal with.

I think we are doing the same thing in (2) when a node is in check but the order is different. We differ in (1). In (1) where the position is not in check, I use the move from the hash table first without generating any move. I used the data from pinned pieces to check for legality, and then if this doesn't produce a cut-off, I generate all tactical moves, and again if this didn't produce a cut-off, I used again the killer moves without generating first the non-tactical moves.

Note that I have routine to determine if a move is check before calling makemove. I used it to decide pruning non checking moves without calling makemove first to determine if a move is a check.

[bob]

In Crafty, I handle two distinct cases:

(1) If I start off not in check at a node, I generate pseudo-legal moves and make 'em one at a time using normal ordering. After selecting the next move and making it, I ask "is my king in check?" and if so, discard the move as illegal. This is very fast since most moves are legal.

(2) If I start off in check at a node, I then generate moves with a special move generator that only produces legal moves. how? It is actually simple. If you are in check, you only have three options... (1) capture the checking piece, unless there are two pieces giving check as in a in a double-discovered-check; (2) interpose if the checking piece is a sliding piece; (3) else move the king out of check. If you look at GenerateCheckEvasions() in Crafty, you will see that I do exactly the above. The plus is that it is slightly faster since I don't need to check for legality and also I know how many legal moves there are instantly which makes the one-reply-to-check extension easier to deal with.

I think we are doing the same thing in (2) when a node is in check but the order is different. We differ in (1). In (1) where the position is not in check, I use the move from the hash table first without generating any move. I used the data from pinned pieces to check for legality, and then if this doesn't produce a cut-off, I generate all tactical moves, and again if this didn't produce a cut-off, I used again the killer moves without generating first the non-tactical moves.

Note that I have routine to determine if a move is check before calling makemove. I used it to decide pruning non checking moves without calling makemove first to determine if a move is a check.

I try the hash move without generating moves as well, but nothing says you won't be in check after making such a move if you have a real hash collision, so it has to be legality checked. I then try captures and next try the killer moves, again without generating the rest of the (non-capture) moves. And I have the same issue there.

I don't need to check legality if I start off in check because the legal move generator only produces legal moves in those positions.

[hgm]

The main problem I have in my engines is this: I get the in-check information from the hash table. (In uMax implicitly, by probing the position for the other side to move, to see if it has a King-capture score.) So if I have a true key collission, I can get a false in-check status.

This makes it possible to get in a mutual-perpetucl cycle, something that is not possible in orthodoc Chess: one side has a genuine perpetual, the other side, due to the key collissions, mistakenly thinks that the opponen's check evasions counter-check him. As I extend for evasions, this leeds to infinite regression, and a crash of the engine.

[Edsel Apostol]

We're doing almost the same except that you make the move before determining if that still leaves the king hanging and therefore leads to an illegal position while my implementation is that I check before making the move if it is legal, thereby saving me the call to unmakemove if it is indeed illegal. It doesn't really matter anyway as most pseudo-moves are legal.

In the case of hash moves and killer moves, I have a routine to check if it is a valid move for that position, therefore it is safe from hash collisions as it makes sure that the move is valid, after that I double check with calling moveIsLegal and that should never leave the king hanging. It's pretty safe, I have not experience any crash or something due to illegal move, it's what Glaurung and Fruit is doing too. Glaurung even uses this technique to avoid using locks in the transposition table as the hash move is being validated anyway.

When in check I also have a legal move generator just like in Crafty and I don't call any move validation for that routine also.

[Edsel Apostol]

Make sure that you will never have hash collisions or maybe just write a routine to determine if a position is in check. If having the information from the hash table is much faster and the crash only happens for maybe 1 in 10000 games then having the speed-up in 9999 games is more than compensates for a 1 game crash.

[bob]

We're doing almost the same except that you make the move before determining if that still leaves the king hanging and therefore leads to an illegal position while my implementation is that I check before making the move if it is legal, thereby saving me the call to unmakemove if it is indeed illegal. It doesn't really matter anyway as most pseudo-moves are legal.

In the case of hash moves and killer moves, I have a routine to check if it is a valid move for that position, therefore it is safe from hash collisions as it makes sure that the move is valid, after that I double check with calling moveIsLegal and that should never leave the king hanging. It's pretty safe, I have not experience any crash or something due to illegal move, it's what Glaurung and Fruit is doing too. Glaurung even uses this technique to avoid using locks in the transposition table as the hash move is being validated anyway.

When in check I also have a legal move generator just like in Crafty and I don't call any move validation for that routine also.

Actually that is _the_ point. AKA procrastination. I only check for legality when I actually have to make the move on the board, In fail-high (CUT) nodes, I generally search just one move and only legality-check that move (if not already in check).

[jwes]

We're doing almost the same except that you make the move before determining if that still leaves the king hanging and therefore leads to an illegal position while my implementation is that I check before making the move if it is legal, thereby saving me the call to unmakemove if it is indeed illegal. It doesn't really matter anyway as most pseudo-moves are legal.

In the case of hash moves and killer moves, I have a routine to check if it is a valid move for that position, therefore it is safe from hash collisions as it makes sure that the move is valid, after that I double check with calling moveIsLegal and that should never leave the king hanging. It's pretty safe, I have not experience any crash or something due to illegal move, it's what Glaurung and Fruit is doing too. Glaurung even uses this technique to avoid using locks in the transposition table as the hash move is being validated anyway.

When in check I also have a legal move generator just like in Crafty and I don't call any move validation for that routine also.

Actually that is _the_ point. AKA procrastination. I only check for legality when I actually have to make the move on the board, In fail-high (CUT) nodes, I generally search just one move and only legality-check that move (if not already in check).

I ran some stats on crafty and got this
check called/moves generated = 1.09, check called/moves made = 1.54 , check called/incheck = 13.62
This makes a legal move generator look better, as it may be expensive, but I doubt it is more expensive than calling incheck 30 times.