Answers.Body: <p>I am not exactly sure what is the question you are asking.</p>
  <p>However, if I were to build a tablebase for fairy conditions or pieces, I would proceed as follows. Note that the solution implies that the tablebase is <em>closed</em>, meaning that performing a legal move from any position in the tablebase yields a position which is also in the tablebase.</p>
  <pre><code>queue = []
  
  foreach position in tablebase:
    if is_mate(position):
      position.store_tablebase_info(mate=...)
      queue.push_back(position)
  
  while queue not empty:
    position = queue.pop_front()
    foreach move in position.list_backward_moves():
      new_position = position.play_backward(move)
      if not new_position.has_tablebase_info():
        new_position.store_tablebase_info(winning=...)
        queue.push_back(new_position)
  
  foreach position in tablebase:
    if not position.has_tablebase_info():
      position.store_tablebase_info(drawn=true)  
  </code></pre>
  <p>Using this simple algorithm, you do not have to introduce heuristics to determine which positions are drawn, as this can be difficult for some fairy conditions.</p>
  <p>Note that position are handled by &quot;distance to mate&quot;, as we initialize the queue with mate positions, then end up adding positions with a distance to mate equal to 1, then those with distance equal to 2, etc.</p>
  <p>Hopefully this helps!</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-03-06T10:11:34.620Z
Answers.Text: When we are processing a `new_position` in the above pseudo-code, we know that the distance to mate (let's call it dtm) is minimum, because we already processed all positions with distance to mate 0, 1, 2, 3, ...., dtm-1, in that order, because of the way we fill the fifo queue.
Answers.UserDisplayName: Étienne
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-03-06T18:41:43.547Z
Answers.Text: I guess I will have to call the detection of dead positions after I run the algorithm anyway. 
  But looking at the algorithm for evaluation you propose, I assume all positions after the backward move is made are always won for the side-to-move ?
Answers.UserDisplayName: Ferazhu
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-03-08T19:14:33.473Z
Answers.Text: @Étienne But backward move will switch "white is mated" to "black wins in 1", but the next backward move will not tell us that "white loses in 2"
Answers.UserDisplayName: Ferazhu
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-03-09T16:15:48.343Z
Answers.Text: Indeed, I went a bit fast with `store_tablebase_info()`, I was focused on finding the drawn positions. In `new_position`, you do not have all information needed to fill all the tablebase info. I can amend the pseudo-code to make it clear if you wish.
Answers.UserDisplayName: Étienne
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-03-06T06:35:16.467Z
Answers.LastActivityDate: 2023-03-06T06:35:16.467Z
Answers.UserDisplayName: Étienne
Answers.Body: <p>You <em>might</em> be computationally better off if you &quot;hotwire&quot; the problem. Consider an orthodox tablebase:</p>
  <ul>
  <li>Death 1: KB/K, KN/K. Trivial detection.</li>
  <li>Death 2: Forced stalemate. Can be detected by playing just a few forward iterations.</li>
  <li>Death 3: Pawn barricade. Needs 8 men.</li>
  </ul>
  <p>I.e., a nonissue in orthodox chess, tricky cases have more men than your usual tablebase.</p>
  <p>Depending on the fairy condition, this can become less trivial (imagine KLi/KLi - there <em>is</em> one mate position, but it can't be reached even with help play - KP/KLi with lion promotion is the only way).</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-03-05T08:09:50.020Z
Answers.LastActivityDate: 2023-03-05T08:09:50.020Z
Answers.UserDisplayName: Hauke Reddmann
Body: <p>I am programming a tablebase for fairy chess, and would like to conclude the game if mate cannot be reached in any way. I guess this has to be detected when the evaluation (win in... / loss in... / draw) is created. So far, my (working) algorithm for evaluating winnable positions looks like this in pseudocode:</p>
  <ul>
  <li>Start with all mate positions and evaluate them</li>
  <li>For each position which has changed evaluation, make one move backwards</li>
  <li>Evaluate the resulting positions by checking all forward moves and pick the best result (unexplored = draw)</li>
  <li>If the &quot;best&quot; result has changed, add the position to the queue for next iteration</li>
  <li>Return to (2)</li>
  </ul>
  <pre><code>activePositions = findAllMatePositions()
  for(ap in activePositions) ap.result=[Loss,0]
  while(activePositions not empty)
  {
   newActivePositions = []
   for (ap in activePositions)
   {
     for(backmove in ap.getBackMoves())
     {
       newPosition = ap.makeBackMove(backmove)
       for(move in newPosition.getMoves())
       {
        // find the best move and evaluation of resulting position
       }
       if(/*result of newPosition has changed */) newActivePositions.push(newPosition)
       ap.undoBackMove(backmove)
     }
    }
    activePositions = newActivePositions
  }
  
  </code></pre>
  <p>Ideally, I would like for the dead position be detected during the main evaluation, but I guess I would need to run it again. Basically the issues are:</p>
  <ul>
  <li>Where to start? Should I need to pick all positions which were not evaluated with win or loss, for the first iteration?</li>
  <li>Would it be easier if I first went for white cannot lose / black cannot lose detection?</li>
  </ul>
  <p>Edit: So to determine draw by both sides, it is rather easy:</p>
  <ul>
  <li>Mark all drawn positions as dead candidates</li>
  <li>For each position, if any of the moves does not lead to dead position candidates, remove it from the candidates as well</li>
  <li>Continue until no candidates are removed in each iteration</li>
  </ul>
  <p>So now only remains (the harder, but not as useful for me) solution how to determine this for a player individually (cannot be helpmated by the other player, but can mate the opponent).</p>
  
Tags: <software><tablebases><retrograde-analysis><dead-position>
Title: How would I detect dead position in a tablebase?
ThreadText: # How would I detect dead position in a tablebase?
  
  (Asked by: username_0 on 2023-03-04)
  
  I am programming a tablebase for fairy chess, and would like to conclude the game if mate cannot be reached in any way. I guess this has to be detected when the evaluation (win in... / loss in... / draw) is created. So far, my (working) algorithm for evaluating winnable positions looks like this in pseudocode:
  
  Start with all mate positions and evaluate them
  For each position which has changed evaluation, make one move backwards
  Evaluate the resulting positions by checking all forward moves and pick the best result (unexplored = draw)
  If the "best" result has changed, add the position to the queue for next iteration
  Return to (2)
  
  activePositions = findAllMatePositions()
  for(ap in activePositions) ap.result=[Loss,0]
  while(activePositions not empty)
  {
   newActivePositions = []
   for (ap in activePositions)
   {
     for(backmove in ap.getBackMoves())
     {
       newPosition = ap.makeBackMove(backmove)
       for(move in newPosition.getMoves())
       {
        // find the best move and evaluation of resulting position
       }
       if(/*result of newPosition has changed */) newActivePositions.push(newPosition)
       ap.undoBackMove(backmove)
     }
    }
    activePositions = newActivePositions
  }
  
  
  Ideally, I would like for the dead position be detected during the main evaluation, but I guess I would need to run it again. Basically the issues are:
  
  Where to start? Should I need to pick all positions which were not evaluated with win or loss, for the first iteration?
  Would it be easier if I first went for white cannot lose / black cannot lose detection?
  
  Edit: So to determine draw by both sides, it is rather easy:
  
  Mark all drawn positions as dead candidates
  For each position, if any of the moves does not lead to dead position candidates, remove it from the candidates as well
  Continue until no candidates are removed in each iteration
  
  So now only remains (the harder, but not as useful for me) solution how to determine this for a player individually (cannot be helpmated by the other player, but can mate the opponent).
  
  **Tags:** software, tablebases, retrograde-analysis, dead-position
  
  
  ---
  
  ## 2 answers
  
  ### Answer by username_1 on 2023-03-06. Score: 1
  
  I am not exactly sure what is the question you are asking.
  However, if I were to build a tablebase for fairy conditions or pieces, I would proceed as follows. Note that the solution implies that the tablebase is closed, meaning that performing a legal move from any position in the tablebase yields a position which is also in the tablebase.
  queue = []
  
  foreach position in tablebase:
    if is_mate(position):
      position.store_tablebase_info(mate=...)
      queue.push_back(position)
  
  while queue not empty:
    position = queue.pop_front()
    foreach move in position.list_backward_moves():
      new_position = position.play_backward(move)
      if not new_position.has_tablebase_info():
        new_position.store_tablebase_info(winning=...)
        queue.push_back(new_position)
  
  foreach position in tablebase:
    if not position.has_tablebase_info():
      position.store_tablebase_info(drawn=true)  
  
  Using this simple algorithm, you do not have to introduce heuristics to determine which positions are drawn, as this can be difficult for some fairy conditions.
  Note that position are handled by "distance to mate", as we initialize the queue with mate positions, then end up adding positions with a distance to mate equal to 1, then those with distance equal to 2, etc.
  Hopefully this helps!
  
  > **Comments:**
  > **username_1**: When we are processing a `new_position` in the above pseudo-code, we know that the distance to mate (let's call it dtm) is minimum, because we already processed all positions with distance to mate 0, 1, 2, 3, ...., dtm-1, in that order, because of the way we fill the fifo queue.  
  > **username_0**: I guess I will have to call the detection of dead positions after I run the algorithm anyway.  But looking at the algorithm for evaluation you propose, I assume all positions after the backward move is made are always won for the side-to-move ?  
  > **username_0**: @username_1 But backward move will switch "white is mated" to "black wins in 1", but the next backward move will not tell us that "white loses in 2"  
  > **username_1**: Indeed, I went a bit fast with `store_tablebase_info()`, I was focused on finding the drawn positions. In `new_position`, you do not have all information needed to fill all the tablebase info. I can amend the pseudo-code to make it clear if you wish.  
  
  ---
  
  ### Answer by username_2 on 2023-03-05. Score: 1
  
  You *might* be computationally better off if you "hotwire" the problem. Consider an orthodox tablebase:
  
  * Death 1: KB/K, KN/K. Trivial detection.
  * Death 2: Forced stalemate. Can be detected by playing just a few forward iterations.
  * Death 3: Pawn barricade. Needs 8 men.
  
  I.e., a nonissue in orthodox chess, tricky cases have more men than your usual tablebase.
  
  Depending on the fairy condition, this can become less trivial (imagine KLi/KLi - there *is* one mate position, but it can't be reached even with help play - KP/KLi with lion promotion is the only way).
  
  
  ---
  
  