Author Topic: Will computers ever solve chess?  (Read 126 times)

chilipepper

  • Full Member
  • ***
  • Posts: 100
  • chilipepper
  • Location: U.S.
    • View Profile
    • QyiQ23607 Pisano
Will computers ever solve chess?
« on: April 18, 2018, 10:34:01 am »
Part 1: "Will computers ever solve chess?"

For background, the thread for this question is very popular at chess.com, but unfortunately it's filled with a lot of speculation, guesswork, spam, and non-relevant commentary. Link here:

https://www.chess.com/forum/view/general/will-computers-ever-solve-chess

The question is also posed here, which is self-moderated, so the "answer" is more concise:

https://cs.stackexchange.com/questions/79272/is-there-an-algorithm-that-can-solve-chess-within-the-span-of-a-human-lifetime

Expanding on this question:

Part 2: "Will computers ever solve infinite chess?" Here the chessboard is unbounded, and it should be assumed chess pieces move with a regular pattern (classical chess pieces, compounds of classical chess pieces, and simple-to-describe chess pieces such as guards and hawks). One example of an infinite chess game is here:
https://chessvariantforum.createaforum.com/variant-reviews/variant-description-chess-on-an-infinite-plane/

Part 3: "Will computers ever solve Trappist-1 (i.e. Infinite Chess with the Huygens)?" The huygens is a chess pieces which jumps prime numbers of squares. This may make solving the game more difficult because the complete set of prime numbers is unknown. The specific rules for Trappist-1 can be found here:
http://www.chessvariants.com/invention/trappist-1

Any comments on Part-1, Part-2, and Part-3 are welcome. :)
the "chilipepper"👹

Share on Facebook Share on Twitter

Agree Agree x 1 View List

John_Lewis

  • Newbie
  • *
  • Posts: 47
    • View Profile
Re: Will computers ever solve chess?
« Reply #1 on: April 18, 2018, 05:42:12 pm »

Expanding on this question:

Part 2: "Will computers ever solve infinite chess?" Here the chessboard is unbounded, and it should be assumed chess pieces move with a regular pattern (classical chess pieces, compounds of classical chess pieces, and simple-to-describe chess pieces such as guards and hawks). One example of an infinite chess game is here:
https://chessvariantforum.createaforum.com/variant-reviews/variant-description-chess-on-an-infinite-plane/


Yes. There are a finite number of pieces. the infinite board is not particularly important past a certain number... I'll call this number X. The actual board size is X in infinite chess, and that size is based on current piece positions, however always centers on the two Kings. So, a piece might wander as far off the board as you like X+1 or X+1,000,000 and it doesn't functionally matter to the game strategy and tactics. The game is bounded to actionable moves by a finite number of pieces and playing in "the hinterland" doesn't matter so long as the computer and deal with it as being "in infinity" or another term "off board". It's influence only matters when it can return to the active board by, likely, one avenue or path. If it can move by two ways, then it's likely on "the active board".

Given this limitation, I see no reason a brute force solution wouldn't eventually be available.
Like Like x 1 View List

Greg Strong

  • Newbie
  • *
  • Posts: 21
    • View Profile
Re: Will computers ever solve chess?
« Reply #2 on: April 18, 2018, 09:54:22 pm »
A brute-force solution to chess will probably not happen unless (A) we get functioning quantum computers with a sufficient number of qubits and (B) a quantum algorithm is developed for chess.

Conventional computers will hit a wall long before chess can be brute-forced.  There are physical limits to miniaturization and clock-speed and we are nearing them rapidly.
Like Like x 1 View List

John_Lewis

  • Newbie
  • *
  • Posts: 47
    • View Profile
Re: Will computers ever solve chess?
« Reply #3 on: April 19, 2018, 01:00:04 pm »
Conventional computers will hit a wall long before chess can be brute-forced.  There are physical limits to miniaturization and clock-speed and we are nearing them rapidly.

Even conventional computers may be able to brute force given the right algorithms. I suspect the wall you are referring to will be solved and Moore's Law will continue on well past the point needed to brute force Chess. This is, of course, my opinion, because the time machine is broken.  ;)

Greg Strong

  • Newbie
  • *
  • Posts: 21
    • View Profile
Re: Will computers ever solve chess?
« Reply #4 on: April 20, 2018, 12:19:25 am »
Even conventional computers may be able to brute force given the right algorithms.

Brute force and algorithmic smarts are practically polar opposites.  The only algorithm which successfully reduced the tree size without any risk overlooking better moves was alpha-beta and that's ancient.  It is almost inconceivable that we'll come up with any further breakthroughs like that.  We do, indeed, improve the strength of our chess programs with better algorithms, but this is done by searching deeper in more promising parts of the tree and searching more shallowly (or pruning altogether) less promising branches.  But this comes with the risk of overlooking things and is no longer "brute force."  You have not "solved" chess, technically speaking, if you have skipped parts of the search tree because they didn't look promising.

I suspect the wall you are referring to will be solved and Moore's Law will continue on well past the point needed to brute force Chess.

Moore's Law is already in trouble.  The writing is on the wall due to physical limitations in miniaturization and heat dissipation.  But Moore's Law only addresses the number of transistors in a CPU, it says nothing about computational performance.  We ran into the wall of maximum single-threaded performance a decade ago.  Computers only become more powerful now through more parallelism.  And parallelism does provide some gains in chess computation but with rapidly diminishing returns.  The exponential growth of the search space in chess is so explosive that it would require something on the order of quadrillions of cores running at a dozen GHz for hundreds of years.  So I'm sorry to report that it's pretty much quantum computers or bust.  Fortunately, I think in the next few decades there is a good chance that we will see some very powerful quantum computers.
Like Like x 1 View List

chilipepper

  • Full Member
  • ***
  • Posts: 100
  • chilipepper
  • Location: U.S.
    • View Profile
    • QyiQ23607 Pisano
Re: Will computers ever solve chess?
« Reply #5 on: April 20, 2018, 10:08:24 pm »
Some other info:

In 1949 Claude Shannon concluded that a naive brute force analysys cannot be used to solve chess because there are too many possible games, and executing a brute force algorithm will take too long. But he did not rule out other methods (so I presume hybrid strategies where brute force is combined with other methods might be possible). His paper can be found here:

http://archive.computerhistory.org/projects/chess/related_materials/text/2-0%20and%202-1.Programming_a_computer_for_playing_chess.shannon/2-0%20and%202-1.Programming_a_computer_for_playing_chess.shannon.062303002.pdf

Regarding infinite chess, Dan Brumleve, Joel Hamkins, and Philipp Schlicht issued a paper "The mate-in-n problem of infinite chess is decidable". They arrived at this conclusion:

"...the problem does not appear to be decidable; and one cannot expect to search an infinitely branching game tree even to finite depth." However, despite the board being unbounded, solution strategies exist, "...the mate-in-n problem of infinite chess is computably decidable..."

The proof depends on the "first-order structure of chess" and piece definitions following "Presburger arithmetic". The paper can be found here:

https://arxiv.org/abs/1201.5597

(This does not necessarily mean that the game can actually be solved - the game's complexity may still exceed technological limitations).

One of the authors maintains a blog where some have asked for some points to be elaborated:

(1) There are versions of infinite chess that do and do not include pawn promotion. The proof to the "decidability of the mate-in-n decision problem" holds for both rule sets (with and without pawn promotion).

(2) Trappist-1 is a type of infinite chess where one of the chess pieces, the huygens, does not obey Presburger arithmetic. Primes cannot be defined using Presburger arithmetic, and therefore the decidability of infinite chess with the huygens is currently unknown: "The huygens piece, however, would break the argument, since the primes are not definable in Presburger arithmetic. So I am not sure whether the mate-in-n problem would still be decidable or not in that case."

Since it isn't even known whether Trappist-1 is decidable, I presume there's no prospect for the game to ever be solved. :(
the "chilipepper"👹
Like Like x 1 View List

BenR

  • Newbie
  • *
  • Posts: 5
    • View Profile
Re: Will computers ever solve chess?
« Reply #6 on: April 22, 2018, 02:07:44 pm »
I think one might be able to get around the prime difficulty of the huygens and (weakly) solve Trappist-1 by replacing say all of black's huygens by stronger pieces and all of white's by weaker pieces, each of which are easier to "compute" with.  If white can still win (or draw) this, then they can win (or draw) the original.  (Is that right?)  Doing the reverse would give a similar statement for black (in case the right answer is "draw.")

(2) Trappist-1 is a type of infinite chess where one of the chess pieces, the huygens, does not obey Presburger arithmetic. Primes cannot be defined using Presburger arithmetic, and therefore the decidability of infinite chess with the huygens is currently unknown: "The huygens piece, however, would break the argument, since the primes are not definable in Presburger arithmetic. So I am not sure whether the mate-in-n problem would still be decidable or not in that case."

Since it isn't even known whether Trappist-1 is decidable, I presume there's no prospect for the game to ever be solved. :(
I thought you introduced the huygens at least in part specifically to break their argument?  Then it's not surprising that it isn't known whether mate-in-n is decidable.  And you seem disappointed that the game might never be solved...why?

chilipepper

  • Full Member
  • ***
  • Posts: 100
  • chilipepper
  • Location: U.S.
    • View Profile
    • QyiQ23607 Pisano
Re: Will computers ever solve chess?
« Reply #7 on: April 23, 2018, 11:31:02 am »
To solve a game means learning which side will win if both sides play perfectly, or learning if both sides can force a draw. The solution should also define the strategy of doing so. If chess is solved and known to be a win for White (for example), then one who is in possession of the "solution" and plays from White, will always be able to win, regardless of the opponent. Strictly speaking, every game requires its own solution. If any rule or piece is altered, then the game may have a different solution.

Although chess is played on an 8x8 board (only 64 squares) solving the game would be a monumental task.

I believe the only thing that will be done with infinite chess and Trappist-1 is theoretical discussion if these games can even be solved, and what resources would be required (algorithms, time, and computer processing power). I'm sure no team or university will actually undertake the task, at least not in my lifetime. I'm usually not one to say something is impossible. Early astronomers once said that there will never be a way to determine the composition of stars. But today astronomers are doing that.

Solving any of these games may require things that we currently can't imagine at the moment. But maybe in the future there will be a way.:)
« Last Edit: April 23, 2018, 09:39:28 pm by chilipepper »
the "chilipepper"👹