Endgame tablebases

Sort:
GBR99

What criterion do Endgame tablebases use to decide if the game ends in a draw (as a best result) after a certain move?

Is it: "Within 50 moves, no victory exists" or "after a certain amount of moves, the best thing to do is go to a position on the board that was there before." Or something else?

Tatzelwurm

It's a draw if neither side can force a win.

Some tablebases are aware of the 50 moves rule, but most are not.

GBR99

I must be silly here but I don't see how a tablebase can tell if neighter side can force a win.

If it's a knight and a king vs a king then we could say that no checkmate-position exists with just those pieces. But if it were a position with a set of pieces where a configuration exists such that a win can be forced. For example, King and pawn vs king. How could a tablebase conclude from that position if it is in fact a draw. 

If we ignore the 50 moves rule, as most tablebases do, one could say in such case: "Give me 1,000,000 moves and I'll force a win!" The only reply I could think of in the latter case is "Eventually, one of those positions has already been on the board. Therefore you can't force a win."

Tatzelwurm

I'll outline a simplified tablebase generation algorithm. It is assumed that only white can win:

  1. Mark all positions as drawn.
  2. Iterate over all drawn white-to-move positions. Mark those positions where you can checkmate as won.
  3. Iterate over all drawn black-to-move positions. Mark those where you can't avoid a "win for white" position as lost.
  4. Iterate over all drawn white-to-move positions. Mark those positions where you can reach a "loss for black" position as won.
  5. Repeat steps 3 and 4 until no further drawn positions can be marked as wins or losses.

This way you can assure that there is no possible win for positions which are still marked as drawn.

Sred

Yes, it's as simple as that: If a given move is winning in n ply, then the move will result in a position losing in n-1 ply and vice versa. There are only finitely many positions, so the recursion will eventually terminate.