Can chess be solved (in part)?

[bob]

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

Again, the math blows that up. How do you _guarantee_ that you choose the best move for white each time? And every time you miss it, you greatly add to the computational requirement. You need a perfect search in order to produce a perfect search. I don't see how you could pull that off.

Here's another fly in the ointment. Actually, the true space is _much_ larger. because of the 50-move rule and repetitions. If the shortest solution is along a path that would violate the 50-move rule, then you have to find a path that will be longer, in order to make an irreversable move every 50 moves even though it is far from optimal, because we have to play within the rules as they exist.

[bob]

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.

Doesn't work. I watched a game between Crafty and Rybka a few weeks back, that was a KRPPP vs KRPPP. There was a forced sequence of moves that led to a won KRP vs KR. So I would not want to say that all KRP vs KRP positions are drawn. There are _many_ that are lost (look at the egtb .tbs files to see) and these will naturally occur in many games.

[Dirt]

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.

I also doubt quantum computers will be of any help for chess.

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,

I think you underestimate my imagination...

You didn't address my primary point, that chess is really much harder than this, but as to the 10^25 number:
At a doubling every two years, in a century we would be about 10^15 faster. I'll accept 10^9 as a currently possible rate. Then in a century we should get 10^(15+9) or 10^24 positions per second, which implies a solution time of ten seconds!

But would we reach the limits of computability before that? Assuming 5x10^9 atoms in a future processor would allow 10^18 of them to fit in a modest 10 kilogram cluster. To finish in ten seconds each processor would only need to be 1/1000 as fast as our Deep Blue standard. And note that if we expand the size of the processors by a factor of 10, it hardly changes the final result.

There are a lot of obstacles to achieving this scale of parallelization, which I alluded to in my original post. We might not succeed in approaching this level of performance, but I think there is a reasonable chance we'll get close enough.

[Uri]

If quantum computing won't be of any help for chess, computers will have, in effect, to use chess theory to solve chess.