Page 1 of 1
En-passant legality test
Posted: Thu Aug 07, 2014 12:14 am
by tetra
Hello!
Right now for generating legal moves based on a bitboard of en-passant pseudo-legal moves I do an "is king in check after move" validation, but this is slow. Theres a much faster way by calculating all the pins even en-passant pins.
In cpw they explain how this legality test is made:
"for strict legality, the ep capturing pawn should not be absolutely pinned, which additionally requires a horizontal pin test of both involved pawns, which disappear from the same rank"
and I understand that ^ .but I don't have any idea how I can calculate the pinned pawns since there are one opposite colour pawn in the same rank and therefore they are not really pinned.
For example in this position: 8/6bb/8/8/R1pP2k1/4P3/P7/K7 b - d3
The pawn on c4 after d2-d4 is "pinned" for the en-passant move but not pinned for the push move!
To find pinned pieces, I generate the rook moves from king square and then i intercept them with our pieces to find the pieces that can pin. After this I calculate the xrays but it will fail because of a second pawn blocking rook rays attacks and will not find the pinned pawn.
Any ideas to do this legality test?
Re: En-passant legality test
Posted: Thu Aug 07, 2014 10:30 pm
by HumbleProgrammer
This may not be the answer you're looking for, but I wrestled with the same problem before giving up and paying for the exposed check test after every e.p. capture if (and only if) the King is on the 4th/5th rank. After parsing over a million games from TWIC, this scenario occurred less than 0.01% of the time, so I rationalized it as "not worth the effort" and focused my optimization lens elsewhere.
Cheers!
Humble Programmer
,,,^..^,,,
Re: En-passant legality test
Posted: Fri Aug 08, 2014 1:09 am
by tetra
HumbleProgrammer wrote:This may not be the answer you're looking for, but I wrestled with the same problem before giving up and paying for the exposed check test after every e.p. capture if (and only if) the King is on the 4th/5th rank. After parsing over a million games from TWIC, this scenario occurred less than 0.01% of the time, so I rationalized it as "not worth the effort" and focused my optimization lens elsewhere.
Thanks for the answer,
you're probably right. I did some tests and removing the legal test of en-passants moves only speed up's the move generator by a 250k nps at most and obviously it will produce some wrong moves. But right now I want to optimize my move generator the most possible and I dont have any more ideas besides this one. Still, I'm quite happy with my speed results but they are far from close to Stockfish nps. Stockfish perft speed is just outrageous..
Re: En-passant legality test
Posted: Fri Aug 08, 2014 2:02 am
by lucasart
Here's my move generator:
https://github.com/lucasart/DiscoCheck/ ... /src/gen.c
As you can see, I generate legal moves directly, and I never play any move to find out if it's legal. Easy as pie: make sure pinned pieces stay on their pin-ray. And for en-passant I "play" the move only on the occupancy bitboard, and.check for sliding attacks.
My movegen is about as fast as SF. Though quite different (SF uses pseudo-legal I use legal directly for all moves, even FRC casting…)
Re: En-passant legality test
Posted: Fri Aug 08, 2014 2:08 am
by tetra
lucasart wrote:Here's my move generator:
https://github.com/lucasart/DiscoCheck/ ... /src/gen.c
As you can see, I generate legal moves directly, and I never play any move to find out if it's legal. Easy as pie: make sure pinned pieces stay on their pin-ray. And for en-passant I "play" the move only on the occupancy bitboard, and.check for sliding attacks.
My movegen is about as fast as SF. Though quite different (SF uses pseudo-legal I use legal directly for all moves, even FRC casting…)
Thats very interesting lucas! But how you make sure that pinned pieces stay on their pin ray? Do you calculate that ray using only bitboards? Without bit operations that must be slow imo...
Re: En-passant legality test
Posted: Fri Aug 08, 2014 3:46 am
by lucasart
Of course rays must be precalculated bitboards. Look at the code:
tss &= bb_ray(kpos, m->fsq);
That's an O(nb our pieces cost) to generate legal moves directly. It's very cheap! It's an order of magnitude less than O(nb legal moves).
Re: En-passant legality test
Posted: Fri Aug 08, 2014 10:13 am
by tetra
lucasart wrote:Of course rays must be precalculated bitboards. Look at the code:
tss &= bb_ray(kpos, m->fsq);
That's an O(nb our pieces cost) to generate legal moves directly. It's very cheap! It's an order of magnitude less than O(nb legal moves).
I don't understand how is that supposed to work..
Image this position:
rnbqk1nr/pppp1ppp/4p3/b7/3P4/2B5/PPP1PPPP/RN1QKBNR w KQkq - 4 4
From what I understand you generate the bishop moves and then if that piece is pinned you intercept those moves with the squares between the king and you piece "from square", but that will fail. That means you will generate the moves Ba5, Bb4 and Bd2 that are actually all legal and then you intercept those moves with the square d2(Ray[e1][c3] = square d2) and after all it will only intercept the move to d2 square.. or am I wrong?
Re: En-passant legality test
Posted: Fri Aug 08, 2014 10:16 am
by tetra
tetra wrote:lucasart wrote:Of course rays must be precalculated bitboards. Look at the code:
tss &= bb_ray(kpos, m->fsq);
That's an O(nb our pieces cost) to generate legal moves directly. It's very cheap! It's an order of magnitude less than O(nb legal moves).
I don't understand how is that supposed to work..
Image this position:
rnbqk1nr/pppp1ppp/4p3/b7/3P4/2B5/PPP1PPPP/RN1QKBNR w KQkq - 4 4
From what I understand you generate the bishop moves and then if that piece is pinned you intercept those moves with the squares between the king and you piece "from square", but that will fail. That means you will generate the moves Bxa5, Bb4 and Bd2 that are actually all legal and then you intercept those moves with the square d2(Ray[e1][c3] = square d2) and after all it will only intercept the move to d2 square.. or am I wrong?
Re: En-passant legality test
Posted: Fri Aug 08, 2014 11:59 am
by lucasart
tetra wrote:lucasart wrote:Of course rays must be precalculated bitboards. Look at the code:
tss &= bb_ray(kpos, m->fsq);
That's an O(nb our pieces cost) to generate legal moves directly. It's very cheap! It's an order of magnitude less than O(nb legal moves).
I don't understand how is that supposed to work..
Image this position:
rnbqk1nr/pppp1ppp/4p3/b7/3P4/2B5/PPP1PPPP/RN1QKBNR w KQkq - 4 4
From what I understand you generate the bishop moves and then if that piece is pinned you intercept those moves with the squares between the king and you piece "from square", but that will fail. That means you will generate the moves Ba5, Bb4 and Bd2 that are actually all legal and then you intercept those moves with the square d2(Ray[e1][c3] = square d2) and after all it will only intercept the move to d2 square.. or am I wrong?
You don't understand what is a "ray":
Code: Select all
ray(E1, C3) = {E1, D2, C3, B4, A5}
A pinned piece move is legal if, and only if, the pinned piece stays on its pin-ray (+add extra conditions for en-passant, and castliing, FRC castling being the most painful to handle...)
Re: En-passant legality test
Posted: Fri Aug 08, 2014 2:48 pm
by tetra
lucasart wrote:tetra wrote:lucasart wrote:Of course rays must be precalculated bitboards. Look at the code:
tss &= bb_ray(kpos, m->fsq);
That's an O(nb our pieces cost) to generate legal moves directly. It's very cheap! It's an order of magnitude less than O(nb legal moves).
I don't understand how is that supposed to work..
Image this position:
rnbqk1nr/pppp1ppp/4p3/b7/3P4/2B5/PPP1PPPP/RN1QKBNR w KQkq - 4 4
From what I understand you generate the bishop moves and then if that piece is pinned you intercept those moves with the squares between the king and you piece "from square", but that will fail. That means you will generate the moves Ba5, Bb4 and Bd2 that are actually all legal and then you intercept those moves with the square d2(Ray[e1][c3] = square d2) and after all it will only intercept the move to d2 square.. or am I wrong?
You don't understand what is a "ray":
Code: Select all
ray(E1, C3) = {E1, D2, C3, B4, A5}
A pinned piece move is legal if, and only if, the pinned piece stays on its pin-ray (+add extra conditions for en-passant, and castliing, FRC castling being the most painful to handle...)
Now I understand! Thank's for everything.