The cost of check & discovered check in bitboards

[Chessnut1071]

Am I the only one who finds these never-ending discussions about which language is better to be quite tiresome? Like every 2nd thread seems to derail into one of these...

I think we got off my original question about including metrics like discovered check in the search plys. I find that including discovered check reduces my engine speed by about 1/3. Including check reduces the engine speed about 1/10, well worth the effort to include it.

My question is, does anyone have a very efficient method to calculate discovered check that doesn't drag down the engine speed.

[pedrojdm2021]

If we wanted to make a fair comparison one should make an effort to implement exactly the same thing in C# and in C++ and compare that.

That's what i just told in the very first reply that i quoted you here.

One can compare a simple bitboard representation, then do some bitwise operations inside a for loop that runs for a considerable numbers of iterations, then you can test the difference

the same algorithm, the same code, no allocations or something else, just doing some operations with some ulong[] arrays in the C# side and some U64 arrays in in the C++ side, and you will see.

In my experience in C# ( . net framework 4.6.1 ) even doing bitwise operations just like the algorithm that appears in chessprogramming wiki:
https://www.chessprogramming.org/Square ... all_Pieces

That thing is very slow in C# at least in the C# that i'm running, you can't call that thing ~6M of times because it will be a very big slowdown. in C++ that should be really fast as you are just doing bitwise operation that are known to be super fast instructions

I don't know if in the . net that you are using that stuff is now very native instructions or much more optimized

one thing that i've noticed is that these engines in . net 5 , the binaries are worth of 10 mb in file size while the binaries that is built from Visual Studio in . net 4 are just 60kb

[pedrojdm2021]

Am I the only one who finds these never-ending discussions about which language is better to be quite tiresome? Like every 2nd thread seems to derail into one of these...

I think we got off my original question about including metrics like discovered check in the search plys. I find that including discovered check reduces my engine speed by about 1/3. Including check reduces the engine speed about 1/10, well worth the effort to include it.

My question is, does anyone have a very efficient method to calculate discovered check that doesn't drag down the engine speed.

detecting checks and discovered checks are a complex task if you want it super fast

i have an idea of having 2 bitboards for "ray attacks", fill them in GenerateMoves() with the current sideToMove attacks_to squares
and use that as a mask to know if your king touches one of these rays

something like
if ((ray_attacks[sideToMove ^ 1] & bitboards[white_king] ) > 0 ) // if true white king is in check

but i haven't tested the performance of that, it is just an idea for now

[Chessnut1071]

Am I the only one who finds these never-ending discussions about which language is better to be quite tiresome? Like every 2nd thread seems to derail into one of these...

I think we got off my original question about including metrics like discovered check in the search plys. I find that including discovered check reduces my engine speed by about 1/3. Including check reduces the engine speed about 1/10, well worth the effort to include it.

My question is, does anyone have a very efficient method to calculate discovered check that doesn't drag down the engine speed.

detecting checks and discovered checks are a complex task if you want it super fast

i have an idea of having 2 bitboards for "ray attacks", fill them in GenerateMoves() with the current sideToMove attacks_to squares
and use that as a mask to know if your king touches one of these rays

something like
if ((ray_attacks[sideToMove ^ 1] & bitboards[white_king] ) > 0 ) // if true white king is in check

but i haven't tested the performance of that, it is just an idea for now

[hgm]

I am not sure what the issue is. Most engines detect whether the side to move is in check, e.g. in order to know whether to give a check extension, or invoke a special move generator for evasions. This is the same task as determining whether the move leading to the node deliverd a check, as the rules of chess do not allow that the check already existed before the move. In general it is not a good idea to spend time on a move before you are sure it is actually going to be searched. So determinig whether a move delivers check already during move generation would only make sense when you need this information to decide whether the move is going to be searched or not. If the rule for that is 'only search if it is a check', it would be better to use a dedicated move generator for selectively generating checks, rather than to generate all moves, and test each of those for delivering checks. (As I think was already pointed out above.)

Detection of checks can be sped up by keeping track of the set of pieces that is aligned with the opponent king. For non-king move this can be done incrementally, e.g. with moveCode[piece] & alignment[to - king], which can be used to set a bit corresponding to the piece in the set of aligned pieces. If a leaper is aligned for check, there is a check; if a slider is aligned it could still be blocked. So slider alignments have to be verified for actually delivering check, which you can do by extracting the aligned sliders one by one from the set of aligned pieces, and test for blocking. The common case is that no sliders will be aligned, so this doesn't take much time. Only after a King move you would have to generate the set of aligned pieces from scratch. But King moves are not very abundant in the tree.

[Chessnut1071]

I am not sure what the issue is. Most engines detect whether the side to move is in check, e.g. in order to know whether to give a check extension, or invoke a special move generator for evasions. This is the same task as determining whether the move leading to the node deliverd a check, as the rules of chess do not allow that the check already existed before the move. In general it is not a good idea to spend time on a move before you are sure it is actually going to be searched. So determinig whether a move delivers check already during move generation would only make sense when you need this information to decide whether the move is going to be searched or not. If the rule for that is 'only search if it is a check', it would be better to use a dedicated move generator for selectively generating checks, rather than to generate all moves, and test each of those for delivering checks. (As I think was already pointed out above.)

Detection of checks can be sped up by keeping track of the set of pieces that is aligned with the opponent king. For non-king move this can be done incrementally, e.g. with moveCode[piece] & alignment[to - king], which can be used to set a bit corresponding to the piece in the set of aligned pieces. If a leaper is aligned for check, there is a check; if a slider is aligned it could still be blocked. So slider alignments have to be verified for actually delivering check, which you can do by extracting the aligned sliders one by one from the set of aligned pieces, and test for blocking. The common case is that no sliders will be aligned, so this doesn't take much time. Only after a King move you would have to generate the set of aligned pieces from scratch. But King moves are not very abundant in the tree.

Testing each move for check can be very quickly done by using a check mask. branch out from the King's position in 8 directions, marking each vector 1 - 8, depending on whether its a diagonal or rank, + or -, and I use 9 for the knight and 10 for the king's position. Then, each pseudo move can be checked by simply testing the square for a check index. When I cleaned up my code, it only reduces my engine speed by a little over 6%; however, it greatly reduces the time to solve for my objective-minimum moves to checkmate. I use 1,025 puzzles from 4 - 20 ply to test both time and nodes called and can guarantee, if you ignore check you will miss the solution of at least a dozen of these puzzles. Check increases in importance the higher ply you go. Using discovered check, however, is another issue. Ignoring that metric also increases the number of missed solutions; but, the time penalty, using my algorithm, reduces my engine speed by about 32%. My objective is to be perfect on the 1,025 solutions regardless of the time.

So, I need a faster way to compute discovered check, and would appreciate any good suggestions.

[hgm]

I am not sure what you mean by 'ignoring check'. Testing moves for check would not buy you anything if you didn't use that info to search moves you wouldn't have searched otherwise. So what exactly are you talking about? Searching checks in Quiescence Search? Just detecting whether a check is a checkmate?

Testing whether a move delivers a discovered check is usually done by detecting alignment of the from-square with the King. This should not be more expensive then detecting alignment of the to-square with the King (which you would do for direct checks). If I understood your previous posting you do this through a lookup vector[toSqr][kingSqr] which returns a number 0-10. And since most pieces will not be aligned, that would typically be the only thing you do. In fact if you do this in the move generator the discovered check is easier. At least if you generate moves per pieces. As once you detect alignment, it would be for all moves of the piece. So you would do it once per piece, not once per move.

When you detect alignment you would just have to determine what is at the end of the ray starting from the King indicated by the vector table.

[Chessnut1071]

I am not sure what you mean by 'ignoring check'. Testing moves for check would not buy you anything if you didn't use that info to search moves you wouldn't have searched otherwise. So what exactly are you talking about? Searching checks in Quiescence Search? Just detecting whether a check is a checkmate?

Testing whether a move delivers a discovered check is usually done by detecting alignment of the from-square with the King. This should not be more expensive then detecting alignment of the to-square with the King (which you would do for direct checks). If I understood your previous posting you do this through a lookup vector[toSqr][kingSqr] which returns a number 0-10. And since most pieces will not be aligned, that would typically be the only thing you do. In fact if you do this in the move generator the discovered check is easier. At least if you generate moves per pieces. As once you detect alignment, it would be for all moves of the piece. So you would do it once per piece, not once per move.

When you detect alignment you would just have to determine what is at the end of the ray starting from the King indicated by the vector table.

"At least if you generate moves per pieces. As once you detect alignment, it would be for all moves of the piece. So you would do it once per piece, not once per move."

I think you are missing one scenario, what if the piece is moved in the direction of the check? For example, white rook attacking a pinned black rook or queen. the rook could retreat in the line of check with no discovered checkmate, or, could leave the line of check and put his king in check. That's a simple problem to solve, just take the absolute value of the line of check direction, and ignore the discovered check if the vectors are the same.

"I am not sure what you mean by 'ignoring check.."

In earlier posts one OP recommended ignoring checks and discovered checks to speed up his search. I found the exact opposite is the case. You miss solutions and the time increases dramatically, since checks are looked at first and have the largest impact for both sides. I'm not sure that was a serious post, but, wanted to see if I misses something.

[hgm]

I think you are missing one scenario, what if the piece is moved in the direction of the check? For example, white rook attacking a pinned black rook or queen. the rook could retreat in the line of check with no discovered checkmate, or, could leave the line of check and put his king in check. That's a simple problem to solve, just take the absolute value of the line of check direction, and ignore the discovered check if the vectors are the same.

Well, I was not missing that, but it just enters in a later stage, which is hardly ever reached. (And thus has little impact on speed.) The point is that the first two tests (from-square alignment and a slider of the proper type behind it) are valid for every move of the piece. Only if these indicate a constellation that allows discovered checks, you can test the moves per direction whether they move along the check ray, and only generate moves in the other directions. That third test would be valid for all moves in a given direction, although that is probably not useful when you use bitboards. It could still be useful when you only want to generate checks, as you would mask away the set of all destinations with the check ray, and then only extract the discovered checks.

"I am not sure what you mean by 'ignoring check.."

In earlier posts one OP recommended ignoring checks and discovered checks to speed up his search. I found the exact opposite is the case. You miss solutions and the time increases dramatically, since checks are looked at first and have the largest impact for both sides. I'm not sure that was a serious post, but, wanted to see if I misses something.

The point is that I don't understand what you mean by 'ignoring'. You mean 'pruning'?

[Chessnut1071]

I think you are missing one scenario, what if the piece is moved in the direction of the check? For example, white rook attacking a pinned black rook or queen. the rook could retreat in the line of check with no discovered checkmate, or, could leave the line of check and put his king in check. That's a simple problem to solve, just take the absolute value of the line of check direction, and ignore the discovered check if the vectors are the same.

Well, I was not missing that, but it just enters in a later stage, which is hardly ever reached. (And thus has little impact on speed.) The point is that the first two tests (from-square alignment and a slider of the proper type behind it) are valid for every move of the piece. Only if these indicate a constellation that allows discovered checks, you can test the moves per direction whether they move along the check ray, and only generate moves in the other directions. That third test would be valid for all moves in a given direction, although that is probably not useful when you use bitboards. It could still be useful when you only want to generate checks, as you would mask away the set of all destinations with the check ray, and then only extract the discovered checks.

"I am not sure what you mean by 'ignoring check.."

In earlier posts one OP recommended ignoring checks and discovered checks to speed up his search. I found the exact opposite is the case. You miss solutions and the time increases dramatically, since checks are looked at first and have the largest impact for both sides. I'm not sure that was a serious post, but, wanted to see if I misses something.

The point is that I don't understand what you mean by 'ignoring'. You mean 'pruning'?

"The point is that I don't understand what you mean by 'ignoring'. You mean 'pruning'?"

Roger that, I mean over pruning!