What is the highest known lower bound for mate in N from starting position?

Question

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?

Answer 1

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.

Answer 2

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.

Answer 3

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

Answer 4

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?"

Answer 5

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.