I’m developing the game fianco (very similar to checkers) in Python and I’m trying to implement the Negamax with alpha beta pruning algorithm but as of now it’s not working as expected. It doesn’t perform the best moves when it should and I can’t understand why. Below you can find the algorithm as well as a very simple evaluation function. The undo and apply_move function are working correctly as well as the generation of the moves.

def negamax(self, board, depth, alpha, beta, color):
        # Base case: if depth is 0 or the game has a winner, return evaluation
        self.log.debug(f"Score:")
        if depth == 0 or board.is_winner() is not None:
            evaluation = color * board.evaluate()  # Multiply by color to get perspective
            return evaluation, None
        
        best_score = -float("inf")
        best_move = None

        normal_moves, captures = board.get_valid_moves_and_captures(board.current_player)
        moves = captures if captures else normal_moves

        for move in moves:
            self.log.debug(f"Valid moves: {moves}")
            self.log.debug(f"Board before move:n {board.board}")
            board.apply_move(move)
            self.log.debug(f"Board after move: {move} by color {color}n {board.board}")            
            score = -self.negamax(board, depth - 1, -beta, -alpha, -color)[0]
            self.log.debug(f"Evaluating move {move} for color {color}: Current best score = {best_score}, Alpha = {alpha}, Beta = {beta}")
            board.undo()  # Undo the move and switch player back
            self.log.debug(f"Board after undo:n {board.board}")
            if score > best_score:
                best_score = score
                best_move = move
            
            alpha = max(alpha, score)
            if alpha >= beta:
                break

        return best_score, best_move

def evaluate(self):
        white_score = 0
        black_score = 0
        winner = self.is_winner()

        if winner == 1:
            return 1500  # High positive score for white win
        elif winner == 2:
            return -1500  # High negative score for black win

        # Calculate scores based on the number of stones
        white_stones = np.sum(self.board == 1)
        black_stones = np.sum(self.board == 2)

        white_score += white_stones * 10  # Each white stone has a base value
        black_score += black_stones * 10  # Each black stone has a base value

        # Additional scoring based on positioning
        for r in range(9):
            for c in range(9):
                if self.board[r, c] == 1:  # White
                    white_score += self.position_score(r, c, 1)
                elif self.board[r, c] == 2:  # Black
                    black_score += self.position_score(r, c, 2)


        # Final evaluation is white score minus black score
        white_score += random.randint(-5, 5)  # Add some randomness to the score
        black_score += random.randint(-5, 5)
        return white_score - black_score

    def position_score(self, r, c, player):
        """Calculate score based on position. Closer to the opponent's back row is better."""
        score = 0
        if player == 1:  # White
            score += 8 - r  # Bonus for being closer to row 8
        else:  # Black
            score += r  # Bonus for being closer to row 0
        return score