DIR Return Create A Forum - Home
---------------------------------------------------------
The Chess Variant Forum
HTML https://chessvariantforum.createaforum.com
---------------------------------------------------------
*****************************************************
DIR Return to: General Discussion
*****************************************************
#Post#: 819--------------------------------------------------
Will computers ever solve chess?
By: chilipepper Date: April 18, 2018, 9:34 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:
HTML 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:
HTML 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:
HTML 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:
HTML http://www.chessvariants.com/invention/trappist-1
Any comments on Part-1, Part-2, and Part-3 are welcome. :)
#Post#: 820--------------------------------------------------
Re: Will computers ever solve chess?
By: John_Lewis Date: April 18, 2018, 4:42 pm
---------------------------------------------------------
[quote author=chilipepper link=topic=126.msg819#msg819
date=1524062041]
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:
HTML https://chessvariantforum.createaforum.com/variant-reviews/variant-description-chess-on-an-infinite-plane/
[/quote]
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.
#Post#: 825--------------------------------------------------
Re: Will computers ever solve chess?
By: Greg Strong Date: April 18, 2018, 8:54 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.
#Post#: 828--------------------------------------------------
Re: Will computers ever solve chess?
By: John_Lewis Date: April 19, 2018, 12:00 pm
---------------------------------------------------------
[quote author=Greg Strong link=topic=126.msg825#msg825
date=1524102862]
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.
[/quote]
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. ;)
#Post#: 831--------------------------------------------------
Re: Will computers ever solve chess?
By: Greg Strong Date: April 19, 2018, 11:19 pm
---------------------------------------------------------
[quote author=John_Lewis link=topic=126.msg828#msg828
date=1524157204]
Even conventional computers may be able to brute force given the
right algorithms.[/quote]
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.
[quote author=John_Lewis link=topic=126.msg828#msg828
date=1524157204]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.[/quote]
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.
#Post#: 835--------------------------------------------------
Re: Will computers ever solve chess?
By: chilipepper Date: April 20, 2018, 9:08 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:
HTML 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:
HTML 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. :(
#Post#: 841--------------------------------------------------
Re: Will computers ever solve chess?
By: BenR Date: April 22, 2018, 1:07 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.")
[quote author=chilipepper link=topic=126.msg835#msg835
date=1524276504]
(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. :(
[/quote]
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?
#Post#: 847--------------------------------------------------
Re: Will computers ever solve chess?
By: chilipepper Date: April 23, 2018, 10:31 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.:)
*****************************************************