False draw claim by Lime

[Richard Allbert]

Great, thanks, I'll take the file down.

Richard

[wgarvin]

Off-topic: The nice effect of these rules (when it comes to endgame databases) is that after 50 non-converting moves *by your opponent*, if he failed to win the game with the 50th move, you are able to claim a draw--it doesn't matter whether you yourself have made 50 consecutive non-converting moves, or only 49! If he didn't checkmate you, you can communicate any move as the "intended move" and atomically claim the draw.

This is only true when you have legal non-capture moves, not? If you are in a position where you can only capture, it is important if you can claim before or after your move.

Joker lost to Ktulu in Leiden last year, because on the 100th ply it could only capture a Queen to get out of check in KQQK... Ktulu apparenty new that Joker could not claim before the move.

Good point. You can't just communicate "any move", it has to be "any non-losing move". So in a bitbase derived from a DTZ50 database, a non-winning position where you can play this 50th draw-preserving move, should be recorded as a draw. However, a position where you can't play the 50th non-zeroing move would be recorded as a loss (and you would not play into that position from any position listed in the database as a draw).

The advantage of DTZ50 is that it allows you to completely and accurately represent the consequences of the FIDE 50-move rule in your database. If the database says "win", that means you can force a win before the 50-move rule takes effect. If the database says "draw", it might mean neither player can force a win at all, or it might mean that one player could force a win but not before his opponent had the opportunity to legitimately claim a 50-move draw.

If your databases are closed under non-zeroing moves (i.e. any move that brings you into the database was a zeroing move), and once you enter the databases then you never leave them, then DTZ50 should be sufficient to win all actually-winnable positions covered by the databases.

I guess a better way to state what I was trying to say, is that because of the way the FIDE rule is written, you don't need a database with 100 different values to the win or to the loss (i.e. encoding the halfmove counter). You only need 50 different values for win, and 50 different values for loss. I guess you have to be careful when writing the retrograde generator, as an off-by-one error could easily give you bogus databases. But if they are generated correctly, they should always be able to play the endings correctly and maximize GTV.

The only possible exception I can think of, is if there is a position where one player is able to use 3-fold repetition of one or more positions, to extend the half-move counter enough to hit the 50-move limit, and thus eke out a draw from a supposedly losing position. I haven't thought about it enough to figure out if this is possible or not.

[hgm]

The only possible exception I can think of, is if there is a position where one player is able to use 3-fold repetition of one or more positions, to extend the half-move counter enough to hit the 50-move limit, and thus eke out a draw from a supposedly losing position. I haven't thought about it enough to figure out if this is possible or not.

Well, if the losing player could even force a single repetition, he would not be losing, as he would keep doing it forever untill the 50 moves were reached. The winning side always must have a progress indicator, like DTM, where it can force a position progressed more on the next move. So you can never return to a position where you have been before, as that would mean that somewhere along the path, progress would have to go down, meaning that the winning side must have played a sub-optimal move.

This is what makes XiangQi tablebases so much harder: there the losing side can almost always force repetitions.

What I don't like about the DTZ50 scheme you sketch is that it does not provide a clue on how to win theoretically drawn positions against imperfect play. Only when the opponent makes an error so gross that he would give away the entire deficit (which in KBBKN can be something like 30 moves, I think), you would stay in the draw sector. So I think one really should fill the won-but-50-move-drawn positions with some progress indicator as well, where DTZ values > 50 could be used.

This requires an interesting trade-off for how to distribute the overrun, if both the current and some successor phase need more than 50 moves. If you can choose between 51 moves now, and 58 later, or 55 now and 55 later, what would be the better strategy?

[wgarvin]

The only possible exception I can think of, is if there is a position where one player is able to use 3-fold repetition of one or more positions, to extend the half-move counter enough to hit the 50-move limit, and thus eke out a draw from a supposedly losing position. I haven't thought about it enough to figure out if this is possible or not.

Well, if the losing player could even force a single repetition, he would not be losing, as he would keep doing it forever untill the 50 moves were reached. The winning side always must have a progress indicator, like DTM, where it can force a position progressed more on the next move. So you can never return to a position where you have been before, as that would mean that somewhere along the path, progress would have to go down, meaning that the winning side must have played a sub-optimal move.

Totally right! I forgot about that. The losing player *wants* to draw (by 3-fold or 50-move or anything else), so he will repeat if he can. The winning player has to force the win, which requires him to avoid such positions. One less thing to worry about!

This is what makes XiangQi tablebases so much harder: there the losing side can almost always force repetitions.

What I don't like about the DTZ50 scheme you sketch is that it does not provide a clue on how to win theoretically drawn positions against imperfect play. Only when the opponent makes an error so gross that he would give away the entire deficit (which in KBBKN can be something like 30 moves, I think), you would stay in the draw sector. So I think one really should fill the won-but-50-move-drawn positions with some progress indicator as well, where DTZ values > 50 could be used.

This requires an interesting trade-off for how to distribute the overrun, if both the current and some successor phase need more than 50 moves. If you can choose between 51 moves now, and 58 later, or 55 now and 55 later, what would be the better strategy?

My particular interest is in bitbases for GTV, combined with scoring heuristics for finding the wins. So in the bitbases, I would want it to say "draw". But of course if you have a full DTZ50 database, you just let that position say "win in 51" or whatever, rather than draw (and just be careful that the eval score you return, is much more like "draw" than "won"). So you can still use those scores to make enough progress against an imperfect opponent, that if they slip up and give up a few moves worth of delay, the position now becomes an actual win for you.

Engines can use databases (or bitbases) in two different phases: (1) guiding the search to positions with known (and hopefully won) GTVs, and (2) once it is actually reached on the board, playing out an ending with GTV-preserving moves.

During the first phase, having these more-than-50 positions return a draw score from eval seems fine. (If you had the full DTZ50, you might want to give "win in 51" or "win in 52" positions a tiny positive score?) But once you actually get into the ending though, there are lots of things you could do. The only essential things are that it does not let GTV get any worse, and that when its on the winning side, it can "make enough progress towards the win" to actually force the win. But you can also try and do "swindle" things in drawn or lost positions (e.g. somehow favor positions that are complicated for a human to play optimally). Preferring "almost winnable" positions over dead draws seems kind of like the swindle logic. "I can't force the win, but if my opponent were to make a mistake, then perhaps I could".

Anyway, once your board position is in the database, then you could hand over control of the game to some dedicated "endgame player" code, that just does database lookups and knows how to make progress toward wins, etc. (Maybe it does some small searches to cover up gaps in the database, if you have any. Maybe it does proof-number searches looking for mates. Etc.) Until you have an "over the board" position that is in the database, you don't need any information except the real GTV and *possibly* a flag saying "drawn, but perhaps I could win this if opponent makes a mistake". So a bitbase could use 2 bits for GTV and cover all of that, and use less memory/cache/etc. than a DTZ50 database with a byte per position.

[hgm]

Preferring "almost winnable" positions over dead draws seems kind of like the swindle logic. "I can't force the win, but if my opponent were to make a mistake, then perhaps I could".

Isn't that what Chess is all about? If that is not your aim, there would be no point in making an opening move...

As for computer Chess, you want to affirm the superiority of your program. Which has little hope of success if it is not indeed superor. So the basic assumption is that you will have 6-men, but the opponent is limited to 5-men, or you have 7, and he only 6. And the question is how to make the most of that advntage.

The problem with scoring 'nearly-won' draws as draws, is that the engine really throws in the towel much to easily. Wth KBPPKB (unlike) it can sac a Pawn on move 1, another Pawn on move 2, and its Bishop on move 3. And it will still be a draw. But certainly not a win, while the possibility of a losing mistake of your opponent in the initial situation was very real. Always hope for a swindle. Joker even continues in KQBK, as black. And did score have a point with it, earning me a $300 cash prize in Leiden!

[wgarvin]

Preferring "almost winnable" positions over dead draws seems kind of like the swindle logic. "I can't force the win, but if my opponent were to make a mistake, then perhaps I could".

Isn't that what Chess is all about? If that is not your aim, there would be no point in making an opening move...

As for computer Chess, you want to affirm the superiority of your program. Which has little hope of success if it is not indeed superor. So the basic assumption is that you will have 6-men, but the opponent is limited to 5-men, or you have 7, and he only 6. And the question is how to make the most of that advntage.

The problem with scoring 'nearly-won' draws as draws, is that the engine really throws in the towel much to easily. Wth KBPPKB (unlike) it can sac a Pawn on move 1, another Pawn on move 2, and its Bishop on move 3. And it will still be a draw. But certainly not a win, while the possibility of a losing mistake of your opponent in the initial situation was very real. Always hope for a swindle. Joker even continues in KQBK, as black. And did score have a point with it, earning me a $300 cash prize in Leiden!

I agree with everything in that post.

But anyway, the handling of draw scores is something that I would be curious to see more experiments around. What kind of range of score values is appropriate to use for various known-drawn positions (-0.2 to +0.2 pawns? or what). Should non-draw scores be given a bias away from zero, to help distinguish draws from non-draws (and avoid preferring a known draw over a possible win, etc (how big should the bias be)? Should there still be some overlap between the range used for draws, and the range used for non-draws? I don't know any of the answers.

[hgm]

Well, as the draw margin for Chess is about +/- 2 Pawns, it would not be crazy to score some draws as +2. E.g. KBPPKB. That is how you would score it without specific knowledge. Of course once you know that it is won from the tablebase, that is basically a mate score. So there is enough room to score the wins you guess based on eval.