The chess game solved by 2263?

Hi,

I just finished reading this interesting article on the Lemonosov endgames tablebase :

http://jovanpetronic.wordpress.com/2013/05/09/lomonosov-endgame-tablebases/

The guy claims that the chess game will be solved by 2263, using the techniques used in the Lemonosov algorithm and being confident in the fact that rapid improvements in technology will overcome todays limitations.

I personaly think it's a bit of a long shot, because I also read on another article that since the number of possible positions during a chess game is larger than the number of atoms in the universe, there is an obvious storage issue, so such a dream would not be possible ...

What do you guys think?

Well, the storage of one position would probably use more than one atom... so it's impossible to create a complete tablebase.

I wonder that assuming chess is fully resolved what constitutes 'best play'. Since if a position is winnable it is evident that best play means winning it in as few moves as possible. A move that allows mate in 5 is better than a move that only allows mate in 50. Buf what if the game of chess is a draw. Is the best to play to reach this draw in as few moves as possible or as many moves as possible.

From a practical point of view I think that in the case of a position that is objectively a draw best play means postponing the draw for as long as possible.

I think the number of possible positions on a chess board isn't that large. It is finite and should be easily solvable using today's mathematics and computers. It is definitely much much smaller than the number of atoms in the universe. In fact, we can use today's computers to shift through all known chess games and create a catalog of unique positions. It is feasible and shouldn't take that long.

The difficult part is to figure out how many unique games (not positions!) there are. Again, the number should be much smaller than the number of atoms in the universe.

I'm glad you decided to use facts not inaccurate guesswork!

Congratulations. You get the prize of the most illiterate comment in the history of chess.com...

Maybe not, but you fully deserve that prize.

In an average chess position there are 35 legal moves.

Suppose that a draw is automatically claimed under the fifty move rule. Since there are finite number of captures ( a maximum of 30 pieces can be captured ) and finite maximal number of pawn advances/promotions ( 2 * 8 * 6 = 96 ) you can put a cap on the maximum length of the game which is ( 30 + 96 ) * 50 = 6300 moves.

Therefore the number of possible games should not be more than 35 to the power of 6300.

This is just my quick calculation. Please anyone correct me if I'm wrong.

@watcha:

The problem in your method is assuming all games to have maximum length (which, by the way, actually is 5899, as you cannot possibly promote all 16 pawns), which is definitely not the case. Instead, we need to assume an average game length - the value of 40 moves (80 ply) has been considered a reasonable estimate.

If assuming 35 possible moves per position in average and an average game length of 80 ply, then the number of possible distinct games would be on the order of 35^80 = ~10^123. Seems somewhat larger than the number of atoms in the Universe.

I don't think it is going to be a storage problem. You don't need to store every bit of information. Take for instance a jpeg file and bmp file. You can develop techniques that allow you to exploit certain intrinsic qualities of the game and compress the data. Another example is fractals; you don't need a bit by bit description of a fractal, an equation is able to store all the information needed to construct one. Or the (ahem) schrodinger equation that encapsulates a quantum state.

I searched a little bit and found the article about the universe stuff : It seems the number of variation from the starting position (the game tree) was worked out by Shannon (https://en.wikipedia.org/wiki/Shannon_number) and the comparison is made here :

"Allis also estimated the game-tree complexity to be at least 10^{^123}, "based on an average branching factor of 35 and an average game length of 80". As a comparison, the number of atoms in the observable universe, to which it is often compared, is estimated to be between 4×10^{^79} and 10^⁸¹."

Well... you can promote all 16 pawns in 1 game.  But in that case you can't count pawn movement and captures separately as to get around the enemy pawn line the pawn would have to capture a piece and so advance forward at the same time.

@ProfessorProfesesen:

I think there are too many arbitrary rules in chess (castling, en passant, checkmate = win vs. stalemate = draw, two-square first pawn move, etc.) to hope to be able to "compress" the whole depth of chess into a reasonably simple recurrent equation. Also, the process for fractals is rather reverse - you start with the equation, and then evaluating it constructs the actual object.

Also, not only storage, but also time and energy would be problems rather unsurmountable for a practical application. Even if the matter of, say, the Andromeda galaxy was sufficient and could be arranged to hold a 32-man tablebase, the latency would be at least a few million years (only counting the time needed to send the request and receive the reply, and assuming zero processing time, which clearly is optimistic to the point of being unrealistic).

lol, that's awsome, I never thought of that.

@waffllemaster:

Yes, I suppose I have taken a bit of a shortcut there by just stating that you couldn't promote all pawns. Nevertheless, as you said, "50-move blocks" are lost anyway due to other concerns if all pawns were to be promoted, hence the maximum number of moves in a game heeding the 50-move rule is smaller than simply 50 * ((6 * 16) + 30).

I don't know if there is any other method beyond brute tree search to solve the game of chess. Our present day understanding is that there is not. If this is so than using even a realistic rather than a maximalistic estimate for the number of possible games ( 10 to the power of 123, as suggested by jaaas ) it should be an impossible task. It has nothing to do with storage capacity just with time. You have to somehow determine for each position if it is mate or stalemate. This should take T time. So the process should take a magnitude of 10^125 * T time ( considering each position in each possible game ). If you want to finish the work in a man's liftetime, T should be less than 10^-116 seconds. For this you need at least a 10^116 Hz processor. Todays processors are in the magnitude of 10^10 Hz ( some low multiples of 1 GHz ). Correct me if I'm wrong.

I sure would love to see the end result of a 'solved' chess game.

u guys r stupid

The idea that Moore's law continues for another 250 years is pretty fanciful as we are already getting near barriers that seem pretty tough to overcome.  In particular, in just a few generations we will have to face quantum tunneling.  That seems a very tough nut to crack...

I have read Stephen Wolfram's book A New Kind of Science. His approach grew out from the examination of cellular automata. His original discovery was that the future state of a cellular automaton cannot be predicted by any formula even if it has a very simple rule. The only way to know what state the automaton will be in certain number of steps is to play out those steps one by one (this is called computational irreducibility). A chess board is similar to a cellular automaton in that it is in a discrete state (the 'position') and the next possible states are determined by some discrete rule ('legal moves'). Therefore it is very unlikely that the game of chess is 'computationally reducible' meaning that you have to play out every possible game in a position before you can know with certainty the result of the game.

I think that actually hitting the speculative "technological singularity" (a moment when humanity cannot follow/control its own technological progress anymore) is considerably more probable than chess ever getting solved by humans.