finalChessEnginePython.py

'''
Chess Engine Python for Orange Pi 5
Made for An Autonomous Over-The-Board Chess Solution For Players in Isolated Conditions
By: Ayaan Dhuka, Landon Doughty, and Caiman Moreno-Earle

Functionality:
Recieves input move from Arduino UNO Board 1 through UART
Calculates best response using engine with the features selected(the features are listed below)
Outputs engine move to Arduino UNO Board 1 through UART
Recieves feature selections and potentiometer depth readings from Arduino UNO Board 2 through UART
Outputs 16 characters for LCD display to Arduino UNO Board 2 through UART

Toggleable Features:
    1. positional awareness(square table + castle bonus) (independent)
    2. opening database (independent) --> database compiled of pgn files from https://www.pgnmentor.com/files.html#openings
    Note: openingBook.txt has all of these pgn files and needs to be in the same folder as this script
    3. random move (turns off all others)
    4. time for search (potentiometer range of values) (independent)

Other Features: 
Every chess rule (basic piece moves, pawn move up 2 ranks at start row, legal moves, short castle, long castle, and en passant) EXCEPT Underpromotion
Recursive Tree Search
Alpha-Beta Pruning
Iterative Deepening
Best Move First Sorting
Psuedo-Legal Move Generation
Legal Move Check
Zobrist Hashing for chess positions (opening database and transposition table)
Position Transposition Table to remove transposed positions from search
Material/Checkmate/Stalemate Evaluation (can add positional awareness from toggle as well) --> material values used: (p: 100, n: 320, b: 330, r: 500, q: 900, k: 20000)

To Do:
add UART connection input human move from Arduino UNO Board 1
add UART connection output engine move to Arduino UNO Board 1
add UART connection input feature selections and potentiometer depth reading from Arduino UNO Board 2
add UART connection output LCD 16 characters to Arduino UNO Board 2

Potential extensions:
fast legal move gen(skip psuedo-legal check)
threading to speed up search
chain captures/check evaluation
'''
#import built-in python modules for random integer and time counter
from random import randint
from time import perf_counter
#define empty square character (can be pretty much any UTF-8 char) on the board array
emptySquare = "_"
#the features that are changed by the UI
enhancedEval = True
openingDatabase = True
randomMove = False
maxTime = 2
#define an abstract piece class to make all the pieces from
class Piece:
    #initialize the class with a property for its board represent char, color, current square in [row, col], and index of piece used in hash and SAN conversion
    def __init__(self, char, color, square, index):
        self.char = char#CAPITAL = BLACK; lower = white
        self.color = color#False is black; True is white
        self.square = square #[row, col] white perspective 0-7
        self.index = index #used in hash/SAN
class Knight(Piece):
    pass
#define Knight material in centipawns
Knight.material = 320
#define Knight square table for white(1) in dictionary, slightly encourage center (controls stronger squares), highly discourage edges(significantly decreases controlled squares)
Knight.table = {
    1: [
[-50,-40,-30,-30,-30,-30,-40,-50],
[-40,-20,  0,  0,  0,  0,-20,-40],
[-30,  0, 10, 15, 15, 10,  0,-30],
[-30,  5, 15, 20, 20, 15,  5,-30],
[-30,  0, 15, 20, 20, 15,  0,-30],
[-30,  5, 10, 15, 15, 10,  5,-30],
[-40,-20,  0,  5,  5,  0,-20,-40],
[-50,-40,-30,-30,-30,-30,-40,-50]
]}
#add the reverse to dictionary for black(0)
Knight.table[0] = [row[::-1] for row in Knight.table[1][::-1]]
#define King class
class King(Piece):
    #inCheck method returns if the King is in check
    def inCheck(self):
        #loop through the board for pieces
        for row in board:
            for piece in row:
                if piece != emptySquare:
                    #if the piece is of the opposite color
                    if piece.color != self.color:
                        #return True if the opponent piece is attacking the King
                        if self.square in piece.getMoveset():
                            return True
        #return False since no opponent pieces are attacking the King
        return False
#define castling rights states
King.canQueenCastle = True
King.canKingCastle = True
King.castled = False
#define King's material value even though the King cannot be taken --> (just a very high number to prioritize king safety)
King.material = 20000
#define King's square table for white(1) in dictionary: highly encourage castling and squares near it, highly discourage leaving the first two ranks (prioritize safety)
King.table = {1: [
[-30,-40,-40,-50,-50,-40,-40,-30],
[-30,-40,-40,-50,-50,-40,-40,-30],
[-30,-40,-40,-50,-50,-40,-40,-30],
[-30,-40,-40,-50,-50,-40,-40,-30],
[-20,-30,-30,-40,-40,-30,-30,-20],
[-10,-20,-20,-20,-20,-20,-20,-10],
 [20, 20,  0,  0,  0,  0, 20, 20],
 [20, 30, 20,  0,  0, 10, 30, 20]
]}
#add the reverse table into the dictionary for black(0)
King.table[0] = [row[::-1] for row in King.table[1][::-1]]
#define the endgame table for white(1) to use once the game has entered into the endgame phase --> an active king becomes more important than safe king
King.tableEndgame = [
[-50,-40,-30,-20,-20,-30,-40,-50],
[-30,-20,-10,  0,  0,-10,-20,-30],
[-30,-10, 20, 30, 30, 20,-10,-30],
[-30,-10, 30, 40, 40, 30,-10,-30],
[-30,-10, 30, 40, 40, 30,-10,-30],
[-30,-10, 20, 30, 30, 20,-10,-30],
[-30,-30,  0,  0,  0,  0,-30,-30],
[-50,-30,-30,-30,-30,-30,-30,-50]
]
#define the reverse endgame table for black(0) to use once the game has entered into the endgame phase: prefer center as there are more squares that the bishop controls
King.tableEndgameReverse= [row[::-1] for row in King.tableEndgame[::-1]]
#define Bishop class
class Bishop(Piece):
    pass
#define Bishop material in centipawns
Bishop.material = 330
#define Bishop square table for white(1) in dictionary
Bishop.table = {1:[
[-20,-10,-10,-10,-10,-10,-10,-20],
[-10,  0,  0,  0,  0,  0,  0,-10],
[-10,  0,  5, 10, 10,  5,  0,-10],
[-10,  5,  5, 10, 10,  5,  5,-10],
[-10,  0, 10, 10, 10, 10,  0,-10],
[-10, 10, 10, 10, 10, 10, 10,-10],
[-10,  5,  0,  0,  0,  0,  5,-10],
[-20,-10,-10,-10,-10,-10,-10,-20]
]}
#add reverse table to dictionary for black(0)
Bishop.table[0]=[row[::-1] for row in Bishop.table[1][::-1]]
#define Rook class
class Rook(Piece):
    pass
#define Rook material count in centipawns
Rook.material = 500
#define the rook move tracking variable for castle rights checking
Rook.moved = False
#define rook square table to dictionary for white(1): edge columns are slightly discouraged (less powerful on edge), central cols are slightly encouraged (helps w/ central control)
#7th rank is highly encouraged (attacks pawns/threatens opponent king)
Rook.table = {1:[
  [0,  0,  0,  0,  0,  0,  0,  0],
  [5, 10, 10, 10, 10, 10, 10,  5],
 [-5,  0,  0,  0,  0,  0,  0, -5],
 [-5,  0,  0,  0,  0,  0,  0, -5],
 [-5,  0,  0,  0,  0,  0,  0, -5],
 [-5,  0,  0,  0,  0,  0,  0, -5],
 [-5,  0,  0,  0,  0,  0,  0, -5],
  [0,  0,  0,  5,  5,  0,  0,  0]
]}
#add reverse table to dictionary for black(0)
Rook.table[0]=[row[::-1] for row in Rook.table[1][::-1]]
#define queen class
class Queen(Piece):
    pass
#define queen material count in centipawns
Queen.material = 900
#define queen square table to dictionary for white(1): center is preferred (controls more squares)
Queen.table = {1:[
[-20,-10,-10, -5, -5,-10,-10,-20],
[-10,  0,  0,  0,  0,  0,  0,-10],
[-10,  0,  5,  5,  5,  5,  0,-10],
[-5,  0,  5,  5,  5,  5,  0, -5],
  [0,  0,  5,  5,  5,  5,  0, -5],
[-10,  5,  5,  5,  5,  5,  0,-10],
[-10,  0,  5,  0,  0,  0,  0,-10],
[-20,-10,-10, -5, -5,-10,-10,-20]
]}
#add reverse table to dictionary for black(0)
Queen.table[0]=[row[::-1] for row in Queen.table[1][::-1]]
#define pawn class
class Pawn(Piece):
    #notifyEnPassant method to update each pawns ability to enPassant and target column
    def notifyEnPassant(self, enPassant, enPassantCol):
        self.enPassant = enPassant
        self.enPassantCol = enPassantCol
#define pawn material count in centipawns
Pawn.material = 100
#define square table for white(1) in dictionary: discourage staying in initial location, encourage central pawn control, VERY HIGHLY encourage 6th/7th rank push for promotion
Pawn.table =  {1:[
 [0,  0,  0,  0,  0,  0,  0,  0],
[50, 50, 50, 50, 50, 50, 50, 50],
[10, 10, 20, 30, 30, 20, 10, 10],
 [5,  5, 10, 25, 25, 10,  5,  5],
 [0,  0,  0, 20, 20,  0,  0,  0],
 [5, -5,-10,  0,  0,-10, -5,  5],
 [5, 10, 10,-20,-20, 10, 10,  5],
 [0,  0,  0,  0,  0,  0,  0,  0]
        ]}
#add reverse table to dictionary for black(0)
Pawn.table[0] = [row[::-1] for row in Pawn.table[1][::-1]]
#define the global board 2D array of all the pieces; piece definition is stated below
#Piece(char, color(True/False), square([row,col]), index(for hashing/SAN))
board = [
[Rook("♖", False, [0,0], 9),Knight("♘", False, [0,1], 7),Bishop("♗", False, [0,2], 8),Queen("♕", False, [0,3], 10),King("♔", False, [0,4], 11),Bishop("♗", False, [0,5], 8),Knight("♘", False, [0,6], 7),Rook("♖", False, [0,7], 9)],
[Pawn("♙", False, [1, i], 6) for i in range(8)],
[emptySquare]*8,
[emptySquare]*8,
[emptySquare]*8,
[emptySquare]*8,
[Pawn("♟︎", True, [6,i], 0) for i in range(8)],
[Rook("♜", True, [7,0], 3),Knight("♞", True, [7,1], 1),Bishop("♝", True, [7,2], 2),Queen("♛", True, [7,3], 4),King("♚", True, [7,4], 5),Bishop("♝", True, [7,5], 2),Knight("♞", True, [7,6], 1),Rook("♜", True, [7,7], 3)]
]
#keep track of kings in this list
kings = [board[0][4], board[7][4]]
# Initializes the zobrist hash table
def initTable():
	# 8x8x12 array of large random numbers to decrease chances of collisions --> when there are two inputs with the same hash
    largeBound = pow(2, 64)
    ZobristTable = [[[randint(0, largeBound) for k in range(12)] for j in range(8)] for i in range(8)]
    return ZobristTable
# Computes the hash value of a given board using the table defined in the function above
def computeHash(ZobristTable):
    #define h as counting variable(will grow to be very large)
	h = 0
    #loop through the board
	for i in range(8):
		for j in range(8):
			if board[i][j] != emptySquare:
                #get a unique identifier (the index property) of the piece at this board location
				piece = board[i][j].index
                #computers run xor very quickly so it is efficient even with large numbers
				h ^= ZobristTable[i][j][piece]
	return h
#init the table to ZobristTable
ZobristTable = initTable()
#function that takes SAN(Standard Algebraic Notation) to the (startRow, startCol, endRow, endCol) of a move for the code to use
#this function requires the SAN move and the color(0(black)/1(white)) of the side that is playing as arguments
def SANtoMove(move, turn):
    #king castle check
    if move == "O-O":
        if turn:
            return (7, 4, 7, 6)
        else:
            return (0, 4, 0, 6)
    #queen castle check
    elif move == "O-O-O":
        if turn:
            return (7, 4, 7, 2)
        else:
            return (0, 4, 0, 2)     
    #remove unnecesssary promotion, checks, and capture addons (dxe8=Q --> de8)
    move = move.replace("=Q","").replace("x","").replace("+","")
    #get the endrow and endcol from the last two characters remaining in the SAN move (e4 --> (4, 4))
    endRow = 8 - int(move[-1])
    endCol = ord(move[-2]) - 97
    #normal pawn move (no capture)
    if len(move) == 2:
        #loop through the pieces in the board
        for row in board:
            for piece in row:
                if piece != emptySquare:
                    #if the piece is a pawn and it is the same color as whose turn it is and it can move to the end location then return this pawn moving to the end location
                    if piece.color == turn and isinstance(piece, Pawn) and [endRow, endCol] in piece.getMoveset():
                        return (piece.square[0], piece.square[1], endRow, endCol)
    #pawn capture
    if move[0].lower() == move[0]:#if first char is lowercase
        #get start column from first char (stated in SAN)
        startCol = ord(move[0])-97
        #loop through rows in board and at the start col
        for row in board:
            #if it's a pawn and can make the move then return this pawn's move to end location
            if isinstance(row[startCol], Pawn):
                if [endRow, endCol] in row[startCol].getMoveset():
                    return (row[startCol].square[0], startCol, endRow, endCol)
    #a dictionary mapping the SAN characters for pieces to the white indices
    charToPieceMap = {
        "N":1,
        "B":2,
        "R":3,
        "Q":4,
        "K":5
    }
    #convert to black index if the piece is black
    index = charToPieceMap[move[0]] + (not turn)*6
    if len(move) == 4:#multi option piece move ex: (Ndxe5) --> this occurs when both knights can take on e5, "d" specifies which one (the one on the d column)
        #use the specified column as start column
        startCol = ord(move[1])-97
        #loop through the rows in the board at the specified column
        for row in board:
            if row[startCol] != emptySquare:
                #return the move if the piece index matches the SAN's piece index and if the piece can move to the end square
                if row[startCol].index == index and [endRow, endCol] in row[startCol].getMoveset():
                    return (row[startCol].square[0], startCol, endRow, endCol)
    #piece move
    #loop through the pieces on the board
    for row in board:
        for piece in row:
            if piece != emptySquare:
                #return the move if the piece index matches the SAN's piece index and if the piece can move to the end square
                if piece.index == index and [endRow, endCol] in piece.getMoveset():
                    return (piece.square[0], piece.square[1], endRow, endCol)
#this function converts a move in the (startRow, startCol, endRow, endCol) format to SAN for displaying the move to the user
def moveToSAN(startRow, startCol, endRow, endCol):
    #stores the piece's index
    pIndex = board[startRow][startCol].index
    #assume the column is undefined
    pieceInitCol = ''
    #loop through board for any piece with the same index
    for row in board:
        for piece in row:
            if piece != emptySquare:
                #skip the piece itself
                if piece == board[startRow][startCol]:
                    continue
                #if the piece has the same index and can also move to the end location legally then define the original column
                elif piece.index == board[startRow][startCol].index and [endRow, endCol] in piece.getMoveset():
                    if isLegal(piece.square[0], piece.square[1], endRow, endCol):
                        pieceInitCol = chr(startCol+97)
    #define a dictionary to translate piece indices into the SAN characters for pieces
    pieceToCharMap = {
        0:"",
        6:"",
        1:"N",
        7:"N",
        2:"B",
        8:"B",
        3:"R",
        9:"R",
        4:"Q",
        10:"Q",
        5:"K",
        11:"K"
    }
    #define capture?
    capture = board[endRow][endCol] != emptySquare
    #define the piece character using the dictionary above
    pieceChar = pieceToCharMap[pIndex]
    #declare the initial output with the piece/capture/endlocation
    output = pieceChar+pieceInitCol+'x'*capture+chr(endCol+97)+str(8-endRow)
    #use special castling symbols the move is castling (col changes by 2 for a king move)
    if pieceChar == "K":
        if endCol - startCol == 2:
            output = "O-O"
        elif endCol - startCol == -2:
            output = "O-O-O"
    #if a pawn is moving
    elif pieceChar == "":
        #add Q for promotion (there is no underpromotion so Q is default)
        if endRow == 0 or endRow == 8:
            output+="Q"
        #add start col for pawn capture
        if capture and len(pieceInitCol) == 0:
            output = chr(startCol+97)+output
    #test to see if the move was a check
    m = makeMove(startRow, startCol, endRow, endCol, True)
    if kings[not board[endRow][endCol].color].inCheck():
        #if it was add a + (b/c of the rules of SAN)
        output+="+"
    #undo the test move
    undoMove(m)
    #return the SAN move
    return output
#this function undoes a move made using a test struct returned by the makeMove function --> this is used when testing moves to return a board to its original state
def undoMove(test):
    #test struct: (startRow, startCol, endRow, endCol, target, blackKingCastled, whiteKingCastled, blackKingCastle, blackQueenCastle, whiteKingCastle, whiteQueenCastle, rookChange?, castleCase)
    startRow, startCol, endRow, endCol, target, kings[0].castled, kings[1].castled, kings[0].canKingCastle, kings[0].canQueenCastle, kings[1].canKingCastle, kings[1].canQueenCastle, rookChange, castleCase, enPassant, promoted = test
    #undo promotion
    if promoted:
        if board[endRow][endCol].color:
            board[endRow][endCol] = promoted
        else:
            board[endRow][endCol] = promoted
    #handle rook change
    if rookChange:
        board[endRow][endCol].moved = False
    #reset castling
    if castleCase == 2:
        board[endRow][0] = board[endRow][3]
        board[endRow][0].square = [endRow, 0]
        board[endRow][3] = emptySquare
    elif castleCase == 1:
        board[endRow][7] = board[endRow][5]
        board[endRow][7].square = [endRow, 7]
        board[endRow][5] = emptySquare
    #undo move
    board[startRow][startCol] = board[endRow][endCol]
    #if enPassant put captured pawn back
    if enPassant:
        board[endRow+(board[endRow][endCol].color*2-1)][endCol] = target
        board[endRow][endCol] = emptySquare
    else:
        board[endRow][endCol] = target
    board[startRow][startCol].square = [startRow,startCol]
#function that makes a move on the board returns test struct that can be used to undo test move 
#legalCheck(False by default) is when this function is called for a legality check or not (if it isn't then enPassant states need to be cleared as it the option only lasts for one move according to chess rules)
def makeMove(startRow, startCol, endRow, endCol, legalCheck=False):
    #test struct: (startRow, startCol, endRow, endCol, target, blackKingCastled, whiteKingCastled, blackKingCastle, blackQueenCastle, whiteKingCastle, whiteQueenCastle, rookChange?, castleCase, enPassant?)
    #clear all pawns enPassant states if this function is not called for a legalCheck
    if not legalCheck:
        for row in board:
            for piece in row:
                if isinstance(piece, Pawn):
                    piece.notifyEnPassant(False, -1)
    #test structure for undoing move in the undoMove function
    test = [startRow, startCol, endRow, endCol, board[endRow][endCol], kings[0].castled, kings[1].castled, kings[0].canKingCastle, kings[0].canQueenCastle, kings[1].canKingCastle, kings[1].canQueenCastle, False, 0, False, False]
    #if rook capture then update castle rights
    if isinstance(board[endRow][endCol], Rook):
        if endCol == 0:
            kings[board[endRow][endCol].color].canQueenCastle = False
        elif endCol == 7:
            kings[board[endRow][endCol].color].canKingCastle = False
    #move swap
    board[endRow][endCol] = board[startRow][startCol]
    board[endRow][endCol].square = [endRow,endCol]
    board[startRow][startCol] = emptySquare
    #if the king moved
    if isinstance(board[endRow][endCol], King):
        if endCol-startCol == 2:#king castle move rook
            board[endRow][5] = board[endRow][7]
            board[endRow][7] = emptySquare
            board[endRow][5].square = [endRow, 5]
            board[endRow][endCol].castled = True
            test[12] = 1
        elif endCol-startCol == -2:#queen castle move rook
            board[endRow][3] = board[endRow][0]
            board[endRow][0] = emptySquare
            board[endRow][3].square = [endRow, 3]
            board[endRow][endCol].castled = True
            test[12] = 2
        #king moved so cannot castle
        board[endRow][endCol].canKingCastle = False
        board[endRow][endCol].canQueenCastle = False
    #if the rook moved
    elif isinstance(board[endRow][endCol], Rook):
        test[11] = not board[endRow][endCol].moved #castle case update
        #change rook to has moved
        if not board[endRow][endCol].moved:
            board[endRow][endCol].moved = True
            #change castling rights since rook has moved
            if startCol == 7:
                kings[board[endRow][endCol].color].canKingCastle = False
            elif startCol == 0:
                kings[board[endRow][endCol].color].canQueenCastle = False
    #if a pawn has moved
    elif isinstance(board[endRow][endCol], Pawn):#pawn
        #white pawn promotion
        if board[endRow][endCol].color and endRow == 0:
            #keep track of pawn before promotion (to undo later)
            test[14] = board[endRow][endCol]
            #change the piece to a queen (no underpromotion yet)
            board[endRow][endCol] = Queen('♛', True, [endRow, endCol], 4)
        #black pawn promotion
        elif not board[endRow][endCol].color and endRow == 7:
            #keep track of pawn before promotion (to undo later)
            test[14] = board[endRow][endCol]
            #change the piece to a queen (no underpromotion yet)
            board[endRow][endCol] = Queen('♕', False, [endRow, endCol], 10)
        #enPassant
        elif abs(endRow-startRow) == 1 and abs(endCol-startCol) == 1 and test[4] == emptySquare:
            #keep track of the pawn that is captured by enPassant to undo in undoMove function
            test[4] = board[endRow+(board[endRow][endCol].color*2-1)][endCol]
            #remove the pawn
            board[endRow+(board[endRow][endCol].color*2-1)][endCol] = emptySquare
            #set enPassant state to true in the test struct for the undoMove function
            test[13] = True
    #if a pawn moves up two give enPassant rights to adjacent pawns
    if (endCol + 1) < 8:
        if isinstance(board[endRow][endCol], Pawn) and abs(endRow-startRow) == 2 and board[endRow][endCol+1] != emptySquare:
            if isinstance(board[endRow][endCol+1], Pawn) and board[endRow][endCol+1].color != board[endRow][endCol].color:
                board[endRow][endCol+1].notifyEnPassant(True, endCol)
    #if a pawn moves up two give enPassant rights to adjacent pawns
    if (endCol - 1) > 0:
        if isinstance(board[endRow][endCol], Pawn) and abs(endRow-startRow) == 2 and board[endRow][endCol-1] != emptySquare:
            if isinstance(board[endRow][endCol-1], Pawn) and board[endRow][endCol-1].color != board[endRow][endCol].color:
                board[endRow][endCol-1].notifyEnPassant(True, endCol)
    #return the test struct used to undo the move
    return test
#this function returns the true legality of a psuedo-legal move generated by piece.getMoveset() (psuedo-legal are all the moves in a pieces range), (true legal is the other rules like cannot move in check etc.)
def isLegal(startRow, startCol, endRow, endCol):
    #if castle through and while in check return False
    if isinstance(board[startRow][startCol], King):
        if endCol - startCol == 2:#king castle
            if not isLegal(startRow, startCol, endRow, endCol-1) or board[startRow][startCol].inCheck():
                return False
        elif endCol - startCol == -2:#queen castle
            if not isLegal(startRow, startCol, endRow, endCol+1) or board[startRow][startCol].inCheck():
                return False
    #try move
    testMove = makeMove(startRow, startCol, endRow, endCol, True)
    #if the king is in check after the move, then the move is illegal
    legal = not kings[board[endRow][endCol].color].inCheck()
    #undo move
    undoMove(testMove)
    #return legality
    return legal
#get the psuedo-legal moves for a knight
def getKnightMoveset(self):
        #set the 8 squares in a moves list from the the knight's start square
        moves = [
            [self.square[0]+1, self.square[1]+2],
            [self.square[0]+1, self.square[1]-2],
            [self.square[0]-1, self.square[1]+2],
            [self.square[0]-1, self.square[1]-2],
            [self.square[0]+2, self.square[1]+1],
            [self.square[0]+2, self.square[1]-1],
            [self.square[0]-2, self.square[1]+1],
            [self.square[0]-2, self.square[1]-1],
        ]
        #add out of board moves to the remove list
        filteredMoves = []
        for move in moves:
            #if in bounds
            if move[0] > -1 and move[0] < 8 and move[1] > -1 and move[1] < 8:
                if board[move[0]][move[1]] != emptySquare:
                    if board[move[0]][move[1]].color != self.color:
                        filteredMoves.append(move)
                else:
                    filteredMoves.append(move)
        return filteredMoves
#set the function to the Knight's moveset method
Knight.getMoveset = getKnightMoveset
#get the psuedo-legal moves for a King
def getKingMoveset(self):
        #initial surrounding squares from the King's square
        moves = [
            [self.square[0]+1, self.square[1]+1],
            [self.square[0]+1, self.square[1]],
            [self.square[0]+1, self.square[1]-1],
            [self.square[0], self.square[1]+1],
            [self.square[0], self.square[1]-1],
            [self.square[0]-1, self.square[1]-1],
            [self.square[0]-1, self.square[1]],
            [self.square[0]-1, self.square[1]+1],
        ]
        #add king castling if there is a path
        if self.canKingCastle:
            if board[self.square[0]][self.square[1]+1] == emptySquare and board[self.square[0]][self.square[1]+2] == emptySquare:
                moves.append([self.square[0], self.square[1]+2])
        #add queen castling if there is a path
        if self.canQueenCastle:
            if board[self.square[0]][self.square[1]-1] == emptySquare and board[self.square[0]][self.square[1]-2] == emptySquare:
                moves.append([self.square[0], self.square[1]-2])
        #remove out of board or piece blocked moves
        filteredMoves = []
        for move in moves:
            #if in bounds and the target square is not a piece of the same color add to filtered moves list
            if move[0] > -1 and move[0] < 8 and move[1] > -1 and move[1] < 8:
                if board[move[0]][move[1]] != emptySquare:
                    if board[move[0]][move[1]].color != self.color:
                        filteredMoves.append(move)
                else:
                    filteredMoves.append(move)
        #return filteredMoves list
        return filteredMoves
#set this function to the getMoveset king method
King.getMoveset = getKingMoveset
#get the psuedo-legal moves for a bishop
def getBishopMoveset(self):
        #empty move list
        moves = []
        #add squares in the +, + direction (until there is an enemy piece (then include and exit) or friendly piece (then exit))
        for i in range(1, min(8-self.square[0], 8-self.square[1])):
            if board[self.square[0]+i][self.square[1]+i] == emptySquare:
                moves.append([self.square[0]+i, self.square[1]+i])
            elif board[self.square[0]+i][self.square[1]+i].color != self.color:
                moves.append([self.square[0]+i, self.square[1]+i])
                break
            else:
                break
        #add squares in the -, - direction (until there is an enemy piece (then include and exit) or friendly piece (then exit))
        for i in range(1, min(self.square[0]+1, self.square[1]+1)):
            if board[self.square[0]-i][self.square[1]-i] == emptySquare:
                moves.append([self.square[0]-i, self.square[1]-i])
            elif board[self.square[0]-i][self.square[1]-i].color != self.color:
                moves.append([self.square[0]-i, self.square[1]-i])
                break
            else:
                break
        #add squares in the -, + direction (until there is an enemy piece (then include and exit) or friendly piece (then exit))
        for i in range(1, min(8-self.square[1], self.square[0]+1)):
            if board[self.square[0]-i][self.square[1]+i] == emptySquare:
                moves.append([self.square[0]-i, self.square[1]+i])
            elif board[self.square[0]-i][self.square[1]+i].color != self.color:
                moves.append([self.square[0]-i, self.square[1]+i])
                break
            else:
                break
        #add squares in the +, - direction (until there is an enemy piece (then include and exit) or friendly piece (then exit))
        for i in range(1, min(8-self.square[0], self.square[1]+1)):
            if board[self.square[0]+i][self.square[1]-i] == emptySquare:
                moves.append([self.square[0]+i, self.square[1]-i])
            elif board[self.square[0]+i][self.square[1]-i].color != self.color:
                moves.append([self.square[0]+i, self.square[1]-i])
                break
            else:
                break
        #return moves list
        return moves
#set the bishop move generation method of the Bishop class
Bishop.getMoveset = getBishopMoveset
#psuedo-legal move generation for rook
def getRookMoveset(self):
        #empty moves list
        moves = []
        #add squares in the +col direction (until there is an enemy piece (then include and exit) or friendly piece (then exit))
        for i in range(self.square[1]+1, 8):
            if board[self.square[0]][i] == emptySquare:
                moves.append([self.square[0], i])
            elif self.color != board[self.square[0]][i].color:
                moves.append([self.square[0], i])
                break
            else:
                break
        #add squares in the -col direction (until there is an enemy piece (then include and exit) or friendly piece (then exit))
        for i in range(self.square[1]-1, -1, -1):
            if board[self.square[0]][i] == emptySquare:
                moves.append([self.square[0], i])
            elif self.color != board[self.square[0]][i].color:
                moves.append([self.square[0], i])
                break
            else:
                break
        #add squares in the +row direction (until there is an enemy piece (then include and exit) or friendly piece (then exit))
        for i in range(self.square[0]+1, 8):
            if board[i][self.square[1]] == emptySquare:
                moves.append([i, self.square[1]])
            elif self.color != board[i][self.square[1]].color:
                moves.append([i, self.square[1]])
                break
            else:
                break
        #add squares in the -row direction (until there is an enemy piece (then include and exit) or friendly piece (then exit))
        for i in range(self.square[0]-1, -1, -1):
            if board[i][self.square[1]] == emptySquare:
                moves.append([i, self.square[1]])
            elif self.color != board[i][self.square[1]].color:
                moves.append([i, self.square[1]])
                break
            else:
                break
        #return moves list
        return moves
#set getMoveset method for rook to the moveset function
Rook.getMoveset = getRookMoveset
#get psuedo-legal moves for the Queen
def getQueenMoveset(self):
        #moveset list
        moves = []
        #rook moves
        for i in range(self.square[1]+1, 8):
            if board[self.square[0]][i] == emptySquare:
                moves.append([self.square[0], i])
            elif self.color != board[self.square[0]][i].color:
                moves.append([self.square[0], i])
                break
            else:
                break
        for i in range(self.square[1]-1, -1, -1):
            if board[self.square[0]][i] == emptySquare:
                moves.append([self.square[0], i])
            elif self.color != board[self.square[0]][i].color:
                moves.append([self.square[0], i])
                break
            else:
                break
        for i in range(self.square[0]+1, 8):
            if board[i][self.square[1]] == emptySquare:
                moves.append([i, self.square[1]])
            elif self.color != board[i][self.square[1]].color:
                moves.append([i, self.square[1]])
                break
            else:
                break
        for i in range(self.square[0]-1, -1, -1):
            if board[i][self.square[1]] == emptySquare:
                moves.append([i, self.square[1]])
            elif self.color != board[i][self.square[1]].color:
                moves.append([i, self.square[1]])
                break
            else:
                break
        #bishop moves
        for i in range(1, min(8-self.square[0], 8-self.square[1])):
            if board[self.square[0]+i][self.square[1]+i] == emptySquare:
                moves.append([self.square[0]+i, self.square[1]+i])
            elif board[self.square[0]+i][self.square[1]+i].color != self.color:
                moves.append([self.square[0]+i, self.square[1]+i])
                break
            else:
                break
        for i in range(1, min(self.square[0]+1, self.square[1]+1)):
            if board[self.square[0]-i][self.square[1]-i] == emptySquare:
                moves.append([self.square[0]-i, self.square[1]-i])
            elif board[self.square[0]-i][self.square[1]-i].color != self.color:
                moves.append([self.square[0]-i, self.square[1]-i])
                break
            else:
                break
        for i in range(1, min(8-self.square[1], self.square[0]+1)):
            if board[self.square[0]-i][self.square[1]+i] == emptySquare:
                moves.append([self.square[0]-i, self.square[1]+i])
            elif board[self.square[0]-i][self.square[1]+i].color != self.color:
                moves.append([self.square[0]-i, self.square[1]+i])
                break
            else:
                break
        for i in range(1, min(8-self.square[0], self.square[1]+1)):
            if board[self.square[0]+i][self.square[1]-i] == emptySquare:
                moves.append([self.square[0]+i, self.square[1]-i])
            elif board[self.square[0]+i][self.square[1]-i].color != self.color:
                moves.append([self.square[0]+i, self.square[1]-i])
                break
            else:
                break
        #return the bishop and rook moves
        return moves
#set the Queen class moveset method to the function above
Queen.getMoveset = getQueenMoveset
def getPawnMoveset(self):
        #add one square forward to the move list
        #remove move if there piece in front
        if not ((self.square[0]-(self.color*2-1)) > 7 or (self.square[0]-(self.color*2-1)) < 0):
            if board[self.square[0]-(self.color*2-1)][self.square[1]] != emptySquare:
                    moves = []
            else:
                moves = [[self.square[0]-(self.color*2-1), self.square[1]]]
        else:
            moves = []
        #two square move check if there is not an opposite colored piece there
        if self.color:#white
            if self.square[0] == 6:
                if board[4][self.square[1]] == emptySquare and board[5][self.square[1]] == emptySquare:
                    moves.append([4, self.square[1]])
        else:
            if self.square[0] == 1:
                if board[3][self.square[1]] == emptySquare and board[2][self.square[1]] == emptySquare:
                    moves.append([3, self.square[1]])
        #check for enPassant
        if self.enPassant:
            moves.append([self.square[0]-(self.color*2-1), self.enPassantCol])
        #check for captures
        if self.square[1] != 7 and not ((self.square[0]-(self.color*2-1)) > 7 or (self.square[0]-(self.color*2-1)) < 0):
            if board[self.square[0]-(self.color*2-1)][self.square[1]+1] != emptySquare:
                if board[self.square[0]-(self.color*2-1)][self.square[1]+1].color != self.color:
                    moves.append([self.square[0]-(self.color*2-1), self.square[1]+1])
        if self.square[1] != 0 and not ((self.square[0]-(self.color*2-1)) > 7 or (self.square[0]-(self.color*2-1)) < 0):
            if board[self.square[0]-(self.color*2-1)][self.square[1]-1] != emptySquare:
                if board[self.square[0]-(self.color*2-1)][self.square[1]-1].color != self.color:
                    moves.append([self.square[0]-(self.color*2-1), self.square[1]-1])
        #return the moveset
        return moves
#set this function to the getMoveset method of the Pawn class
Pawn.getMoveset = getPawnMoveset
#this is the function that does a heuristic evalution of the current board (base case in the recursive tree)
def evaluate(turn):#turn 0 is black turn; turn 1 is white turn
    #initialize evaluation
    eval = 0
    #return large numbers for checkmate
    #generate all possible legal moves
    canMove = False
    #loop through pieces in the board to see if they can move
    for row in board:
        if canMove:
            break
        for piece in row:
            if canMove:
                break
            if piece != emptySquare:
                if piece.color == turn:
                    for move in piece.getMoveset():
                        if isLegal(piece.square[0], piece.square[1], move[0], move[1]):
                            canMove = True
                            break
    #if the pieces cannot move
    if not canMove:
        if kings[turn].inCheck():#"infinite" evaluation for checkmate
            return (-99999 * (turn*2-1))\
        #0 eval for stalemate (it is a draw)
        return 0
    #loop through pieces and count material and square table position bonus per piece
    for row in board:
        for piece in row:
            if piece != emptySquare:
                squareTable = piece.table[piece.color]
                eval += piece.material * (piece.color*2-1) + (enhancedEval * (squareTable[piece.square[0]][piece.square[1]] * (piece.color*2-1)))
    #return final eval
    return eval
#print board function for testing purposes of the chess engine --> prints the board and returns the board as a string w/ no spaces
def printBoard():
    #initialize return value
    output = ""
    #loop through squares in the board
    for row in board:
        for piece in row:
            #print the emptySquare character if the square is empty
            if piece == emptySquare:
                print(emptySquare, end=" ")
                output+=emptySquare
            #print the piece's character otherwise
            else:
                print(piece.char, end=" ")
                output+=piece.char
        #add a new line between each row
        print("", end = "\n")
    #return the string representation of the board as output
    return output
#initialize the move transposition table as a hash map for hashes and their respective evaluations at recorded depth
moveTranspositionTable = {
}
#initialize global variables for tracking iterative deepening
doneSearching = False
#define a node of the recursive tree
class TreeNode:
    def __init__(self, move, color, depth, alpha=-99999, beta=99999):
        global doneSearching
        global startSearchTime
        self.move = move
        self.color = color
        self.depth = depth
        self.eval = (self.color * 2 - 1) * 99999
        if perf_counter()-startSearchTime > maxTime:
            doneSearching = True
        self.hasLegalMoves = False
        if self.depth > 0:
            #make move
            startRow, startCol, endRow, endCol = self.move
            testMove = makeMove(startRow, startCol, endRow, endCol)
            moveHash = computeHash(ZobristTable)
            if moveHash in moveTranspositionTable.keys():
                values = moveTranspositionTable[moveHash]
                if values[1] >= self.depth and values[0] == self.color:
                    self.eval = values[2]
                    undoMove(testMove)
                    return
            #find all children
            for row in board:
                for piece in row:
                    if piece != emptySquare:
                        if piece.color != self.color:
                            for move2 in piece.getMoveset():
                                if isLegal(piece.square[0], piece.square[1], move2[0], move2[1]):
                                    self.hasLegalMoves = True
                                    if self.color:
                                        self.eval = min(self.eval, TreeNode([piece.square[0], piece.square[1], move2[0], move2[1]], not self.color, self.depth-1, alpha, beta).eval)
                                        if self.eval < alpha:
                                            undoMove(testMove)
                                            return
                                        beta = min(beta, self.eval)
                                    else:
                                        self.eval = max(self.eval, TreeNode([piece.square[0], piece.square[1], move2[0], move2[1]], not self.color, self.depth-1, alpha, beta).eval)
                                        if self.eval > beta:
                                            undoMove(testMove)
                                            return
                                        alpha = max(alpha, self.eval)
            if not self.hasLegalMoves:
                if kings[not self.color].inCheck():
                    self.eval = -99999 * (self.color*2-1)
                else:
                    self.eval = 0
            #add current position hash:eval to table
            moveTranspositionTable[moveHash] = (self.color, self.depth, self.eval)
            #undo move
            undoMove(testMove)
        else:
            #make move
            startRow, startCol, endRow, endCol = self.move
            testMove = makeMove(startRow, startCol, endRow, endCol)
            #find eval
            self.eval = evaluate(self.color)
            #undo move
            undoMove(testMove)
def blackMove(SANmove):
    global startSearchTime
    startSearchTime = perf_counter()
    global openingDatabase
    if openingDatabase:
        global games
        newGames = []
        for game in games:
            if game[:len(SANmove)] == SANmove:
                newGames.append(game[len(SANmove)+1:])#remove comma as well
        if len(newGames) == 0:
            openingDatabase = False
        if openingDatabase:
            x = randint(0, len(newGames)-1)
            lenBestMove = newGames[x].find(',')
            bestSANMove = newGames[x][:lenBestMove]
            bestMove = SANtoMove(bestSANMove, 0)
            games.clear()
            for newGame in newGames:
                if newGame[:lenBestMove] == bestSANMove:
                    games.append(newGame[lenBestMove+1:])#remove comma as well
            return (bestMove, 0)
    #generate all possible legal moves
    moves = []
    for row in board:
        for piece in row:
            if piece != emptySquare:
                if not piece.color:
                    for move in piece.getMoveset():
                        if isLegal(piece.square[0], piece.square[1], move[0], move[1]):
                            moves.append((piece.square[0], piece.square[1], move[0], move[1]))
    if len(moves) == 0:
            if kings[0].inCheck():
                print("White wins!")
            else:
                print("Draw by Stalemate")
            quit()
    if randomMove:#random moves (difficulty 1)
        x = randint(0, len(moves)-1)
        return (moves[x], 0)
    else:
        global doneSearching
        #generate depth 1 search moves
        roots = [TreeNode(mov, 0, 1) for mov in moves]
        moveEvalPairs = [(root.eval, root.move) for root in roots]
        d=1
        #iterative deepening
        while 1:
            roots.clear()
            d+=1
            moveEvalPairs.sort(reverse = True)
            #generate roots
            searchTime = perf_counter()
            for val, mov in moveEvalPairs:
                    if doneSearching:
                        roots.clear()
                        break
                    node = TreeNode(mov, 0, d-1)
                    roots.append(node)
            if doneSearching:
                break
            bestEval = 100000
            for root in roots:
                if root.eval < bestEval:
                    bestEval = root.eval
                    bestMove = root.move
            moveEvalPairs.clear()
            moveEvalPairs = [(root.eval, root.move) for root in roots]
            print(f"{d}: {perf_counter()-searchTime}")
        print("done searching")
        doneSearching = False
        return (bestMove, bestEval)
#init all pawns' en Passant
for row in board:
    for piece in row:
        if isinstance(piece, Pawn):
            piece.notifyEnPassant(False, -1)
#init board and game state variables
printBoard()
positionCounter = {}
moveSinceCapture = 0
endgame = False
#initialize opening book from openingBook.txt file (compiled from https://www.pgnmentor.com/files.html#openings)
if openingDatabase:
    print("Started Compiling Opening Book")
    with open("openingBook.txt", "r") as f:
        games = [line.rstrip() for line in f]
        games.pop(0)
        f.close()
print("Done Compiling Opening Book")
#run main code in loop:
while 1:
    pawnMove = False
    emptyCount = board.count(emptySquare)
    while 1:#while input is bad keep asking
        strMove = input("Your move: ")[:4]
        try:
            startRow, endRow = 7 - (int(strMove[1])-1), 7 - (int(strMove[3])-1)
            startCol, endCol = ord(strMove[0])-97, ord(strMove[2])-97
        except:
            continue
        if board[startRow][startCol] == emptySquare:
            continue
        if not board[startRow][startCol].color:
            continue
        if not [endRow,endCol] in board[startRow][startCol].getMoveset():
            continue
        if not isLegal(startRow, startCol, endRow, endCol):
            continue
        break
    #print SAN(standard algebraic notation) move
    SANmove = moveToSAN(startRow, startCol, endRow, endCol)
    print(f"Playing {SANmove}")
    makeMove(startRow, startCol, endRow, endCol)
    if isinstance(board[endRow][endCol], Pawn):
        pawnMove = True
    displayBoard = printBoard()
    try:
        positionCounter[displayBoard] += 1
        if positionCounter[displayBoard] == 3:
            print("Draw by 3-fold Repetition")
            quit()
    except:
        positionCounter[displayBoard] = 1
    print("Thinking... ", end = "")
    response, currentEvaluation = blackMove(SANmove)
    print(f"Playing {moveToSAN(response[0],response[1],response[2],response[3])}")
    print("+"*(currentEvaluation>=0)+str(currentEvaluation/100))
    makeMove(response[0], response[1], response[2], response[3])
    displayBoard = printBoard()
    try:
        positionCounter[displayBoard] += 1
        if positionCounter[displayBoard] == 3:
            print("Draw by 3-fold Repetition")
            quit()
    except:
        positionCounter[displayBoard]  = 1
    if isinstance(board[response[2]][response[3]], Pawn):
        pawnMove = True
    if board.count(emptySquare) != emptyCount or pawnMove:
        moveSinceCapture = 0
    moveSinceCapture += 1
    if moveSinceCapture == 50:
        print("Draw by 50 move rule")
        quit()
    if displayBoard.count('♜') == 0 and displayBoard.count('♖') == 0 and displayBoard.count('♛') == 0 and displayBoard.count('♕') == 0 and displayBoard.count('♟︎') == 0 and displayBoard.count('♙') == 0 and displayBoard.count('♝') + displayBoard.count('♞') <= 1 and displayBoard.count('♗') + displayBoard.count('♘') <= 1:
        print("Draw by insufficient material")
        quit()
    #define endgame
    '''
    Both sides have no queens or
    Every side which has a queen has additionally no other pieces or one minorpiece maximum.    
    '''
    if ((displayBoard.count('♛') == 0) or (displayBoard.count('♜') == 0 and displayBoard.count('♝') + displayBoard.count('♞') <= 1)) and ((displayBoard.count('♕') == 0) or (displayBoard.count('♖') == 0 and displayBoard.count('♗') + displayBoard.count('♘') <= 1)):
        print("its endgame now")
        endgame = True
        King.table[1] = King.tableEndgame
        King.table[0] = King.tableEndgameReverse