Thoughts On Solving Chess

21 May 2008

Thoughts On Solving Chess

One of the great 20^th century achievements of mankind are the AK-47, the portable hairdryer, and powered human flight. Another important one is the advent of digital computers and programs that can beat the strongest human players in chess. At the beginning of the 21^st century, mankind had essentially lost the great game of chess against the beastly machine.

Chess engines are today as sophisticated as computing power and storage capacity are abundant. So can chess be “solved”? Can it be proven that white can force a win or black can force a draw with perfect play?

Apparently not. Or not yet. The number of possible positions on a chess board is said to be too large, and the number of possible sequences of positions, i.e. games, is even larger. I argue though that it should be possible to both prove that a solution exists as well as deliver such solution over time.

These thoughts are a purely intuitive shot from the hip, made by a non-mathematician and below-average chess player that does not know how to code.

Assume the following:

1. There is a finite number of squares. (64, say)
2. There is a finite number of pieces. (16 to be precise)
3. The rules of chess apply. This includes draw by threefold repetition and the fifty move rule.

The fifty move rule we need to relax to not exclude cases in which more than fifty moves are needed to secure a win. It has been shown that extending the fifty move rule to a 100 move rule sufficiently covers those exceptions but the number of moves in that rule is in my opinion irrelevant so long as it is finite.

It should follow that:

1. There is a finite number of legal moves in any position. This follows from assumptions 1, 2 and 3. (Undisputed I guess.)

and

1. There is a finite number of possible positions. (This one rather large and estimated to be around 10⁴⁰.

Hence:

1. There is a finite number of possible sequences of positions, i.e. games. (Follows from assumptions 1 to 4.) This number is, quite naturally, astronomically large.

In other words, the decision tree representing any possible chess game should have fixed and exact size. (Any guesses?) The size changes if you alter the fifty move rule. All it needs to “solve” chess would be to calculate every branch in the tree. If in a given position more than one move guarantees a win or a draw then they can be ranked in terms of efficiency such as “best move is the one leading to a win or draw in the shortest number of moves” or “best move is the one leading to a win or draw with minimum loss of material” or “best move is the one leading to a win or draw with minimum number of squares moved” or a combination thereof.

Easy, ey? So what’s the problem? The sheer size of the tree. Computing power by far not enough plus storage capacity needed for endgame tablebases blah blah. Talking of tablebases, all it needs is a tablebase covering 32 pieces on the board and chess is (by default) solved. Solving by backward induction or “retrograde analysis” as they call it. Can’t somebody just *do it* in a lazy afternoon?

Here are some suggestions on how to get closer to that goal:

• Leave the beast running. As much as the value of Pi has been calculated to x trillion significant figures, one good processor with one good chess engine and one good database should be able to do it over time. A long long time.
• Network: Engines as well as databases around the world can be combined to help solve chess. What it would need though are a common set of standards:
  • Interface
  • Rules
  • Documentation of code, hardware and parameters
  • Output format
  • Chunking: dedicate certain resources to certain specific tasks, e.g. 100 super-computers work on all 7 piece endgames, 1000 work on all 8 piece endgames etc.

This slicing of chess into certain modules with well-defined start and end points will be crucial to solving it – no computer or database will be able to do it alone in the foreseeable future – I see networking or hardware, software and liveware (humans) as the only viable solution.

Also it would take some big corporation (like IBM maybe?) to devote the programming, networking and management know-how to do this.

As I have started with shots from the hip I shall continue to do so and take a few guesses. Let’s call them Baldini’s Chess Theorems:

Baldini’s Chess Theorem Zero:

It took less than 50 years from the first digital chess engine to the human world champion being beaten by one with standard time rules. Similarly, I argue that mankind will have solved chess within the next 50 years, i.e. by 20 May 2058.

Baldini’s Chess Theorem 1:

White can force a draw on the first move with perfect play on both sides thereafter.

Baldini’s Chess Theorem 2:

Black can force a draw after an imperfect first move by white with perfect play on both sides thereafter.

Baldini’s Chess Theorem 3:

Either side can force a win after either (i) one opponent’s move at or above a critical level of imperfection with perfect play on both sides before and thereafter or (ii) a maximum number of imperfect opponent’s moves below critical level with perfect play before, in between and thereafter. (Theorem 3 assumes that the side forcing the win always plays perfectly.)

Baldini’s Chess Theorem 4:

The critical level of imperfection for Theorem 3 is at or below 100 evaluation points (i.e. 1 pawn) of modern chess engines.

Baldini’s Chess Theorem 5:

The maximum number of imperfect opponent’s moves below critical level for Theorem 3 (ii) is at or below 10.

I pledge to write a passionate love letter to the nominee of your choice for each Theorem proven wrong.

Yo folks, that’s it for the moment. Please send me your criticism, feedback and corrections. Make me aware if I have inadvertently reinvented the wheel by overlooking existing material. Give me pushback.

And please donate some money using paypal so that I can keep writing. One dollar will give me courage, ten dollars will buy me food, 100 will help pay the rent, for 200 I will write on the topic of your choice and for 20,000 you get a PhD thesis on the topic of your choice. And no, you will not be allowed to take credit for it or influence findings.

My email is <max [dot] baldini [at] gmail [dot] com>.

Keep it real and come back for more stuff.

Yours truly,

Max Baldini

Tags: Chess, Chess Theorem, Chess Theory, Computer Chess, Game Theory, Max Baldini, Perfect Chess Move, Perfect Move, Perfect Play, Solved Game, Solving Chess, Supercomputer