How would I detect dead position in a tablebase?

Question

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).

Answer 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).

Answer 2

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!