Magic Bitboards and PEXT
Magic Bitboards and PEXT The Problem: Sliding Piece Attacks Why Sliding Pieces Are Hard Non-sliding pieces (knight, king, pawn): Fixed attack pattern regardless of board state Can pre-compute all attacks at startup Simple lookup: StepAttacksBB[piece][square] Sliding pieces (rook, bishop, queen): Attack pattern depends on blocking pieces Can’t pre-compute all possibilities (too many combinations) The Challenge Rook on e4 - different scenarios: Scenario 1: Empty board 8 . . . . X . . . 7 . . . . X . . . 6 . . . . X . . . 5 . . . . X . . . 4 X X X X R X X X ← Attacks entire rank and file 3 . . . . X . . . 2 . . . . X . . . 1 . . . . X . . . a b c d e f g h Scenario 2: Blocked by pieces 8 . . . . . . . . 7 . . . . . . . . 6 . . . . X . . . 5 . . . . X . . . 4 . . X X R X . . ← Blocked at c4 and f4 3 . . . . X . . . 2 . . . . . . . . 1 . . . . . . . . a b c d e f g h (Pieces at: c4, e2, e6, f4) The question: How do we efficiently compute attacks for ANY occupancy pattern? ...