Alpha-Beta Pruning Minimax Chess Bot

I've written a chess bot that uses the minimax algorithm to play chess, even though I barely know how to play. What could possibly go wrong?

Minimax is a decision rule in game theory that seeks to minimize the possible loss of a situation, or in this case, to prevent the AI from being at a "disadvantage" with the player. The bot plays through a bunch of moves, determines how much of a loss they incur, and chooses a move with the lowest disadvantage.

My implementation is in Python and uses the python-chess library to create a chessboard.

So, let's look at the code. First, I set up the board as follows:

board = chess.Board()
values = {chess.PAWN: 1, chess.KNIGHT: 3, chess.BISHOP: 3, chess.ROOK: 5, chess.QUEEN: 9, chess.KING: 0}

To calculate advantage, I iterate through all of the pieces on the chess board and add or subtract their values from a running count depending on their color. By weighing more valuable pieces, you could be more nuanced, but I'm just going for simplicity.

def get_advantage(board):
    count = 0;
    piecemap = board.piece_map()

    for i in piecemap:
        val = values[piecemap[i].piece_type]

        if piecemap[i].color == chess.WHITE: count -= val
        if piecemap[i].color == chess.BLACK: count += val

    return count

Next, I implement the actual minimax functions. The following two recursive methods calculate how to maximize the bot's advantage throughout the game. The min() method iterates through all legal moves on the chess board, and for each one, it calculates the advantage of making that move with get_advantage(). Then, it calls the max() method with the updated state of the board, reducing a depth value by 1 (which I'll touch on in a moment). After iterating through all the moves, it returns the move with the minimum advantage. The max() method does the opposite, finding the maximum advantage for all possible moves.

def min(board, depth):
    vmin = 999
    for i in board.legal_moves:
        board.push(i)
        if (depth != 0):
            moveval = get_advantage(board) + max(board, depth - 1)
        else:
            board.pop()
            return 0

        if (moveval < vmin):
            vmin = moveval

        board.pop()

    return vmin

def max(board, depth):
    vmax = 999
    for i in board.legal_moves:
        board.push(i)
        if (depth != 0):
            moveval = get_advantage(board) + min(board, depth - 1)
        else:
            board.pop()
            return 0

        if (moveval > vmax):
            vmax = moveval

        board.pop()

    return vmax

So, what is the depth parameter doing? It controls how far into the future the bot foresees moves, controlling the depth of the search tree for the minimax algorithm. This algorithm would be infinitely recursive and computationally unfeasible if this parameter didn't exist.

In the following method, I calculate which move the bot should take based on our minimax values using a technique known as alpha-beta pruning. We iterate through legal moves again, calling our minimax method pair to find the advantage with a depth of 2. The depth of the search tree affects time complexity nonlinearly, so keep this value low if you don't want to wait 10 minutes for the bot's move. We then compile a set of moves that have the highest advantages into an array and randomly choose one of them.

def calculate_move(board):
    init_moves = []

    vmax = -999

    for i in board.legal_moves:
        board.push(i)

        moveval = min(board, 2) + get_advantage(board)

        if (moveval == vmax):
            init_moves.append(i)

        elif (moveval > vmax):
            init_moves.clear()
            init_moves.append(i)
            vmax = moveval

        board.pop()

    board.push(random.choice(init_moves))

Finally, we run the game loop as follows.

while check_over_condition(board) > 0:
    while True:
        try:
            print("Enter your move: ")
            move = input()
            board.push(chess.Move.from_uci(move));

            print("\nYour move")
            print(board)

            calculate_move(board)

            print("\nBot's move")
            print(board)

        except:
            print("Invalid move")

And that's it! We have a fully functioning minimax chess bot in Python. To play, enter the starting coordinate for your move and the end position. For example, moving a pawn forward by 2 would be 'b2b4.'