Answers.Body: <p>I would first like to acknowledge that this answer is somewhat speculative; this is the first time I've seen this feature in a a chess engine, and I'd be interested to know what other chess programmers think of my answer. </p>
  
  <hr>
  
  <p>Contrary to what is commonly believed, (good) chess engines don't just "search all possible moves" up to a certain depth then pick the best one. If we were limited to this, modern engines would only be ~1600. An incredibly, stupidly important idea in chess programming is that of "<a href="https://www.chessprogramming.org/Reductions" rel="nofollow noreferrer">reductions</a>." There are many different types, but the basic idea is that computers don't search some lines it doesn't consider promising.</p>
  
  <p>Of course, this is a very double edged sword. On the one hand, you get much deeper and more effective searches, but on the other you are destined to miss something. To give you a taste, consider the following position:</p>
  
  <pre><code>[FEN "3n3k/rp4pp/1p5r/pPp1pp2/PpPp1p2/3PpPp1/RN2P1P1/QBNR1BK1 b - - 0 1"]
  </code></pre>
  
  <p>I'm confident a reasonable player can find the simple mate for black (get both rooks on the h file, and mate on h1, after Ne6 to ensure that White cannot break through), but Stockfish 10 can't find it at "<strong>depth 50</strong>". This happens because the mate involves like 7 consecutive quiet moves, which Stockfish doesn't see as significant enough to warrant intensive search. (<a href="https://lichess.org/study/ZHKBWGvq" rel="nofollow noreferrer">Another example on Lichess</a>.) When engines miss tactics, most of the time something like this is to blame.</p>
  
  <p>One of the most common forms of this technique are "<a href="https://www.chessprogramming.org/Late_Move_Reductions" rel="nofollow noreferrer">late move reductions</a>," wherein the computer <strong>selectively</strong> reduces moves found later in the move ordering. (this sorta presupposes you have semi-decent move ordering, but you said you already knew a little of that, so we're skipping it).  </p>
  
  <hr>
  
  <p>Next, <a href="https://www.chessprogramming.org/Iterative_Deepening" rel="nofollow noreferrer">iterative deepening</a>. Basically, the idea is that if you ask Stockfish to search at depth 25, it will start by searching depth 1, then depth 2, then depth 3,... then depth 25. This seems like a stupid idea at first, but it has various benefits most of which I won't go into. What's relevant here is that the depth 24 search informs decisions about reductions the depth 25 search makes. So if depth 24 says a move isn't too promising, depth 25 is less likely to search it deeply. (this is a <strong>massive</strong> simplification).</p>
  
  <hr>
  
  <p>Ok so what's happening in the commit?</p>
  
  <blockquote>
    <p>The effect is that in positions with many 3-fold draw lines, different lines are followed at each iteration. This keeps the search much more dynamic, as opposed to being locked to one particular 3-fold.</p>
  </blockquote>
  
  <p>Here's how I'm reading this: Before the commit, the computer will be searching the same draws at every iteration. If there are lots of 3-fold lines, it's possible the computer won't search all of them (or at least, all of them deeply). This can lead to "blind spots," where the computer doesn't notice some sideline in a move with a draw score. </p>
  
  <p>Before the commit, each successive iteration would have (roughly) the same blind spots (albeit with more resources to notice the sideline). After the commit, the blind spots are scrambled at each iteration, making it less likely to miss the sideline.</p>
  
  <hr>
  
  <p>As a toy hypothetical example (which shouldn't be taken too literally): say we have two "draw" moves A and B, both of which are way out at the horizon of the search. Because they are so far away, the computer's evaluation of them is very bad (for several reasons, but for the time being we can just think that only a few of A and B's children are searched due to reductions) so it's possible A and B aren't actually draws. </p>
  
  <p>Now for whatever reason (perhaps reductions), let's say the computer has allocated 5 resources to search the "best" draw move and 3 resources for the "second best" draw move at iteration 24, while allocating 6 and 4 respectively at iteration 25. </p>
  
  <p>Let's also say A is a genuine draw, but B has a sideline which isn't, and will be noticed if it is searched with 5 resources.</p>
  
  <p>Before the commit, if A is searched first at iteration 24, it will likely also be searched first at iteration 25 (meaning the sideline slips through), but after the commit, A and B are equally likely to be searched at each iteration, meaning the sideline is more likely to be found at <em>some</em> iteration, whereupon the computer will take note and correct.</p>
  
  <p>I don't know if that made any sense whatsoever, but I hope it helps.</p>
  
  <hr>
  
  <p>Again, I'm very open to being corrected here. This is just my reading of the commit.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-05-25T16:27:24.583Z
Answers.Text: Can you please add a principal variation for your example? It seems like White can break through and prevent Black from using the two rooks to reach an easy checkmate, by sacrificing a lot of material. For example, 1... Nf7 2. Nb3 Ra8 3. Rc1 Rd8 4. Nxb4 Rdd6 5. Qxd4 exd4 6. Nxd4 cxd4 7. c5 bxc5 8. Rxc5 axb4, if I didn't make a mistake. Also, why does Black have 13 pawns?
Answers.UserDisplayName: user21820
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-05-25T18:18:32.300Z
Answers.Text: The 13 pawns are to disallow massive material sacrifices like this; the position is meant to illustrate a point, not display a shortcoming in Stockfish. 
  
  When I initially made it, I forced in a few lines (1... Ne6 not Nf7), and beat it until I was satisfied. This doesn't mean there isn't some other line (that Stockfish doesn't see!) which lets white break through by giving up a bunch of material. I made a few minor modifications to the link (discordinating white's piece further) with similar results.
  
  I wasn't trying to create an airtight puzzle, but to make a point about reductions.
Answers.UserDisplayName: Noah Caplinger
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-05-26T06:30:56.073Z
Answers.Text: I understand the point you were making. However, it would be really nice to actually have an airtight demonstration of that very point. Would you mind if I modify your example to make sure of that? =)
Answers.UserDisplayName: user21820
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-05-26T17:32:57.837Z
Answers.Text: sure, go ahead (I'll delete this once you do)
Answers.UserDisplayName: Noah Caplinger
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-05-27T16:42:58.197Z
Answers.Text: Ok I tried my best; do you mind checking to see if you spot any holes? The purpose of the pawn at f5 is to prevent a White knight from jumping in like "1... Ne6 2. Nb3 Ra8 3. Nd2 Rf8 4. Ne4 fxe4 5. dxe4 Rff6 6. Nd3 Rh5 7. Nxe5 Rxe5 8. Rxd4 Nxd4 9. Rd2 exd2 10. Qxd4 cxd4". And this time it seems that the surest Black strategy is really Ne6 as shown by "1... Ne6 2. Nb3 Ra8 3. Rc1 Rf8 4. Nd1 Rff6 5. Nxc5 Nxc5 6. Qxd4 exd4 7. Nxe3 fxe3". Incidentally, Stockfish now gives White an even higher score due to the extra rook heheh.
Answers.UserDisplayName: user21820
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-05-12T22:43:53.487Z
Answers.LastActivityDate: 2020-05-27T16:36:57.897Z
Answers.LastEditDate: 2020-05-27T16:36:57.897Z
Answers.UserDisplayName: Noah Caplinger
Answers.Body: <p>The general answer is that by scoring these "3-fold" and "50-move" draws with some randomization, the engine will naturally be encouraged to explore different lines of play on successive searches. Moreover, these "draws" won't all be flooded into the Transposition Table (Big table of saved search results) with the same score.</p>
  
  <p>I put "50-move" in quotes for a reason. Due to how positions are stored into the Transposition Table (often without regard for the actual 50-move counter), its possible for a position to "appear" to be a draw, but not actually be. The best example would be the cursed-wins / blessed-losses that occur in the Syzygy Tablebases, which require an extension of the 50-move rule in order to obtain mate without drawing.</p>
  
  <p>For "3-fold" draws, there is a similar reason. I am not absolutely certain of the inner workings of Stockfish, but I believe the following is true for Stockfish (and is certainly true for some others): Often time "2-fold" repetitions are scored as draws. This is to speedup the search greatly (gains elo). I say "often times". Sometimes this is not the case, like when the first occurrence of a given position occurred BEFORE the root of the search. In other words, the the "2-fold" occurs entirely in the search, and has not actually been played in part or in full over the board. Again, this trick of randomization encourages some additional exploration, which helps to avoid rather "unlucky" understandings of a position.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-05-14T12:21:23.813Z
Answers.LastActivityDate: 2020-05-14T12:21:23.813Z
Answers.UserDisplayName: AndrewGrant
Body: <p>In <a href="https://github.com/official-stockfish/Stockfish/commit/97d2cc9a9c1c4b6ff1b470676fa18c7fc6509886" rel="noreferrer">this commit</a>, a change was made to the way Stockfish scores board positions that are draws due to 3-fold repetition or 50-move limits. Prior to this commit, a drawn position was assigned a score of zero; afterwards, it is randomly assigned a score of +/-1 (that is, a tiny non-zero value). In the commit message, the intended result is explained:</p>
  
  <blockquote>
    <p>The effect is that in positions with many 3fold draw lines, different
    lines are followed at each iteration. This keeps the search much more dynamic,
    as opposed to being locked to one particular 3fold.</p>
    
    <p>An example of a position where master suffers from 3fold-blindness and this patch
    solves quickly is the famous TCEC game 53:</p>
    
    <p>FEN: 3r2k1/pr6/1p3q1p/5R2/3P3p/8/5RP1/3Q2K1 b - - 0 51</p>
    
    <p>master doesn't see that this is a lost position (draw eval up to depth 50) as
    Qf6-e6 d4-d5 (found by patch at depth 23) leads to a loss.</p>
  </blockquote>
  
  <p>I don't understand what the change actually accomplishes. Why is visiting drawn positions in different orders helpful? What is meant by "3fold blindness"?</p>
  
  <p>For reference, here's the board position mentioned in the message.</p>
  
  <pre><code>[FEN "3r2k1/pr6/1p3q1p/5R2/3P3p/8/5RP1/3Q2K1 b - - 0 51"]
  </code></pre>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-05-11T20:14:58.067Z
Comments.Text: How familiar are you with iterative deepening, move ordering heuristics and late move reduction? I have a speculative answer that requires some pre-requisites.
Comments.UserDisplayName: Noah Caplinger
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-05-11T22:15:07.697Z
Comments.Text: @NoahCaplinger I've written [my own chess engine](https://github.com/MarkZH/Genetic_Chess/) that uses minimax and alpha-beta pruning, so I have some familiarity with ordering moves to maximize pruning. I've read a little about iterative deepening. Go ahead and write your answer. Even if I don't understand a prerequisite, I'll have a starting point for doing my own research. If appropriate, links to the [chessprogramming wiki](https://www.chessprogramming.org/Main_Page) would help, too.
Comments.UserDisplayName: Mark H
Tags: <engines><stockfish><programming>
Title: Stockfish draw value randomization and "3-fold blindness"
ThreadText: # Stockfish draw value randomization and "3-fold blindness"
  
  (Asked by: username_0 on 2020-05-11)
  
  In this commit, a change was made to the way Stockfish scores board positions that are draws due to 3-fold repetition or 50-move limits. Prior to this commit, a drawn position was assigned a score of zero; afterwards, it is randomly assigned a score of +/-1 (that is, a tiny non-zero value). In the commit message, the intended result is explained:
  
  The effect is that in positions with many 3fold draw lines, different
    lines are followed at each iteration. This keeps the search much more dynamic,
    as opposed to being locked to one particular 3fold.
  An example of a position where master suffers from 3fold-blindness and this patch
    solves quickly is the famous TCEC game 53:
  FEN: 3r2k1/pr6/1p3q1p/5R2/3P3p/8/5RP1/3Q2K1 b - - 0 51
  master doesn't see that this is a lost position (draw eval up to depth 50) as
    Qf6-e6 d4-d5 (found by patch at depth 23) leads to a loss.
  
  I don't understand what the change actually accomplishes. Why is visiting drawn positions in different orders helpful? What is meant by "3fold blindness"?
  For reference, here's the board position mentioned in the message.
  [FEN "3r2k1/pr6/1p3q1p/5R2/3P3p/8/5RP1/3Q2K1 b - - 0 51"]
  
  **Tags:** engines, stockfish, programming
  
  > **Comments:**
  > **username_1**: How familiar are you with iterative deepening, move ordering heuristics and late move reduction? I have a speculative answer that requires some pre-requisites.  
  > **username_0**: @NoahCaplinger I've written [my own chess engine](https://github.com/MarkZH/Genetic_Chess/) that uses minimax and alpha-beta pruning, so I have some familiarity with ordering moves to maximize pruning. I've read a little about iterative deepening. Go ahead and write your answer. Even if I don't understand a prerequisite, I'll have a starting point for doing my own research. If appropriate, links to the [chessprogramming wiki](https://www.chessprogramming.org/Main_Page) would help, too.  
  
  ---
  
  ## 2 answers
  
  ### Answer by username_1 on 2020-05-12. Score: 2
  
  I would first like to acknowledge that this answer is somewhat speculative; this is the first time I've seen this feature in a a chess engine, and I'd be interested to know what other chess programmers think of my answer. 
  
  Contrary to what is commonly believed, (good) chess engines don't just "search all possible moves" up to a certain depth then pick the best one. If we were limited to this, modern engines would only be ~1600. An incredibly, stupidly important idea in chess programming is that of "reductions." There are many different types, but the basic idea is that computers don't search some lines it doesn't consider promising.
  Of course, this is a very double edged sword. On the one hand, you get much deeper and more effective searches, but on the other you are destined to miss something. To give you a taste, consider the following position:
  [FEN "3n3k/rp4pp/1p5r/pPp1pp2/PpPp1p2/3PpPp1/RN2P1P1/QBNR1BK1 b - - 0 1"]
  
  I'm confident a reasonable player can find the simple mate for black (get both rooks on the h file, and mate on h1, after Ne6 to ensure that White cannot break through), but Stockfish 10 can't find it at "depth 50". This happens because the mate involves like 7 consecutive quiet moves, which Stockfish doesn't see as significant enough to warrant intensive search. (Another example on Lichess.) When engines miss tactics, most of the time something like this is to blame.
  One of the most common forms of this technique are "late move reductions," wherein the computer selectively reduces moves found later in the move ordering. (this sorta presupposes you have semi-decent move ordering, but you said you already knew a little of that, so we're skipping it).  
  
  Next, iterative deepening. Basically, the idea is that if you ask Stockfish to search at depth 25, it will start by searching depth 1, then depth 2, then depth 3,... then depth 25. This seems like a stupid idea at first, but it has various benefits most of which I won't go into. What's relevant here is that the depth 24 search informs decisions about reductions the depth 25 search makes. So if depth 24 says a move isn't too promising, depth 25 is less likely to search it deeply. (this is a massive simplification).
  
  Ok so what's happening in the commit?
  
  The effect is that in positions with many 3-fold draw lines, different lines are followed at each iteration. This keeps the search much more dynamic, as opposed to being locked to one particular 3-fold.
  
  Here's how I'm reading this: Before the commit, the computer will be searching the same draws at every iteration. If there are lots of 3-fold lines, it's possible the computer won't search all of them (or at least, all of them deeply). This can lead to "blind spots," where the computer doesn't notice some sideline in a move with a draw score. 
  Before the commit, each successive iteration would have (roughly) the same blind spots (albeit with more resources to notice the sideline). After the commit, the blind spots are scrambled at each iteration, making it less likely to miss the sideline.
  
  As a toy hypothetical example (which shouldn't be taken too literally): say we have two "draw" moves A and B, both of which are way out at the horizon of the search. Because they are so far away, the computer's evaluation of them is very bad (for several reasons, but for the time being we can just think that only a few of A and B's children are searched due to reductions) so it's possible A and B aren't actually draws. 
  Now for whatever reason (perhaps reductions), let's say the computer has allocated 5 resources to search the "best" draw move and 3 resources for the "second best" draw move at iteration 24, while allocating 6 and 4 respectively at iteration 25. 
  Let's also say A is a genuine draw, but B has a sideline which isn't, and will be noticed if it is searched with 5 resources.
  Before the commit, if A is searched first at iteration 24, it will likely also be searched first at iteration 25 (meaning the sideline slips through), but after the commit, A and B are equally likely to be searched at each iteration, meaning the sideline is more likely to be found at some iteration, whereupon the computer will take note and correct.
  I don't know if that made any sense whatsoever, but I hope it helps.
  
  Again, I'm very open to being corrected here. This is just my reading of the commit.
  
  > **Comments:**
  > **username_2**: Can you please add a principal variation for your example? It seems like White can break through and prevent Black from using the two rooks to reach an easy checkmate, by sacrificing a lot of material. For example, 1... Nf7 2. Nb3 Ra8 3. Rc1 Rd8 4. Nxb4 Rdd6 5. Qxd4 exd4 6. Nxd4 cxd4 7. c5 bxc5 8. Rxc5 axb4, if I didn't make a mistake. Also, why does Black have 13 pawns?  
  > **username_1**: The 13 pawns are to disallow massive material sacrifices like this; the position is meant to illustrate a point, not display a shortcoming in Stockfish.   When I initially made it, I forced in a few lines (1... Ne6 not Nf7), and beat it until I was satisfied. This doesn't mean there isn't some other line (that Stockfish doesn't see!) which lets white break through by giving up a bunch of material. I made a few minor modifications to the link (discordinating white's piece further) with similar results.  I wasn't trying to create an airtight puzzle, but to make a point about reductions.  
  > **username_2**: I understand the point you were making. However, it would be really nice to actually have an airtight demonstration of that very point. Would you mind if I modify your example to make sure of that? =)  
  > **username_1**: sure, go ahead (I'll delete this once you do)  
  > **username_2**: Ok I tried my best; do you mind checking to see if you spot any holes? The purpose of the pawn at f5 is to prevent a White knight from jumping in like "1... Ne6 2. Nb3 Ra8 3. Nd2 Rf8 4. Ne4 fxe4 5. dxe4 Rff6 6. Nd3 Rh5 7. Nxe5 Rxe5 8. Rxd4 Nxd4 9. Rd2 exd2 10. Qxd4 cxd4". And this time it seems that the surest Black strategy is really Ne6 as shown by "1... Ne6 2. Nb3 Ra8 3. Rc1 Rf8 4. Nd1 Rff6 5. Nxc5 Nxc5 6. Qxd4 exd4 7. Nxe3 fxe3". Incidentally, Stockfish now gives White an even higher score due to the extra rook heheh.  
  
  ---
  
  ### Answer by username_3 on 2020-05-14. Score: 2
  
  The general answer is that by scoring these "3-fold" and "50-move" draws with some randomization, the engine will naturally be encouraged to explore different lines of play on successive searches. Moreover, these "draws" won't all be flooded into the Transposition Table (Big table of saved search results) with the same score.
  
  I put "50-move" in quotes for a reason. Due to how positions are stored into the Transposition Table (often without regard for the actual 50-move counter), its possible for a position to "appear" to be a draw, but not actually be. The best example would be the cursed-wins / blessed-losses that occur in the Syzygy Tablebases, which require an extension of the 50-move rule in order to obtain mate without drawing.
  
  For "3-fold" draws, there is a similar reason. I am not absolutely certain of the inner workings of Stockfish, but I believe the following is true for Stockfish (and is certainly true for some others): Often time "2-fold" repetitions are scored as draws. This is to speedup the search greatly (gains elo). I say "often times". Sometimes this is not the case, like when the first occurrence of a given position occurred BEFORE the root of the search. In other words, the the "2-fold" occurs entirely in the search, and has not actually been played in part or in full over the board. Again, this trick of randomization encourages some additional exploration, which helps to avoid rather "unlucky" understandings of a position.
  
  
  ---
  
  