Chess Backtracking solution for endgames written in Python doesn't work fine

I have a rather simple chess endgame Python code implementing negamax strategy given below but it behaves quite strange. Negamax means that both players play fully rationally, i.e. the best move leading to the quickest mate or the longest defense as possible is carried out by both sides. It prints correctly this position in ASCII table, but the best move Kb2c2 is not even considered when I have printed all legal moves. I'm even unable to force the code consider at any stage of searching the best move by white king K. I would like if some can dig into the code and tell me what's wrong.

The output:

. . . . . . . . . . . k . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . K . p . . . . . . . . . . . .

Na tahu je: bílý (white to move in Czech language) b2c3 <LegalMoveGenerator at 0x1d473d26b50 (Ke8, Kd8, Kc8, Ke7, Kc7, Ke6, Kd6, Kc6, d1=Q, d1=R, d1=B, d1=N+)> <LegalMoveGenerator at 0x1d473d26250 (Kd4, Kc4, Kb4, Kd3, Kb3, Kxd2, Kc2, Kb2)> <LegalMoveGenerator at 0x1d473d24050 (Kf8, Kd8, Kf7, Ke7, Kd7, d1=Q+, d1=R+, d1=B, d1=N)> <LegalMoveGenerator at 0x1d473d25e10 (Ke5, Kd5, Kc5, Ke4, Kc4, Ke3, Kd3, Kc3)> <LegalMoveGenerator at 0x1d473d25110 (Kg8, Ke8, Kg7, Kf7, Ke7, d1=Q, d1=R, d1=B, d1=N)> <LegalMoveGenerator at 0x1d473d27110 (Kf6, Ke6, Kd6, Kf5, Kd5, Kf4, Ke4, Kd4)>

The code:

import chess
import time
import threading

# Globální proměnná pro sledování počtu prohledaných pozic
positions_count = 0

def update_positions_count(last_time_printed):
    global positions_count
    while not board.is_game_over():
        if time.time() - last_time_printed > 1:
            print(f"\rProhledaných pozic: {positions_count}", end='')
            last_time_printed = time.time()

def evaluate_board(board, depth):
    global positions_count
    positions_count += 1

    if board.is_checkmate():
        return 10000 - depth
    if board.is_stalemate() or board.can_claim_draw():
        return 0
    return None

# ... negamax, find_best_move ...
# Negamax algoritmus
def negamax(board, depth, alpha, beta, color):
    evaluated = evaluate_board(board, depth)
    if evaluated is not None:
        return color * evaluated

    if depth == 0 or board.is_game_over():
        return 0

    max_eval = float('-inf')
    print(board.legal_moves)
    for move in board.legal_moves:
        board.push(move)
        eval = -negamax(board, depth - 1, -beta, -alpha, -color)
        board.pop()
        max_eval = max(max_eval, eval)
        alpha = max(alpha, eval)
        if alpha >= beta:
            break

    return max_eval

def find_best_move(board, depth):
    best_move = None
    best_value = float('-inf')
    alpha = float('-inf')
    beta = float('inf')
    color = 1 if board.turn else -1

    print(f"Na tahu je: {'bílý' if board.turn else 'černý'}")

    for move in board.legal_moves:
        print(move.uci())  # Vypíše tahy ve formátu UCI
        if move.uci() == "c1c2":  # Příklad pro tah bílého krále
            print("HERE")
        board.push(move)
        board_value = -negamax(board, depth - 1, -beta, -alpha, -color)
        board.pop()

        if board_value > best_value:
            best_value = board_value
            best_move = move

    return best_move

# Hlavní část kódu
#start_position = "8/8/8/8/8/7Q/k7/2K5 w - - 0 1"
#start_position = "8/3k4/8/8/8/8/1K6/8 w - - 0 1"
start_position = "8/3k4/8/8/8/8/1K1p4/8 w - - 0 1"
board = chess.Board(start_position)
depth = 11  # Můžete zvážit snížení hloubky pro rychlejší výsledky
last_time_printed = time.time()

positions_count_thread = threading.Thread(target=update_positions_count, args=(last_time_printed,), daemon=True)
positions_count_thread.start()

print(board)
print()

while not board.is_game_over():
    best_move = find_best_move(board, depth)
    if best_move is not None:
        board.push(best_move)
        print("\n", board)  # Vytiskne šachovnici po provedení nejlepšího tahu
    else:
        print("Žádný další legální tah není možný.")
        break

print("\nKonec hry")

Also this program does have a similar bug:


%reset -f
import chess
import time
import threading

# Globální proměnné
positions_count = 0
stop_thread = False
start_time = time.time()

#positions_count = 0
positions_count_lock = threading.Lock()
#stop_thread = False

def update_positions_count_and_time():
    global positions_count, start_time
    while not stop_thread:
        elapsed_time = time.time() - start_time
        formatted_time = format_time(elapsed_time)
        print(f"\rProhledaných pozic: {positions_count} Čas: {formatted_time}", end='')
        time.sleep(1)

def format_time(seconds):
    """Převede sekundy na formát %dd %hh %mm %ss."""
    days, seconds = divmod(seconds, 86400)
    hours, seconds = divmod(seconds, 3600)
    minutes, seconds = divmod(seconds, 60)
    return f"{int(days)}d {int(hours):02d}h {int(minutes):02d}m {int(seconds):02d}s"

# ... (zbytek funkcí negamax a find_best_move) ...
def negamax(board, depth, alpha, beta, color, move_history):
    evaluated = evaluate_board(board, depth)
    if evaluated is not None:
        return color * evaluated

    if depth == 0 or board.is_game_over():
        return 0

    max_eval = float('-inf')
    for move in board.legal_moves:
        board.push(move)
        move_history.append(board.fen())
        eval = -negamax(board, depth - 1, -beta, -alpha, -color, move_history)
        board.pop()
        move_history.pop()
        if eval > max_eval:
            max_eval = eval
        alpha = max(alpha, eval)
        if alpha >= beta:
            break

    return max_eval

def find_best_move(board, depth):
    best_move = None
    best_value = float('-inf')
    alpha = float('-inf')
    beta = float('inf')
    color = 1 if board.turn else -1
    move_history = [board.fen()]

    for move in board.legal_moves:
        board.push(move)
        move_history.append(board.fen())
        board_value = -negamax(board, depth - 1, -beta, -alpha, -color, move_history)
        board.pop()
        move_history.pop()
        if board_value > best_value:
            best_value = board_value
            best_move = move

    return best_move, move_history

# def update_positions_count():
#     global positions_count
#     while not stop_thread:
#         with positions_count_lock:
#             print(f"\rProhledaných pozic: {positions_count}", end='')
#         time.sleep(1)

def evaluate_board(board, depth):
    global positions_count
    if board.is_checkmate():
        with positions_count_lock:
            positions_count += 1
        return 10000 - depth
    if board.is_stalemate() or board.can_claim_draw():
        with positions_count_lock:
            positions_count += 1
        return 0
    with positions_count_lock:
        positions_count += 1
    return None

# ... (zbytek funkcí negamax a find_best_move) ...

start_position = "8/3k4/8/8/8/8/1K1p4/8 w - - 0 1"
board = chess.Board(start_position)
depth = 9

print(board)

positions_count_thread = threading.Thread(target=update_positions_count_and_time, daemon=True)
positions_count_thread.start()

best_move, move_history = find_best_move(board, depth)
stop_thread = True

for fen in move_history[::-1]:
    print(chess.Board(fen))
    print()

if best_move is not None:
    print(f"Nejlepší tah je: {best_move.uci()}")
else:
    print("Žádný další legální tah není možný.")

print("\nKonec hry")


. . . . . . . .
. . . k . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. K . p . . . .
. . . . . . . .
Prohledaných pozic: 610556 Čas: 0d 00h 01m 27s. . . . . . . .
. . . k . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. K . p . . . .
. . . . . . . .

Nejlepší tah je: b2c3

Konec hry

paxx0 / paxx2

Chess Backtracking solution for endgames written in Python doesn't work fine #3