Efficiently Detect Whether a Move Gives Check

[oriyonay]

Hi friends
What's the best way of detecting whether a move gives check (preferably without having to play the move)? I'm using a bitboard representation

- Ori

[expositor]

If you are wanting to know whether several moves give check (e.g. determing whether moves give check at move generation time), I'd recommend reading Generating Legal Chess Moves Efficiently by Peter Ellis Jones. If you want to know whether a single move gives check, it's probably fastest to update the bitboards (a few xor operations) and then calculate destinations from the king (pretending it's a rook and seeing if the destinations overlap with an enemy queen or rook, pretending it's a bishop and seeing if the destinations overlap with an enemy queen or bishop, pretending it's a knight, &c) – which catches both direct checks and discovered checks.

[oriyonay]

I'd recommend reading Generating Legal Chess Moves Efficiently by Peter Ellis Jones.

Thank you, I'm familiar with the article, and my move generation is pretty fast My question is, given a move (e2e4 for example), determine whether it gives check, without playing the move.

[expositor]

Coincidentally, I was editing my response while you were typing; have you tried the second strategy? If so, and it wasn't sufficiently performant, I'll have to do some thinking.

[expositor]

Oh, sorry, I just realized I left out something important. The reason I mentioned Peter Ellis Jones' article was because you can do something similar (precompute masks). In pseudocode, something like:

Code: Select all

// Direct checks
//   If a piece moves to a destination within the vantage of its kind,
//   we know check is being delivered
opp_king_sq    := boards[opponent+king].tzcnt()
rook_vantage   :=   rook_destinations(occupation, opp_king_sq)
bishop_vantage := bishop_destinations(occupation, opp_king_sq)
vantage_masks := [
  0, rook_vantage | bishop_vantage, rook_vantage, bishop_vantage,
  knight_destinations(opp_king_sq), pawn_attacks(turn, opp_king_sq)
]

// Discovered checks
//   If a piece is on a waylay square, we will calculate its span to the enemy king, and
//   if the piece moves to a destination outside that span, we know check is being delivered
waylay_mask := 0
for attacker in queen...knight {
  atk_sources := self.boards[player+attacker]
  while atk_sources != 0 {
    atk_src := atk_sources.tzcnt()
    span := match attacker {
      queen  =>  any_span(opp_king_sq, atk_src),
      rook   => cruciform_span(opp_king_sq, atk_src),
      bishop => saltire_span(opp_king_sq, atk_src),
    }
    intermediate := span & occupation
    if intermediate.popcnt() == 1 {
      waylay_mask |= intermediate
    }
    atk_sources &= atk_sources - 1	// clears the lowest set bit
  }
}

// and while generating the moves for a particular piece,

discovery_mask :=
  if (1 << src_sq) & waylay_mask == 0 {
    0xFFFFFFFFFFFFFFFF
  }
  else {
    line_through(src_sq, opp_king_sq)
  }

gives_check :=
  (1 << dst_sq) & vantage_mask[piece] != 0 || (1 << dst_sq) & discovery_mask == 0

(This happens to be the strategy I currently employ. Doing legal-only move generation, in which I also tag each move for check delivery, I get around 40–50 mnode/s for single-threaded perft. Add in zobrist key updates to move application and that drops to 35–40 mnode/s or so.)

Again, I think this is only more performant if you are calculating check delivery for many moves in a batch. Otherwise, I believe that second strategy (in my first message) is faster.

[expositor]

I should mention that the code above is, with very little modification, directly copied from Expositor's source. I've not distributed the engine publicly yet, except to a few friends, but the source is licensed under the Affero General Public License, and I'd like the code above to be treated similarly (which is to say, feel free to use the idea in any way, including for writing closed source, but please do not copy the code without also making it available under the terms of a copyleft license to anyone who might interact with it).

[dangi12012]

Hi friends
What's the best way of detecting whether a move gives check (preferably without having to play the move)? I'm using a bitboard representation
- Ori

You dont need to play the move - just emulate the occupancy change on the single register with occ ^= (from | to) for moves and occ &= ~ from for takes.
I have written the fastest cpu movegen ever - so I will just share what I used before having a pinmask (then you dont need the step you want to calculate anyway because the movegen is fully legal and detects check with a single & operation)

For your question: https://github.com/Gigantua/Gigantua/bl ... t.hpp#L154
Get the mask for a queen from the position of the king and look if sliders are inside that. (insanely fast)

If yes - send out rays fromt the position of the king for rooks and bishops.
map atkHV = Lookup::Rook(kingsq, brd.Occ) & EnemyRookQueen<white>(brd);

knight and pawn checks are just the same. Lookup::Knight(kingsq) & EnemyKnight<white>(brd)

So all in all probably 20 branchless simple x64 instructions

[chrisw]

Hi friends
What's the best way of detecting whether a move gives check (preferably without having to play the move)? I'm using a bitboard representation

- Ori

Pre-compute a u64 lookup[pt][s1][s2], for every piece type if there a legal move connection between s1,s2 set bit 0. For ray pieces set the inbetween bits of they exist.

I’m assuming a pin mask will have found discovered checks.

For direct checks:
m = lookup[pt][sqto][sqking]

check = m && (onlyonebit(m) || !( (m&~1ull) & occ))

Basically if the mask is not zero and contains either only one bit (bit 0) or it’s inbetween mask is not occupied then it’s a check. We take advantage of the fact that bit 0 can never be an inbetween bit.

Should work for all piece types.