How long it will take a Super Computer to solve chess?

[pichy]

Solving chess means finding an optimal strategy for playing chess, i.e. one by which one of the players (White or Black) can always force a victory, or both can force a draw.

Recent scientific advances have not significantly changed that assessment. The game of checkers was solved in 2007,[5] but it has roughly the square root of the number of positions in chess. Jonathan Schaeffer, the scientist who led the effort, said a breakthrough such as quantum computing would be needed before solving chess could even be attempted, but he does not rule out the possibility, saying that the one thing he learned from his 16-year effort of solving checkers "is to never underestimate the advances in technology".[6] Assuming computational power continues to increase exponentially, chess would be solved "before 2250".[7]
[edit] Notes

http://rjlipton.wordpress.com/2010/05/1 ... s-one-day/

[rbarreira]

Who knows what is possible. Some futurists talk about the possibility of harnessing the energy in a whole star to make a computer by surrounding the star with the computer.

[Ponti]

When computers get close to that, take my chess variant:

- 10x10 board

- 4 rooks to each side: white´s : Ra1,Rb1, Ri1,Rj1;
black´s Ra10, Rb10, Ri10, Rj10.

- 2 pawns ahead of these new rooks: Pa2, Pj2; Pa9, Pj9.

The only rule that changes is castling:
- it is allowed to castle "normally" with the inner rook OR
- if the inner rook is not at the first rank, it is allowed to castle with the outer rook. All the exceptions to castling apply in both cases.

[towforce]

When computers get close to that, take my chess variant: 10x10 board...

It will be mathematicians who solve chess - not game tree programmers.

Maths is quietly advancing all the time: for example, computer algebra systems (even free, open source ones) keep on improving, progress is being made on collapsing sparse matrices more efficiently (which may or may not help in eventually resolving chess - but certainly helps with linear algebra and integer programming), and from time to time polynomial-time solutions are found to puzzles that had previously been assumed to be NP-Hard (given that it has been solved to 85,900 cities, a search space of 85,900!=9.6e386,526 possible solutions, is possible to make a case that the travelling salesman problem falls into this category IMO).

I concede that game tree programming might "effectively" solve chess - we might see a chess program that cannot be beaten sooner than we expect - but this will not "prove" that chess is a draw - and, as you point out, it could anyway be easily "unsolved" by enlarging the game.

[pichy]

When computers get close to that, take my chess variant: 10x10 board...

It will be mathematicians who solve chess - not game tree programmers.

Maths is quietly advancing all the time: for example, computer algebra systems (even free, open source ones) keep on improving, progress is being made on collapsing sparse matrices more efficiently (which may or may not help in eventually resolving chess - but certainly helps with linear algebra and integer programming), and from time to time polynomial-time solutions are found to puzzles that had previously been assumed to be NP-Hard (given that it has been solved to 85,900 cities, a search space of 85,900!=9.6e386,526 possible solutions, is possible to make a case that the travelling salesman problem falls into this category IMO).

I concede that game tree programming might "effectively" solve chess - we might see a chess program that cannot be beaten sooner than we expect - but this will not "prove" that chess is a draw - and, as you point out, it could anyway be easily "unsolved" by enlarging the game.

What I meant to say is that it will come a time when chess is finally solved on a standard 8x8 board just like checker was solved with the program Chinook that the best a player playing against Chinook can achieve is a draw.


On July 19, 2007, the journal Science published Schaeffer's team's article "Checkers Is Solved", presenting their proof that the best a player playing against Chinook can achieve is a draw.

[towforce]

What I meant to say is that it will come a time when chess is finally solved on a standard 8x8 board just like checker was solved with the program Chinook that the best a player playing against Chinook can achieve is a draw.

Chess is a much more complicated game than draughts (checkers). IMO, nobody can know for sure ANY of the following:

a) how deep a game tree search would have to be

b) how much knowledge would be needed to do a perfect static evaluation

c) related to b) - when mathematics will provide a full (or partial) solution

As previously stated, my opinion is that first we'll get a game-tree program that cannot be beaten (a practical, but not a theoretical, solution), and later we'll get a mathematical proof that chess is a draw.

The nature of these kinds of events is that they take longer than you expect to happen - but when they do, they then happen more quickly than you'd ever have believed possible.

[Dirt]

When computers get close to that, take my chess variant:

- 10x10 board
...

I don't think that solving chess would make it unplayable. The problems with chess is that there are too many draws, and grandmasters spent too much of their time learning openings. The best solution is to keep the game simple while resolving these problems. I think we should switch to FRC for now, and only look to larger boards if that doesn't work.

[UncombedCoconut]

and from time to time polynomial-time solutions are found to puzzles that had previously been assumed to be NP-Hard (given that it has been solved to 85,900 cities, a search space of 85,900!=9.6e386,526 possible solutions, is possible to make a case that the travelling salesman problem falls into this category IMO).

This is tangential, but the traveling salesman problem is mathematically proven to be NP-hard. (If a polynomial-time solution were found, then a known algorithm using TSP as a subroutine could emulate a non-deterministic computer with polynomial-time slow-down.) Even assuming P != NP, though, this only restricts the worst-case behavior of a TSP algorithm. Smart algorithms can do better than factorial runtime, and can perform much better in "average" than "pathological" cases.

[towforce]

and from time to time polynomial-time solutions are found to puzzles that had previously been assumed to be NP-Hard (given that it has been solved to 85,900 cities, a search space of 85,900!=9.6e386,526 possible solutions, is possible to make a case that the travelling salesman problem falls into this category IMO).

This is tangential, but the traveling salesman problem is mathematically proven to be NP-hard. (If a polynomial-time solution were found, then a known algorithm using TSP as a subroutine could emulate a non-deterministic computer with polynomial-time slow-down.) Even assuming P != NP, though, this only restricts the worst-case behaviour of a TSP algorithm. Smart algorithms can do better than factorial runtime, and can perform much better in "average" than "pathological" cases.

That is tangential to this thread - but it is highly relevant to the binary classifiers thread.

If it is possible to generate permutations of heuristics that can fairly accurately categorise chess positions as either "win" or "not win" (my intuition is that this would be easier than most of that thread's voters think), then it doesn't matter if the classifier's algorithm is either polynomial or "mathematically clean" - it wouldn't matter if the building of the classification took weeks. The end product would be a high quality evaluation function that would run in less than polynomial time - in other words, a near instantaneous position evaluation at better than GM level!

This would be of even more value in non computer friendly games like Go.

[poisonedpawn]

forever