Updating pinned pieces map? When/how?

[KhepriChess]

I've been messing around with creating an "IsLegal" function to test for move legality before actually making the move. I've gotten it working but I'm trying to speed it up (it's slower method I currently use). I'm having trouble with pinned pieces (again) though.

What I'm getting stuck on is how/when to update the pinned pieces map. For example, take this simple sequence:

[pgn][Variant "From Position"]
[FEN "8/2p5/3p4/KP5r/1R3p1k/8/4P1P1/8 w - - 0 1"]

1. e4[/pgn]

After e2e4, I assume that I should no longer consider the black pawn pinned. My current code still considers it pinned after e2e4, so when it tests the legality of f4f3 is says that move is not legal.

I know I could easily call my method that generates the pinned pieces map after every move, but I'm not sure if that's really the correct thing to do. Though I'm not sure how else I'd do it.

My reference for this has been Stockfish. It appears to set the pinned map when the FEN is loaded. But I can't find any other calls to update those maps in the code. Surely somewhere/somehow it does.

[hgm]

Note that f4 is still pinned after e2-e4 w.r.t. e.p. capture.

The key for incremental update seems to be that you land on a square that is attacked by an enemy slider. That means you block some of its moves, which could have pinned something. You would only be interested in sliders aligned with a King. You could make a lookup table indexed by King location and to-square to get the set of squares where a blocked pinner could be, and then test whether a piece of the relevant type is present on one of those squares.

[Aleks Peshkov]

You need to use occupancy bitboard for checking pins in the state after the move. En Passant capture move changes 3 squares: from, to and captured pawn.

[tcusr]

https://github.com/official-stockfish/S ... n.cpp#L315

[KhepriChess]

https://github.com/official-stockfish/S ... n.cpp#L315

Well, I had seen that function but apparently missed that it's called in the do_move and do_null_move methods. So that's easy enough to do.

And everything works now! But man, it's super slow. I guess now that's it's working I can try taking some passing at performance.

[tcusr]

https://github.com/official-stockfish/S ... n.cpp#L315

Well, I had seen that function but apparently missed that it's called in the do_move and do_null_move methods. So that's easy enough to do.

And everything works now! But man, it's super slow. I guess now that's it's working I can try taking some passing at performance.

an underrated method that i've never seen mentioned is the one described in this paper (page 35).
it's designed for a mailbox representation but i think it can be translated to a bitboard one. this only works when the current side to move is not in check so you also need a generator for check evasions.

[dangi12012]

I tried incremental updates - and I can tell you that when you do optimal XRAY code that becomes cheaper than looking than all the bookkeeping needed to incrementally do XRAY.
It kind of made me angry - it took 2 weeks to write good incremental bitboards only to find out that the final solution was 15% slower than just calculating Xrays on every move.

(They are quite cheap - single Xray queen call to PEXT - has the same speed as a queen lookup itself)
Actually PEXT and Magic Bitboards are the only two algos that can do Xrays in the same amount of time as Rays.

So in summary: Updating pinned pieces was slower - when using the optimal xray algo.
PinnedHV = Xray_rook(king) & enemyRookQueen.


My solution was to take to 2 or 3 bits that changed in the position and update only those xrays and rays that are affected.
Was complicated, cool to think and solve, but ultimately slower than 1 extra call to pext.

[KhepriChess]

This whole undertaking was prompted by me reading hgm's comment here: https://talkchess.com/forum3/viewtopic. ... 79#p931962

The "IsAttacked" method mentioned is exactly how I've been doing it: make the move, then check to see if the king is attacked and if it is then unmake the move.

After reading his comment, I implemented an "IsLegal" function and as part of that, a whole way to keep track of pinned pieces (as I mentioned above). But it seems that the whole up-pinned-pieces-on-make-move thing is too slow. Part of the problem seems to be the additional calls to get/pop the least-significant bit and to count bits, which is slow as hell in JS (mostly because there's no low level/CPU instructions to call to do those things).

I tried incremental updates - and I can tell you that when you do optimal XRAY code that becomes cheaper than looking than all the bookkeeping needed to incrementally do XRAY.
It kind of made me angry - it took 2 weeks to write good incremental bitboards only to find out that the final solution was 15% slower than just calculating Xrays on every move.

(They are quite cheap - single Xray queen call to PEXT - has the same speed as a queen lookup itself)
Actually PEXT and Magic Bitboards are the only two algos that can do Xrays in the same amount of time as Rays.

So in summary: Updating pinned pieces was slower - when using the optimal xray algo.
PinnedHV = Xray_rook(king) & enemyRookQueen.


My solution was to take to 2 or 3 bits that changed in the position and update only those xrays and rays that are affected.
Was complicated, cool to think and solve, but ultimately slower than 1 extra call to pext.

I was initially using the xray methods like you wrote:

Code: Select all

PinnedHV = Xray_rook(king) & enemyRookQueen

But this was hilariously slow for me. I ended up using empty board attack maps (i.e. attacks on an empty board) that are initialized at the start. This was so much faster.

The whole thing is still slower (and weaker) though. I might need to get creative with solutions here to try and work around the inherent shortcomings of JS.

[dangi12012]

Emscripten my friend.
Compiles to JS or Webasm.

[KhepriChess]

Emscripten my friend.
Compiles to JS or Webasm.

I've been tempted to use emcripten, or other web assembly languages, but I intentionally chose to write this in JS to see how it worked with BigInts. I now know it's slow as heck (just in general, any operations on BigInts are painfully slow), but I'll keep at it since my overall goal isn't to come up with some super strong engine.