home *** CD-ROM | disk | FTP | other *** search
/ Mac Easy 2010 May / Mac Life Ubuntu.iso / casper / filesystem.squashfs / usr / share / python-support / gnome-games-data / glchess / chess / board.py < prev    next >
Encoding:
Python Source  |  2009-04-14  |  41.7 KB  |  1,174 lines
  1. # -*- coding: utf-8 -*-
  2. """Module implementing the chess rules.
  3.  
  4. To use create an instance of the chess board:
  5. >>> b = board.ChessBoard()
  6.  
  7. Board locations can be represented in two forms:
  8. o A 2-tuple containing the file and rank as integers (see below).
  9. o A string with the location in SAN format.
  10.  
  11. e.g. The black king is on the square (4,7) or 'e8'.
  12.  
  13. The chess board with rank and file numbers:
  14.  
  15.              Black Pieces
  16.  
  17.    +---+---+---+---+---+---+---+---+
  18. 7  |<R>|<N>|<B>|<Q>|<K>|<B>|<N>|<R>|
  19.    +---+---+---+---+---+---+---+---+
  20. 6  |<P>|<P>|<P>|<P>|<P>|<P>|<P>|<P>|
  21.    +---+---+---+---+---+---+---+---+
  22. 5  |   | . |   | . |   | . |   | . |
  23.    +---+---+---+---+---+---+---+---+
  24. 4  | . |   | . |   | . |   | . |   |
  25.    +---+---+---+---+---+---+---+---+
  26. 3  |   | . |   | . |   | . |   | . |
  27.    +---+---+---+---+---+---+---+---+
  28. 2  | . |   | . |   | . |   | . |   |
  29.    +---+---+---+---+---+---+---+---+
  30. 1  |-P-|-P-|-P-|-P-|-P-|-P-|-P-|-P-|
  31.    +---+---+---+---+---+---+---+---+
  32. 0  |-R-|-N-|-B-|-Q-|-K-|-B-|-N-|-R-|
  33.    +---+---+---+---+---+---+---+---+
  34.      0   1   2   3   4   5   6   7
  35.      
  36.              White Pieces
  37.              
  38. Pieces are moved by:
  39. >>> move = b.movePiece(board.WHITE, 'd1', 'd3')
  40. If the move is not None then the internal state is updated and the
  41. next player can move.
  42. If the result is None then the request is ignored.
  43.  
  44. A move can be checked if it is legal first by:
  45. >>> result = b.testMove(board.WHITE, 'd1', 'd3')
  46. The returns the same values as movePiece() except the internal state
  47. is never updated.
  48.  
  49. The location of pieces can be checked using:
  50. >>> piece = b.getPiece('e1')
  51. >>> pieces = b.getAlivePieces()
  52. >>> casualties = b.getDeadPieces()
  53. The locations are always in the 2-tuple format.
  54. These methods return references to the ChessPiece objects on the board.
  55.  
  56. The history of the game can be retrieved by passing a move number to
  57. the get*() methods. This number is the move count from the game start.
  58. It also supports negative indexing:
  59. 0  = board before game starts
  60. 1  = board after white's first move
  61. 2  = board after black's first move
  62. -1 = The last move
  63. e.g.
  64. To get the white pieces after whites second move.
  65. >>> pieces = b.getAlivePieces(3)
  66.  
  67. The ChessPiece objects are static per board. Thus references can be compared
  68. between move 0 and move N. Note promoted pieces are a new piece object.
  69.  
  70. When any piece is moved onPieceMoved() method is called. If the ChessBoard
  71. class is extended this signal can be picked up by the user. If movePiece()
  72. or testMove() is called while in this method an exception is raised.
  73. """
  74.  
  75. __author__ = 'Robert Ancell <bob27@users.sourceforge.net>'
  76. __license__ = 'GNU General Public License Version 2'
  77. __copyright__ = 'Copyright 2005-2006  Robert Ancell'
  78.  
  79. __all__ = ['ChessPiece', 'ChessBoard', 'Move']
  80.  
  81. import bitboard
  82.  
  83. # The two players
  84. WHITE = 'White'
  85. BLACK = 'Black'
  86.  
  87. # The piece types
  88. PAWN   = 'P'
  89. ROOK   = 'R'
  90. KNIGHT = 'N'
  91. BISHOP = 'B'
  92. QUEEN  = 'Q'
  93. KING   = 'K'
  94.  
  95. class ChessPiece:
  96.     """An object representing a chess piece"""
  97.     
  98.     # The colour of the piece
  99.     __colour = None
  100.     
  101.     # The type of the piece (pawn, knight ...) 
  102.     __type = None
  103.     
  104.     def __init__(self, colour, type):
  105.         """Constructor for a chess piece.
  106.         
  107.         'colour' is the piece colour (WHITE or BLACK).
  108.         'type' is the piece type (PAWN, ROOK, KNIGHT, BISHOP, QUEEN or KING).
  109.         """
  110.         self.__colour = colour
  111.         self.__type = type
  112.         
  113.     def getColour(self):
  114.         """Get the colour of this piece.
  115.         
  116.         Returns WHITE or BLACK.
  117.         """
  118.         return self.__colour
  119.     
  120.     def getType(self):
  121.         """Get the type of this piece.
  122.         
  123.         Returns PAWN, ROOK, KNIGHT, BISHOP, QUEEN or KING.
  124.         """
  125.         return self.__type
  126.     
  127.     def __str__(self):
  128.         """Returns a string representation of this piece"""
  129.         return self.__colour + ' ' + self.__type
  130.     
  131.     def __repr__(self):
  132.         return '<%s>' % str(self)
  133.     
  134. class ChessPlayerState:
  135.     """
  136.     """
  137.     # Flags to show if still able to castle
  138.     canShortCastle = True
  139.     canLongCastle  = True
  140.     
  141.     # Flag to show if this player is in check
  142.     inCheck        = False
  143.     
  144.     def __init__(self, state = None):
  145.         """
  146.         """
  147.         if state is None:
  148.             return
  149.  
  150.         # Copy the exisiting state
  151.         self.canShortCastle = state.canShortCastle
  152.         self.canLongCastle = state.canLongCastle
  153.         
  154.     def __eq__(self, state):
  155.         """Compare two states are equal"""
  156.         if self.canShortCastle != state.canShortCastle:
  157.             return False
  158.         if self.canLongCastle != state.canLongCastle:
  159.             return False
  160.         return True
  161.     
  162.     def __ne__(self, state):
  163.         return not self == state
  164.  
  165. class Move:
  166.     """
  167.     """
  168.     # List of pieces that have moved
  169.     # (start, end, piece)
  170.     # state = None for new pieces
  171.     # end = None for taken pieces
  172.     moves  = []
  173.     
  174.     # The piece that was taken in this move or None if no victim
  175.     victim = None
  176.  
  177.     # Flag to show if the opponent is in check
  178.     opponentInCheck = False
  179.     
  180.     # Flag to show if the opponent can move
  181.     opponentCanMove = False
  182.     
  183.     # Flag to show if this move has caused a three-fold repetition
  184.     threeFoldRepetition = False
  185.     
  186.     # Flag to show if this is the fiftith move in a row
  187.     # without a pawn being moved or a piece taken
  188.     fiftyMoveRule = False
  189.  
  190. class ChessBoardState:
  191.     """
  192.     """    
  193.     # The move number 
  194.     moveNumber      = 0
  195.     
  196.     # A dictionary of piece by location
  197.     squares         = None
  198.     
  199.     # The dead pieces in the order they were killed
  200.     casualties      = None
  201.     
  202.     # The move that got us to this state
  203.     lastMove        = None
  204.     
  205.     # Pieces moved that got us to this state
  206.     moves           = None
  207.  
  208.     # If the last move was a pawn march the location where it can be taken by en-passant
  209.     enPassantSquare = None
  210.  
  211.     # The state of the players
  212.     whiteState      = None
  213.     blackState      = None
  214.     
  215.     # Counter of the number of moves taken made where no pawn has moved
  216.     # and no piece has been taken
  217.     fiftyMoveCount  = 0
  218.     
  219.     # Flag to show if the previous move has caused a three fold repition
  220.     threeFoldRepetition = False
  221.  
  222.     # Bitboards
  223.     whiteBitBoard = 0
  224.     blackBitBoard = 0
  225.     allBitBoard   = 0
  226.  
  227.     def __init__(self, lastState = None):
  228.         """Constuctor for storing the state of a chess board.
  229.         
  230.         'lastState' is the previous board state
  231.                     or a dictionary containing the initial state of the board
  232.                     or None to start an empty board.
  233.  
  234.         Example:
  235.             
  236.         pawn = ChessPiece(WHITE, PAWN)
  237.         ChessBoardState({'a2': pawn, ...})
  238.         
  239.         Note if a dictionary is provided the casualties will only record the pieces
  240.         killed from this point onwards.
  241.         """
  242.         # Start empty
  243.         if lastState is None:
  244.             self.whiteBitBoard = 0
  245.             self.blackBitBoard = 0
  246.             self.allBitBoard = 0
  247.             self.moveNumber = 0
  248.             self.squares = {}
  249.             self.casualties = []
  250.             self.moves = []
  251.             self.whiteState = ChessPlayerState()
  252.             self.blackState = ChessPlayerState()
  253.             
  254.         # Use provided initial pieces
  255.         elif type(lastState) is dict:
  256.             self.moveNumber = 0
  257.             self.squares = {}
  258.             self.casualties = []
  259.             self.moves = []            
  260.             self.whiteBitBoard = 0
  261.             self.blackBitBoard = 0
  262.             self.allBitBoard = 0
  263.             for coord, piece in lastState.iteritems():
  264.                 self.squares[coord] = piece
  265.                 field = bitboard.LOCATIONS[bitboard.getIndex(coord)]
  266.                 if piece.getColour() is WHITE:
  267.                     self.whiteBitBoard |= field
  268.                 else:
  269.                     self.blackBitBoard |= field
  270.                 self.allBitBoard |= field
  271.  
  272.             self.whiteState = ChessPlayerState()
  273.             self.blackState = ChessPlayerState()
  274.  
  275.         # Copy exisiting state
  276.         elif isinstance(lastState, ChessBoardState):
  277.             self.whiteBitBoard = lastState.whiteBitBoard
  278.             self.blackBitBoard = lastState.blackBitBoard
  279.             self.allBitBoard = lastState.allBitBoard
  280.             self.moveNumber = lastState.moveNumber + 1
  281.             self.squares = lastState.squares.copy()
  282.             self.casualties = lastState.casualties[:]
  283.             self.lastMove = lastState.lastMove
  284.             self.moves = lastState.moves[:]
  285.             self.enPassantSquare = lastState.enPassantSquare
  286.             self.whiteState = ChessPlayerState(lastState.whiteState)
  287.             self.blackState = ChessPlayerState(lastState.blackState)
  288.             self.fiftyMoveCount = lastState.fiftyMoveCount
  289.  
  290.         else:
  291.             raise TypeError('ChessBoardState(oldState) or ChessBoardState({(0,0):pawn, ...})')
  292.         
  293.     def addPiece(self, location, colour, pieceType):
  294.         # Create the piece
  295.         piece = ChessPiece(colour, pieceType)
  296.  
  297.         # Put the piece in it's initial location
  298.         assert(self.squares.has_key(location) is False)
  299.         assert(type(location) == str)
  300.         self.squares[location] = piece
  301.         
  302.         # Update the bitboards
  303.         field = bitboard.LOCATIONS[bitboard.getIndex(location)]
  304.         if colour is WHITE:
  305.             self.whiteBitBoard |= field
  306.         else:
  307.             self.blackBitBoard |= field
  308.         self.allBitBoard |= field
  309.  
  310.         return piece
  311.  
  312.     def getPiece(self, location):
  313.         """Get the piece at a given location.
  314.         
  315.         'location' is the location in algebraic format (string).
  316.         
  317.         Return the piece at this location or None if there is no piece there.
  318.         """
  319.         assert(type(location) is str and len(location) == 2)
  320.         try:
  321.             return self.squares[location]
  322.         except KeyError:
  323.             return None
  324.     
  325.     def inCheck(self, colour):
  326.         """Test if the player with the given colour is in check.
  327.         
  328.         'colour' is the colour of the player to check.
  329.         
  330.         Return True if they are in check (or checkmate) or False otherwise.
  331.         """
  332.         # Find the location of this players king(s)
  333.         for kingCoord, king in self.squares.iteritems():
  334.             # Not our king
  335.             if king.getType() != KING or king.getColour() != colour:
  336.                 continue
  337.             if self.squareUnderAttack(colour, kingCoord):
  338.                 return True
  339.  
  340.         return False
  341.     
  342.     def squareUnderAttack(self, colour, location, requirePiece = True):
  343.         """Check if a square is under attack according to FIDE chess rules (Article 3.1)
  344.         
  345.         'colour' is the colour considered to own this square.
  346.         'location' is the location to check.
  347.         'requirePiece' if True only considers this square under attack if there is a piece in it.
  348.         
  349.         Return True if there is an enemy piece that can attach this square.
  350.         """
  351.         if requirePiece and self.getPiece(location) is None:
  352.             return False
  353.         
  354.         # See if any enemy pieces can take this king
  355.         for enemyCoord, enemyPiece in self.squares.iteritems():
  356.             # Ignore friendly pieces
  357.             if enemyPiece.getColour() == colour:
  358.                 continue
  359.  
  360.             # See if this piece can take
  361.             board = ChessBoardState(self)
  362.             if board.movePiece(enemyPiece.getColour(), enemyCoord, location, testCheck = False, applyMove = False):
  363.                 return True
  364.             
  365.         return False
  366.  
  367.     def canMove(self, colour):
  368.         """Test if the player with the given colour is in checkmate.
  369.         
  370.         'colour' is the colour of the player to check.
  371.         
  372.         Return True if they are in checkmate or False otherwise.
  373.         """
  374.         # If can move any of their pieces then not in checkmate
  375.         for coord, piece in self.squares.iteritems():
  376.             # Only check pieces of the given colour
  377.             if piece.getColour() != colour:
  378.                 continue
  379.  
  380.             # See if this piece can be moved anywhere
  381.             for rank in 'abcdefgh':
  382.                 for file in '12345678':
  383.                     board = ChessBoardState(self)
  384.                     if board.movePiece(colour, coord, rank + file, applyMove = False):
  385.                         return True
  386.  
  387.         return False
  388.     
  389.     def _getSquareColour(self, coord):
  390.         return {'a8': WHITE, 'b8': BLACK, 'c8': WHITE, 'd8': BLACK, 'e8': WHITE, 'f8': BLACK, 'g8': WHITE, 'h8': BLACK,
  391.                 'a7': BLACK, 'b7': WHITE, 'c7': BLACK, 'd7': WHITE, 'e7': BLACK, 'f7': WHITE, 'g7': BLACK, 'h7': WHITE,
  392.                 'a6': WHITE, 'b6': BLACK, 'c6': WHITE, 'd6': BLACK, 'e6': WHITE, 'f6': BLACK, 'g6': WHITE, 'h6': BLACK,
  393.                 'a5': BLACK, 'b5': WHITE, 'c5': BLACK, 'd5': WHITE, 'e5': BLACK, 'f5': WHITE, 'g5': BLACK, 'h5': WHITE,
  394.                 'a4': WHITE, 'b4': BLACK, 'c4': WHITE, 'd4': BLACK, 'e4': WHITE, 'f4': BLACK, 'g4': WHITE, 'h4': BLACK,
  395.                 'a3': BLACK, 'b3': WHITE, 'c3': BLACK, 'd3': WHITE, 'e3': BLACK, 'f3': WHITE, 'g3': BLACK, 'h3': WHITE,
  396.                 'a2': WHITE, 'b2': BLACK, 'c2': WHITE, 'd2': BLACK, 'e2': WHITE, 'f2': BLACK, 'g2': WHITE, 'h2': BLACK,
  397.                 'a1': BLACK, 'b1': WHITE, 'c1': BLACK, 'd1': WHITE, 'e1': BLACK, 'f1': WHITE, 'g1': BLACK, 'h1': WHITE}[coord]
  398.  
  399.     def sufficientMaterial(self):
  400.         """Test if there are sufficient pieces to be able to perform checkmate.
  401.         
  402.         Return True if sufficient pieces to make checkmate or False otherwise.
  403.         """
  404.         knightCount = 0
  405.         bishopCount = 0
  406.         for coord, piece in self.squares.iteritems():
  407.             pieceType = piece.getType()
  408.             
  409.             # Any pawns, rooks or queens can perform check
  410.             if pieceType == PAWN or pieceType == ROOK or pieceType == QUEEN:
  411.                 return True
  412.  
  413.             # Multiple knights can check
  414.             if pieceType == KNIGHT:
  415.                 knightCount += 1
  416.                 if knightCount > 1:
  417.                     return True
  418.  
  419.             # Bishops on different colours can check
  420.             if pieceType == BISHOP:
  421.                 bishopCount += 1 
  422.                 colour = self._getSquareColour(coord)
  423.                 if bishopCount > 1:
  424.                     if colour != bishopSquareColour:
  425.                         return True
  426.                 bishopSquareColour = colour
  427.  
  428.         return False
  429.         
  430.     allowedMoves = {WHITE: {PAWN:   bitboard.WHITE_PAWN_MOVES,
  431.                             ROOK:   bitboard.ROOK_MOVES,
  432.                             BISHOP: bitboard.BISHOP_MOVES,
  433.                             KNIGHT: bitboard.KNIGHT_MOVES,
  434.                             QUEEN:  bitboard.QUEEN_MOVES,
  435.                             KING:   bitboard.WHITE_KING_MOVES},
  436.                     BLACK: {PAWN:   bitboard.BLACK_PAWN_MOVES,
  437.                             ROOK:   bitboard.ROOK_MOVES,
  438.                             BISHOP: bitboard.BISHOP_MOVES,
  439.                             KNIGHT: bitboard.KNIGHT_MOVES,
  440.                             QUEEN:  bitboard.QUEEN_MOVES,
  441.                             KING:   bitboard.BLACK_KING_MOVES}}
  442.     
  443.     def movePiece(self, colour, start, end, promotionType = QUEEN, testCheck = True, allowSuicide = False, applyMove = True):
  444.         """Move a piece.
  445.         
  446.         'colour' is the colour of the player moving.
  447.         'start' is a the location to move from in algebraic format (string).
  448.         'end' is a the location to move to in algebraic format (string).
  449.         'promotionType' is the type of piece to promote to if required.
  450.         'testCheck' is a flag to control if the opponent will be in check after this move.
  451.         'allowSuicide' if True means a move is considered valid even
  452.                        if it would put the moving player in check.
  453.         'applyMove' is a flag to control if the move is applied to the board (True) or just tested (False).
  454.         
  455.         Returns the pieces moved in the form (result, moves).
  456.         The moves are a list containing tuples of the form (piece, start, end). If a piece was removed
  457.         'end' is None. If the result is successful the pieces on the board are modified.
  458.         If the move is illegal None is returned.
  459.         """
  460.         assert(promotionType is not KING)
  461.         assert(type(start) is str and len(start) == 2)
  462.         assert(type(end) is str and len(end) == 2)
  463.  
  464.         # Get the piece to move
  465.         try:
  466.             piece = self.squares[start]
  467.         except KeyError:
  468.             return None
  469.         if piece.getColour() is not colour:
  470.             return None
  471.  
  472.         # BitBoard indexes
  473.         startIndex = bitboard.getIndex(start)
  474.         endIndex = bitboard.getIndex(end)
  475.         
  476.         # Check if this move is possible
  477.         field = self.allowedMoves[colour][piece.getType()]
  478.         if field[startIndex] & bitboard.LOCATIONS[endIndex] == 0:
  479.             return None
  480.             
  481.         # Check if there are any pieces between the two moves
  482.         # Note this only checks horizontal, vertical and diagonal moves so
  483.         # has no effect on the knights
  484.         if self.allBitBoard & bitboard.INBETWEEN_SQUARES[startIndex][endIndex]:
  485.             return None
  486.  
  487.         # Get the players
  488.         if colour is WHITE:
  489.             enemyColour = BLACK
  490.             playerState = self.whiteState
  491.         elif colour is BLACK:
  492.             enemyColour = WHITE
  493.             playerState = self.blackState
  494.         else:
  495.             assert(False)
  496.         
  497.         # Copy the player state before it is changed
  498.         originalPlayerState = ChessPlayerState(playerState)
  499.         
  500.         whiteBitBoard = self.whiteBitBoard
  501.         blackBitBoard = self.blackBitBoard
  502.         allBitBoard = self.allBitBoard
  503.  
  504.         # Check if moving onto another piece (must be enemy)
  505.         try:
  506.             target = self.squares[end]
  507.             if target.getColour() == colour:
  508.                 return None
  509.         except KeyError:
  510.             target = None
  511.         victim = target
  512.         
  513.         # Get the rank relative to this colour's start rank
  514.         if colour == BLACK:
  515.             baseFile = '8'
  516.         else:
  517.             baseFile = '1'
  518.             
  519.         # The new en-passant square
  520.         enPassantSquare = None
  521.         
  522.         # A list of pieces that have been moved
  523.         moves = []
  524.         
  525.         # Check move is valid:
  526.  
  527.         # King can move one square or castle
  528.         if piece.getType() is KING:
  529.             # Castling:
  530.             shortCastle = ('e' + baseFile, 'g' + baseFile)
  531.             longCastle  = ('e' + baseFile, 'c' + baseFile)
  532.             if (start, end) == shortCastle or (start, end) == longCastle:
  533.                 # Cannot castle out of check
  534.                 if self.inCheck(colour):
  535.                     return None
  536.  
  537.                 # Cannot castle if required pieces have moved
  538.                 if end[0] == 'c':
  539.                     if not playerState.canLongCastle:
  540.                         return None
  541.                     rookLocation = 'a' + baseFile
  542.                     rookEndLocation = 'd' + baseFile
  543.                 else:
  544.                     if not playerState.canShortCastle:
  545.                         return None
  546.                     rookLocation = 'h' + baseFile
  547.                     rookEndLocation = 'f' + baseFile
  548.  
  549.                 # Check rook is still there
  550.                 try:
  551.                     rook = self.squares[rookLocation]
  552.                 except KeyError:
  553.                     return None
  554.                 if rook is None or rook.getType() is not ROOK or rook.getColour() != piece.getColour():
  555.                     return None
  556.  
  557.                 # Check no pieces between the rook and king
  558.                 a = bitboard.getIndex(rookLocation)
  559.                 b = bitboard.getIndex(rookEndLocation)
  560.                 if self.allBitBoard & bitboard.INBETWEEN_SQUARES[a][b]:
  561.                     return None
  562.                 
  563.                 # The square the king moves over cannot be attackable
  564.                 if self.movePiece(colour, start, rookEndLocation, applyMove = False) is None:
  565.                     return None
  566.  
  567.                 # Rook moves with the king
  568.                 moves.append((rook, rookLocation, rookEndLocation, False))
  569.  
  570.             # Can no longer castle once the king is moved
  571.             playerState.canShortCastle = False
  572.             playerState.canLongCastle = False
  573.             
  574.             moves.append((piece, start, end, False))
  575.  
  576.         # Rooks move orthogonal
  577.         elif piece.getType() is ROOK:
  578.             # Can no longer castle once have move the required rook
  579.             if start == 'a' + baseFile:
  580.                 playerState.canLongCastle = False
  581.             elif start == 'h' + baseFile:
  582.                 playerState.canShortCastle = False
  583.             moves.append((piece, start, end, False))
  584.  
  585.         # On base rank pawns move on or two squares forwards.
  586.         # Pawns take other pieces diagonally (1 square).
  587.         # Pawns can take other pawns moving two ranks using 'en passant'.
  588.         # Pawns are promoted on reaching the other side of the board.
  589.         elif piece.getType() is PAWN:
  590.             # Calculate the files that pawns start on and move over on marches
  591.             if baseFile == '1':
  592.                 pawnFile  = '2'
  593.                 marchFile = '3'
  594.                 farFile   = '8'
  595.             else:
  596.                 pawnFile  = '7'
  597.                 marchFile = '6'
  598.                 farFile   = '1'
  599.                 
  600.             # When marching the square that is moved over can be taken by en-passant
  601.             if (start[1] == '2' and end[1] == '4') or (start[1] == '7' and end[1] == '5'):
  602.                 enPassantSquare = start[0] + marchFile
  603.     
  604.             # Can only take when moving diagonally
  605.             if start[0] != end[0]:
  606.                 # FIXME: Set victim
  607.                 # We either need a victim or be attacking the en-passant square
  608.                 if victim is None:
  609.                     if end != self.enPassantSquare:
  610.                         return None
  611.                     
  612.                     # Kill the pawn that moved
  613.                     moves.append((self.lastMove[0], self.lastMove[2], self.lastMove[2], True))
  614.             elif victim is not None:
  615.                 return None
  616.             
  617.             # Promote pawns when they hit the far rank
  618.             if end[1] == farFile:
  619.                 # Delete the current piece and create a new piece
  620.                 moves.append((piece, start, end, True))
  621.                 moves.append((ChessPiece(colour, promotionType), None, end, False))
  622.             else:
  623.                 moves.append((piece, start, end, False))
  624.  
  625.         # Other pieces are well behaved
  626.         else:
  627.             moves.append((piece, start, end, False))
  628.  
  629.         # Store this move
  630.         oldLastMove = self.lastMove
  631.         self.lastMove = (piece, start, end)
  632.         oldEnPassantSquare = self.enPassantSquare
  633.         self.enPassantSquare = enPassantSquare
  634.  
  635.         # Delete a victim
  636.         if victim is not None:
  637.             moves.append((victim, end, end, True))
  638.             
  639.         # Move the pieces:
  640.  
  641.         # Remove the moving pieces from the board
  642.         for (p, s, e, d) in moves:
  643.             if s is None:
  644.                 continue
  645.             self.squares.pop(s)
  646.             
  647.             field = bitboard.LOCATIONS[bitboard.getIndex(s)]
  648.             self.whiteBitBoard &= ~field
  649.             self.blackBitBoard &= ~field
  650.             self.allBitBoard &= ~field
  651.                 
  652.         # Put pieces in their new locations
  653.         for (p, s, e, d) in moves:
  654.             if d:
  655.                 continue
  656.             self.squares[e] = p
  657.  
  658.             field = bitboard.LOCATIONS[bitboard.getIndex(e)]
  659.             if p.getColour() is WHITE:
  660.                 self.whiteBitBoard |= field
  661.             else:
  662.                 self.blackBitBoard |= field
  663.             self.allBitBoard |= field
  664.  
  665.         # Test for check and checkmate
  666.         result = moves
  667.         if testCheck:
  668.             # Cannot move into check, if would be then undo move
  669.             if self.inCheck(colour):
  670.                 applyMove = False
  671.                 result = None
  672.  
  673.         # Undo the moves if only a test
  674.         if applyMove is False:
  675.             # Empty any squares moved into
  676.             for (p, s, e, d) in moves:
  677.                 if not d:
  678.                     self.squares.pop(e)
  679.                         
  680.             # Put pieces back into their original locatons
  681.             for (p, s, e, d) in moves:
  682.                 if s is not None:
  683.                     self.squares[s] = p
  684.  
  685.             # Undo player state
  686.             if colour == WHITE:
  687.                 self.whiteState = originalPlayerState
  688.             else:
  689.                 self.blackState = originalPlayerState
  690.             
  691.             # Undo stored move and en-passant location
  692.             self.lastMove = oldLastMove
  693.             self.enPassantSquare = oldEnPassantSquare
  694.  
  695.             # Revert bitboards
  696.             self.whiteBitBoard = whiteBitBoard
  697.             self.blackBitBoard = blackBitBoard
  698.             self.allBitBoard = allBitBoard
  699.             
  700.         else:
  701.             self.moves = result
  702.             
  703.             # Remember the casualties
  704.             if victim is not None:
  705.                 self.casualties.append(victim)
  706.  
  707.             # If a piece taken or a pawn moved 50 move count is reset
  708.             if victim is not None or piece.getType() is PAWN:
  709.                 self.fiftyMoveCount = 0
  710.             else:
  711.                 self.fiftyMoveCount += 1
  712.                 
  713.         return result
  714.  
  715.     def __eq__(self, board):
  716.         """Compare if two boards are the same"""
  717.         if len(self.squares) != len(board.squares):
  718.             return False
  719.  
  720.         if self.enPassantSquare != board.enPassantSquare:
  721.             return False
  722.         if self.whiteState != board.whiteState or self.blackState != board.blackState:
  723.             return False
  724.         
  725.         for (coord, piece) in self.squares.iteritems():
  726.             try:
  727.                 p = board.squares[coord]
  728.             except KeyError:
  729.                 return False
  730.             if piece.getType() is not p.getType() or piece.getColour() is not p.getColour():
  731.                 return False
  732.             
  733.         return True
  734.     
  735.     def __ne__(self, board):
  736.         return not self == board
  737.         
  738.     def __str__(self):
  739.         """Covert the board state to a string"""
  740.         out = ''
  741.         blackSquare = False
  742.         for file in '87654321':
  743.             out += '       +---+---+---+---+---+---+---+---+\n'
  744.             out += '    ' + file + '  |'
  745.             blackSquare = not blackSquare
  746.             
  747.             for rank in 'abcdefgh':
  748.                 blackSquare = not blackSquare
  749.                 try:
  750.                     piece = self.squares[rank + file]
  751.                 except:
  752.                     piece = None
  753.                 if piece is None:
  754.                     # Checkerboard
  755.                     if blackSquare:
  756.                         out += ' . '
  757.                     else:
  758.                         out += '   '
  759.                 else:
  760.                     s = piece.getType()
  761.                     if piece.getColour() is WHITE:
  762.                         s = '-' + s + '-'
  763.                     elif piece.getColour() is BLACK:
  764.                         s = '<' + s + '>'
  765.                     else:
  766.                         assert(False)
  767.                     out += s
  768.                 
  769.                 out += '|'
  770.         
  771.             out += '\n'
  772.         
  773.         out += "       +---+---+---+---+---+---+---+---+\n"
  774.         out += "         a   b   c   d   e   f   g   h"
  775.         
  776.         return out
  777.  
  778. class ChessBoard:
  779.     """An object representing a chess board.
  780.     
  781.     This class contains a chess board and all its previous states.
  782.     """
  783.     def __init__(self, initialState = None):
  784.         """Constructor for a chess board"""
  785.         self.__inCallback = False
  786.         if initialState is None:
  787.             self.__resetBoard()
  788.         else:
  789.             self.__boardStates = [initialState]
  790.         
  791.     def onPieceMoved(self, piece, start, end, delete):
  792.         """Called when a piece is moved on the chess board.
  793.         
  794.         'piece' is the piece being moved.
  795.         'start' is the start location of the piece (tuple (file,rank) or None if the piece is being created.
  796.         'end' is the end location of the piece (tuple (file,rank))
  797.         'delete' is a flag to show if the piece should be deleted when it arrives there (boolean).
  798.         """
  799.         pass
  800.  
  801.     # Public methods
  802.  
  803.     def getPiece(self, location, moveNumber = -1):
  804.         """Get the piece at a given location.
  805.         
  806.         'location' is the board location to check in algebraic format (string).
  807.         'moveNumber' is the move to get the pieces from (integer).
  808.         
  809.         Return the piece (ChessPiece) at this location or None if there is no piece there.
  810.         Raises an IndexError exception if moveNumber is invalid.
  811.         """
  812.         return self.__boardStates[moveNumber].getPiece(location)
  813.     
  814.     def getAlivePieces(self, moveNumber = -1):
  815.         """Get the alive pieces on the board.
  816.         
  817.         'moveNumber' is the move to get the pieces from (integer).
  818.         
  819.         Returns a dictionary of the alive pieces (ChessPiece) keyed by location.
  820.         Raises an IndexError exception if moveNumber is invalid.
  821.         """
  822.         state = self.__boardStates[moveNumber]
  823.         return state.squares.copy()
  824.     
  825.     def getDeadPieces(self, moveNumber = -1):
  826.         """Get the dead pieces from the game.
  827.         
  828.         'moveNumber' is the move to get the pieces from (integer).
  829.         
  830.         Returns a list of the pieces (ChessPiece) in the order they were killed.
  831.         Raises an IndexError exception if moveNumber is invalid.
  832.         """
  833.         state = self.__boardStates[moveNumber]
  834.         return state.casualties[:]
  835.  
  836.     def testMove(self, colour, start, end, promotionType = QUEEN, allowSuicide = False, moveNumber = -1):
  837.         """Test if a move is allowed.
  838.         
  839.         'colour' is the colour of the player moving.
  840.         'start' is a the location to move from in algebraic format (string).
  841.         'end' is a the location to move to in algebraic format (string).
  842.         'allowSuicide' if True means a move is considered valid even
  843.                        if it would put the moving player in check. This is
  844.                        provided for SAN move calculation.
  845.         
  846.         Returns the same as movePiece() except the move is not recorded.
  847.         """
  848.         return self.movePiece(colour, start, end, promotionType = promotionType, allowSuicide = allowSuicide, test = True, moveNumber = moveNumber)
  849.     
  850.     def squareUnderAttack(self, colour, location, moveNumber = -1):
  851.         state = self.__boardStates[moveNumber]
  852.         return state.squareUnderAttack(colour, location)
  853.     
  854.     def sufficientMaterial(self, moveNumber = -1):
  855.         """Test if there are sufficient pieces to be able to perform checkmate.
  856.         
  857.         Return True if sufficient pieces to make checkmate or False otherwise.
  858.         """
  859.         state = self.__boardStates[moveNumber]
  860.         return state.sufficientMaterial()
  861.  
  862.     def movePiece(self, colour, start, end, promotionType = QUEEN, allowSuicide = False, test = False, moveNumber = -1):
  863.         """Move a piece.
  864.         
  865.         'colour' is the colour of the player moving.
  866.         'start' is a the location to move from in algebraic format (string).
  867.         'end' is a the location to move to in algebraic format (string).
  868.         'allowSuicide' if True means a move is considered valid even
  869.                        if it would put the moving player in check. This is
  870.                        provided for SAN move calculation.
  871.  
  872.         Return information about the move performed (Move) or None if the move is illegal.
  873.         """
  874.         assert(self.__inCallback is False)
  875.         
  876.         state = ChessBoardState(self.__boardStates[moveNumber])
  877.         if not state.movePiece(colour, start, end, promotionType = promotionType, allowSuicide = False):
  878.             return None
  879.  
  880.         victim = None
  881.         for (piece, start, end, delete) in state.moves:
  882.             # The victim is the enemy piece that has been deleted
  883.             if delete and piece.getColour() != colour:
  884.                 victim = piece
  885.             
  886.             # Notify the child class of the moves
  887.             if not test:
  888.                 self.__onPieceMoved(piece, start, end, delete)
  889.  
  890.         # Check if this board state has been repeated three times
  891.         sameCount = 0
  892.         for s in self.__boardStates:
  893.             if state == s:
  894.                 sameCount += 1
  895.                 if sameCount >= 2:
  896.                     state.threeFoldRepetition = True
  897.                     break
  898.                 
  899.         if colour is WHITE:
  900.             opponentColour = BLACK
  901.         else:
  902.             opponentColour = WHITE
  903.  
  904.         # Push the board state
  905.         if not test:
  906.             self.__boardStates.append(state)
  907.         move = Move()
  908.         move.moves = state.moves
  909.         move.victim = victim
  910.         move.opponentInCheck = state.inCheck(opponentColour)
  911.         move.opponentCanMove = state.canMove(opponentColour)
  912.         move.threeFoldRepetition = state.threeFoldRepetition
  913.         move.fiftyMoveRule = state.fiftyMoveCount >= 50
  914.         return move
  915.     
  916.     def undo(self):
  917.         """Undo the last move"""
  918.         undoState = self.__boardStates[-1]
  919.         self.__boardStates = self.__boardStates[:-1]
  920.  
  921.         # Undo the moves
  922.         for (piece, start, end, delete) in undoState.moves:
  923.             self.__onPieceMoved(piece, end, start, False)
  924.  
  925.     def __str__(self):
  926.         """Returns a representation of the current board state"""
  927.         return str(self.__boardStates[-1])
  928.     
  929.     # Private methods
  930.     
  931.     def __onPieceMoved(self, piece, start, end, delete):
  932.         """
  933.         """
  934.         self.__inCallback = True
  935.         self.onPieceMoved(piece, start, end, delete)
  936.         self.__inCallback = False
  937.     
  938.     def __addPiece(self, state, colour, pieceType, location):
  939.         """Add a piece into the board.
  940.         
  941.         'state' is the board state to add the piece into.
  942.         'colour' is the colour of the piece.
  943.         'pieceType' is the type of piece to add.
  944.         'location' is the start location of the piece in algebraic format (string).
  945.         """
  946.         piece = state.addPiece(location, colour, pieceType)
  947.         
  948.         # Notify a child class the piece creation
  949.         self.__onPieceMoved(piece, None, location, False)
  950.  
  951.     def __resetBoard(self):
  952.         """Set up the chess board.
  953.         
  954.         Any exisiting states are deleted.
  955.         The user will be notified of the piece deletions.
  956.         """
  957.         # Make the board
  958.         initialState = ChessBoardState()
  959.         self.__boardStates = [initialState]
  960.         
  961.         # Populate the board
  962.         secondRank = [('a', ROOK), ('b', KNIGHT), ('c', BISHOP), ('d', QUEEN),
  963.                       ('e', KING), ('f', BISHOP), ('g', KNIGHT), ('h', ROOK)]
  964.         for (rank, piece) in secondRank:
  965.             # Add a second rank and pawn for each piece
  966.             self.__addPiece(initialState, WHITE, piece, rank + '1')
  967.             self.__addPiece(initialState, WHITE, PAWN,  rank + '2')
  968.             self.__addPiece(initialState, BLACK, piece, rank + '8')
  969.             self.__addPiece(initialState, BLACK, PAWN,  rank + '7')
  970.  
  971. if __name__ == '__main__':
  972.     p = ChessPiece(WHITE, QUEEN)
  973.     print p
  974.     print repr(p)
  975.     
  976.     def test_moves(name, colour, start, whitePieces, blackPieces, validResults):
  977.         print name + ':'
  978.         board = {}
  979.         for coord, piece in whitePieces.iteritems():
  980.             board[coord] = ChessPiece(WHITE, piece)
  981.         for coord, piece in blackPieces.iteritems():
  982.             board[coord] = ChessPiece(BLACK, piece)
  983.         s = ChessBoardState(board)
  984.         resultMatrix = {}
  985.         for rank in 'abcdefgh':
  986.             for file in '12345678':
  987.                 end = rank + file
  988.                 try:
  989.                     expected = validResults[end]
  990.                 except:
  991.                     expected = None
  992.                 x = ChessBoardState(s)
  993.                 b = ChessBoard(x)
  994.                 move = b.movePiece(colour, start, end)
  995.                 resultMatrix[end] = move
  996.                 
  997.                 isAllowed = validResults.__contains__(end)
  998.                 if (move is None and isAllowed) or (move is not None and not isAllowed):
  999.                     print 'Unexpected result: ' + str(start) + '-' + str(end) # + ' is a ' + str(result) + ', should be ' + str(expected)
  1000.         
  1001.         out = ''
  1002.         for file in '87654321':
  1003.             out += '       +---+---+---+---+---+---+---+---+\n'
  1004.             out += '    ' + file + '  |'
  1005.             
  1006.             for rank in 'abcdefgh':
  1007.                 coord = rank + file
  1008.                 try:
  1009.                     move = resultMatrix[coord]
  1010.                 except:
  1011.                     p = 'X'
  1012.                 else:
  1013.                     if move is not None and move.opponentInCheck:
  1014.                         if move.opponentCanMove:
  1015.                             p = '+'
  1016.                         else:
  1017.                             p = '#'
  1018.                     else:
  1019.                         p = ' '
  1020.                     
  1021.                 piece = s.getPiece(rank + file)
  1022.                 if piece is not None:
  1023.                     p = piece.getType()
  1024.  
  1025.                 piece = s.getPiece(rank + file)
  1026.  
  1027.                 if piece is None:
  1028.                     box = ' ' + p + ' ' 
  1029.                 else:
  1030.                     if piece.getColour() is BLACK:
  1031.                         box = '=' + p + '='
  1032.                     elif piece.getColour() is WHITE:
  1033.                         box = '-' + p + '-'
  1034.                 
  1035.                 out += box + '|'
  1036.         
  1037.             out += '\n'
  1038.         
  1039.         out += "       +---+---+---+---+---+---+---+---+\n"
  1040.         out += "         a   b   c   d   e   f   g   h\n"
  1041.         print out
  1042.                     
  1043.     c = ChessBoard()
  1044.     
  1045.     result = """       +---+---+---+---+---+---+---+---+
  1046.     8  |<R>|<N>|<B>|<Q>|<K>|<B>|<N>|<R>|
  1047.        +---+---+---+---+---+---+---+---+
  1048.     7  |<P>|<P>|<P>|<P>|<P>|<P>|<P>|<P>|
  1049.        +---+---+---+---+---+---+---+---+
  1050.     6  |   | . |   | . |   | . |   | . |
  1051.        +---+---+---+---+---+---+---+---+
  1052.     5  | . |   | . |   | . |   | . |   |
  1053.        +---+---+---+---+---+---+---+---+
  1054.     4  |   | . |   | . |   | . |   | . |
  1055.        +---+---+---+---+---+---+---+---+
  1056.     3  | . |   | . |   | . |   | . |   |
  1057.        +---+---+---+---+---+---+---+---+
  1058.     2  |-P-|-P-|-P-|-P-|-P-|-P-|-P-|-P-|
  1059.        +---+---+---+---+---+---+---+---+
  1060.     1  |-R-|-N-|-B-|-Q-|-K-|-B-|-N-|-R-|
  1061.        +---+---+---+---+---+---+---+---+
  1062.          a   b   c   d   e   f   g   h"""
  1063.  
  1064.     if str(c) != result:
  1065.         print 'Got:'
  1066.         print str(c)
  1067.         
  1068.         print 
  1069.         print 'Expected:'
  1070.         print result
  1071.     print str(c)
  1072.  
  1073.     # Test pawn moves
  1074.     test_moves('Pawn', WHITE, 'e4', {'e4': PAWN}, {}, ['e5'])
  1075.     test_moves('Pawn on base rank', WHITE, 'e2', {'e2': PAWN}, {}, ['e3','e4'])
  1076.     
  1077.     # Test rook moves
  1078.     test_moves('Rook', WHITE, 'e4', {'e4': ROOK}, {},
  1079.                ['a4', 'b4', 'c4',
  1080.                 'd4', 'f4', 'g4',
  1081.                 'h4', 'e1', 'e2',
  1082.                 'e3', 'e5', 'e6',
  1083.                 'e7', 'e8'])
  1084.  
  1085.     # Test knight moves
  1086.     test_moves('Knight', WHITE, 'e4', {'e4': KNIGHT}, {},
  1087.                ['d6', 'f6', 'g5',
  1088.                 'g3', 'f2', 'd2',
  1089.                 'c3', 'c5'])
  1090.                
  1091.     # Test bishop moves
  1092.     test_moves('Bishop', WHITE, 'e4', {'e4': BISHOP}, {},
  1093.                ['a8', 'b7', 'c6',
  1094.                 'd5', 'f3', 'g2',
  1095.                 'h1', 'b1', 'c2',
  1096.                 'd3', 'f5', 'g6',
  1097.                 'h7'])
  1098.     
  1099.     # Test queen moves
  1100.     test_moves('Queen', WHITE, 'e4', {'e4': QUEEN}, {},
  1101.                ['a8', 'b7', 'c6',
  1102.                 'd5', 'f3', 'g2',
  1103.                 'h1', 'b1', 'c2',
  1104.                 'd3', 'f5', 'g6',
  1105.                 'h7', 'a4', 'b4',
  1106.                 'c4', 'd4', 'f4',
  1107.                 'g4', 'h4', 'e1',
  1108.                 'e2', 'e3', 'e5',
  1109.                 'e6', 'e7', 'e8'])
  1110.     
  1111.     # Test king moves
  1112.     test_moves('King', WHITE, 'e4', {'e4': KING}, {},
  1113.                ['d5', 'e5', 'f5',
  1114.                 'd4', 'f4', 'd3',
  1115.                 'e3', 'f3'])
  1116.                 
  1117.     # Test pieces blocking moves
  1118.     test_moves('Blocking', WHITE, 'd4',
  1119.                {'d4': QUEEN, 'e4': PAWN, 'd6': KNIGHT, 'd2': ROOK, 'f6': BISHOP, 'e3': BISHOP,
  1120.                 'b4':PAWN, 'b2': PAWN, 'a7': PAWN},
  1121.                {'d8': KNIGHT, 'c4': PAWN},
  1122.                ['b6', 'c5', 'd5',
  1123.                 'e5', 'c4', 'c3',
  1124.                 'd3'])
  1125.     
  1126.     # Test moving in/out of check
  1127.     test_moves('Moving into check', WHITE, 'e4', {'e4': KING}, {'e6': ROOK},
  1128.                ['d5', 'f5',
  1129.                 'd4', 'f4',
  1130.                 'd3', 'f3'])
  1131.     test_moves('Held in check', WHITE, 'e4', {'e4': KING}, {'f6': ROOK},
  1132.                ['d5', 'e5', 'd4',
  1133.                 'd3', 'e3'])
  1134.     
  1135.     # Test putting opponent in check
  1136.     test_moves('Putting opponent in check', WHITE, 'd3', {'d3': BISHOP}, {'d7': KING, 'd6': ROOK},
  1137.                ['a6', 'b5', 'c4',
  1138.                 'e2', 'f1', 'b1',
  1139.                 'c2', 'e4', 'f5',
  1140.                 'g6', 'h7']) # check=b5,f5
  1141.     
  1142.     # Test putting opponent into checkmate
  1143.     test_moves('Putting opponent into checkmate', WHITE, 'c1', {'c1': BISHOP, 'g1': ROOK, 'a7': ROOK}, {'h8': KING},
  1144.                ['b2', 'a3',
  1145.                 'd2', 'e3', 'f4',
  1146.                 'g5', 'h6']) # checkmate=b2
  1147.     #FIXME
  1148.                 
  1149.     # Test putting own player in check by putting oppononent in check (i.e. can't move)
  1150.     test_moves('Cannot put opponent in check if we would go into check',
  1151.                WHITE, 'd3', {'d2': KING, 'd3': BISHOP}, {'d7': KING, 'd6': ROOK}, [])
  1152.  
  1153.     # Test castling
  1154.     test_moves('Castle1', WHITE, 'e1', {'e1': KING, 'a1': ROOK}, {},
  1155.                ['d2', 'e2', 'f2',
  1156.                 'd1', 'f1', 'c1'])
  1157.     test_moves('Castle2', BLACK, 'e8', {}, {'e8': KING, 'h8': ROOK},
  1158.                ['d7', 'e7', 'f7',
  1159.                 'd8', 'f8', 'g8'])
  1160.     
  1161.     # Test castling while in check
  1162.     test_moves('Castle in check1', BLACK, 'e8', {'f1': ROOK}, {'e8': KING, 'h8': ROOK},
  1163.                ['d7', 'e7', 'd8'])
  1164.     test_moves('Castle in check2', BLACK, 'e8', {'e1': ROOK}, {'e8': KING, 'h8': ROOK},
  1165.                ['d7', 'd8',
  1166.                 'f7', 'f8'])
  1167.     test_moves('Castle in check3', BLACK, 'e8', {'h1': ROOK}, {'e8': KING, 'h8': ROOK},
  1168.                ['d7', 'e7', 'f7',
  1169.                 'd8', 'f8', 'g8'])
  1170.                
  1171.     # Test en-passant
  1172.     #FIXME
  1173.     
  1174.