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

chilipepper

  • Full Member
  • ***
  • Posts: 100
  • chilipepper
  • Location: U.S.
    • View Profile
    • QyiQ23607 Pisano
Re: Will computers ever solve chess?
« 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