3

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}

8
  • 1
    I’m voting to close this question because I believe this question belongs on a programming stack exchange and not on here.
    – Tommiie
    Commented Feb 21 at 20:52
  • 4
    @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.
    – Brian Towers
    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?
    – koedem
    Commented Feb 22 at 12:37

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.