Answers.Body: <p>This is essentially the question of what is the <a href="http://en.wikipedia.org/wiki/Game_complexity" rel="nofollow">game complexity</a> of chess. Note that by finiteness, we know that chess <em>is</em> determined, but we do not know if the starting position is a win for white, a win for black, or a draw.  The game complexity of chess is roughly the minimum number of positions we need to check in the game tree to determine the state of the initial position.  This is known as the <a href="https://en.wikipedia.org/wiki/Shannon_number" rel="nofollow">Shannon number</a>.  In the influential paper <em>Programming a Computer for Playing Chess</em>, Shannon estimated that the Shannon number is at least 10^{120).  Note that the number of particles in the Universe is estimated to be 10^(80).  To answer the question, we actually want to know the <em>height</em> of the game tree  when the initial position becomes determined.  We should also divide this height by 2, since a <em>move</em> in chess is typically considered a white and black move.   The branching factor of the tree is estimated to be about 30.  Thus, we can take the largest N such that 30^(2N) &lt; 10^(120).  </p>
  
  <p><strong>Answer.</strong> By the back of the envelope, N=40 works.  Coincidentally, this happens to be the length of an average game between grandmasters (although they often resign and do not actually play the game to conclusion).   </p>
  
  <p><strong>Edit.</strong> The moral of the story is that I was trying to estimate an upper bound for your lower bound.  The first part of Shannon's reasoning is not circular; he says that there are about 30 legal moves from each position, and this number is reasonably constant for the first portion of a game.  </p>
  
  <p>Thus, we can estimate the current <em>known</em> value of N (which is really what you are asking, let's call this N') to be at most log_30 (C) where C is equal to the amount of computing power that has existed in the history of mankind.  Even with conservative estimates for C, we get something like  N' at most 20.  In practice, I don't think anyone has carried out this computation very far up the tree, since a priori we know that the computation becomes infeasible after a very short height and it is not necessary to <em>exhaustively</em> search the tree to write good chess programs.  </p>
  
  <p>Note however, that you are asking a slightly weaker question, since it is possible that the initial state of the game is a draw with optimal play.  So, one could get bounds for N by writing a program whose goal was to not lose for as long as possible.  We could then play this program against the best programs or human players in the world and see what the length of a shortest game is.  Again, this does not properly answer the question, since we cannot assume that our opponents are <em>playing optimally</em>.  True optimal play requires full knowledge of the game tree, but we have seen that this is computationally infeasible.  Thus, the best we can currently do is approximate an optimally playing opponent with a Kasparov or a very good chess program. </p>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2013-08-07T07:18:47.717Z
Answers.Text: I don't think this exactly answers the question (it gives an estimate for N instead of the best known lower bound), but nevertheless, good answer!
Answers.UserDisplayName: Sami Liedes
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2013-08-07T09:56:15.210Z
Answers.Text: Actually, according to [Wikipedia's Shannon number article](http://en.wikipedia.org/wiki/Shannon_number) Shannon estimated the number from the fact that a typical game lasts about 40 moves, so this is circular reasoning.
Answers.UserDisplayName: Sami Liedes
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2013-08-07T03:56:17.297Z
Answers.LastActivityDate: 2013-08-07T11:17:32.360Z
Answers.LastEditDate: 2013-08-07T11:17:32.360Z
Answers.UserDisplayName: Tony Huynh
Answers.Body: <p>It's not true that the starting position is not winnable in 5 moves or less using the canonical definition of a full move in chess. It can be done in 2 moves via <a href="http://en.wikipedia.org/wiki/Fool%27s_mate" rel="nofollow">Fool's Mate</a>.</p>
  
  <p>To address your question, the strength of a chess engine is dependent on the software and hardware. In 1997, Deep Blue was a proof of hardware concept, a massively parallel supercomputer capable of evaluating 200 million moves per second with an average depth of 7-8 moves. However, in 2006, Deep Fritz running on a dual-core personal computer had equivalent results while only evaluating 8 million moves per second.</p>
  
  <p>Today, the strongest supercomputer that has been applied to chess is <a href="http://en.wikipedia.org/wiki/Blue_Gene" rel="nofollow">Blue Gene</a>. Using 131,000 processors, <a href="http://www-03.ibm.com/ibm/history/ibm100/us/en/icons/bluegene/" rel="nofollow">Blue Gene can calculate 280 trillion operations per second</a>. Although there is no data to confirm the depth to which Blue Gene can calculate, I would suppose it would be quite deep. Of course, this is dependent on how long the computer runs.</p>
  
  <p>However, we cannot in this case use the term 'exhaustive' when 'solving' and opening. A chess engine has no need to go to the end of the line when it is certain that the end result is decisive. In such, the program would exit when it became clear that the evaluation was clearly in favor of one side. This is known in theoretical computer science as <a href="http://en.wikipedia.org/wiki/Alpha%E2%80%93beta_pruning" rel="nofollow">Alpha-Beta pruning</a>.</p>
  
  <p>If I had to make a rough estimate, I would say that Blue Gene would be able to calculate around between 15 and 20 moves per second. Although its hardware and software is extremely impressive, we have to remember that the complexity of chess scales exponentially. According to recent <a href="http://en.wikipedia.org/wiki/Shannon_number" rel="nofollow">estimates</a>, the game-tree complexity of chess is at least 10^123 and the number of potential positions at 10^46.7.</p>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2013-07-30T21:30:51.067Z
Answers.Text: That Kings Gambit bust was Chessbase's April Fools prank: http://en.chessbase.com/Home/TabId/211/PostId/4008051/the-chessbase-april-fool-s-prank.aspx
Answers.UserDisplayName: Bort
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2013-07-30T21:42:03.803Z
Answers.Text: Wow. I sure got fooled. Thanks for the info.
Answers.UserDisplayName: Andrew Ng
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2013-07-31T07:36:50.217Z
Answers.Text: By "winnable", I meant forced mate, i.e. winnable given optimum play from the opponent. Seems I need to edit my question to clarify :)
Answers.UserDisplayName: Sami Liedes
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2013-07-30T21:13:44.167Z
Answers.LastActivityDate: 2013-07-30T21:47:16.153Z
Answers.LastEditDate: 2013-07-30T21:47:16.153Z
Answers.UserDisplayName: Andrew Ng
Answers.Body: <p>You may look <a href="http://chesstempo.com/chess-forum/endgame_problems/competition_longest_move_to_mate-t770.0.html" rel="nofollow">here</a> for a discussion. Of course you should not use the 50 move rule, but according to this forum, the record is hold so far by this position (black to move):</p>
  
  <pre><code>8/1r6/8/6n1/5k2/1b6/3K3N/7Q w - - 0 1
  </code></pre>
  
  <p>517 moves to a winning position and 525 to mate (best play by both sides). 
  See <a href="http://timkr.home.xs4all.nl/chess2/diary_16.htm" rel="nofollow">here</a>, entry 316. Thus this is a winning position with no win in less than 525 moves. </p>
  
  <p>Let me also reproduce Bourzutschky's comments: "Even deeper 7-man endings may exist, but I doubt it. That such a great depth is still possible with so much firepower on the board suggests that even deeper endings may arise with 8 pieces, perhaps in krnnkbbn. This ending could be generated with 64 GB of RAM in a few months on a fast single CPU machine and about 5 terabytes of storage. Any takers?"</p>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2013-08-10T09:19:43.057Z
Answers.Text: This does not answer the question, but I find the details very interesting!
Answers.UserDisplayName: Halvard
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2013-08-10T09:00:55.317Z
Answers.LastActivityDate: 2013-08-10T21:44:06.583Z
Answers.LastEditDate: 2013-08-10T21:44:06.583Z
Answers.UserDisplayName: J.-E. Pin
Answers.Body: <p>Assuming there is a winning continuation from a given position and assuming perfect play, implies <code>N</code> is fixed and not bounded (otherwise its not perfect play!).</p>
  
  <p>In this case one has to really work backwards - which is accomplished by <a href="http://en.wikipedia.org/wiki/Endgame_tablebase" rel="nofollow">Endgame Tablebase</a> </p>
  
  <p><em>The tablebases of all endgames with up to six pieces are available for free download, and may also be queried using web interfaces (see the external links below). Nalimov tablebase requires more than one terabyte of storage space</em></p>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2013-07-31T07:44:18.323Z
Answers.Text: That's true, but it is still possible to know a lower bound for N without knowing N (for example, we know that there most certainly is not a forced mate in 2 from the starting position; therefore we know that N>=3 without knowing N.
Answers.UserDisplayName: Sami Liedes
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2013-07-31T08:05:19.503Z
Answers.Text: But your question started with the assumption that there is a winning continuation from the given position. In which case `N` is fixed, with perfect play.
Answers.UserDisplayName: Nishanth
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2013-07-31T08:11:55.550Z
Answers.Text: Saw your edit now!
Answers.UserDisplayName: Nishanth
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2013-07-31T04:31:41.853Z
Answers.LastActivityDate: 2013-07-31T04:31:41.853Z
Answers.UserDisplayName: Nishanth
Answers.Body: <p>Edit: Sorry, looks like I misread the question.  My guess is that any reasonable N is well outside the horizon of a computer.  If we set up a very powerful computer to caluclate the starting position that's probably the only confident X we could show, let's say it could 10 million nodes per second after 10 days we could calculate 10 * 86400 * 10^8 nodes = 8.64 * 10^13 nodes.  If we assume the average position in the first 20 moves has about 15 legal moves (lower because beginning has much less and probably even slightly lower because of alpha-beta pruning) which is only about 12 moves after 10 days (position only after move 6) so you see why this problem is ugly.  However I think practical play probably suggests a much, much, much higher value.  I'll take good money against any computer human combination you can come up with that I can not get checkmated in 20 moves (if that's my only goal).</p>
  
  <p>Let's ignore that chess is most likely a draw.  We must consider the rules under which chess is played in practice.  In almost every tournament situation there's a 50 move rule in effect which states that the game is a draw if "the last 50 consecutive moves have been made by each player without the movement of any pawn and without the capture of any piece."</p>
  
  <p>So this means we can have 49.5 moves per capture or pawn move.  Each pawn can move up to 6 times and there are 15 pieces which can be captured for each side (although one piece must remain to deliver checkmate) so we can put an upper bound on the number of moves.</p>
  
  <p>This works out to 49.5 * (8 * 2 * 6 (pawn moves) + 29) = 6187.5
  So this means that IF chess is a forced win for white with adhering to the 50 move rule then it is in at most 6188 moves for white.  I could probably lower this a tiny bit without doing too much by saying that all K + piece mates v K mates that are forced (Rook at Queen only) are doable in substantially less than 50 moves (I think about 16 playing around with Nalimov for some "tough" cases.  So I think we can probably subtract 34 moves from that total confidently for 6134!</p>
  
  <p>Therefore:
  <strong>If chess is a forced win for white with adhering to the 50 move rule then it is in at most 6134 moves.</strong></p>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2013-07-30T22:16:17.043Z
Answers.Text: The question asked for a lower bound, not an upper bound.
Answers.UserDisplayName: dfan
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2013-07-30T22:19:34.320Z
Answers.Text: I thought it wanted the best lower bound on the upper bound.  Or is the question asking whether or not chess is definitely not mate in X where X might be 30 or something.
Answers.UserDisplayName: WorruB
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2013-07-30T22:15:11.257Z
Answers.LastActivityDate: 2013-07-30T22:34:49.673Z
Answers.LastEditDate: 2013-07-30T22:34:49.673Z
Answers.UserDisplayName: WorruB
Body: <p><strong>Edit</strong>: It seems my question was not clear enough. Let me rephrase: What is the largest N for which we can knowingly say "chess, from the starting position, is not a forced mate in N moves"?</p>
  
  <p>Chess is not solved, i.e. it is not known what the outcome from starting position is given perfect play.</p>
  
  <p>However, if the starting position is win for either player, it is a mate in N for some N. Also by example, if we know for certain that the starting position is not winnable in 5 moves (for either player), 5 is a lower bound for N.</p>
  
  <p>Roughly how deep is it feasible to search exhaustively from the starting position in practice? How high a lower bound for N is known?</p>
  
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2016-09-22T12:37:23.090Z
Comments.Text: @DanielB No, [549 is the longest](http://rocketcheckmate.blogspot.com.ar/2014/06/mate-in-549.html)  known, found in 7man tablebases.
Comments.UserDisplayName: Santropedro
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2013-08-21T12:21:58.130Z
Comments.Text: Out of curiosity: the longest known forced mate (assuming perfect play) was discovered during a 7-man endgame table effort, and it's item [316 on the Open Chess Diary by Tim Krabbé](http://timkr.home.xs4all.nl/chess2/diary_16.htm).  It's 517 moves long.  Now, this position might not *necessarily* be reachable using perfect play, but it shows the scale of the problem in general.  Brute forcing from a starting position, we could probably get to a few dozen moves depth at most, with current hardware.
Comments.UserDisplayName: Daniel B
Tags: <analysis><software><theory><chess-algorithms>
Title: What is the highest known lower bound for mate in N from starting position?
ThreadText: # What is the highest known lower bound for mate in N from starting position?
  
  (Asked by: username_0 on 2013-07-30)
  
  **Edit**: It seems my question was not clear enough. Let me rephrase: What is the largest N for which we can knowingly say "chess, from the starting position, is not a forced mate in N moves"?
  
  Chess is not solved, i.e. it is not known what the outcome from starting position is given perfect play.
  
  However, if the starting position is win for either player, it is a mate in N for some N. Also by example, if we know for certain that the starting position is not winnable in 5 moves (for either player), 5 is a lower bound for N.
  
  Roughly how deep is it feasible to search exhaustively from the starting position in practice? How high a lower bound for N is known?
  
  **Tags:** analysis, software, theory, chess-algorithms
  
  > **Comments:**
  > **username_2**: Out of curiosity: the longest known forced mate (assuming perfect play) was discovered during a 7-man endgame table effort, and it's item [316 on the Open Chess Diary by Tim Krabbé](http://timkr.home.xs4all.nl/chess2/diary_16.htm).  It's 517 moves long.  Now, this position might not *necessarily* be reachable using perfect play, but it shows the scale of the problem in general.  Brute forcing from a starting position, we could probably get to a few dozen moves depth at most, with current hardware.  
  > **username_1**: @DanielB No, [549 is the longest](http://rocketcheckmate.blogspot.com.ar/2014/06/mate-in-549.html)  known, found in 7man tablebases.  
  
  ---
  
  ## 5 answers
  
  ### Answer by username_3 on 2013-08-07. Score: 6
  
  This is essentially the question of what is the [game complexity](http://en.wikipedia.org/wiki/Game_complexity) of chess. Note that by finiteness, we know that chess *is* determined, but we do not know if the starting position is a win for white, a win for black, or a draw. The game complexity of chess is roughly the minimum number of positions we need to check in the game tree to determine the state of the initial position. This is known as the [Shannon number](https://en.wikipedia.org/wiki/Shannon_number). In the influential paper *Programming a Computer for Playing Chess*, Shannon estimated that the Shannon number is at least 10^{120). Note that the number of particles in the Universe is estimated to be 10^(80). To answer the question, we actually want to know the *height* of the game tree when the initial position becomes determined. We should also divide this height by 2, since a *move* in chess is typically considered a white and black move. The branching factor of the tree is estimated to be about 30. Thus, we can take the largest N such that 30^(2N) < 10^(120).
  
  **Answer.** By the back of the envelope, N=40 works. Coincidentally, this happens to be the length of an average game between grandmasters (although they often resign and do not actually play the game to conclusion).
  
  **Edit.** The moral of the story is that I was trying to estimate an upper bound for your lower bound. The first part of Shannon's reasoning is not circular; he says that there are about 30 legal moves from each position, and this number is reasonably constant for the first portion of a game.
  
  Thus, we can estimate the current *known* value of N (which is really what you are asking, let's call this N') to be at most log\_30 (C) where C is equal to the amount of computing power that has existed in the history of mankind. Even with conservative estimates for C, we get something like N' at most 20. In practice, I don't think anyone has carried out this computation very far up the tree, since a priori we know that the computation becomes infeasible after a very short height and it is not necessary to *exhaustively* search the tree to write good chess programs.
  
  Note however, that you are asking a slightly weaker question, since it is possible that the initial state of the game is a draw with optimal play. So, one could get bounds for N by writing a program whose goal was to not lose for as long as possible. We could then play this program against the best programs or human players in the world and see what the length of a shortest game is. Again, this does not properly answer the question, since we cannot assume that our opponents are *playing optimally*. True optimal play requires full knowledge of the game tree, but we have seen that this is computationally infeasible. Thus, the best we can currently do is approximate an optimally playing opponent with a Kasparov or a very good chess program.
  
  > **Comments:**
  > **username_0**: I don't think this exactly answers the question (it gives an estimate for N instead of the best known lower bound), but nevertheless, good answer!  
  > **username_0**: Actually, according to [Wikipedia's Shannon number article](http://en.wikipedia.org/wiki/Shannon_number) Shannon estimated the number from the fact that a typical game lasts about 40 moves, so this is circular reasoning.  
  
  ---
  
  ### Answer by username_4 on 2013-07-30. Score: 3
  
  It's not true that the starting position is not winnable in 5 moves or less using the canonical definition of a full move in chess. It can be done in 2 moves via [Fool's Mate](http://en.wikipedia.org/wiki/Fool%27s_mate).
  
  To address your question, the strength of a chess engine is dependent on the software and hardware. In 1997, Deep Blue was a proof of hardware concept, a massively parallel supercomputer capable of evaluating 200 million moves per second with an average depth of 7-8 moves. However, in 2006, Deep Fritz running on a dual-core personal computer had equivalent results while only evaluating 8 million moves per second.
  
  Today, the strongest supercomputer that has been applied to chess is [Blue Gene](http://en.wikipedia.org/wiki/Blue_Gene). Using 131,000 processors, [Blue Gene can calculate 280 trillion operations per second](http://www-03.ibm.com/ibm/history/ibm100/us/en/icons/bluegene/). Although there is no data to confirm the depth to which Blue Gene can calculate, I would suppose it would be quite deep. Of course, this is dependent on how long the computer runs.
  
  However, we cannot in this case use the term 'exhaustive' when 'solving' and opening. A chess engine has no need to go to the end of the line when it is certain that the end result is decisive. In such, the program would exit when it became clear that the evaluation was clearly in favor of one side. This is known in theoretical computer science as [Alpha-Beta pruning](http://en.wikipedia.org/wiki/Alpha%E2%80%93beta_pruning).
  
  If I had to make a rough estimate, I would say that Blue Gene would be able to calculate around between 15 and 20 moves per second. Although its hardware and software is extremely impressive, we have to remember that the complexity of chess scales exponentially. According to recent [estimates](http://en.wikipedia.org/wiki/Shannon_number), the game-tree complexity of chess is at least 10^123 and the number of potential positions at 10^46.7.
  
  > **Comments:**
  > **username_5**: That Kings Gambit bust was Chessbase's April Fools prank: http://en.chessbase.com/Home/TabId/211/PostId/4008051/the-chessbase-april-fool-s-prank.aspx  
  > **username_4**: Wow. I sure got fooled. Thanks for the info.  
  > **username_0**: By "winnable", I meant forced mate, i.e. winnable given optimum play from the opponent. Seems I need to edit my question to clarify :)  
  
  ---
  
  ### Answer by username_6 on 2013-08-10. Score: 1
  
  You may look here for a discussion. Of course you should not use the 50 move rule, but according to this forum, the record is hold so far by this position (black to move):
  8/1r6/8/6n1/5k2/1b6/3K3N/7Q w - - 0 1
  
  517 moves to a winning position and 525 to mate (best play by both sides). 
  See here, entry 316. Thus this is a winning position with no win in less than 525 moves. 
  Let me also reproduce Bourzutschky's comments: "Even deeper 7-man endings may exist, but I doubt it. That such a great depth is still possible with so much firepower on the board suggests that even deeper endings may arise with 8 pieces, perhaps in krnnkbbn. This ending could be generated with 64 GB of RAM in a few months on a fast single CPU machine and about 5 terabytes of storage. Any takers?"
  
  > **Comments:**
  > **username_7**: This does not answer the question, but I find the details very interesting!  
  
  ---
  
  ### Answer by username_8 on 2013-07-31. Score: 1
  
  Assuming there is a winning continuation from a given position and assuming perfect play, implies `N` is fixed and not bounded (otherwise its not perfect play!).
  
  In this case one has to really work backwards - which is accomplished by [Endgame Tablebase](http://en.wikipedia.org/wiki/Endgame_tablebase)
  
  *The tablebases of all endgames with up to six pieces are available for free download, and may also be queried using web interfaces (see the external links below). Nalimov tablebase requires more than one terabyte of storage space*
  
  > **Comments:**
  > **username_0**: That's true, but it is still possible to know a lower bound for N without knowing N (for example, we know that there most certainly is not a forced mate in 2 from the starting position; therefore we know that N>=3 without knowing N.  
  > **username_8**: But your question started with the assumption that there is a winning continuation from the given position. In which case `N` is fixed, with perfect play.  
  > **username_8**: Saw your edit now!  
  
  ---
  
  ### Answer by username_9 on 2013-07-30. Score: 0
  
  Edit: Sorry, looks like I misread the question. My guess is that any reasonable N is well outside the horizon of a computer. If we set up a very powerful computer to caluclate the starting position that's probably the only confident X we could show, let's say it could 10 million nodes per second after 10 days we could calculate 10 \* 86400 \* 10^8 nodes = 8.64 \* 10^13 nodes. If we assume the average position in the first 20 moves has about 15 legal moves (lower because beginning has much less and probably even slightly lower because of alpha-beta pruning) which is only about 12 moves after 10 days (position only after move 6) so you see why this problem is ugly. However I think practical play probably suggests a much, much, much higher value. I'll take good money against any computer human combination you can come up with that I can not get checkmated in 20 moves (if that's my only goal).
  
  Let's ignore that chess is most likely a draw. We must consider the rules under which chess is played in practice. In almost every tournament situation there's a 50 move rule in effect which states that the game is a draw if "the last 50 consecutive moves have been made by each player without the movement of any pawn and without the capture of any piece."
  
  So this means we can have 49.5 moves per capture or pawn move. Each pawn can move up to 6 times and there are 15 pieces which can be captured for each side (although one piece must remain to deliver checkmate) so we can put an upper bound on the number of moves.
  
  This works out to 49.5 \* (8 \* 2 \* 6 (pawn moves) + 29) = 6187.5
  So this means that IF chess is a forced win for white with adhering to the 50 move rule then it is in at most 6188 moves for white. I could probably lower this a tiny bit without doing too much by saying that all K + piece mates v K mates that are forced (Rook at Queen only) are doable in substantially less than 50 moves (I think about 16 playing around with Nalimov for some "tough" cases. So I think we can probably subtract 34 moves from that total confidently for 6134!
  
  Therefore:
  **If chess is a forced win for white with adhering to the 50 move rule then it is in at most 6134 moves.**
  
  > **Comments:**
  > **username_10**: The question asked for a lower bound, not an upper bound.  
  > **username_9**: I thought it wanted the best lower bound on the upper bound.  Or is the question asking whether or not chess is definitely not mate in X where X might be 30 or something.  
  
  ---
  
  