Does bounded rationality allow draw-traps against perfect-play-seeking agents?

[gflohr]

I have watched this YouTube video about how to escape into a draw from an otherwise lost position:



At around 15:30, the author Jonas van Dael says that "even engines don't understand this position". He refers to the position leading to that one:

[d]8/1b6/8/8/8/5k1p/7P/6K1 w - - 0 100

Don't get me wrong, IMHO the video is really good, worth watching for me, and I totally get the point of what Jonas van Dael means by "understand". Let's also ignore the fact that the game of chess is solved for all positions with no more than seven pieces on the board.

In this exact position (the move before that was either h3 or a capture), Stockfish 17.1 reports just a small advantage of around half a pawn for black, even at shallow depths. Bless them for "understanding" that black's massive material advantage is never worth more than 56 centipawns, on my machine at a depth well below the 50-move horizon.

The engine evaluation changes if both sides have fruitlessly pushed around their pieces for 49 more moves: 8/1b6/8/8/8/5k1p/7P/6K1 w - - 98 149

Now, every engine will probably converge to a draw evaluation, because optimal play within the move horizon will always lead to 3-fold repetition or 50 moves without progress.

Let's get back to the initial position. It is not a technical draw, because a draw can only be claimed after 50 more moves without progress or a 3-fold repetition. But even in the initial position, the very obvious strategies will work: White has to stay in the corner, keeping the black pawn away from promoting and avoiding a mate. Black has to wait for white to blunder. It would be pointless to make engines smarter here, because they don't have kids, and they don't have to go to the loo.

My question is: If I play against a bug-free engine, and the engine does not have enough time to search to depth 100, are there positions where a human can set up a trap so that an engine will give up a win for a draw? In other words: Even when most of the recipes for "how to win against a chess engine" have been refuted since Kasparov vs. Deep Blue, are there still recipes for how to draw from a lost position against a strong engine? I’m not talking about bugs or evaluation mistakes, but about structurally unavoidable horizon effects, about positions where the game-theoretic value is a win, but the search-theoretic value collapses to a draw under bounded depth.

[syzygy]

My question is: If I play against a bug-free engine, and the engine does not have enough time to search to depth 100, are there positions where a human can set up a trap so that an engine will give up a win for a draw?

I did not watch the video but obviously if an engine misevaluates a drawn position that can occur in a real game as a win, then there are losing positions where the losing side can trick the winning side into a draw (unless you give the engine enough time to let the search see the problem).

But there are no positions that will be inherently misevaluated. You can always modify the evaluation function to get it right. And for a specific position there will always be NNUE nets that get that specific position right. At the same time, in chess there are no evaluation functions that fit in the world's total data storage capacity that gets ALL positions right (now we'll be getting people arguing that there might be "polynomials" that encode the "hidden structure" of chess but that's nonsense and I am going to ignore them)..

I would suggest not to use vague terms like "bounded rationality" and "agents" (or "epistemically" for that matter). They don't add anything to the discussion. Just be clear and concrete. (I am guessing this recent wave of vague terminology is coming from LLMs?)

[hgm]

As I already mentioned elsewhere it is not optimal to take the 50-move rule too seriously. In many situations one side should be able to achieve something in far fewer than 50 moves, and if it cannot it would be a very strong indication that it is a fortress draw.

One tell-tale sign of a draw is making all moves with a single, or a small subset of pieces. Especially with sliders; these should be able to move anywhere in very few moves, and if progress is to be made, it could make it within these few moves. And if it cannot, then more moves won't help.

Slow pieces like King might require more moves, but also provide a progress measure that could be used to reset the counter. Namely getting closer to where they need to be. Going in a direction where there are no enemy pieces is in general not a way to achieve anything, and should strongly decrese the move budget for achieving anything.

[OttoLau]

I have watched this YouTube video about how to escape into a draw from an otherwise lost position:



At around 15:30, the author Jonas van Dael says that "even engines don't understand this position". He refers to the position leading to that one:

[d]8/1b6/8/8/8/5k1p/7P/6K1 w - - 0 100

Don't get me wrong, IMHO the video is really good, worth watching for me, and I totally get the point of what Jonas van Dael means by "understand". Let's also ignore the fact that the game of chess is solved for all positions with no more than seven pieces on the board.

In this exact position (the move before that was either h3 or a capture), Stockfish 17.1 reports just a small advantage of around half a pawn for black, even at shallow depths. Bless them for "understanding" that black's massive material advantage is never worth more than 56 centipawns, on my machine at a depth well below the 50-move horizon.

The engine evaluation changes if both sides have fruitlessly pushed around their pieces for 49 more moves: 8/1b6/8/8/8/5k1p/7P/6K1 w - - 98 149

Now, every engine will probably converge to a draw evaluation, because optimal play within the move horizon will always lead to 3-fold repetition or 50 moves without progress.

Let's get back to the initial position. It is not a technical draw, because a draw can only be claimed after 50 more moves without progress or a 3-fold repetition. But even in the initial position, the very obvious strategies will work: White has to stay in the corner, keeping the black pawn away from promoting and avoiding a mate. Black has to wait for white to blunder. It would be pointless to make engines smarter here, because they don't have kids, and they don't have to go to the loo.

My question is: If I play against a bug-free engine, and the engine does not have enough time to search to depth 100, are there positions where a human can set up a trap so that an engine will give up a win for a draw? In other words: Even when most of the recipes for "how to win against a chess engine" have been refuted since Kasparov vs. Deep Blue, are there still recipes for how to draw from a lost position against a strong engine? I’m not talking about bugs or evaluation mistakes, but about structurally unavoidable horizon effects, about positions where the game-theoretic value is a win, but the search-theoretic value collapses to a draw under bounded depth.

By tge way did you know that this pegasus chess guy is a fraud and cheater? He has been exposed numerous times on youtube. Deletes all comments exposing him.

[gflohr]

By tge way did you know that this pegasus chess guy is a fraud and cheater? He has been exposed numerous times on youtube. Deletes all comments exposing him.

I didn't. Sorry for promoting the video.

[gflohr]

I did not watch the video but obviously if an engine misevaluates a drawn position that can occur in a real game as a win, then there are losing positions where the losing side can trick the winning side into a draw (unless you give the engine enough time to let the search see the problem).

Yes, that answers the question.

But there are no positions that will be inherently misevaluated. You can always modify the evaluation function to get it right. And for a specific position there will always be NNUE nets that get that specific position right. At the same time, in chess there are no evaluation functions that fit in the world's total data storage capacity that gets ALL positions right (now we'll be getting people arguing that there might be "polynomials" that encode the "hidden structure" of chess but that's nonsense and I am going to ignore them)..

What struck me is that Stockfish at depth < 31 sees a relatively small advantage for black, and at depth 31 the evaluation suddenly goes up to more than 50 cp. The exact evaluation on my machine is 58. That made me wonder whether a human can set up a trap in such a way that Stockfish would prefer the draw evaluated with 58 cp over a win in 49 moves that has an evaluation of just 57 cp. And, yes, of course, it would. Only I wasn't able to find such a position.

[gflohr]

One tell-tale sign of a draw is making all moves with a single, or a small subset of pieces. Especially with sliders; these should be able to move anywhere in very few moves, and if progress is to be made, it could make it within these few moves. And if it cannot, then more moves won't help.

I had tried to find a position leading to the example, where white has the choice of either losing the (useless) bishop or a piece seemingly worth less, like a knight or a pawn, which would eventually guarantee a win. But even at shallow depths, the engine always finds a mate with the other piece and sacrifices the bishop. In other words, you are right.

So the answer to my question is: Yes, a human can set up a draw trap for an engine, but only if the human is smarter than the engine and then it could also just go for a win in the first place. But there are no universally valid recipes for luring an engine into a draw.

[syzygy]

What struck me is that Stockfish at depth < 31 sees a relatively small advantage for black, and at depth 31 the evaluation suddenly goes up to more than 50 cp. The exact evaluation on my machine is 58. That made me wonder whether a human can set up a trap in such a way that Stockfish would prefer the draw evaluated with 58 cp over a win in 49 moves that has an evaluation of just 57 cp. And, yes, of course, it would. Only I wasn't able to find such a position.

In practice a human cannot set up such a trap without sheer luck. Even though there is no doubt that there are many positions which are gravely misevaluated by Stockfish, we just don't know which positions or, if you know one, how to get Stockfish to cooperate so that you can reach it from the starting position.

(To beat Stockfish as a human, run it without a book, single-threaded and at a fixed time per move so that it plays practically deterministically. Then you can always find a way to beat Stockfish consistently by just playing it over and over, systematically trying out variations until you find a weakness; I suggest to use an engine in this "training yourself" phase. Once you finally find a winning sequence of moves, just repeat those moves over and over again. Do not update Stockfish because you would have to start again from scratch.)

[syzygy]

Btw, the claim in the video that no engine understands the draw is false. Stockfish's hand-crafted evaluation (or rather its specialized endgame code) would have detected it.

edit: oops, this is probably wrong. There is code for detecting draws with rook pawns and a bishop of the wrong color, but here the bishop is not of the wrong color. Still, this is just a matter of a few lines of code. (Or of using tablebases as you already mentioned.)

[jkominek]

My question is: If I play against a bug-free engine, and the engine does not have enough time to search to depth 100, are there positions where a human can set up a trap so that an engine will give up a win for a draw? In other words: Even when most of the recipes for "how to win against a chess engine" have been refuted since Kasparov vs. Deep Blue, are there still recipes for how to draw from a lost position against a strong engine? I’m not talking about bugs or evaluation mistakes, but about structurally unavoidable horizon effects, about positions where the game-theoretic value is a win, but the search-theoretic value collapses to a draw under bounded depth.

The short answer is no, probably not - not without loosening the framing of your question.

First to address the trivial issue: even the best of software still makes mistakes, so of course there exist an ample supply of positions where it will drop a win under normal game playing conditions.

So I take the phrasing of "are there positions" as meaning a) are there one or more large classes of positions exhibiting some form of similarity that b) can be identified as such by a skilled human chess player, and furthermore c) the player can execute knowledge held in human form - operating under limited long term and short term working memory - such that members of the position class can be reliably exploited to beneficial effect?

That used to be true. To supply an example of how old-timers used to talk about it I'll quote from a post by Robert Hyatt, author of the important engine Crafty, back from the year 2000.

https://www.stmintz.com/ccc/index.php?id=128926

> But you have had many years of observing human-computer play. Have you observed systematic patterns or trends?

[Hyatt]
Several. Computers are still overly materialistic. They will often win a
pawn and totally wreck their position. Or win a pawn heading into a position
that a human knows can't be lost by the other side. And endgames are _still_
not solved. I can give you a couple of cases I watched another Computer play
against Crafty last night, while an IM and I were chatting about the games.
Computers are still horrible at overlooking kingside attacks. And they often
don't understand blocked positions at all. Trying to avoid blocking things is
one 'crutch' that I rely on with Crafty, but it isn't the "final solution" by
any stretch of the imagination.

Four situations, or position classes, are mentioned here as problematic for engines circa 2000. One is "see a capture make a capture." Two is blockaded pawn structures. Three is meandering aimlessly through flat endgames. Four is king side attacks that are recognized too late in the game as threatening. In the latter two cases it was not uncommon for the engine to have reached an theoretically won position by the late middlegame, but squanders it away back to a draw against alert humans. As you can appreciate the programmers knew about these problems and worked hard in improving their evaluation function and search algorithms.

In the here and now I believe the bag of tricks has emptied out. There used to be a small number of posters who would spam this board with exaggerated claims of being able to reliably beat Stockfish with anti-computer Hippopotamus-like structures. Such work did not hold up under scrutiny, to put it politely.

If we drop the requirement that it be humans who are the ones laying and exploiting positional traps, a couple illustrations come to mind. The first is "thorn pawns". When Alpha Zero, and then Leela Zero, and then Stockfish adopted neural nets they discovered a fascinating way to exploit weaknesses of engines with human crafted evaluation functions (HCEs). They would throw a pawn up the board and (as White) plant it on h6 without leaving it hanging. This became annoying to Black - a "thorn in the side", hence the name - inciting the HCE engine to distraction and eventual mistake.

The second is the way recent Stockfish seems to have a magical ability to exploit the 50-move rule in semi-blocked positions against still very strong computer opponents, inducing them to make a mistake in theoretically drawn positions. The strategy Stockfish employs is called "block & lock, shuffle shuffle shuffle, sac, win."

That noted, suppose we take a modern engine and restricted it to search at most two ply. Under such conditions there will be structurally unavoidable horizon effects that can be exploited -- because even the highest fidelity of evaluation neural nets cannot pack all of chess knowledge inside the range of a two ply search. This is argument by extreme case, though.

The phrasing "structurally unavoidable horizon effects" is a funny one. So what would make the horizon effect of limited search unavoidable, let alone "structurally unavoidable"? Well, suppose you are presented with a 100 ply deep random tree with random leaf node values. A heuristic function is uninformative against a random tree; there is no choice but to search the entire thing to find the gold coins at the bottom. This is an extreme example in the other direction. On the flip side, the horizon effect is not exploitable through guiding the opponent into traps, either.

In chess there is an abundance of information that is captured during neural network learning, which during a game is patched with search. What is left behind is residual information. When engines were weak this residual information contained structure, which, for a few decades, an ever-decreasing contingent of human players could exploit advantageously.

Considering the strongest engines today, the residual information is increasingly sparse, and takes on an increasingly random character. To be fair, that what remains is random, or pseudo-random, is not something I can prove. But it is what I posit. I'd be surprised, and fascinated, if the leftovers have much structure left to be found. Then again chess is a massive mathematical object abundant in intrigue.