Can chess be solved (in part)?

[M ANSARI]

I think the task of solving chess is not as difficult as some would have it. I know that there are more possible chess moves than there are atoms in the universe etc...

The truth is that even from the beginning a lot of moves can be thrown out ... and thus a dramatic reduction of the number moves are possible. For example I can see very soon the possibility of an engine scoring 100% against Nf6 d4 Ng8 e5 Nf6 Nc3 Ng8. No matter how hard you try to improve blacks play by trying different moves you will reach a point in engine development that would win 100% of the time. A similar situation can happen when you have a rook and King vs. King. Most engines will be able to win without EGTB's even without calculating to mate simply because they will know how to restrict blacks King until a mating sequence is found.

Although that would not be the same as solving all 32 EGTB's it sure would satisfy me as "practical" solving of chess.

[ozziejoe]

no no. I just miscounted. for it to be solved, you would have to have a response for every possible move. You would just be cutting down your possible responses

[Uri Blass]

I think the task of solving chess is not as difficult as some would have it. I know that there are more possible chess moves than there are atoms in the universe etc...

The truth is that even from the beginning a lot of moves can be thrown out ... and thus a dramatic reduction of the number moves are possible. For example I can see very soon the possibility of an engine scoring 100% against Nf6 d4 Ng8 e5 Nf6 Nc3 Ng8. No matter how hard you try to improve blacks play by trying different moves you will reach a point in engine development that would win 100% of the time. A similar situation can happen when you have a rook and King vs. King. Most engines will be able to win without EGTB's even without calculating to mate simply because they will know how to restrict blacks King until a mating sequence is found.

Although that would not be the same as solving all 32 EGTB's it sure would satisfy me as "practical" solving of chess.

I agree that the practical solution may not be hard to achieve as some suggest but I do not expect it to happen in the near future.

To be more accurate I define chess to be probably practically solved if you find a program that never lose with black or always wins with white

We are not close to this situation and even today almost 1/3 of the correspondence games of the world championship(when people are allowed to use programs) are finished in non draw results when most of the games are drawn.

My guess is that chess is not going to be practically solved in the next 15 years but it may be practically solved later.

Uri

[S.Taylor]

I think the task of solving chess is not as difficult as some would have it. I know that there are more possible chess moves than there are atoms in the universe etc...

The truth is that even from the beginning a lot of moves can be thrown out ... and thus a dramatic reduction of the number moves are possible. For example I can see very soon the possibility of an engine scoring 100% against Nf6 d4 Ng8 e5 Nf6 Nc3 Ng8. No matter how hard you try to improve blacks play by trying different moves you will reach a point in engine development that would win 100% of the time. A similar situation can happen when you have a rook and King vs. King. Most engines will be able to win without EGTB's even without calculating to mate simply because they will know how to restrict blacks King until a mating sequence is found.

Although that would not be the same as solving all 32 EGTB's it sure would satisfy me as "practical" solving of chess.

I agree that the practical solution may not be hard to achieve as some suggest but I do not expect it to happen in the near future.

To be more accurate I define chess to be probably practically solved if you find a program that never lose with black or always wins with white

We are not close to this situation and even today almost 1/3 of the correspondence games of the world championship(when people are allowed to use programs) are finished in non draw results when most of the games are drawn.

My guess is that chess is not going to be practically solved in the next 15 years but it may be practically solved later.

Uri

Uri, do you think that we might see surprises if/when chess is nearer to being solved?
Do you think that there might be moves which make big differences to an ultimate intelligence (close to solved) which at the momment look either like mistakes, or atleast, not too relevant?

[bob]

Who says that 1. h4 is not the best move for white and the only way to force a win? Until you can prove that is not the case, you can't exclude the move.

Joseph's method would be useful to proving that Black can't win the game, and with the correct implementation, you only need to search about 5% of the chess positions you would need otherwise. Unfortunately, since they increase exponentially, it hardly matters at all.

To prove that black can't win, you have to pick some white move and search everything below that point. And if it is a draw or loss for black you are done. You just reduced the tree search space from something like 10^50 to just over 10^48. Somehow I don't think that is enough. And if the first white move loses, then you get to do it again.

[bob]

I think the task of solving chess is not as difficult as some would have it. I know that there are more possible chess moves than there are atoms in the universe etc...

The truth is that even from the beginning a lot of moves can be thrown out ... and thus a dramatic reduction of the number moves are possible. For example I can see very soon the possibility of an engine scoring 100% against Nf6 d4 Ng8 e5 Nf6 Nc3 Ng8. No matter how hard you try to improve blacks play by trying different moves you will reach a point in engine development that would win 100% of the time. A similar situation can happen when you have a rook and King vs. King. Most engines will be able to win without EGTB's even without calculating to mate simply because they will know how to restrict blacks King until a mating sequence is found.

Although that would not be the same as solving all 32 EGTB's it sure would satisfy me as "practical" solving of chess.

Just apply the math...

a good estimate is 2^168 as we have developed an encoding that can represent the entire chess board in 168 bits. Assume that can be beat, and that we drive the search space to about 10^50. Alpha beta reduces that by the square root of the search space, or to 10^25. We won't be searching that tree within the next 1,000 years...

[Dirt]

Just apply the math...

a good estimate is 2^168 as we have developed an encoding that can represent the entire chess board in 168 bits. Assume that can be beat, and that we drive the search space to about 10^50. Alpha beta reduces that by the square root of the search space, or to 10^25. We won't be searching that tree within the next 1,000 years...

Well, 10^25 sounds to me like something we might well manage within a century. There's a lot of uncertainty in just how fast we'll advance, and I'm not quite certain that the huge number of processors could be used efficiently enough. Plausibly, though, I think we might.

However...

For this technique shouldn't we be using the game-tree complexity instead of the number of positions? Wikipedia estimates that at 10^123, which would mean over 10^61 leaves for alpha-beta with perfect move order. Even assuming that number can be trimmed by using some rationally sized tablebases, it still looks quite daunting.

The most promising path for finding the truth about the start position in chess might be partially non-constructive methods, as was suggested by someone here in the past. Something like: A rook advantage in material always wins, except <millions of special cases>. If that could be shown by logical argument instead of exhaustive search it would help a lot. I don't really expect anything like that would work, but I'm not absolutely certain it couldn't.

[ozziejoe]

I see your point Bob. However, i think one coudl use a more radical method than merely eliminating first move options. Once black moves, you again give white only one possible move. Then black moves again, and you consider only one white move (maybe the best move identified at depth 30 by rybka). By giving white only one move, you radically reduce the space. You could reduce the space further if you chose good moves that also reduced blacks options.

You are right. You could get it wrong somewhere in the tree and have to start again. However, I think you could probably get the first 10 white moves right, and maybe event he first 20 with very deep analysis. if we can nail those first 20 moves (e.g., at least white equality in every position), we would surely reduce the space a great deal.

Maybe we are not there, but i don't think the true space is 10^48. bob, what space would be sufficiently small to partially solve chess. 10^10? Or something in that order. Maybe that is still too large


best

J

[M ANSARI]

Again ... I think the idea of solving it by brute force will not be necessary. Remember that white or black can dictate the direction of a gamen which dramatically reduces the number of moves that need to be calculated. I mean you can pretty much guarantee today that Rybka vs say Zappa II will be a draw if you have King + Rook + Pawn on both sides. So you will also get into situations where there is no need to calculate to the nth degree because the outcome will be known by simply knowing that the engine will be able to handle the position and draw.

I can think of one way you can rapidly reach a situation where you would consider chess to be solved. I would get 1,000,000 eight core computers running the strongest engines with a prize of $1000 for each person who can win against one of these computers. When a certain line gets a win you have a team of top professional GM's analyze and fix certain lines that lose. Within 5 years I bet you would reach a situation where winning a game would be impossible. Then you would increase the prize to say 1 million dollars ... which would again clean up the last remaining winning lines for white. I can easily envision a situation where a chess entity will have such a huge and comprehensive opening database and with the ability of being strong enough to draw certain positions you will have a situation where chess is solved ... Most likely chess will be proven a draw with perfect play.

[bob]

Just apply the math...

a good estimate is 2^168 as we have developed an encoding that can represent the entire chess board in 168 bits. Assume that can be beat, and that we drive the search space to about 10^50. Alpha beta reduces that by the square root of the search space, or to 10^25. We won't be searching that tree within the next 1,000 years...

Well, 10^25 sounds to me like something we might well manage within a century. There's a lot of uncertainty in just how fast we'll advance, and I'm not quite certain that the huge number of processors could be used efficiently enough. Plausibly, though, I think we might.

However...

For this technique shouldn't we be using the game-tree complexity instead of the number of positions? Wikipedia estimates that at 10^123, which would mean over 10^61 leaves for alpha-beta with perfect move order. Even assuming that number can be trimmed by using some rationally sized tablebases, it still looks quite daunting.

The most promising path for finding the truth about the start position in chess might be partially non-constructive methods, as was suggested by someone here in the past. Something like: A rook advantage in material always wins, except <millions of special cases>. If that could be shown by logical argument instead of exhaustive search it would help a lot. I don't really expect anything like that would work, but I'm not absolutely certain it couldn't.

Again, apply the math. Let's take a century to solve 10^25 positions. That means 10^23 per year (10^25 / 100). which leaves us at 2.74 x 10^20 positions per day or 1,.14 x 10^19 per hour. Or, finally 3.17 x 10^15 positions per second.

To pull this off you need to search one position ever 315 x 10^-18 seconds, or

.000000000000000315 seconds per position...

Deep Blue could search a theoretical max of one billion positions per second or .000000001 seconds per position. Nothing else today comes even close so let's take that as "what we wish today's state of the art could be".

To pull this off, we need to search 1,000,000,000 times faster than the best we know of with today's hardware. Realistically, I have seen speeds of 100M nodes per second on exotic hardware, which is 10x worse than deep blue. If we use that number instead, then we need to go 10 billion times faster than today's very best to search that tree space in a century of time. If you take today's PC, and use a single processor, I have seen maybe 3.0M nodes per second on a single core-2 processor. So multiply the above by about 1,000...

Now to reality. To run at the above speed, the microprocessor would have to fit inside the nucleus of an atom, because the propagation time of energy (electrical, light, etc) demands that. So what type of energy transfer mechanism are you going to use? Not an electron. That won't fit inside an atom, and we'd need billions of them. Photons?

So, today, there is no technology that will get us there. And no, the much-heralded quantum computing won't touch it either.

That is simply a daunting problem. And note that if we extend that 100 years by a factor of 10, it hardly changes the final result.

This is just not doable, not only by any potential extensions of today's hardware, but also not by any imaginable future development.

Do you really think hardware advances can do that? If you assume the current doubling of speed every 2 years,