14

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?

  • 1
    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é. 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. – Daniel B Aug 21 '13 at 12:21
  • @DanielB No, 549 is the longest known, found in 7man tablebases. – Santropedro Sep 22 '16 at 12:37
6

This is essentially the question of what is the 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. 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.

| improve this answer | |
  • 1
    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! – Sami Liedes Aug 7 '13 at 7:18
  • 3
    Actually, according to Wikipedia's Shannon number article Shannon estimated the number from the fact that a typical game lasts about 40 moves, so this is circular reasoning. – Sami Liedes Aug 7 '13 at 9:56
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.

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. Using 131,000 processors, Blue Gene can calculate 280 trillion operations per second. 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.

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, the game-tree complexity of chess is at least 10^123 and the number of potential positions at 10^46.7.

| improve this answer | |
  • That Kings Gambit bust was Chessbase's April Fools prank: en.chessbase.com/Home/TabId/211/PostId/4008051/… – Bort Jul 30 '13 at 21:30
  • Wow. I sure got fooled. Thanks for the info. – Andrew Ng Jul 30 '13 at 21:42
  • 1
    By "winnable", I meant forced mate, i.e. winnable given optimum play from the opponent. Seems I need to edit my question to clarify :) – Sami Liedes Jul 31 '13 at 7:36
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

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

| improve this answer | |
  • 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. – Sami Liedes Jul 31 '13 at 7:44
  • 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. – Nishanth Jul 31 '13 at 8:05
  • Saw your edit now! – Nishanth Jul 31 '13 at 8:11
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?"

| improve this answer | |
  • 1
    This does not answer the question, but I find the details very interesting! – Halvard Aug 10 '13 at 9:19
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.

| improve this answer | |
  • The question asked for a lower bound, not an upper bound. – dfan Jul 30 '13 at 22:16
  • 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. – WorruB Jul 30 '13 at 22:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.