lichess.org

Timeout in a dead position

I think if you give me a couple of free weeks, I could write software using blocked bishops euristics and transposition tables that could distinguish all examples above. But I just don't think this problem is really worth two my free weeks :)

I believe that there have been many attempts. Still it is astonishing. If I am capable to see in an instant that there are no chances to win - how do I do this? Why is it so difficult to code the same algorithm my brain is using?
Or are there examples where everybody would say: It is a draw - while it is not?

@sheckley666

Has it been 50 moves for the engine trying it's best to lose vs the engine trying it's best to win?
Has a mate happened yet? no? it's drawn

Thanks, I agree with the answer in that link:

> In sum, I do not believe you can have an algorithm that is 100% accurate in distinguishing between dead and alive positions that runs in reasonable time. Brute force is the only 100% reliable method, but it is definitely not efficient. You can get a decent success rate for "practical" positions with heuristics, but it will not be 100% accurate, even for real game positions.

@Sybotes
> If I am capable to see in an instant that there are no chances to win - how do I do this? Why is it so difficult to code the same algorithm my brain is using?
Because the problem of generating formal proofs better than humans is not solved by AI field yet. When you see a dead position, you can usually make some argument like "the pawns are blocked, the bishops can't pass through the pawn shield, the kings as well, therefore no capture or check can be made, and the game is a draw". This is not a thing that a modern chess engine could understand. When I said I could have code this algorithm I meant I could code a bunch of such common "dead" arguments that you could not easily find a position which cannot be proved dead using them. But as it is correctly stated, 100% accurate method is hard to come up with.
> Or are there examples where everybody would say: It is a draw - while it is not?
Basically human brain is also not 100% accurate in evaluating some convoluted positions like one in Illion's stackexchange answer:
Bb1k1b2/bKp1p1p1/1pP1P1P1/pP6/6P1/P7/8/8 w - - 0 1
With long enough think you can figure this is not a draw, but I bet you are not "capable to see it in an instant"

The problem largely looks like NP-hard. It is easy to verify if any given sequence of moves leads to mate, but it is hard to check if such a sequence exists. It "looks like NP-hard", but may not in fact be if it turns out there is a set of heuristics you could use to solve everything with 100% accuracy.
@lurarose
> Has it been 50 moves for the engine trying it's best to lose vs the engine trying it's best to win?
First, there is no such thing like engine trying to lose, and it is not easy to code such. Second, this engine is irrelevant, because such an engine would assume that the opponent tries to lose as well (not win), and would miss a path to checkmate where a handful of cooperation is required. So in a game vs engine trying to win it will make inferior moves. If you mean such engine that "it tries to lose assuming the opponent tries to win", then you only reformulated the problem into coding such engine, but this doesn't make it any easier. Moreover, the engine trying to win should not be the usual chess engine, but it should assume that the opponent tries to lose...

It cannot be coded that's true but one solution could be to have an adjudication system where a human decides such cases. It's just not very practical and some cases are hard to decide.

Reconnecting