# Why this Python code for a simple endgame yields wrong results?

I have a Python code as below for a trivial (for a human) endgame, but I'm unable to make it output correct results. I'm seeking for a fully optimal play by both player: the stronger player should try to give a checkmate in as few moves plys as possible while the weaker should resist as long as possible.

White K has Q but the output yields 1/2-1/2 but should be 1-0:

The output

``````{'fen': '8/8/8/8/5K2/2Q5/4k3/8 w - - 7 4', 'moves_to_mate': None, 'parent': None, 'color': True, 'result': '1/2-1/2', 'processed': True, 'sequence': [], 'children': [2, 11199, 22222, 31395, 40914, 50378, 54511, 75474, 95362, 117264, 136888, 158232, 180357, 196703, 213664, 225570, 231329, 243028, 254132, 265819, 272614, 277452, 281510, 286774, 299674, 314783, 316683, 321578, 331712, 334283, 338150], 'up': True, 'seeking_draw': True}

Also ,the result should be 'moves_to_mate == 5' but is None.
``````

The code in Python

``````import chess

def initialize_game_tree(initial_fen):
"""Initializes the game tree with the root node."""
return {
1: {
'fen': initial_fen,
'moves_to_mate': None,
'parent': None,
'color': chess.WHITE if ' w' in initial_fen else chess.BLACK,
'result': None,
'processed': False,
'sequence': [],
'children': [],
'up': False,
'seeking_draw': ' w' in initial_fen,
}
}

def evaluate_position(board):
"""Evaluates the board position without considering draw-seeking behavior explicitly."""
if board.is_checkmate():
return '1-0' if board.turn == chess.BLACK else '0-1'
if board.is_stalemate() or board.is_insufficient_material() or board.can_claim_draw():
return '1/2-1/2'
return None

def expand_and_evaluate(A, node_id=1, current_depth=0, max_depth=5):
"""Expands the game tree and evaluates positions."""
node = A[node_id]
board = chess.Board(node['fen'])

if current_depth >= max_depth or board.is_game_over():
node['result'] = evaluate_position(board)
node['processed'] = True
node['up'] = True
return

for move in board.legal_moves:
board.push(move)
child = {
'fen': board.fen(),
'moves_to_mate': None,
'parent': node_id,
'color': not node['color'],
'result': evaluate_position(board),
'processed': board.is_game_over(),
'sequence': [],
'children': [],
'up': False,
'seeking_draw': node['seeking_draw'],
}
board.pop()
child_id = len(A) + 1
A[child_id] = child
node['children'].append(child_id)
expand_and_evaluate(A, child_id, current_depth + 1, max_depth)

def update_optimal_strategy(A, node_id):
"""Updates nodes with optimal play strategies."""
node = A[node_id]

if node['processed'] and node['up']:
return

if not node['children']:
node['processed'] = True
node['up'] = True
return

optimal_moves_to_mate, optimal_result = None, None

for child_id in node['children']:
child = A[child_id]
update_optimal_strategy(A, child_id)

if child['result'] == '1-0' and node['color'] == chess.BLACK or \
child['result'] == '0-1' and node['color'] == chess.WHITE:
moves_to_mate = 0 if child['moves_to_mate'] is None else child['moves_to_mate']
if optimal_moves_to_mate is None or moves_to_mate < optimal_moves_to_mate:
optimal_moves_to_mate = moves_to_mate
optimal_result = child['result']

if optimal_result:
node['moves_to_mate'] = optimal_moves_to_mate + 1 if optimal_moves_to_mate is not None else 1
node['result'] = optimal_result
else:
node['result'] = '1/2-1/2'

node['processed'] = True
node['up'] = True

# Main execution
initial_fen = "8/8/8/8/5K2/2Q5/4k3/8 w - - 7 4"
A = initialize_game_tree(initial_fen)
expand_and_evaluate(A, max_depth=5)  # Adjust max_depth as needed
update_optimal_strategy(A, 1)

print(A[1])  # Print the root node for demonstration

def print_boards_for_children(A, parent_key):
"""Prints boards for all children of a given node."""
for key in A[parent_key]['children']:
child = A[key]
print(f"Child {key}: {child['fen']}\n{chess.Board(child['fen'])}\n")

print_boards_for_children(A, 1)
``````

EDIT I've created one more version which has the problem that the sequence returned is ridiculously long and doesn't give an optimal sequence of move for both players, please see below:

And this is my new code

This is the output

........................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................Root Node: Key: 1, FEN: 7k/1Q6/8/4K3/8/8/8/8 w - - 8 5, Result: 1, Moves to mate: 3, Processed: True, Sequence: ['b7c8', 'b7b8', 'b7a8', 'b7h7', 'b7g7', 'b7f7', 'b7e7', 'b7d7', 'b7c7', 'b7a7', 'b7c6', 'b7b6', 'b7a6', 'b7d5', 'b7b5', 'b7e4', 'b7b4', 'b7f3', 'b7b3', 'b7g2', 'b7b2', 'b7h1', 'b7b1', 'e5f6', 'h8g8', 'b7g7', 'e5e6', 'e5d6', 'e5f5', 'e5d5', 'e5f4', 'e5e4', 'e5d4'], Up: True {'fen': '7k/1Q6/8/4K3/8/8/8/8 w - - 8 5', 'moves_to_mate': 3, 'parent': None, 'color': True, 'result': 1, 'processed': True, 'sequence': ['b7c8', 'b7b8', 'b7a8', 'b7h7', 'b7g7', 'b7f7', 'b7e7', 'b7d7', 'b7c7', 'b7a7', 'b7c6', 'b7b6', 'b7a6', 'b7d5', 'b7b5', 'b7e4', 'b7b4', 'b7f3', 'b7b3', 'b7g2', 'b7b2', 'b7h1', 'b7b1', 'e5f6', 'h8g8', 'b7g7', 'e5e6', 'e5d6', 'e5f5', 'e5d5', 'e5f4', 'e5e4', 'e5d4'], 'up': True}

• I’m voting to close this question because I believe this question belongs on a programming stack exchange and not on here. Commented Feb 21 at 20:52
• @Tommiie According to the help center (chess.stackexchange.com/help/on-topic) Chess-specific questions about programming a chess engine or other chess software are welcome. Commented Feb 21 at 23:49
• @BrianTowers Thank you for your kind comment. I've spent an incredible amount of time trying to make my relatively short code to work, but I've failed. Hopefully I will get help here. Commented Feb 22 at 5:39
• @BrianTowers I've created a new version of my code which is slightly better, but still the optimal sequence is a bit too long and hence also not optimal for both players. Please see my EDIT. Commented Feb 22 at 11:43
• Is there a reason why your algorithm works in such a "convoluted" way? As I understand it, you first create the set of all descendants up to a certain depth, then iterate over them to evaluate the terminal positions, then propagate some results upward? Why not instead of storing all descendants, immediately evaluate them and propagate the highest value of all children up immediately? Commented Feb 22 at 12:37