Answers.Body: <p>The other answer is wrong; we <strong>can in fact</strong> program the chess engine to favour traps! As you already noted, when the engine thinks it is winning it should simply choose the best move. So the question is how to aim for the sharpest lines for the opponent when it is losing. This is of course subjective, and depends on the kind of opponent we are pitting it against, but there are a few obvious ways to achieve this.</p>
  
  <p>Firstly, we could compute the best play assuming the opponent makes exactly one mistake (as seen from our game tree). Best play assumes that both players make zero mistakes, but we are aiming to trick the opponent to make a mistake, hence we need to know what are the best lines if the opponent does make a mistake. We now have two evaluation scores for each move X, one for the best play and one for the best play with one opponent mistake. Denote these by E0(X) and E1(X) respectively. We can then combine these two scores by some heuristic to obtain an overall score. The safest heuristic is to choose the move X with E1(X)≥0 such that E0(X) is maximum. This heuristic in fact agrees with choosing the best move X if E0(X)>0, since E1(X)≥E0(X). A slightly less safe heuristic is to choose the move with E1(X)>0 such that E0(X) is maximum, which might occasionally choose an inferior move if the best move X has E0(X)=0, in order to try for a win. You can of course design your own heuristic if you want your engine to play more dangerously.</p>
  
  <p>Another way is to incorporate some probabilistic evaluation, by treating opponent play as a random process that occasionally makes mistakes with the distribution of the chosen move depending on the scores of the available moves. I do not think that this is a good general approach, because although it may do well against humans (humans being careless creatures), it is not going to do well against other computer players, as compared to the other approach I gave above.</p>
  
  <p>I also want to emphasize that for this question ("when the game outcome is within their horizon"), any 'hack' such as 'contempt factor' is simply not applicable, because all the terminal nodes in the game tree have known outcomes. Also, many chess engines use a 'contempt factor' instead of the kind of technique I described because it is computationally cheap ('contempt' can be implemented simply as a slightly negative score for a probable forced draw). But if you can already see all the outcomes from a position onwards, it is trivial and costs almost nothing to implement the technique I gave above. The reason it is expensive if the outcome is beyond the search horizon is that, since alpha-beta pruning may prune branches with mistakes, we would frequently need to search substantially more branches to compute E1 correctly.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-04-23T12:26:49.943Z
Answers.Text: Comments are not for extended discussion; this conversation has been [moved to chat](https://chat.stackexchange.com/rooms/107090/discussion-on-answer-by-user21820-how-do-chess-engines-decide-which-best-line-to).
Answers.UserDisplayName: Brian Towers
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-09-18T21:13:13.870Z
Answers.Text: @user21820 "compute the best play assuming the opponent makes exactly one mistake (as seen from our game tree)" what exactly constitutes making a 'mistake' in the gametree? How do we detect this (given access to the full gametree)?
Answers.UserDisplayName: Mobeus Zoom
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-09-18T21:19:34.397Z
Answers.Text: Is it simply '(if we go down this branch of the gametree then) on *some* subsequent move the opponent will play a move that drops the evaluation according to subsequent best play (i.e. win with best-play -> draw with best-play -> loss with best-play)'?
Answers.UserDisplayName: Mobeus Zoom
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-09-18T21:22:02.923Z
Answers.Text: @MobeusZoom: No. It's just a trivial recursion. Look up dynamic programming.
Answers.UserDisplayName: user21820
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-09-18T21:31:55.903Z
Answers.Text: I'm not asking an algorithmic question but a mathematical one (how you are defining a 'mistake' according to the gametree).
Answers.UserDisplayName: Mobeus Zoom
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-09-18T21:37:36.377Z
Answers.Text: @MobeusZoom: Mistake means choosing a move that leads to a poorer outcome (under optimal play thereafter). Clearly here we want this mistake to have the second-best outcome.
Answers.UserDisplayName: user21820
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-10-04T16:28:36.460Z
Answers.Text: @user21820 The more I think about this the less viable it seems (as a theoretic concept). If you do not assign probabilities to mistakes, then this algorithm is like saying (assuming theoretical result is a draw) 'do not go for lines where **every** move the opponent plays maintains a draw but rather where the opponent has >=1 possible moves that would drop the evaluation'. But this is trivially not worth the extra compute because there are exceptionally few positions where every possible move-choice will maintain the draw. I.E., it only filters out a tiny, not useful portion of the gametree.
Answers.UserDisplayName: Mobeus Zoom
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-10-04T16:31:50.573Z
Answers.Text: In other words, before your opponent has made a mistake, almost all of the gametree looks viable (because there are possible move-choices that would be mistakes in almost every position); *after* they have made a mistake, you of course just switch to optimal play since now you can force a win.
Answers.UserDisplayName: Mobeus Zoom
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-10-04T16:39:01.997Z
Answers.Text: @MobeusZoom: You clearly do not understand the algorithm. But sorry I am not interested in explaining anymore.
Answers.UserDisplayName: user21820
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-10-04T16:48:32.327Z
Answers.Text: Riiight. Well I 'understand' all the 'other' research in this area, which you do not refer to, so perhaps you should [have a look at it](https://athena.ecs.csus.edu/~gordonvs/papers/TMM.pdf) and establish where your algorithm differs.
Answers.UserDisplayName: Mobeus Zoom
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-10-04T16:53:16.043Z
Answers.Text: As I said, I'm not interested in explaining when you criticize something you do not understand.
Answers.UserDisplayName: user21820
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-10-04T16:57:45.277Z
Answers.Text: I *do* understand. (It is up to you whether you want to use invective, be silent, or actually respond in a way that clarifies your argument.) The point is it is not useful in chess to have an evaluation score for 'the best play with one opponent mistake' because this is E0 iff the opponent has no opportunity to make a mistake, and otherwise is identical for all positions where a mistake is possible, and the former is extremely rare on the gametree. The latter is where trappy minimax and ideas proposed in research differ from yours (but require an opponent model). Engage with the research first
Answers.UserDisplayName: Mobeus Zoom
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-10-04T16:58:25.257Z
Answers.Text: As for 'criticism' it should be clear I have put in the effort to understand your idea before pointing out the issue. Assess for yourself from the past research (like I linked) whether or not your idea really works.
Answers.UserDisplayName: Mobeus Zoom
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-10-04T17:00:03.643Z
Answers.Text: Stop asking me to engage with research when you are simply making false statements about the algorithm I proposed. And stop pinging me.
Answers.UserDisplayName: user21820
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-10-04T17:15:17.793Z
Answers.Text: Lol, as usual, users love to downvote things that they do not understand, besides claiming to "engage in research".
Answers.UserDisplayName: user21820
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-04-20T04:23:43.397Z
Answers.LastActivityDate: 2020-04-20T06:38:49.690Z
Answers.LastEditDate: 2020-04-20T06:38:49.690Z
Answers.UserDisplayName: user21820
Answers.Body: <p>If the engine can choose between getting mated in 2 or mated in 3, it'll choose the line where it is mated in 3 (even though the mate in 2 might be 'more difficult' to spot for humans).</p>
  <p>It can't really set traps, because it doesn't know what things might be difficult to spot for a human (or other engine) opponent. It just evaluates the position, without really knowing it's playing a game against somebody; a notable exception is the implementation of <a href="https://chess.stackexchange.com/a/26511/7297">contempt</a>, basically a slight modification of the evaluation in order to prevent drawing too early.</p>
  <p>For example, in Stockfish, scores for won or lost positions are computed with the function <code>mated_in</code> (and, more rarely, its negated form <code>mate_in</code>).  As you can see in <a href="https://github.com/official-stockfish/Stockfish/blob/221893bf679f70098e6f751fded2fe843471c6be/src/types.h#L381" rel="nofollow noreferrer">the code</a>, a loss is scored as a large negative value plus the number of ply until the loss, so the engine favors winning lines that are fast and losing lines that are slow.</p>
  <p>The tie-breaking for draws is usually arbitrary.  For instance, in Stockfish, scores for drawn positions are either the constant <code>VALUE_DRAW</code> or computed by the function <a href="https://github.com/official-stockfish/Stockfish/blob/221893bf679f70098e6f751fded2fe843471c6be/src/search.cpp#L91" rel="nofollow noreferrer"><code>value_draw</code></a> to be <code>VALUE_DRAW</code> plus or minus one.  The bonus depends on the thread's node counter, which is essentially up to luck, so the variations in scores for drawn positions are not really based on the positions themselves.  This small bit of noise in draw scoring is more to <a href="https://github.com/official-stockfish/Stockfish/commit/97d2cc9a9c1c4b6ff1b470676fa18c7fc6509886" rel="nofollow noreferrer">keep the search from fixating on certain three-fold repetitions</a> than to help it choose among lines.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-04-18T19:58:25.973Z
Answers.Text: Typical use case; you setup a winning position against an engine in order to train yourself on "winning a won position" against a strong opponent. There's a mate in 15 -that of course you just can't see- but the engine sees it, and being its turn to play, it gives up its queen getting into a trivially won endgame for you (but with a mate distance larger than 15).
Answers.UserDisplayName: emdio
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-04-19T06:57:01.400Z
Answers.Text: I actually don't know about draws. I never really programmed a chess engine myself :)
Answers.UserDisplayName: Glorfindel
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-04-19T10:11:01.850Z
Answers.Text: @which-line, the only answer I can think about is just read about the alpha-beta search. It covers also the important topic of good move ordering in order to find -faster- the best move.
Answers.UserDisplayName: emdio
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-07-05T01:47:48.397Z
Answers.Text: This answer over-generalises. Yes, this how the most popular engines operate, but they don't have to. They *can* find and set traps, and they *could* prioritise lines with a tiny chance of winning over drawing out a certain a death (against perfect play) a bit longer.
Answers.UserDisplayName: Steve Bennett
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-04-18T18:16:59.250Z
Answers.LastActivityDate: 2021-07-04T14:12:46.247Z
Answers.LastEditDate: 2021-07-04T14:12:46.247Z
Answers.UserDisplayName: Glorfindel
Body: <p>Inspired by the Hot Network Question <a href="https://chess.stackexchange.com/questions/29236">"In this puzzle, why does white play dxe5?"</a>, when a chess engine is in a position that it can definitively call lost, drawn, or won, what policy is used to decide among lines that lead to the same outcome?</p>
  
  <p>In a won position, the answer seems easy: play the line that leads to checkmate fastest.  But in a lost or drawn position, the engine's opponent may not realize the situation, so it should continue fighting, ideally playing a complicated line and setting traps in hopes of swindling a draw or win.  But it is not clear to me how the code could identify such a line from a game tree and evaluation scores alone.</p>
  
  <p>(In a game with time controls, the answer may be more complicated; I am okay with an answer that ignores considerations of time pressure.)</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-04-19T10:29:32.787Z
Comments.Text: “In a won position, the answer seems easy: play the line that leads to checkmate fastest” — not necessarily. Syzygy tablebases are organized in a way that while they never surrender a win to the 50 move counter, they sometimes suggest very long and roundabout sequences of moves. This is because storing exact moves to the fastest win would require extra space, which Syzygy aims to avoid.
Comments.UserDisplayName: Roman Odaisky
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-04-19T14:02:15.733Z
Comments.Text: Interesting question. Recently I have been using AI Factory's chess on a mobile device at a level that I am able to beat about 50% of the time (I won't embarrass myself and say what that level is) It's [Treebeard chess engine](http://www.aifactory.co.uk/newsletter/2005_02_treebeard_chess.htm) frequently allows preventable mates in 1 or 2 in lost positions by playing active moves which have some swindle potential. I don't know if this is an artifact of the way they hobble the engine's full strength at lower levels or clever programming on their part.
Comments.UserDisplayName: John Coleman
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-04-20T05:50:53.627Z
Comments.Text: @JohnColeman: You may be interested in my answer, which is focused on obtaining a strong chess engine that can try to lay traps without requiring inbuilt domain knowledge. To answer your query, the Treebeard engine is [said to have human error modelling](http://www.aifactory.co.uk/newsletter/2019_01_playing_badly.htm), and the example given (the Fajarowicz Trap) shows the kind of 'errors' the engine might make to seem more human. It may explain why you feel that it tries to swindle you when losing, because it plays moves based on how it thinks humans would play, not the absolute best line.
Comments.UserDisplayName: user21820
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-04-20T07:18:12.077Z
Comments.Text: @RomanOdaisky: ok but the OP's intent is not asking about endgames and 50-move-rule.
Comments.UserDisplayName: smci
Tags: <engines><programming><evaluation><chess-algorithms>
Title: How do chess engines decide which best line to play when the game outcome is within their horizon?
ThreadText: # How do chess engines decide which best line to play when the game outcome is within their horizon?
  
  (Asked by: username_0 on 2020-04-18)
  
  Inspired by the Hot Network Question ["In this puzzle, why does white play dxe5?"](https://chess.stackexchange.com/questions/29236), when a chess engine is in a position that it can definitively call lost, drawn, or won, what policy is used to decide among lines that lead to the same outcome?
  
  In a won position, the answer seems easy: play the line that leads to checkmate fastest. But in a lost or drawn position, the engine's opponent may not realize the situation, so it should continue fighting, ideally playing a complicated line and setting traps in hopes of swindling a draw or win. But it is not clear to me how the code could identify such a line from a game tree and evaluation scores alone.
  
  (In a game with time controls, the answer may be more complicated; I am okay with an answer that ignores considerations of time pressure.)
  
  **Tags:** engines, programming, evaluation, chess-algorithms
  
  > **Comments:**
  > **username_1**: “In a won position, the answer seems easy: play the line that leads to checkmate fastest” — not necessarily. Syzygy tablebases are organized in a way that while they never surrender a win to the 50 move counter, they sometimes suggest very long and roundabout sequences of moves. This is because storing exact moves to the fastest win would require extra space, which Syzygy aims to avoid.  
  > **username_2**: Interesting question. Recently I have been using AI Factory's chess on a mobile device at a level that I am able to beat about 50% of the time (I won't embarrass myself and say what that level is) It's [Treebeard chess engine](http://www.aifactory.co.uk/newsletter/2005_02_treebeard_chess.htm) frequently allows preventable mates in 1 or 2 in lost positions by playing active moves which have some swindle potential. I don't know if this is an artifact of the way they hobble the engine's full strength at lower levels or clever programming on their part.  
  > **username_3**: @username_2: You may be interested in my answer, which is focused on obtaining a strong chess engine that can try to lay traps without requiring inbuilt domain knowledge. To answer your query, the Treebeard engine is [said to have human error modelling](http://www.aifactory.co.uk/newsletter/2019_01_playing_badly.htm), and the example given (the Fajarowicz Trap) shows the kind of 'errors' the engine might make to seem more human. It may explain why you feel that it tries to swindle you when losing, because it plays moves based on how it thinks humans would play, not the absolute best line.  
  > **username_4**: @username_1: ok but the OP's intent is not asking about endgames and 50-move-rule.  
  
  ---
  
  ## 2 answers
  
  ### Answer by username_7 on 2020-04-18. Score: 20 | Accepted answer
  
  If the engine can choose between getting mated in 2 or mated in 3, it'll choose the line where it is mated in 3 (even though the mate in 2 might be 'more difficult' to spot for humans).
  
  It can't really set traps, because it doesn't know what things might be difficult to spot for a human (or other engine) opponent. It just evaluates the position, without really knowing it's playing a game against somebody; a notable exception is the implementation of [contempt](https://chess.stackexchange.com/a/26511/7297), basically a slight modification of the evaluation in order to prevent drawing too early.
  
  For example, in Stockfish, scores for won or lost positions are computed with the function `mated_in` (and, more rarely, its negated form `mate_in`). As you can see in [the code](https://github.com/official-stockfish/Stockfish/blob/221893bf679f70098e6f751fded2fe843471c6be/src/types.h#L381), a loss is scored as a large negative value plus the number of ply until the loss, so the engine favors winning lines that are fast and losing lines that are slow.
  
  The tie-breaking for draws is usually arbitrary. For instance, in Stockfish, scores for drawn positions are either the constant `VALUE_DRAW` or computed by the function [`value_draw`](https://github.com/official-stockfish/Stockfish/blob/221893bf679f70098e6f751fded2fe843471c6be/src/search.cpp#L91) to be `VALUE_DRAW` plus or minus one. The bonus depends on the thread's node counter, which is essentially up to luck, so the variations in scores for drawn positions are not really based on the positions themselves. This small bit of noise in draw scoring is more to [keep the search from fixating on certain three-fold repetitions](https://github.com/official-stockfish/Stockfish/commit/97d2cc9a9c1c4b6ff1b470676fa18c7fc6509886) than to help it choose among lines.
  
  > **Comments:**
  > **username_8**: Typical use case; you setup a winning position against an engine in order to train yourself on "winning a won position" against a strong opponent. There's a mate in 15 -that of course you just can't see- but the engine sees it, and being its turn to play, it gives up its queen getting into a trivially won endgame for you (but with a mate distance larger than 15).  
  > **username_7**: I actually don't know about draws. I never really programmed a chess engine myself :)  
  > **username_8**: @username_0, the only answer I can think about is just read about the alpha-beta search. It covers also the important topic of good move ordering in order to find -faster- the best move.  
  > **username_9**: This answer over-generalises. Yes, this how the most popular engines operate, but they don't have to. They *can* find and set traps, and they *could* prioritise lines with a tiny chance of winning over drawing out a certain a death (against perfect play) a bit longer.  
  
  ---
  
  ### Answer by username_3 on 2020-04-20. Score: 7
  
  The other answer is wrong; we **can in fact** program the chess engine to favour traps! As you already noted, when the engine thinks it is winning it should simply choose the best move. So the question is how to aim for the sharpest lines for the opponent when it is losing. This is of course subjective, and depends on the kind of opponent we are pitting it against, but there are a few obvious ways to achieve this.
  
  Firstly, we could compute the best play assuming the opponent makes exactly one mistake (as seen from our game tree). Best play assumes that both players make zero mistakes, but we are aiming to trick the opponent to make a mistake, hence we need to know what are the best lines if the opponent does make a mistake. We now have two evaluation scores for each move X, one for the best play and one for the best play with one opponent mistake. Denote these by E0(X) and E1(X) respectively. We can then combine these two scores by some heuristic to obtain an overall score. The safest heuristic is to choose the move X with E1(X)≥0 such that E0(X) is maximum. This heuristic in fact agrees with choosing the best move X if E0(X)>0, since E1(X)≥E0(X). A slightly less safe heuristic is to choose the move with E1(X)>0 such that E0(X) is maximum, which might occasionally choose an inferior move if the best move X has E0(X)=0, in order to try for a win. You can of course design your own heuristic if you want your engine to play more dangerously.
  
  Another way is to incorporate some probabilistic evaluation, by treating opponent play as a random process that occasionally makes mistakes with the distribution of the chosen move depending on the scores of the available moves. I do not think that this is a good general approach, because although it may do well against humans (humans being careless creatures), it is not going to do well against other computer players, as compared to the other approach I gave above.
  
  I also want to emphasize that for this question ("when the game outcome is within their horizon"), any 'hack' such as 'contempt factor' is simply not applicable, because all the terminal nodes in the game tree have known outcomes. Also, many chess engines use a 'contempt factor' instead of the kind of technique I described because it is computationally cheap ('contempt' can be implemented simply as a slightly negative score for a probable forced draw). But if you can already see all the outcomes from a position onwards, it is trivial and costs almost nothing to implement the technique I gave above. The reason it is expensive if the outcome is beyond the search horizon is that, since alpha-beta pruning may prune branches with mistakes, we would frequently need to search substantially more branches to compute E1 correctly.
  
  > **Comments:**
  > **username_5**: Comments are not for extended discussion; this conversation has been [moved to chat](https://chat.stackexchange.com/rooms/107090/discussion-on-answer-by-username_3-how-do-chess-engines-decide-which-best-line-to).  
  > **username_6**: @username_3 "compute the best play assuming the opponent makes exactly one mistake (as seen from our game tree)" what exactly constitutes making a 'mistake' in the gametree? How do we detect this (given access to the full gametree)?  
  > **username_6**: Is it simply '(if we go down this branch of the gametree then) on *some* subsequent move the opponent will play a move that drops the evaluation according to subsequent best play (i.e. win with best-play -> draw with best-play -> loss with best-play)'?  
  > **username_3**: @username_6: No. It's just a trivial recursion. Look up dynamic programming.  
  > **username_6**: I'm not asking an algorithmic question but a mathematical one (how you are defining a 'mistake' according to the gametree).  
  > **username_3**: @username_6: Mistake means choosing a move that leads to a poorer outcome (under optimal play thereafter). Clearly here we want this mistake to have the second-best outcome.  
  > **username_6**: @username_3 The more I think about this the less viable it seems (as a theoretic concept). If you do not assign probabilities to mistakes, then this algorithm is like saying (assuming theoretical result is a draw) 'do not go for lines where **every** move the opponent plays maintains a draw but rather where the opponent has >=1 possible moves that would drop the evaluation'. But this is trivially not worth the extra compute because there are exceptionally few positions where every possible move-choice will maintain the draw. I.E., it only filters out a tiny, not useful portion of the gametree.  
  > **username_6**: In other words, before your opponent has made a mistake, almost all of the gametree looks viable (because there are possible move-choices that would be mistakes in almost every position); *after* they have made a mistake, you of course just switch to optimal play since now you can force a win.  
  > **username_3**: @username_6: You clearly do not understand the algorithm. But sorry I am not interested in explaining anymore.  
  > **username_6**: Riiight. Well I 'understand' all the 'other' research in this area, which you do not refer to, so perhaps you should [have a look at it](https://athena.ecs.csus.edu/~gordonvs/papers/TMM.pdf) and establish where your algorithm differs.  
  > **username_3**: As I said, I'm not interested in explaining when you criticize something you do not understand.  
  > **username_6**: I *do* understand. (It is up to you whether you want to use invective, be silent, or actually respond in a way that clarifies your argument.) The point is it is not useful in chess to have an evaluation score for 'the best play with one opponent mistake' because this is E0 iff the opponent has no opportunity to make a mistake, and otherwise is identical for all positions where a mistake is possible, and the former is extremely rare on the gametree. The latter is where trappy minimax and ideas proposed in research differ from yours (but require an opponent model). Engage with the research first  
  > **username_6**: As for 'criticism' it should be clear I have put in the effort to understand your idea before pointing out the issue. Assess for yourself from the past research (like I linked) whether or not your idea really works.  
  > **username_3**: Stop asking me to engage with research when you are simply making false statements about the algorithm I proposed. And stop pinging me.  
  > **username_3**: Lol, as usual, users love to downvote things that they do not understand, besides claiming to "engage in research".  
  
  ---
  
  