7

If computers just check in an openings-DB what to do in the first 10, 15 or even 20 moves, and if they just check the endgames-DB at the endgame; wouldn't it reach a point where they have a DB of perfect games that goes from opening to endgame?

1
  • 1
    While there is perfect play available on the back end in the form of endgame tablebases (as noted e.g. in Sam's answer below), one doesn't know whether any moves on the front end coming from opening databases are optimal play or not. Determining perfect play wouldn't be a matter of meeting in the middle, but just of working backwards as far as one can.
    – ETD
    Commented Sep 4, 2013 at 22:18

4 Answers 4

5

To my mind, what you are asking is can a computer ever "know" the correct move and evaluation in every conceivable position. Without such complete knowledge, it wouldn't be possible to play perfectly because every evaluation is dependent on evaluations of the multitude of possible upcoming positions. This perfection is what endgame tablebases provide. Outside of contexts where distance to mate can be calculated, tablebases are the only context in which computers have a "perfect" understanding of a position. For reference, 5 piece tablebases (e.g. 2 kings and 3 other pieces) require 7 GB of storage. 6 piece tablebases require 1.2 TB, and 7 man tablebases are only recently completed and require 140 TBs. To solve chess completely, you would need a 32 man tablebase.

The problem is comparable in fictional magnitude to the calculation of the "Ultimate Question of Life, the Universe, and Everything" as depicted in Hitchhiker's Guide to the Galaxy. In that case an entire planet, was devoted to identifying the question. It seems an equally pointless and gargantuan task to attempt to "solve" chess.

Just to put your mind at ease... even though computers may play well above the level of the best humans today, there are still plenty of decisive games between top level computers today. Check out the ongoing TCEC tournament. Clearly, computers are still quite capable of mistakes.

3

I will try a more serious answer because the discussion becomes pointless if we resort to empty arguments. Yes, the Universe may be finite, and yes, the "Ultimate Question of Life, the Universe, and Everything" may need a full Earth and 7.5 million years to solve... so what?

Let's do some quick numbers. Each of the 64 squares can be empty or hold one of 12 different pieces (R, K, B, Q, K, and P in black and white), so the total number of positions that you could set is at most

13^64 = 196053476430761073330659760423566015424403280004115787589590963842248961.

That is about 2 x 10^71 different positions. Of course this is a huge overestimate, because most positions are fake (we should eliminate positions with three or more kings, nine or more white pawns, pawns in the eighth rank, quadruple checks, etc). Let's take the square root:

13^32 = 442779263776840698304313192148785281,

or about 5 x 10^35. By taking the square root we are pretending that for each legal position there is a chess Universe worth of distinct fake positions. This is probably an underestimate, so the true answer must be somewhere in between these two numbers. Now we can confidently say that computers cannot study every legal position in a reasonable time. Even the "tiny" 13^32 is too large...

Wait! so am I arguing against myself? No! Computers cannot analyze every position one-by-one. BUT that is not the only way to solve chess. We humans are reasonably smart. In fact, smart enough to have invented chess. What I suggest is the possibility that people may find shortcuts; rules of thumb that eliminate many cases at a glance. We already have many trivial ones; for instance "K+Q vs K always wins". More sophisticated rules could be found by yet-unknown arguments, perhaps supported by computer tables.

Solving chess by analyzing all positions is brute force, and impractical. Solving chess in a smart manner may still be possible, and I do not see any obstacle. In fact, I do expect computers armed with faster processors and better chess knowledge may become provably perfect within 50 years.

1

Chess is a finite game. Lots and lots of positions, but finite. Eventually, with enough computing power, yes, computers will be able to play a perfect game. When will that happen? That is a different question. It could be less than 10 years if enough breakthroughs in algorithms and hardware are made. It could take 50 years. Who knows?

2
  • Who knows? I suppose that's possible to calculate how many moves are still there in the "middle" (where the computer still has to computer since they are outside any tablebase) and how much time it could take to calculate them.
    – jupoent
    Commented Sep 4, 2013 at 18:55
  • 3
    Arguably, the universe is finite as well. Something can be finite, yet outside the practicable bounds of knowability. Commented Sep 4, 2013 at 20:40
1

The game will not be solvable for a long time. In fact, it will never be solvable unless insanely radical hardware advancements are made. The search tree is too deep and too wide. Since we're talking about 'solving' chess, not 'winning the game', heuristics will not do; every move played - every one of them - must be evaluated to completion.

Choose the fastest processor you know of, multiply its speed by 1000 and you are really no closer to solving this problem. Multiply it by a million instead. Still, no closer from any practical sense.

Right now the new hotness in computer architecture is called a 'quantum computer'. They are still very primitive. The gist is that they can manipulate objects that are in multiple states. So theoretically, a pawn could be on a2 and a3 at the same time. With decades and decades of development, this could yield unheard-of efficiencies. Or, like bubble memory, it could fade away not long after making a splash.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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