I'm building my own chess engine in Python But I've got stuck

I have  a rather simple chess endgame Python code implementinng `negamax strategy` given below but it behaves strange.
Negamax means that when both players play fully rationally the best move leading to the quickest mate or the longest defense by both sides.
It prints correctly this position, 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 **huh** 

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:
[python]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")[/python]

First i have to say that i do not fully understand your code, because i dont speak Czech. Also i think your "negamax" algorithm is called minimax (its the same as the one i once programmed and i the tutorials i followed it was called minimax)

But I found your mistake. Your evaluate_board function does only check for draw or checkmate. If none of both conditions are met, it returns None. Then in your negamax function if the evaluation is None and if the depth == 0, 0 gets returned.

So your engine thinks the position is a draw no matter what. You will need some logic to actually evaluate the position. You should rewrite this:

to something like this:

You are already checking if the game is over before your if statement, so you can remove board.is_game_over(). Then you will have to write logic to assign a given position a value which determines if the position is good or bad. I would recommend to count the pieces for the beginning

Also i have to add, that python isn´t the best programming language to write a chess engine, because its performance sucks. If you want to get serious about the strength of your engine you should take a faster language like c++.

Agreed. Though you can improve the python performance by using pypy which does just in time compilation. You can expect about a 3 to 4x performance improvement.

Thank you very much for your help. What I intended to do is to evaluate **up to the very end** the negamax logic. I want the fully search the tree of the game with very few pieces, always at most 5. So I do not need the refined version

if depth == 0:
 return countpieces(board)

because in case my engine doesn't evaluate the position as lost, nothing else matters to me.

Not even evaluating as a lost is deemed to be the same result for me, I'm also interested

in how many moves I'm able to survive with my previous move.

In case the position is lost, I'm trying survive as long as theoretically possible. I believe that the negamax logic is appropriate here. Also , I do not care about slowing down up to any reasonable number,, be it 10 times slower than C++, or 100 times slower. In case I were interested in efficiency I would use Python wrapper together with StockFish :-)

So to resume my question now: I would like to understand why my engine doesn't output `Kb2c2` which is `the only move protecting p from promoting to black q`.

Not only that it doesn't suggest it, it even doesn't consider it!

Feel free to copy in here any Czech sentence you need to understand to help me!

*A post-note* Your advice to change

if depth == 0:
 return countpieces(board)

strangely enough , works. But why, if I'm consistently searching for the entire game space,

this at least partially solves my problem ?

Also, finally, would it work even better if I distinguished how many white and how many black pieces are there on the board , while taking into account whose turn is it: black's or white's ?

You only search for 11 ply (your depth). If you do not take the pawn, it is mate in 10 moves. The diffrence between ply and moves is, that ply is a turn, while a move is one ply from white and one from black. And the depth variable in chess engines (also yours) is in ply. So technically your program only searches for 4.5 moves into the future.

Obviosly there is no mate and the program thinks everything is a draw. If you want to go on with your idea, you have to remove the depth variable. Then it would calculate until the games finishes.

But if you do this, i would still recommend you to write a simple evaluation function to order the moves you want to look at because you do not want to calculate that a rook promotion happens and the next 50 moves the kings moving aimlessly around.

OK. But this code https://pastebin.com/vuriKiys suggests h8g8 which is not best move, please see below !

And the move is not even diplayed, the position is still the initial one.

Could you correct that link code to be a good one and paste it on the pastebin and give me a link to it here ? Thank you.

Počáteční pozice: (Start position)
. . . . . . . K
. . . . . . . .
k . P . . . . .
. . . . . . . p
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .

Prohledaných pozic: 38716906 Čas: 0d 01h 10m 33s
Historie tahů od nejlepšího k počátečnímu:
. . . . . . . K
. . . . . . . .
k . P . . . . .
. . . . . . . p
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .

Nejlepší tah je: h8g8

Konec hry

Why ka6 moves to ka7 instead of ph4 ?

Isn't ph4 more optimal for black?

The oputput is here and the code what has achieved below:

Output:

Počáteční pozice:
. . . . . . . K
. . . . . . . .
k . P . . . . .
. . . . . . . p
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .

Prohledaných pozic: 43661880 Čas: 0d 02h 19m 22sPo tahu:
. . . . . . . .
. . . . . . K .
k . P . . . . .
. . . . . . . p
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .

Prohledaných pozic: 165219395 Čas: 0d 08h 41m 57sPo tahu:
. . . . . . . .
k . . . . . K .
. . P . . . . .
. . . . . . . p
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .

Prohledaných pozic: 275368567 Čas: 0d 14h 35m 14s

Code:

import chess
import time
import threading

positions_count = 0
stop_thread = False

def count_pieces(board):
"""Spočítá a vrátí počet figurek na šachovnici."""
count = 0
for square in chess.SQUARES:
if board.piece_at(square):
count += 1
return count

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"

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

def evaluate_material(board):
"""Vrátí celkovou hodnotu materiálu na šachovnici."""
piece_values = {chess.PAWN: 1, chess.KNIGHT: 3, chess.BISHOP: 3, chess.ROOK: 5, chess.QUEEN: 9, chess.KING: 0}
total_value = 0
for square in chess.SQUARES:
piece = board.piece_at(square)
if piece:
value = piece_values[piece.piece_type]
if piece.color == chess.WHITE:
total_value += value
else:
total_value -= value
return total_value

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 color * evaluate_material(board)

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

# ... (Předchozí definice funkcí zůstávají stejné) ...

def find_and_execute_best_move(board, depth):
"""Najde a provede nejlepší tah na šachovnici."""
best_move, move_history = find_best_move(board, depth)
if best_move:
board.push(best_move)
print("Po tahu:")
print(board)
print()
return best_move

start_position = "7K/8/k1P5/7p/8/8/8/8 w - - 0 1"
board = chess.Board(start_position)
depth = 13

start_time = time.time()
print("Počáteční pozice:")
print(board)
print()

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

while not board.is_game_over():
find_and_execute_best_move(board, depth)
if board.is_checkmate() or board.is_stalemate() or board.can_claim_draw():
break

stop_thread = True

print("Konec hry")
if board.is_checkmate():
print("Mat!")
elif board.is_stalemate() or board.can_claim_draw():
print("Remíza!")

stop_thread = True