Skip to content

Piece Movements

Jump to bottom
Nick Slerts edited this page Dec 30, 2015 · 5 revisions

Bitwise Operations

  • The use of bitboards enables the use of bit operations for movement generation
>>n    shifts bits n of bits to the right (keeps left most bit as is, use >>> to force 0)
<<n    shifts bits n of bits to the left
n & m    bits in n **AND** m that are both 1 are retained as 1s in result
n | m    bits in n **OR** m that are both 1 are retained as 1s in result
n ^ m    bits in n **OR** m that are 1 **BUT NOT BOTH** are retained as 1s in result (exclusive-or)

Bitboards Required

Board Control

  • 2 Files: A & H
    • prevent bad pawn moves (File H -> File A)
    • hold 1's for each bit contained in given file
  • 4 Ranks
    • 1 & 8
      • used for pawn promotion
      • hold 1's for each bit contained in given rank
    • 4 & 5
      • used for en passant
      • hold 1's for each bit contained in given rank
  • 1 empty spaces
    • hold 1's for each bit that does not have a pc

Captures & Not Captures

  • 1 for spaces with black pcs that white can capture
    • bP, bN, bB, bR, bQ
  • 1 for spaces with white pcs that black can capture
    • wP, wN, wB, wR, wQ
  • 1 for spaces of pcs that white can't capture
    • wP, wN, wB, wR, wQ, wK, bK (because you should never capture the opposing king)
  • 1 for spaces of pcs that black can't capture
    • bP, bN, bB, bR, bQ, bK, wK (because you should never capture the opposing king)

Current Piece Positions

  • 6 white: pawn, knights, bishops, rooks, queen, king
  • 6 black: pawn, knights, bishops, rooks, queen, king

Piece moves

  • 3 for sliding pieces (Bishops, Rooks, Queens)

    • occupied: all positions occupied on current path
    • slider: position of current sliding pc.
    • result: all positions sliding pc can move

  • 2 for pawns (1 each for white and black)

  • 2 for knights (1 each for white and black)

  • 2 for king (1 each for white and black)

Move generation

  • concatenate list of all possible moves
  • maintain history of moves made
  • search can be optimized by only looking between first and last destinations

Pawn Moves

Forward movements

  • 1 space
    • >> 8 (white pawn)
    • << 8 (black pawn)
  • 2 spaces
    • >> 16 (white pawn)
    • << 16 (black pawn)
    • 8 bit shift must also be empty

Attacks

  • left
    • >> 9 (white pawn)
    • << 7 (black pawn)
  • right
    • >> 7 (white pawn)
    • << 9 (black pawn)
  • en passant

En Passant

  • if player moves pawn 2 spaces, to rank 4 (black pawn) or 5 (white pawn), and there is an enemy pawn in an adjacent file
    • opposing pawn can attack as if player only moved forward 1 rank
  • need to know move history
  • if player makes move creating opportunity then bitboard is generated masking file it is possible in

Sliding Pieces (Bishops, Rooks, Queens)

  • hyperbole quintessence
    • sliding in negative index direction: occupied XOR (occupied - 2*slider)
    • sliding in positive index direction: occupied XOR !(!occupied - 2*!slider)
  • occupied has to be multiplied by a mask for ray mask
    • horizontal: rank
      • rook, queen
    • vertical: file
      • rook, queen
    • diagonals: diagonal and antidiagonals
      • bishop, queen
      • diagonal goes top left to bottom right
      • antidiagonal goes top right to bottom left
  • outer loop goes through entire board to find all pcs of each type
    • all moves must be determined for all found
  • warning: don't forget to & with pieces that can't be captured
Clone this wiki locally