Alpha-beta search for drawing endgames

[hgm]

The problem is that even when you could solve the path-dependence problem, the repetition can usually be postponed so long that it is way outside the search horizon. Even in KPK it can take a long time before the strong side eventually has to chose between repetition, stalemate or giving up the Pawn, if the Pawn is still far from the promotion square. Or even simpler: K vs K, before the search can see a contempt score, rathere than a zero material evaluation.

[klx]

So my counter argument is that if there is a win after A then that win is available the first time you encounter A regardless of history.

Ah, right good point. Thanks, let me think about this for a bit!

[klx]

The problem is that even when you could solve the path-dependence problem, the repetition can usually be postponed so long that it is way outside the search horizon. Even in KPK it can take a long time before the strong side eventually has to chose between repetition, stalemate or giving up the Pawn

So my thought here was that if we can use a TT and still ensure correct results, we could still solve it, since there are only going to be so many possible unique states. For example with 3 pieces, there is going to be less than 64^3 = ~260,000 states. Even if we can't always use the TT entry (due to insufficient depth), I'm thinking this should still be trivially searchable?

Of course once we get up to 5+ pieces we are going to have a lot of possible states, but perhaps all of them will not be explored in practice? Unsure about this...

[hgm]

With only few pieces retrograde analysis becomes very easy too. And it needs only 3 bits per position, while a TT will need something like 9 bytes = 72 bits per position. And in a TT the probing is scattered over the entire table, virtually always missing the cache. With retrograde analysis you can run through the set of possible positions in a sequence that processes dozens of them with a single memory access. So it is typically several orders of magnitude faster.

Marcel van Kervinck's 'Pretty Fast' EGT generator solves the KBNK end-game in 110 msec on my laptop. Now present a mate-in-25 KBNK position to a strong engine (without using EGT, of course), to see how long it takes to find the mate...

[klx]

With only few pieces retrograde analysis becomes very easy too...

Fair point. Let me process this.