Body: <p>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.</p>
  <p>White K has Q but the output yields 1/2-1/2 but should be 1-0:</p>
  <p><strong>The output</strong></p>
  <pre><code>{'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.
  </code></pre>
  <p><strong>The code in Python</strong></p>
  <pre><code>import chess
  
  def initialize_game_tree(initial_fen):
      &quot;&quot;&quot;Initializes the game tree with the root node.&quot;&quot;&quot;
      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):
      &quot;&quot;&quot;Evaluates the board position without considering draw-seeking behavior explicitly.&quot;&quot;&quot;
      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):
      &quot;&quot;&quot;Expands the game tree and evaluates positions.&quot;&quot;&quot;
      node = A[node_id]
      board = chess.Board(node['fen'])
  
      if current_depth &gt;= 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):
      &quot;&quot;&quot;Updates nodes with optimal play strategies.&quot;&quot;&quot;
      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 &lt; 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 = &quot;8/8/8/8/5K2/2Q5/4k3/8 w - - 7 4&quot;
  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):
      &quot;&quot;&quot;Prints boards for all children of a given node.&quot;&quot;&quot;
      for key in A[parent_key]['children']:
          child = A[key]
          print(f&quot;Child {key}: {child['fen']}\n{chess.Board(child['fen'])}\n&quot;)
  
  print_boards_for_children(A, 1)
  </code></pre>
  <p><strong>EDIT</strong> 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:</p>
  <p><a href="https://pastebin.com/C1pWxhcN" rel="nofollow noreferrer">And this is my new code</a></p>
  <p><strong>This is the output</strong></p>
  <p>........................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................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}</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2024-02-21T20:52:32.017Z
Comments.Text: I’m voting to close this question because I believe this question belongs on a programming stack exchange and not on here.
Comments.UserDisplayName: Tommiie
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2024-02-21T23:49:38.243Z
Comments.Text: @Tommiie According to the help center (https://chess.stackexchange.com/help/on-topic) *Chess-specific questions about programming a chess engine or other chess software are welcome.*
Comments.UserDisplayName: Brian Towers
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2024-02-22T05:39:00.937Z
Comments.Text: @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.
Comments.UserDisplayName: user2925716
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2024-02-22T11:43:03.147Z
Comments.Text: @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**.
Comments.UserDisplayName: user2925716
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2024-02-22T12:37:41.647Z
Comments.Text: 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?
Comments.UserDisplayName: koedem
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2024-02-22T12:49:38.497Z
Comments.Text: In general the code appears to be quite confusing, I would recommend debugging the code execution to see what is actually going on inside of there.
  Also, the printed sequence is clearly not an actual move sequence but rather a list of legal moves, albeit for a different position than the root position it should look at.
Comments.UserDisplayName: koedem
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2024-02-23T09:09:18.227Z
Comments.Text: @koedem Could you try to fix it ? I've got stuck.
Comments.UserDisplayName: user2925716
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2024-02-23T16:58:35.880Z
Comments.Text: I don't have time right now for a detailed answer, but if you want to learn about this kind of thing I would recommend the chess programming wiki, it has a lot of useful information. For a simple search like this one you may for example look at this: https://www.chessprogramming.org/Minimax#Implementation
Comments.UserDisplayName: koedem
Tags: <engines><software><computer-chess><python>
Title: Why this Python code for a simple endgame yields wrong results?
ThreadText: # Why this Python code for a simple endgame yields wrong results?
  
  (Asked by: username_0 on 2024-02-21)
  
  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}
  
  **Tags:** engines, software, computer-chess, python
  
  > **Comments:**
  > **username_1**: I’m voting to close this question because I believe this question belongs on a programming stack exchange and not on here.  
  > **username_2**: @username_1 According to the help center (https://chess.stackexchange.com/help/on-topic) *Chess-specific questions about programming a chess engine or other chess software are welcome.*  
  > **username_0**: @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.  
  > **username_0**: @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**.  
  > **username_3**: 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?  
  > **username_3**: In general the code appears to be quite confusing, I would recommend debugging the code execution to see what is actually going on inside of there. Also, the printed sequence is clearly not an actual move sequence but rather a list of legal moves, albeit for a different position than the root position it should look at.  
  > **username_0**: @username_3 Could you try to fix it ? I've got stuck.  
  > **username_3**: I don't have time right now for a detailed answer, but if you want to learn about this kind of thing I would recommend the chess programming wiki, it has a lot of useful information. For a simple search like this one you may for example look at this: https://www.chessprogramming.org/Minimax#Implementation  
  
  ---
  
  ## 0 answers
  
  