ChessBoard.py

#/usr/bin/env python

#####################################################################
# ChessBoard v2.05 is created by John Eriksson - http://arainyday.se
# It's released under the Gnu Public Licence (GPL)
# Have fun!
#####################################################################

#####################################################################
# Michael and Dennis said that they did some optimizations on the
# code, so credit for that goes to them.
#####################################################################

from copy import deepcopy
from pprint import pprint
#import pygame

#MB 03/30: Promotion options already written in, just need to remove hard coding
#of Queen promotion value, maybe add a pop-up menu to select piece
class ChessBoard:


    # Color values
    WHITE = 0
    BLACK = 1
    NOCOLOR = -1

    #for scoring purposes
    SWHITE = 1
    SBLACK = -1
    SNOCOLOR = 0

    # Promotion values
    QUEEN = 1
    ROOK = 2
    KNIGHT = 3
    BISHOP = 4

    # Reason values
    INVALID_MOVE = 1
    INVALID_COLOR = 2
    INVALID_FROM_LOCATION = 3
    INVALID_TO_LOCATION = 4
    MUST_SET_PROMOTION = 5
    GAME_IS_OVER = 6
    AMBIGUOUS_MOVE = 7

    # Result values
    NO_RESULT = 0
    WHITE_WIN = 1
    BLACK_WIN = 2
    STALEMATE = 3
    FIFTY_MOVES_RULE = 4
    THREE_REPETITION_RULE = 5

    # Special moves
    NORMAL_MOVE = 0
    EP_MOVE = 1
    EP_CAPTURE_MOVE = 2
    PROMOTION_MOVE = 3
    KING_CASTLE_MOVE = 4
    QUEEN_CASTLE_MOVE = 5

    # Text move output type
    AN = 0      # g4-e3
    SAN = 1     # Bxe3
    LAN = 2     # Bg4xe3

    _game_result = 0
    _reason = 0

    # States
    _turn = WHITE
    _white_king_castle = True
    _white_queen_castle = True
    _black_king_castle = True
    _black_queen_castle = True
    _board = None
    _ep = [0,0]      #none or the location of the current en passant pawn
    _fifty = 0

    _black_king_location = (0,0)
    _white_king_location = (0,0)

    # three rep stack
    _three_rep_stack = []

    # full state stack
    _state_stack = []
    _state_stack_pointer = 0

    # all moves, stored to make it easier to build textmoves
    #[piece,from,to,takes,promotion,check/checkmate,specialmove]
    #["KQRNBP",(fx,fy),(tx,ty),True/False,"QRNB"/None,"+#"/None,0-5]
    _cur_move = [None,None,None,False,None,None,0]
    _moves = []

    _promotion_value = 0

    def __init__(self):
        self.resetBoard()
        #self.posRect = pygame.Rect(0,0,60,60)
        self.mousePos = [-1,-1]
        self.markPos = [-1,-1]
        self.validMoves = []
        self.nodesSearched = 0
        self.moveNumber = 0
        self.w_king_x = 4
        self.w_king_y = 7
        self.w_king_diag_1 = [(3,6),(2,5),(1,4),(0,3)]
        self.w_king_diag_2 = [(5,6),(6,5),(7,4)]
        self.b_king_x = 4
        self.b_king_y = 0
        self.b_king_diag_1 = [(5,1),(6,2),(7,3)]
        self.b_king_diag_2 = [(3,1),(2,2),(1,3),(0,4)]

    def state2str(self):

        b = ""
        for l in self._board:
            b += "%s%s%s%s%s%s%s%s" % (l[0],l[1],l[2],l[3],l[4],l[5],l[6],l[7])

        d = (b,
        self._turn,
        self._white_king_castle,
        self._white_queen_castle,
        self._black_king_castle,
        self._black_queen_castle,
        self._ep[0],
        self._ep[1],
        self._game_result,
        self._fifty)

        #turn,wkc,wqc,bkc,bqc,epx,epy,game_result,fifty
        s = "%s%d%d%d%d%d%d%d%d:%d" % d

        return s

    def loadCurState(self):
        s = self._state_stack[self._state_stack_pointer-1]
        b= s[:64]
        v = s[64:72]
        f =  int(s[73:])

        idx = 0
        for r in range(8):
            for c in range(8):
                self._board[r][c]=b[idx]
                idx+=1

        self._turn                  = int(v[0])
        self._white_king_castle     = int(v[1])
        self._white_queen_castle    = int(v[2])
        self._black_king_castle     = int(v[3])
        self._black_queen_castle    = int(v[4])
        self._ep[0]                 = int(v[5])
        self._ep[1]                 = int(v[6])
        self._game_result           = int(v[7])

        self._fifty = f

    def pushState(self):

        if self._state_stack_pointer != len(self._state_stack):
            self._state_stack = self._state_stack[:self._state_stack_pointer]
            self._three_rep_stack =  self._three_rep_stack[:self._state_stack_pointer]
            self._moves = self._moves[:self._state_stack_pointer-1]

        three_state = [self._white_king_castle,
            self._white_queen_castle,
            self._black_king_castle,
            self._black_queen_castle,
            deepcopy(self._board),
            #changed from deepcopy to list copy
            list(self._ep)]
        self._three_rep_stack.append(three_state)

        state_str = self.state2str()
        self._state_stack.append(state_str)

        self._state_stack_pointer = len(self._state_stack)

    def pushMove(self):
        #changed from deep copy to normal copy for this list.
        self._moves.append(list(self._cur_move))

    def threeRepetitions(self):

        ts = self._three_rep_stack[:self._state_stack_pointer+1] #added a plus one here without much of a reason

        if not len(ts):
            return False

        last = ts[len(ts)-1]
        if(ts.count(last) == 3):
            return True
        return False

    def updateKingLocations(self):
        for y in range(0,8):
            for x in range(0,8):
                if self._board[y][x] == "K":
                    self._white_king_location = (x,y)
                if self._board[y][x] == "k":
                    self._black_king_location = (x,y)

    def updateKingLines(self,king_pos):
        if self._turn == self.WHITE:
            self.w_king_x = king_pos[0]
            self.w_king_y = king_pos[1]
            self.w_king_diag_1 = []
            self.w_king_diag_2 = []
            for i in range(1,8): #loop through squares that are diagonal to king
                self.w_king_diag_1.append( (self.w_king_x+i,self.w_king_y+i) )
                self.w_king_diag_1.append( (self.w_king_x-i,self.w_king_y-i) )
                self.w_king_diag_2.append( (self.w_king_x+i,self.w_king_y-i) )
                self.w_king_diag_2.append( (self.w_king_x-i,self.w_king_y+i) )
        else:
            self.b_king_x = king_pos[0]
            self.b_king_y = king_pos[1]
            self.b_king_diag_1 = []
            self.b_king_diag_2 = []
            for i in range(1,8): #loop through squares that are diagonal to king
                self.b_king_diag_1.append( (self.b_king_x+i,self.b_king_y+i) )
                self.b_king_diag_1.append( (self.b_king_x-i,self.b_king_y-i) )
                self.b_king_diag_2.append( (self.b_king_x+i,self.b_king_y-i) )
                self.b_king_diag_2.append( (self.b_king_x-i,self.b_king_y+i) )

    def setEP(self,epPos):
        self._ep[0], self._ep[1] = epPos

    def clearEP(self):
        self._ep[0] = 0
        self._ep[1] = 0


    def endGame(self, reason):
        self._game_result = reason

    def sameLineAsKing(self,piece_pos):
        """returns whether there is a straight line between a piece and the king."""
        px,py = piece_pos
        if self._turn == self.WHITE:
            if px == self.w_king_x or py == self.w_king_y:
                return True
            if piece_pos in self.w_king_diag_1 or piece_pos in self.w_king_diag_2:
                return True
        else:
            if px == self.b_king_x or py == self.b_king_y:
                return True
            if piece_pos in self.b_king_diag_1 or piece_pos in self.b_king_diag_2:
                return True
        return False

    def checkKingGuard(self,fromPos,moves,specialMoves={}):
        result = []
        if self._turn == self.WHITE:
            kx,ky = self._white_king_location
        else:
            kx,ky = self._black_king_location
        fx,fy = fromPos

        if self.sameLineAsKing(fromPos): #must be in same line as king to be protecting him
            done = False
            fp = self._board[fy][fx]
            self._board[fy][fx] = "." #check if my piece protects king before moving
            if not self.isThreatened(kx,ky):
                done = True
            self._board[fy][fx] = fp

            if done:
                return moves

        for m in moves:
            tx,ty = m
            sp = None
            fp = self._board[fy][fx]
            tp = self._board[ty][tx]

            self._board[fy][fx] = "."
            self._board[ty][tx] = fp

            if specialMoves.has_key(m) and specialMoves[m] == self.EP_CAPTURE_MOVE:
                sp = self._board[self._ep[1]][self._ep[0]]
                self._board[self._ep[1]][self._ep[0]] = "."

            if not self.isThreatened(kx,ky): #check if my piece protects king after moving
                    result.append(m)

            if sp:
                self._board[self._ep[1]][self._ep[0]] = sp

            self._board[fy][fx] = fp
            self._board[ty][tx] = tp

        return result

    def isFree(self,x,y):
        return self._board[y][x] == '.'

    def getColorS(self,x,y):
        """get color for scoring"""
        if self._board[y][x] == '.':
            return self.SNOCOLOR
        elif self._board[y][x].isupper():
            return self.SWHITE
        elif self._board[y][x].islower():
            return self.SBLACK

#    def getColor(self,x,y):
#        if self._board[y][x] == '.':
#            return self.NOCOLOR
#        elif self._board[y][x].isupper():
#            return self.WHITE
#        elif self._board[y][x].islower():
#            return self.BLACK
#
#
    def getColor(self,x,y):
        color = self._board[y][x]
        if 'A'<= color <='Z':
            return self.WHITE
        elif 'a'<= color <='z':
            return self.BLACK
        else:
            return self.NOCOLOR

    def isThreatened(self,lx,ly,player=None):

        if player == None:
            player = self._turn

        dirs = [(1,0),(-1,0),(0,1),(0,-1),(1,1),(-1,1),(1,-1),(-1,-1)]
        for d in dirs:
            x = lx
            y = ly
            dx,dy = d
            steps = 0
            while True:
                steps+=1
                x+=dx
                y+=dy
                if x<0 or x>7 or y<0 or y>7:
                    break
                if self.isFree(x,y):
                    continue
                elif self.getColor(x,y)==player:
                    break
                else:
                    p = self._board[y][x].upper()
                    if p == 'K' and steps == 1:
                        return True
                    elif p == 'Q':
                        return True
                    elif p == 'R' and abs(dx) != abs(dy):
                        return True
                    elif p == 'B' and abs(dx) == abs(dy):
                        return True
                    break

        m =[(lx+1,ly+2),(lx+2,ly+1),(lx+2,ly-1),(lx+1,ly-2),(lx-1,ly+2),(lx-2,ly+1),(lx-1,ly-2),(lx-2,ly-1)]
        for p in m:
            if p[0] >= 0 and p[0] <= 7 and p[1] >= 0 and p[1] <= 7:
                if self._board[p[1]][p[0]] == "n" and player==self.WHITE:
                    return True
                elif self._board[p[1]][p[0]] == "N" and player==self.BLACK:
                    return True

        if player == self.WHITE:
            if lx<7 and ly>0 and self._board[ly-1][lx+1] == 'p':
                return True
            elif lx>0 and ly>0 and self._board[ly-1][lx-1] == 'p':
                return True
        else:
            if lx<7 and ly<7 and self._board[ly+1][lx+1] == 'P':
                return True
            elif lx>0 and ly<7 and self._board[ly+1][lx-1] == 'P':
                return True


        return False


    def hasAnyValidMoves(self,player=None):
        if player == None:
            player = self._turn

        for y in range(0,8):
            for x in range(0,8):
                if self.getColor(x,y) == player:
                    if len(self.getValidMoves((x,y))):
                        return True
        return False

    #-----------------------------------------------------------------
    def traceValidMoves(self,fromPos,dirs,maxSteps=8):
        moves = []
        for d in dirs:
            x,y = fromPos
            dx,dy = d
            steps = 0
            while True:
                x+=dx
                y+=dy
                if x<0 or x>7 or y<0 or y>7:
                    break
                if self.isFree(x,y):
                    moves.append((x,y))
                elif self.getColor(x,y)!=self._turn:
                    moves.append((x,y))
                    break
                else:
                    break
                steps+=1
                if steps == maxSteps:
                    break
        return moves

    def getValidQueenMoves(self,fromPos):
        moves = []
        dirs = [(1,0),(-1,0),(0,1),(0,-1),(1,1),(-1,1),(1,-1),(-1,-1) ]

        moves = self.traceValidMoves(fromPos,dirs)

        moves = self.checkKingGuard(fromPos,moves)


        return moves

    def getValidRookMoves(self,fromPos):
        moves = []
        dirs = [(1,0),(-1,0),(0,1),(0,-1)]

        moves = self.traceValidMoves(fromPos,dirs)

        moves = self.checkKingGuard(fromPos,moves)

        return moves

    def getValidBishopMoves(self,fromPos):
        moves = []
        dirs = [(1,1),(-1,1),(1,-1),(-1,-1) ]

        moves = self.traceValidMoves(fromPos,dirs)

        moves = self.checkKingGuard(fromPos,moves)

        return moves

    def getValidPawnMoves(self,fromPos):
        moves = []
        specialMoves = {}
        fx,fy = fromPos

        if self._turn == self.WHITE:
            movedir = -1
            startrow = 6
            ocol = self.BLACK
            eprow = 3
            promorow = 1
        else:
            movedir = 1
            startrow = 1
            ocol = self.WHITE
            eprow = 4
            promorow = 6

        if self.isFree(fx,fy+movedir):
            moves.append((fx,fy+movedir))

        if fy == startrow:
            if self.isFree(fx,fy+movedir) and self.isFree(fx,fy+(movedir*2)):
                moves.append((fx,fy+(movedir*2)))
                specialMoves[(fx,fy+(movedir*2))] = self.EP_MOVE

        if fx < 7 and self.getColor(fx+1,fy+movedir) == ocol:
            moves.append((fx+1,fy+movedir))
        if fx > 0 and self.getColor(fx-1,fy+movedir) == ocol:
            moves.append((fx-1,fy+movedir))

        if fy == eprow and self._ep[1] != 0:
            if self._ep[0] == fx+1:
               moves.append((fx+1,fy+movedir))
               specialMoves[(fx+1,fy+movedir)] = self.EP_CAPTURE_MOVE
            if self._ep[0] == fx-1:
               moves.append((fx-1,fy+movedir))
               specialMoves[(fx-1,fy+movedir)] = self.EP_CAPTURE_MOVE

        if fy == promorow:
            if self.isFree(fx,fy+movedir):
                specialMoves[(fx,fy+movedir)] = self.PROMOTION_MOVE
            try:
                diag_right_col = self.getColor(fx+1,fy+movedir)
                if diag_right_col == ocol:
                    specialMoves[(fx+1,fy+movedir)] = self.PROMOTION_MOVE
            except:
                pass
            try:
                diag_left_col = self.getColor(fx-1,fy+movedir)
                if diag_left_col == ocol:
                    specialMoves[(fx-1,fy+movedir)] = self.PROMOTION_MOVE
            except:
                pass

        moves = self.checkKingGuard(fromPos,moves,specialMoves)
        return (moves,specialMoves)

    def getValidKnightMoves(self,fromPos):
        moves = []
        fx,fy = fromPos
        m =[(fx+1,fy+2),(fx+2,fy+1),(fx+2,fy-1),(fx+1,fy-2),(fx-1,fy+2),(fx-2,fy+1),(fx-1,fy-2),(fx-2,fy-1)]
        for p in m:
            if p[0] >= 0 and p[0] <= 7 and p[1] >= 0 and p[1] <= 7:
                if self.getColor(p[0],p[1])!=self._turn:
                    moves.append(p)
        moves = self.checkKingGuard(fromPos,moves)

        return moves

    def getValidKingMoves(self,fromPos):
        moves = []
        specialMoves={}

        if self._turn == self.WHITE:
            c_row = 7
            c_king = self._white_king_castle
            c_queen = self._white_queen_castle
            k = "K"
        else:
            c_row = 0
            c_king = self._black_king_castle
            c_queen = self._black_queen_castle
            k = "k"

        dirs = [(1,0),(-1,0),(0,1),(0,-1),(1,1),(-1,1),(1,-1),(-1,-1) ]

        t_moves = self.traceValidMoves(fromPos,dirs,1)
        moves = []

        self._board[fromPos[1]][fromPos[0]] = '.'

        for m in t_moves:
            if not self.isThreatened(m[0],m[1]):
                moves.append(m)

        if c_king:
            if self.isFree(5,c_row) and self.isFree(6,c_row) and self._board[c_row][7].upper() == 'R':
                if not self.isThreatened(4,c_row) and not self.isThreatened(5,c_row) and not self.isThreatened(6,c_row):
                    moves.append((6,c_row))
                    specialMoves[(6,c_row)] = self.KING_CASTLE_MOVE
        if c_queen:
            if self.isFree(3,c_row) and self.isFree(2,c_row) and self.isFree(1,c_row) and self._board[c_row][0].upper() == 'R':
                if not self.isThreatened(4,c_row) and not self.isThreatened(3,c_row) and not self.isThreatened(2,c_row):
                    moves.append((2,c_row))
                    specialMoves[(2,c_row)] = self.QUEEN_CASTLE_MOVE

        self._board[fromPos[1]][fromPos[0]] = k

        return (moves,specialMoves)

    # -----------------------------------------------------------------------------------

    def movePawn(self,fromPos,toPos):
        moves,specialMoves = self.getValidPawnMoves(fromPos)

        if not toPos in moves and not toPos in specialMoves:
            print "pawn tried to make an invalid move!"
            return False

        if specialMoves.has_key(toPos):
            t = specialMoves[toPos]
        else:
            t = 0

        if t == self.EP_CAPTURE_MOVE:
            self._board[self._ep[1]][self._ep[0]] = '.'
            self._cur_move[3]=True
            self._cur_move[6]=self.EP_CAPTURE_MOVE

        pv = self._promotion_value
        if self._turn == self.WHITE and toPos[1] == 0:
#            if pv == 0:
#                self._reason = self.MUST_SET_PROMOTION
#                return False
            pc = ['Q','R','N','B']
            p = pc[0]
            self._cur_move[4]=p
            self._cur_move[6]=self.PROMOTION_MOVE
            #self._promotion_value = 0
        elif self._turn == self.BLACK and toPos[1] == 7:
#            if pv == 0:
#                self._reason = self.MUST_SET_PROMOTION
#                return False
            pc = ['q','r','n','b']
            p = pc[0]
            self._cur_move[4]=p
            self._cur_move[6]=self.PROMOTION_MOVE
            #self._promotion_value = 0
        else:
            p = self._board[fromPos[1]][fromPos[0]]

        if t == self.EP_MOVE:
            self.setEP(toPos)
            self._cur_move[6]=self.EP_MOVE
        else:
            self.clearEP()

        if self._board[toPos[1]][toPos[0]] != '.':
            self._cur_move[3]=True

        self._board[toPos[1]][toPos[0]] = p
        self._board[fromPos[1]][fromPos[0]] = "."

        self._fifty = 0
        return True


    def moveKnight(self,fromPos,toPos):
        moves = self.getValidKnightMoves(fromPos)

        if not toPos in moves:
            print "knight tried to make an invalid move!"
            return False

        self.clearEP()

        if self._board[toPos[1]][toPos[0]] == ".":
            self._fifty+=1
        else:
            self._fifty=0
            self._cur_move[3]=True

        self._board[toPos[1]][toPos[0]] = self._board[fromPos[1]][fromPos[0]]
        self._board[fromPos[1]][fromPos[0]] = "."
        return True


    def moveKing(self,fromPos,toPos):
        if self._turn == self.WHITE:
            c_row = 7
            k = "K"
            r = "R"
        else:
            c_row = 0
            k = "k"
            r = "r"

        moves,specialMoves = self.getValidKingMoves(fromPos)

        if specialMoves.has_key(toPos):
            t = specialMoves[toPos]
        else:
            t = 0

        if not toPos in moves and not toPos in specialMoves:
            print "king tried to make an invalid move!"
            return False

        self.clearEP()

        if self._turn == self.WHITE:
            self._white_king_castle = False
            self._white_queen_castle = False
        else:
            self._black_king_castle = False
            self._black_queen_castle = False

        if t == self.KING_CASTLE_MOVE:
            self._fifty+=1
            self._board[c_row][4] = "."
            self._board[c_row][6] = k
            self._board[c_row][7] = "."
            self._board[c_row][5] = r
            self._cur_move[6] = self.KING_CASTLE_MOVE
        elif t == self.QUEEN_CASTLE_MOVE:
            self._fifty+=1
            self._board[c_row][4] = "."
            self._board[c_row][2] = k
            self._board[c_row][0] = "."
            self._board[c_row][3] = r
            self._cur_move[6] = self.QUEEN_CASTLE_MOVE
        else:
            if self._board[toPos[1]][toPos[0]] == ".":
                self._fifty+=1
            else:
                self._fifty=0
                self._cur_move[3]=True

            self._board[toPos[1]][toPos[0]] = self._board[fromPos[1]][fromPos[0]]
            self._board[fromPos[1]][fromPos[0]] = "."


        self.updateKingLocations()
        self.updateKingLines(toPos) #update the location of diagonals, rows, and cols the king is in
        return True

    def moveQueen(self,fromPos,toPos):

        moves = self.getValidQueenMoves(fromPos)

        if not toPos in moves:
            print "queen tried to make an invalid move!"
            return False

        self.clearEP()

        if self._board[toPos[1]][toPos[0]] == ".":
            self._fifty+=1
        else:
            self._fifty=0
            self._cur_move[3]=True

        self._board[toPos[1]][toPos[0]] = self._board[fromPos[1]][fromPos[0]]
        self._board[fromPos[1]][fromPos[0]] = "."
        return True

    def moveBishop(self,fromPos,toPos):
        moves = self.getValidBishopMoves(fromPos)

        if not toPos in moves:
            print "bishop tried to make an invalid move!"
            return False

        self.clearEP()

        if self._board[toPos[1]][toPos[0]] == ".":
            self._fifty+=1
        else:
            self._fifty=0
            self._cur_move[3]=True

        self._board[toPos[1]][toPos[0]] = self._board[fromPos[1]][fromPos[0]]
        self._board[fromPos[1]][fromPos[0]] = "."
        return True

    def moveRook(self,fromPos,toPos):

        moves = self.getValidRookMoves(fromPos)

        if not toPos in moves:
            print "rook tried to make an invalid move!"
            return False

        fx,fy = fromPos
        if self._turn == self.WHITE:
            if fx == 0:
                self._white_queen_castle = False
            if fx == 7:
                self._white_king_castle = False
        if self._turn == self.BLACK:
            if fx == 0:
                self._black_queen_castle = False
            if fx == 7:
                self._black_king_castle = False

        self.clearEP()

        if self._board[toPos[1]][toPos[0]] == ".":
            self._fifty+=1
        else:
            self._fifty=0
            self._cur_move[3]=True

        self._board[toPos[1]][toPos[0]] = self._board[fromPos[1]][fromPos[0]]
        self._board[fromPos[1]][fromPos[0]] = "."
        return True


    def _parseTextMove(self,txt):

        txt = txt.strip()
        promotion = None
        dest_x = 0
        dest_y = 0
        h_piece = "P"
        h_rank = -1
        h_file = -1

        # handle the special
        if txt == "O-O":
            if self._turn == 0:
                return (None,4,7,6,7,None)
            if self._turn == 1:
                return (None,4,0,6,0,None)
        if txt == "O-O-O":
            if self._turn == 0:
                return (None,4,7,2,7,None)
            if self._turn == 1:
                return (None,4,0,2,0,None)

        files = {"a":0,"b":1,"c":2,"d":3,"e":4,"f":5,"g":6,"h":7}
        ranks = {"8":0,"7":1,"6":2,"5":3,"4":4,"3":5,"2":6,"1":7}

        # Clean up the textmove
        "".join(txt.split("e.p."))
        t = []
        for ch in txt:
            if ch not in "KQRNBabcdefgh12345678":
                continue
            t.append(ch)

        if len(t)<2:
            return None

        # Get promotion if any
        if t[-1] in ('Q','R','N','B'):
            promotion = {'Q':1,'R':2,'N':3,'B':4}[t.pop()]

        if len(t)<2:
            return None

        # Get the destination
        if not files.has_key(t[-2]) or not ranks.has_key(t[-1]):
            return None

        dest_x = files[t[-2]]
        dest_y = ranks[t[-1]]

        # Pick out the hints
        t = t[:-2]
        for h in t:
            if h in ('K','Q','R','N','B','P'):
                h_piece = h
            elif h in ('a','b','c','d','e','f','g','h'):
                h_file = files[h]
            elif h in ('1','2','3','4','5','6','7','8'):
                h_rank = ranks[h]

        # If we have both a source and destination we don't need the piece hint.
        # This will make us make the move directly.
        if h_rank > -1 and h_file > -1:
            h_piece = None

        return (h_piece,h_file,h_rank,dest_x,dest_y,promotion)

    def _formatTextMove(self,move,format):
        #piece,from,to,take,promotion,check

        piece = move[0]
        fpos = tuple(move[1])
        tpos = tuple(move[2])
        take = move[3]
        promo = move[4]
        check = move[5]
        special = move[6]

        files = "abcdefgh"
        ranks = "87654321"
        if format == self.AN:
            res = "%s%s%s%s" % (files[fpos[0]],ranks[fpos[1]],files[tpos[0]],ranks[tpos[1]])
        elif format == self.LAN:

            if special == self.KING_CASTLE_MOVE:
                return "O-O"
            elif special == self.QUEEN_CASTLE_MOVE:
                return "O-O-O"

            tc = "-"
            if take:
                tc = "x"
            pt = ""
            if promo:
                pt = "=%s" % promo
            if piece == "P":
                piece = ""
            if not check:
                check = ""
            res = "%s%s%s%s%s%s%s%s" % (piece,files[fpos[0]],ranks[fpos[1]],tc,files[tpos[0]],ranks[tpos[1]],pt,check)
        elif format == self.SAN:

            if special == self.KING_CASTLE_MOVE:
                return "O-O"
            elif special == self.QUEEN_CASTLE_MOVE:
                return "O-O-O"

            tc = ""
            if take:
                tc = "x"
            pt = ""
            if promo:
                pt = "=%s" % promo.upper()
            p = piece
            if self._turn == self.BLACK:
                p = p.lower()
            if piece == "P":
                piece = ""
            if not check:
                check = ""
            fx,fy = fpos
            hint_f = ""
            hint_r = ""
            for y in range(8):
                for x in range(8):
                    if self._board[y][x] == p:
                        if x == fx and y == fy:
                            continue
                        vm = self.getValidMoves((x,y))
                        if tpos in vm:
                            if fx == x:
                                hint_r = ranks[fy]
                            else:
                                hint_f = files[fx]
            if piece == "" and take:
                hint_f = files[fx]
            res = "%s%s%s%s%s%s%s%s" % (piece,hint_f,hint_r,tc,files[tpos[0]],ranks[tpos[1]],pt,check)
        return res

    def _formatAIMove(self,move):
        #piece,from,to,take,promotion,check
        piece = self._board[move[1][1]][move[1][0]]
        fpos = tuple(move[0])
        tpos = tuple(move[1])

        files = "abcdefgh"
        ranks = "87654321"
        piece = piece.upper()
        if piece == "P":
            piece = ""
        return "%s%s%s-%s%s" % (piece,files[fpos[0]],ranks[fpos[1]],files[tpos[0]],ranks[tpos[1]])

    #----------------------------------------------------------------------------
    # PUBLIC METHODS
    #----------------------------------------------------------------------------

    def resetBoard(self):
        """
        Resets the chess board and all states.
        """
        self._board = [
            ['r','n','b','q','k','b','n','r'],
            ['p']*8,
            ['.']*8,
            ['.']*8,
            ['.']*8,
            ['.']*8,
            ['P']*8,
            ['R','N','B','Q','K','B','N','R']
            ]
        self._turn = self.WHITE
        self._white_king_castle = True
        self._white_queen_castle = True
        self._black_king_castle = True
        self._black_queen_castle = True
        self._ep = [0,0]
        self._fifty = 0
        self._three_rep_stack = []
        self._state_stack = []
        self._moves = []
        self._reason = 0
        self._game_result = 0
        self.pushState()
        self.updateKingLocations()

    def setFEN(self,fen):
        """
        Sets the board and states accoring from a Forsyth-Edwards Notation string.
        Ex. 'rnbqkbnr/pp1ppppp/8/2p5/4P3/5N2/PPPP1PPP/RNBQKB1R b KQkq - 1 2'
        """
        self._three_rep_stack = []
        self._state_stack = []
        self._moves = []
        self._reason = 0
        self._game_result = 0

        fparts = fen.split()
        newstate = ""

        #BOARD
        for c in fparts[0]:
            if c in "kqrnbpKQRNBP":
                newstate += c
            elif c in "12345678":
                newstate += '.' * int(c)
        #TURN
        newstate += str("wb".index(fparts[1]))

        #CASTLING
        kq = "KQkq"
        for p in kq:
            if p in fparts[2]:
                newstate += "1"
            else:
                newstate += "0"

        #EN PASSANT
        if len(fparts[3]) == 2:
            newstate += str("abcdefgh".index(fparts[3][0].lower()))
            newstate += str("87654321".index(fparts[3][1]))
        else:
            newstate += "00"

        #GAME RESULT
        newstate+="0"

        #HALF COUNT
        newstate+=":%s" % fparts[4]

        self._state_stack.append(newstate)
        self._state_stack_pointer = 1
        self.loadCurState()

        three_state = [self._white_king_castle,
            self._white_queen_castle,
            self._black_king_castle,
            self._black_queen_castle,
            deepcopy(self._board),
            #changed ep from deepcopy to list copy
            list(self._ep)]

        self._three_rep_stack.append(three_state)

        self.updateKingLocations()

    def getFEN(self):
        """
        Returns the current state as Forsyth-Edwards Notation string.
        """
        s = self._state_stack[self._state_stack_pointer-1]

        b= s[:64]
        v = s[64:72]
        fifty =  s[73:]

        rows = []
        for i in range(8):
            row = b[i*8:(i+1)*8]
            cnt = 0; res = ""
            for c in row:
                if c == ".":
                    cnt+=1
                else:
                    if cnt:
                        res += str(cnt);
                        cnt=0
                    res+=c
            if cnt:
                res += str(cnt)
            rows.append(res)
        board = "/".join(rows)

        turn = (["w","b"])[int(v[0])]

        kq = ""
        if int(v[1]): kq+="K"
        if int(v[2]): kq+="Q"
        if int(v[3]): kq+="k"
        if int(v[4]): kq+="q"
        if not kq:
            kq = "-"

        x = int(v[5])
        y = int(v[6])
        ep = "-"
        if not (y == 0):
            if not (x==7):
                if turn == "b" and self._board[y][x+1] == 'p':
                    ep = "%s%s" % ( ("abcdefgh")[x], ("87654321")[y+1])
                elif turn == "w" and self._board[y][x+1] == 'P':
                    ep = "%s%s" % ( ("abcdefgh")[x], ("87654321")[y-1])

            if not (x==0):
                if turn == "b" and self._board[y][x-1] == 'p':
                    ep = "%s%s" % ( ("abcdefgh")[x], ("87654321")[y+1])
                elif turn == "w" and self._board[y][x-1] == 'P':
                    ep = "%s%s" % ( ("abcdefgh")[x], ("87654321")[y-1])

        move = (self._state_stack_pointer+1)/2

        return "%s %s %s %s %s %d" % (board,turn,kq,ep,fifty,move)

    def getMoveCount(self):
        """
        Returns the number of halfmoves in the stack.
        Zero (0) means no moves has been made.
        """
        return len(self._state_stack)-1

    def getCurrentMove(self):
        """
        Returns the current halfmove number. Zero (0) means before first move.
        """
        return self._state_stack-1

    def gotoMove(self,move):
        """
        Goto the specified halfmove. Zero (0) is before the first move.
        Return False if move is out of range.
        """
        move+=1
        if move > len(self._state_stack):
            return False
        if move < 1:
            return False

        self._state_stack_pointer = move
        self.loadCurState()


    def gotoFirst(self):
        """
        Goto before the first known move.
        """
        self._state_stack_pointer = 1
        self.loadCurState()

    def gotoLast(self):
        """
        Goto after the last knwon move.
        """
        self._state_stack_pointer = len(self._state_stack)
        self.loadCurState()

    def undo(self):
        """
        Undo the last move. Can be used to step back until the initial board setup.
        Returns True or False if no more moves can be undone.
        """
        if self._state_stack_pointer <= 1:
            return False
        self._state_stack_pointer -= 1
        self.loadCurState()
        return True

    def redo(self):
        """
        If you used the undo method to step backwards you can use this method to step forward until the last move i reached.
        Returns True or False if no more moves can be redone.
        """
        if self._state_stack_pointer == len(self._state_stack):
            return False
        self._state_stack_pointer += 1
        self.loadCurState()
        return True

    def setPromotion(self, promotion):
        """
        Tell the chessboard how to promote a pawn.
        1=QUEEN,2=ROOK,3=KNIGHT,4=BISHOP
        You can also set promotion to 0 (zero) to reset the promotion value.
        """
        self._promotion_value = promotion

    def getPromotion(self):
        """
        Returns the current promotion value.
        1=QUEEN,2=ROOK,3=KNIGHT,4=BISHOP
        """
        return self._promotion_value

    def isCheck(self):
        """
        Returns True if the current players king is checked.
        """
        if self._turn == self.WHITE:
            kx,ky = self._white_king_location
        else:
            kx,ky = self._black_king_location

        return self.isThreatened(kx,ky,self._turn)

    def someoneChecked(self):
        """
        Returns True if the either players king is checked.
        """
        wkx,wky = self._white_king_location
        bkx,bky = self._black_king_location
        return self.isThreatened(wkx,wky,ChessBoard.WHITE) or self.isThreatened(bkx,bky,ChessBoard.BLACK)

    def isGameOver(self):
        """
        Returns True if the game is over by either checkmate or draw.
        """
        if self._game_result:
            return True
        return False

    def getGameResult(self):
        """
        Returns the reason for game over.
        It can be the following reasons: 1=WHITE_WIN , 2=BLACK_WIN, 3=STALEMATE,4=FIFTY_MOVES_RULE,5=THREE_REPETITION_RULE.
        If game is not over this method returns zero(0).
        """
        return self._game_result

    def getBoard(self):
        """
        Returns a copy of the current board layout. Uppercase letters for white, lovercase for black.
        K=King, Q=Queen, B=Bishop, N=Night, R=Rook, P=Pawn.
        Empty squares are markt with a period (.)
        """
        return deepcopy(self._board)

    def getShallowBoard(self):
        """Returns the board itself for evaluation purposes, avoids deepcopy"""
        return self._board

    def getTurn(self):
        """
        Returns the current player. 0=WHITE, 1=BLACK.
        """
        return self._turn

    def getReason(self):
        """
        Returns the reason to why addMove returned False.
        1=INAVLID_MOVE,2=INVALID_COLOR,3=INVALID_FROM_LOCATION,4=INVALID_TO_LOCATION,5=MUST_SET_PROMOTION,5=GAME_IS_OVER
        """
        return self._reason

    def getValidMoves(self,location):
        """
        Returns a list of valid moves. (ex [ [3,4],[3,5],[3,6] ... ] ) If there isn't a valid piece on that location or the piece on the selected
        location hasn't got any valid moves an empty list is returned.
        The location argument must be a tuple containing an x,y value Ex. (3,3)
        """
        if self._game_result:
            return []

        x,y = location

        if x < 0 or x > 7 or y < 0 or y > 7:
            return False

#        self.updateKingLocations()

        if self.getColor(x,y) != self._turn:
            return []

        p = self._board[y][x].upper()
        if p == 'P':
            m,s = self.getValidPawnMoves(location)
            return m
        elif p == 'R':
            return self.getValidRookMoves(location)
        elif p == 'B':
            return self.getValidBishopMoves(location)
        elif p == 'Q':
            return self.getValidQueenMoves(location)
        elif p == 'K':
            m,s = self.getValidKingMoves(location)
            for key in s:
                m.append(key)
#                print "returning king's special move from getvalidmoves function"
#                print str(key) + str(s[key])
            return m
        elif p == 'N':
            return self.getValidKnightMoves(location)
        else:
            return []

    def getValidMovesS(self,location):
        """
        Returns the number of valid moves with symmetry slightly faster for activity scoring.
        Doesn't add pawn or king activity.
        """
        if self._game_result: #if game over, return none
            return 0

        x,y = location

#        self.updateKingLocations()

        p = self._board[y][x].upper()
        if p == '.':
            return 0
        elif p == 'P':
            return 0
        elif p == 'R':
            return len(self.getValidRookMoves(location))*self.getColorS(x,y)
        elif p == 'B':
            return len(self.getValidBishopMoves(location))*1.1*self.getColorS(x,y)
        elif p == 'Q':
            return len(self.getValidQueenMoves(location))/2.0*self.getColorS(x,y)
        elif p == 'K':
            return 0
        elif p == 'N':
            return len(self.getValidKnightMoves(location))*1.4*self.getColorS(x,y)
        else:
            return 0

    def addMove(self,fromPos,toPos):
        """
        Tries to move the piece located om fromPos to toPos. Returns True if that was a valid move.
        The position arguments must be tuples containing x,y value Ex. (4,6).
        This method also detects game over.

        If this method returns False you can use the getReason method to determin why.
        """

        self._reason = 0
        #                piece,from,to,take,promotion,check,specialmove
        self._cur_move = [None,None,None,False,None,None,self.NORMAL_MOVE]

        if self._game_result:
            self._result = self.GAME_IS_OVER
            return False

        self.updateKingLocations()

        fx,fy = fromPos
        tx,ty = toPos

        self._cur_move[1]=fromPos
        self._cur_move[2]=toPos

        #check invalid coordinates
        if fx < 0 or fx > 7 or fy < 0 or fy > 7:
            self._reason = self.INVALID_FROM_LOCATION
            return False

        #check invalid coordinates
        if tx < 0 or tx > 7 or ty < 0 or ty > 7:
            self._reason = self.INVALID_TO_LOCATION
            return False

        #check if any move at all
        if fx==tx and fy==ty:
            self._reason = self.INVALID_TO_LOCATION
            return False

        #check if piece on location
        if self.isFree(fx,fy):
            self._reason = self.INVALID_FROM_LOCATION
            return False

        #check color of piece
        if self.getColor(fx,fy) != self._turn:
            self._reason = self.INVALID_COLOR
            return False

        # Call the correct handler
        p = self._board[fy][fx].upper()
        self._cur_move[0]=p
        if p == 'P':
            if not self.movePawn((fx,fy),(tx,ty)):
                if not self._reason:
                    self._reason = self.INVALID_MOVE
                return False
        elif p == 'R':
            if not self.moveRook((fx,fy),(tx,ty)):
                self._reason = self.INVALID_MOVE
                return False
        elif p == 'B':
            if not self.moveBishop((fx,fy),(tx,ty)):
                self._reason = self.INVALID_MOVE
                return False
        elif p == 'Q':
            if not self.moveQueen((fx,fy),(tx,ty)):
                self._reason = self.INVALID_MOVE
                return False
        elif p == 'K':
            if not self.moveKing((fx,fy),(tx,ty)):
                self._reason = self.INVALID_MOVE
                return False
        elif p == 'N':
            if not self.moveKnight((fx,fy),(tx,ty)):
                self._reason = self.INVALID_MOVE
                return False
        else:
            return False

        if self._turn == self.WHITE:
            self._turn = self.BLACK
        elif self._turn == self.BLACK:
            self._turn = self.WHITE

        if self.isCheck():
            self._cur_move[5]="+"

        if not self.hasAnyValidMoves():
            if self.isCheck():
                self._cur_move[5]="#"
                if self._turn == self.WHITE:
                    self.endGame(self.BLACK_WIN)
                else:
                    self.endGame(self.WHITE_WIN)
            else:
                self.endGame(self.STALEMATE)
        else:
            if self._fifty == 100:
                self.endGame(self.FIFTY_MOVES_RULE)
            elif self.threeRepetitions():
                self.endGame(self.THREE_REPETITION_RULE)

        self.pushState()
        self.pushMove()

        return True

    def addMoveS(self,fromPos,toPos):
        """
        Tries to move the piece located om fromPos to toPos. Returns True if that was a valid move.
        The position arguments must be tuples containing x,y value Ex. (4,6).
        This method also detects game over.

        If this method returns False you can use the getReason method to determin why.
        """

        self._reason = 0
        #                piece,from,to,take,promotion,check,specialmove
        self._cur_move = [None,None,None,False,None,None,self.NORMAL_MOVE]

        if self._game_result:
            self._result = self.GAME_IS_OVER
            return False

        self.updateKingLocations()

        fx,fy = fromPos
        tx,ty = toPos

        self._cur_move[1]=fromPos
        self._cur_move[2]=toPos

        p = self._board[fy][fx].upper()
        self._cur_move[0]=p
        if p == 'P':
            if not self.movePawn((fx,fy),(tx,ty)):
                if not self._reason:
                    self._reason = self.INVALID_MOVE
                return False
        elif p == 'R':
            if not self.moveRook((fx,fy),(tx,ty)):
                self._reason = self.INVALID_MOVE
                return False
        elif p == 'B':
            if not self.moveBishop((fx,fy),(tx,ty)):
                self._reason = self.INVALID_MOVE
                return False
        elif p == 'Q':
            if not self.moveQueen((fx,fy),(tx,ty)):
                self._reason = self.INVALID_MOVE
                return False
        elif p == 'K':
            if not self.moveKing((fx,fy),(tx,ty)):
                self._reason = self.INVALID_MOVE
                return False
        elif p == 'N':
            if not self.moveKnight((fx,fy),(tx,ty)):
                self._reason = self.INVALID_MOVE
                return False
        else:
            return False

        if self._turn == self.WHITE:
            self._turn = self.BLACK
        elif self._turn == self.BLACK:
            self._turn = self.WHITE

        if self.isCheck():
            self._cur_move[5]="+"

        if not self.hasAnyValidMoves():
            if self.isCheck():
                self._cur_move[5]="#"
                if self._turn == self.WHITE:
                    self.endGame(self.BLACK_WIN)
                else:
                    self.endGame(self.WHITE_WIN)
            else:
                self.endGame(self.STALEMATE)
        else:
            if self._fifty == 100:
                self.endGame(self.FIFTY_MOVES_RULE)
            elif self.threeRepetitions():
                self.endGame(self.THREE_REPETITION_RULE)

        self.pushState()
        self.pushMove()

        return True

    def getLastMoveType(self):
        """
        Returns a value that indicates if the last move was a "special move".
        Returns -1 if no move has been done.
        Return value can be:
        0=NORMAL_MOVE
        1=EP_MOVE (Pawn is moved two steps and is valid for en passant strike)
        2=EP_CAPTURE_MOVE (A pawn has captured another pawn by using the en passant rule)
        3=PROMOTION_MOVE (A pawn has been promoted. Use getPromotion() to see the promotion piece.)
        4=KING_CASTLE_MOVE (Castling on the king side.)
        5=QUEEN_CASTLE_MOVE (Castling on the queen side.)
        """
        if self._state_stack_pointer<=1: # No move has been done at thos pointer
            return -1

        self.undo()
        move = self._moves[self._state_stack_pointer-1]
        res = move[6]
        self.redo()

        return res


    def getLastMove(self):
        """
        Returns a tupple containing two tupples describing the move just made using the internal coordinates.
        In the format ((from_x,from_y),(to_x,to_y))
        Ex. ((4,6),(4,4))
        Returns None if no moves has been made.
        """
        if self._state_stack_pointer<=1: # No move has been done at thos pointer
            return None

        self.undo()
        move = self._moves[self._state_stack_pointer-1]
        res = (move[1],move[2])
        self.redo()

        return res


    def addTextMove(self,txt):
        """
        Adds a move using several different standards of the Algebraic chess notation.
        AN Examples: 'e2e4' 'f1d1' 'd7-d8' 'g1-f3'
        SAN Examples: 'e4' 'Rfxd1' 'd8=Q' 'Nxf3+'
        LAN Examples: 'Pe2e4' 'Rf1xd1' 'Pd7d8=Q' 'Ng1xf3+'
        """
        res = self._parseTextMove(txt)
        if not res:
            self._reason = self.INVALID_MOVE
            return False
        else:
            piece,fx,fy,tx,ty,promo = res

        if promo:
            self.setPromotion(promo)

        if not piece:
            return self.addMove((fx,fy),(tx,ty))

        if self._turn == self.BLACK:
            piece = piece.lower()

        move_to = None
        move_from = None
        found_move = False
        for y in range(8):
            for x in range(8):
                if self._board[y][x] == piece:
                    if fx > -1 and fx != x:
                        continue
                    if fy > -1 and fy != y:
                        continue
                    vm = self.getValidMoves((x,y))
                    for m in vm:
                        if m[0] == tx and m[1] == ty:
                            if found_move:
                                self._reason = self.AMBIGUOUS_MOVE
                                return False
                            found_move = True
                            move_from = (x,y)
                            move_to = (tx,ty)

        if found_move:
            return self.addMove(move_from,move_to)

        self._reason = self.INVALID_MOVE
        return False

    def getAllTextMoves(self,format=1):
        """
        Returns a list of all moves done so far in Algebraic chess notation.
        Returns None if no moves has been made.
        """
        if self._state_stack_pointer<=1: # No move has been done at this pointer
            return None

        res = []

        point = self._state_stack_pointer

        self.gotoFirst()
        while True:
            move = self._moves[self._state_stack_pointer-1]
            res.append(self._formatTextMove(move,format))
            if self._state_stack_pointer >= len(self._state_stack)-1:
                break
            self.redo()

        self._state_stack_pointer = point
        self.loadCurState()

        return res

    def getLastTextMove(self,format=1):
        """
        Returns the latest move as Algebraic chess notation.
        Returns None if no moves has been made.
        """
        if self._state_stack_pointer<=1: # No move has been done at thos pointer
            return None

        self.undo()
        move = self._moves[self._state_stack_pointer-1]
        res = self._formatTextMove(move,format)
        self.redo()
        return res

    def printBoard(self): #shou
        """
        Print the current board layout.
        """
        print "  +-----------------+"
        rank = 8
        for l in self._board:
            print "%d | %s %s %s %s %s %s %s %s |" % (rank,l[0],l[1],l[2],l[3],l[4],l[5],l[6],l[7])
            rank-=1
        print "  +-----------------+"
        print "    A B C D E F G H"