Minimax algorithm and checkers game

Question

I am implementing Checkers game using Minimax algorithm and Python. There are two players - both are computers. I was looking for a similar problem's solution but I could not find any and I have been struggling with it for few days. My entry point is this function:

def run_game(board):
    players = board.players
    is_move_possible = True
    move = 0
    while is_move_possible:
        is_move_possible = move_piece_minimax(board, players[move % 2])
        move += 1

It starts the game and calls the next function which is supposed to do the best move, basing on MiniMax algorithm, for the first player. After that first move, it calls this function for the second player and this loop will end once the game is won by one of the players. This function looks as following:

def move_piece_minimax(board, player):
    best_move = minimax(copy.deepcopy(board), player, 0)
    if best_move.score == +infinity or best_move.score == -infinity:
        return False
    move_single_piece(board.fields, player, best_move)
    return True

The first line calls the MiniMax algorithm, which I will describe later, and is supposed to find the best possible move for the player. I am passing a deep copy of whole board here, as I do not want the original one to be edited during execution of MiniMax algorithm. The condition checks for a win condition so if either maximizing player wins or minimizing one. If none of them won, best_move is performed. Moving to the main problem here, I implemented MiniMax algorithm as following:

def minimax(board, player, depth):
    best_move = Move(-1, -1, -infinity if player.name == PLAYER_NAMES['P1'] else +infinity)

    if depth == MAX_SEARCH_DEPTH or game_over(board):
        score = evaluate(board)
        return Move(-1, -1, score)

    for correct_move in get_all_correct_moves(player, board.fields):
        x, y, piece = correct_move.x, correct_move.y, correct_move.piece
        move_single_piece(board.fields, player, correct_move)
        player_to_move = get_player_to_move(board, player)
        move = minimax(board, player_to_move, depth + 1)    # <--- here is a recursion
        move.x = x
        move.y = y
        move.piece = piece

        if player.name == PLAYER_NAMES['P1']:
            if move.score > best_move.score:
                best_move = move  # max value
        else:
            if move.score < best_move.score:
                best_move = move  # min value

    return best_move

I decided that player 'P1' is a maximizing player and player 'P2' is a minimizing one. Starting from the first line, best_move variable holds a reference to a Move object which has the following fields:

class Move:
    def __init__(self, x, y, score, piece=None):
        self.x = x
        self.y = y
        self.score = score
        self.piece = piece

I am initializing best_move.score to -Infinity in case of the maximizing player and to +Infinity otherwise.

The first condition checks if depth reached the maximal level(for testing purposes it is set to 2) or the game is over. If yes, it evaluates current board's situation and returns a Move object holding current board's score. Otherwise, my algorithm looks for all legal/correct moves for the player and performs the first one.

After performing it, this function is called in a recursive manner but with incremented depth and changed moving player. The function runs again with changing parameters until the first if condition executes.

Once the execution goes to that branch, the board's evaluation score is returned and later, in a for loop after recursive call, coordinates x, y and a piece, which was moved, are assigned to a Move object.

Last conditions check if the new score is a better score for that specific player. If this is a maximizing player, so in my case P1, it checks if new score is higher that the previous one. In the case of minimizing player, the algorithm looks for the lowest score.

After performing all correct moves for that player, my algorithm should return one best_move.

Expected result
Single object of a Move class with coordinates x and y, evaluated board's score, which is +Infinity/-Infinity only in a case of win for one of the players, and an object of Piece class which will be moved to [x, y] coordinates.

Actual result
Single object of Move class with coordinates x and y, evaluated board's score which is equal to +Infinity after first call of MiniMax function. None of pieces changed its position so the game is not over yet. However, score is +Infinity so function move_piece_minimax() will return False - meaning no more moves are possible. Therefore, my program will stop execution with no changes on the board. Here is the screenshot of initial and final board's states - nothing is changed during exectuion as the first call returns +Infinity.

My question is, what I missed during implementation of MiniMax algorithm? Did I make any mistake? I am also open to any code improvements or suggestions. If any additional functions will be needed for you to understand my implementation, I will provide them. Thank you!

Answer 1

In the minimax function, you should do either of the following

1. Make a copy of your board before placing pieces

2. Remove the placed piece after recursively calling your minimax function

Otherwise your board will be getting filled with pieces with recursion and you'll receive an error stating that there's no moves left. Minimax is meant to do in-depth searching by placing pieces, so you should implement a method so it doesn't modify your original board.