Answers.Body: <p>The problem every time you have such enormous number of configurations, is that any "simple-minded" description of configurations to discard will remove an insignificant portion of the total.</p>
  
  <p>In the case at hand, there are trillions upon trillions of positions with a bare king (for instance), but they represent a small fraction of a percent of all positions. </p>
  
  <p>You still have to deal with the bulk of configurations that make chess hard, so the difficulty of the original problem is still there.</p>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-12-28T15:28:12.160Z
Answers.Text: Indeed it still remains rather intangible. The only work I've seen touching on such questions is sequencing chess on arXiv: https://arxiv.org/abs/1609.04648
Answers.UserDisplayName: Ellie
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-12-26T21:00:37.627Z
Answers.LastActivityDate: 2017-12-26T21:00:37.627Z
Answers.UserDisplayName: yrodro
Answers.Body: <p>I'm guessing that by complexity, you mean an estimate for the number of legal positions that aren't 'clearly' lost by some measure (otherwise the answer is exponential, despite the addition of your constraint), as if to build a tablebase that can play through non-trivially lost/won positions (ignoring the technicalities of the missing tablebase problem that would arise...).</p>
  
  <p>One estimate of the <a href="https://www.youtube.com/watch?v=Km024eldY1A" rel="nofollow noreferrer">number of 'sensible' chess games</a>;  3^(40*2) ~ 10^40 seems reasonable; however, this answer doesn't work in this setting, because of the way your question is phrased.</p>
  
  <p>I claim that our hypothetical 32-man, 'non-trivial' tablebase is composed mostly of positions arising from games that would have otherwise been drawn. I argue as follows: 60% of grandmaster games are draws; let's say (an arbitrary guess) that a third of this are agreed draws i.e. 20% of games at move 30. Another arbitrary assumption: let's say material is equal at these positions at move 30, 3 pawns and 3 pieces having been exchanged. Each side has to trade off 9 more pawns/pieces to get to bare kings. Assuming an exchange every 4 or 5 moves, again with 3 'sensible' moves in each position, the number of games concluding in this manner would be approximately 3^(30*2) * 0.2 * 3(40*2) = 0.2 * 3^160 ~ 10^80, which dwarfs the estimated number of 'sensible' chess games.</p>
  
  <p>This highlights the significance of exponential growth: the percentage of 
   agreed draws doesn't really matter (as long as it's not zero), and neither does 'clearly' won/lost positions in the setting of a '32-man' tablebase.</p>
  
  <p>My main point is, a fairly reasonable estimate to your required answer would still be of the form n^m where n is the average number of 'sensible' moves in a position, and m is the expected number of half-moves to get down to bare kings.</p>
  
  <p>Also, to be precise, the number of positions (double/triple/multiple-counting transpositions) is closer to m*(n^m).</p>
  
  <p>Now of course, if you include trivially drawn positions, things become really tricky, but we have to draw the line somewhere...</p>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-12-26T18:55:02.687Z
Answers.LastActivityDate: 2017-12-26T19:05:28.540Z
Answers.LastEditDate: 2017-12-26T19:05:28.540Z
Answers.UserDisplayName: Ken Wei
Answers.Body: <p>It's hard to see if a position is clearly won or not, especially when just counting material:</p>
  
  <pre><code>[FEN "3N2rk/4K1bb/4nn2/8/8/8/7q/qqqqqqqq w - - 0 1"]
  
  1. Nf7#
  </code></pre>
  
  <p>or the various positions with pawn chains all over the board, which can't be broken by rooks or a bishop of the wrong color.</p>
  
  <p>So I doubt exclusion of clearly won positions is going to make much of a difference in terms of complexity; it's even likely to make it <em>more</em> complex.</p>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-12-26T09:31:00.867Z
Answers.Text: Agreed. I am not looking for an exact number, but rather an estimate.
Answers.UserDisplayName: user1583209
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-12-26T09:26:16.327Z
Answers.LastActivityDate: 2017-12-26T09:26:16.327Z
Answers.UserDisplayName: Glorfindel
Body: <p>I understand that chess is pretty complex regarding the game tree complexity (Shannon number) or number of possible positions. If we were trying to solve chess (whuch I know is impossible for practical reasons), however we might not be interested in all positions. For instance I remember reading that for the 7 men tablebase they excluded positions where one side had a bare king.</p>
  
  <p>Is there an estimate for the complexity of chess if clearly won positions are excluded?</p>
  
Tags: <tablebases>
Title: Complexity of critical positions
ThreadText: # Complexity of critical positions
  
  (Asked by: username_0 on 2017-12-26)
  
  I understand that chess is pretty complex regarding the game tree complexity (Shannon number) or number of possible positions. If we were trying to solve chess (whuch I know is impossible for practical reasons), however we might not be interested in all positions. For instance I remember reading that for the 7 men tablebase they excluded positions where one side had a bare king.
  
  Is there an estimate for the complexity of chess if clearly won positions are excluded?
  
  **Tags:** tablebases
  
  
  ---
  
  ## 3 answers
  
  ### Answer by username_1 on 2017-12-26. Score: 3
  
  The problem every time you have such enormous number of configurations, is that any "simple-minded" description of configurations to discard will remove an insignificant portion of the total.
  
  In the case at hand, there are trillions upon trillions of positions with a bare king (for instance), but they represent a small fraction of a percent of all positions.
  
  You still have to deal with the bulk of configurations that make chess hard, so the difficulty of the original problem is still there.
  
  > **Comments:**
  > **username_2**: Indeed it still remains rather intangible. The only work I've seen touching on such questions is sequencing chess on arXiv: https://arxiv.org/abs/1609.04648  
  
  ---
  
  ### Answer by username_3 on 2017-12-26. Score: 2
  
  I'm guessing that by complexity, you mean an estimate for the number of legal positions that aren't 'clearly' lost by some measure (otherwise the answer is exponential, despite the addition of your constraint), as if to build a tablebase that can play through non-trivially lost/won positions (ignoring the technicalities of the missing tablebase problem that would arise...).
  
  One estimate of the [number of 'sensible' chess games](https://www.youtube.com/watch?v=Km024eldY1A); 3^(40\*2) ~ 10^40 seems reasonable; however, this answer doesn't work in this setting, because of the way your question is phrased.
  
  I claim that our hypothetical 32-man, 'non-trivial' tablebase is composed mostly of positions arising from games that would have otherwise been drawn. I argue as follows: 60% of grandmaster games are draws; let's say (an arbitrary guess) that a third of this are agreed draws i.e. 20% of games at move 30. Another arbitrary assumption: let's say material is equal at these positions at move 30, 3 pawns and 3 pieces having been exchanged. Each side has to trade off 9 more pawns/pieces to get to bare kings. Assuming an exchange every 4 or 5 moves, again with 3 'sensible' moves in each position, the number of games concluding in this manner would be approximately 3^(30\*2) \* 0.2 \* 3(40\*2) = 0.2 \* 3^160 ~ 10^80, which dwarfs the estimated number of 'sensible' chess games.
  
  This highlights the significance of exponential growth: the percentage of
  agreed draws doesn't really matter (as long as it's not zero), and neither does 'clearly' won/lost positions in the setting of a '32-man' tablebase.
  
  My main point is, a fairly reasonable estimate to your required answer would still be of the form n^m where n is the average number of 'sensible' moves in a position, and m is the expected number of half-moves to get down to bare kings.
  
  Also, to be precise, the number of positions (double/triple/multiple-counting transpositions) is closer to m\*(n^m).
  
  Now of course, if you include trivially drawn positions, things become really tricky, but we have to draw the line somewhere...
  
  
  ---
  
  ### Answer by username_4 on 2017-12-26. Score: 1
  
  It's hard to see if a position is clearly won or not, especially when just counting material:
  
  ```
  [FEN "3N2rk/4K1bb/4nn2/8/8/8/7q/qqqqqqqq w - - 0 1"]
  
  1. Nf7#
  
  ```
  
  or the various positions with pawn chains all over the board, which can't be broken by rooks or a bishop of the wrong color.
  
  So I doubt exclusion of clearly won positions is going to make much of a difference in terms of complexity; it's even likely to make it *more* complex.
  
  > **Comments:**
  > **username_0**: Agreed. I am not looking for an exact number, but rather an estimate.  
  
  ---
  
  