2

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

2 Answers 2

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

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!

5
  • It seems that this algorithm takes shortcuts: instead of minimaxing all forward moves to label a position, it just takes the first forward move of the position that is encountered backwards. Is there some hidden mechanism that 'makes right', or is this not a tablebase for maintaining an exact distance-to-mate?
    – user30536
    Mar 6, 2023 at 7:19
  • 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.
    – Étienne
    Mar 6, 2023 at 10:11
  • 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 ?
    – Ferazhu
    Mar 6, 2023 at 18:41
  • @É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"
    – Ferazhu
    Mar 8, 2023 at 19:14
  • 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.
    – Étienne
    Mar 9, 2023 at 16:15

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.