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

  • 1 for pawns

  • 1 for knights

  • 2 for king

    • one for king moves
    • one for all spaces opponent can move

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

Pawns

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

Knights

  • use mask for knights span of attack
  • shift bits of mask to wherever the knight is positioned
  • shift differs depending on where knight is positioned (if-else)

    • 18 knightSpan << (knightPos - 18)

    • <=18 knightSpan >> (18 - knightPos)
  • bits will wrap in shift, so columns must be cleared in order to prevent invalid moves
    • knightPos % 8 < 4 then !files_GH
    • knightPos % 8 >= 4 then !files_AB
  • shift is 18 because mask is created from knight placed on 18th square

Kings

  • similar to knights except
    • kingPos > 9 kingSpan << (kingPos - 9)
    • kingPos <= 9 kingSpan >> (9 - kingPos)
  • retains same blanking to avoid invalid move creations from wrapping
  • shift is 9 because mask is created from king placed at 9th position
  • need to determine all unsafe position for king to move
    • bit board for all places opposing pieces can move to

Castling

  • maintain booleans for enabling/disabling castling

    • if king moves castling is disabled
    • if a rook moves castling is disabled in that direction

  • booleans must be passed to move generator to know if it should incl castling in move creation

  • king destinations: fileC (queen side) or fileG (king side)

  • rook destiniation: fileD (queen side) or fileF (king side)

  • Rules (taken from wikipedia: castling)

    • The king and the chosen rook are on the player's first rank.
    • Neither the king nor the chosen rook has previously moved.
    • There are no pieces between the king and the chosen rook.
    • The king is not currently in check.
    • The king does not pass through a square that is attacked by an enemy piece.
    • The king does not end up in check. (True of any legal move.)

Handling black and white movements

  • generalize functions to work on either white or black pieces by taking boards and variables as parameters
  • EXCEPTION: Pawns are direction dependent
    • be sure to clear proper files for attacks
    • be sure index +1 and -1 are assigned properly
Clone this wiki locally