15
$\begingroup$

Current chess algorithms go about 1 or maybe 2 levels down a tree of possible paths depending on the player's move's and the opponent's moves. Let's say that we have the computing power to develop an algorithm that predicts all possible movements of the opponent in a chess game. An algorithm that has all the possible paths that opponent can take at any given moment depending on the players moves. Can there ever be a perfect chess algorithm that will never lose? Or maybe an algorithm that will always win? I mean in theory someone who can predict all the possible moves must be able to find a way to defeat each and every one of them or simply choose a different path if a certain one will effeminately lead him to defeat.....

edit-- What my question really is. Let's say we have the computing power for a perfect algorithm that can play optimally. What happens when the opponent plays with the same optimal algorithm? That also will apply in all 2 player games with finite number (very large or not) of moves. Can there ever be an optimal algorithm that always wins?

Personal definition: An optimal algorithm is a perfect algorithm that always wins... (not one that never loses, but one that always wins

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ see also what is computational complexity of solving chess, tcs.se $\endgroup$
    – vzn
    Commented Dec 12, 2012 at 15:50
  • $\begingroup$ This question is based on several misconceptions. First, chess computers look way farther than one or two ply ahead: even five years ago on an ordinary laptop, pretty ordinary chess programs were looking 15-16 ply ahead, and 25+ on critical lines. Second, the definition of "perfect" as "always wins" cannot be achieved, as shown in the answers. Third, chess engines don't "predict" moves: they calculate and play moves that are good against any possible responses. $\endgroup$
    – David Richerby
    Commented Apr 3, 2014 at 20:50

6 Answers 6

Reset to default
14
$\begingroup$

Your question is akin to the old chestnut: "What happens when an irresistible force meets an immovable object?" The problem is in the question itself: the two entities as described cannot exist in the same logically consistent universe. Your optimal algorithm, an algorithm that always wins, cannot be played by both sides in a game where one side must win and the other must by definition lose. Thus your optimal algorithm as defined cannot exist.

Improve this answer
$\endgroup$
6
  • 3
    $\begingroup$ Well it can, for example, an algorithm that lets the first player win. This would mean playing first has an advantage. Or perhaps the optimal algorithm only allows the second player to win. This would give the second player an advantage. The third possibility(s) is an algorithm that allows one of players to always force a draw, though not guarantee a win (because as the OP wants to know, this is what happens, for example, if both players play the same winning strategy, if there is no advantage in playing first or second). $\endgroup$
    – Realz Slaw
    Commented Dec 12, 2012 at 0:48
  • 3
    $\begingroup$ @Realz Well, yes, if you change the definition of an "optimal algorithm" then you can prove whatever you like. I used the definition that the questioner asked us to use. $\endgroup$
    – Kyle Jones
    Commented Dec 12, 2012 at 1:07
  • $\begingroup$ This is the answer I was trying to get out of people. There cannot be an algorithm that always wins because It's a game of 2 players so there is no way that algorithm can work because both players can have the same algorithm so simply at least one of the two is forced not to win (lose or draw). I asked the same question to my teacher and it took us a lot of talking for him to get to this conclusion $\endgroup$
    – John Demetriou
    Commented Dec 12, 2012 at 11:38
  • 3
    $\begingroup$ @JohnDemetriou The problem is that that conclusion is wrong. Chess is not a symmetric game because of the first-mover advantage - it is entirely possible that an optimal algorithm exists that allows White to play and win, but Black cannot use that algorithm for the simple reason that she is not White! $\endgroup$
    – Steven Stadnicki
    Commented Dec 12, 2012 at 16:42
  • $\begingroup$ It's also possible, I should note, that going first isn't actually an advantage and that there is actually an algorithm that always allows Black to win against best play by White - but it should be immediately obvious that there is no algorithm that could always allow one to win whether Black or White. This is why people speak of 'best result possible', because 'winning from both sides' is trivially impossible. $\endgroup$
    – Steven Stadnicki
    Commented Dec 12, 2012 at 16:48
23
$\begingroup$

First of all, I believe that chess algorithms look more than 2 plies down, although they don't consider all different possibilities; pruning the search tree is very important to avoid the combinatorial explosion in the number of possible moves.

For a game like chess, there are three possibilities as to the identity of the winner: either player 1 has a winning strategy, or player 2 has a winning strategy, or both players draw under optimal play. It is not known which is the case for the game of chess. However, since chess is a finite game, there is a computer algorithm, consisting of a very large table, which plays chess optimally.

Of course, such an algorithm wouldn't be practical. But for some simpler games, the "value" of the game (which player wins, if any) has been determined, and an optimal algorithm has been devised. Such a game is known as a solved game.

The mathematical subject that deals with (what are known as) combinatorial games is combinatorial game theory. Mathematicians have developed a recursive method to determine the value of a game given the graph of the game, which includes all the allowed positions and moves. You should be able to find a description of this algorithm in the Wikipedia entry or any lecture notes on the subject.

Improve this answer
$\endgroup$
11
  • $\begingroup$ yes, indeed, but I was trying to answer to any answer with another question, what happens when both players play with optimal algorithm???? what happens if a player finds a way to defeat the optimal algorithm? $\endgroup$
    – John Demetriou
    Commented Dec 10, 2012 at 20:57
  • 11
    $\begingroup$ @JohnDemetriou When both players play optimally, you'll get some result. That result is called the value of the game. If chess is white win, that means that nothing black could possibly do could beat a white player playing optimally. White effectively has a huge book (or is capable of producing the move from such a book computationally) that contains a perfect counter for any move black can make in any possible situation that develops from the start of the game. BTW, chillax on the question marks. One per sentence is sufficient. $\endgroup$
    – rrenaud
    Commented Dec 10, 2012 at 21:52
  • $\begingroup$ I apologize for the question marks. It is just the way I type in general. What if chess is the most optimal win. If white and black have the same book and have the same counters? What will happen then? $\endgroup$
    – John Demetriou
    Commented Dec 11, 2012 at 10:19
  • 1
    $\begingroup$ @JohnDemetriou "Optimal" means "the best possible". If the mathematical consequences of the rules of chess are that the best black can possibly do against an optimal white is draw (or even can only delay white's victory for as long as possible), then the optimal algorithm for black is one that achieves that, and its able to win against most non-optimal opponents. $\endgroup$
    – Ben
    Commented Dec 11, 2012 at 22:36
  • 1
    $\begingroup$ @JohnDemetriou It's possible that there is an algorithm that always wins as White; obviously that algorithm could not always win as Black for the reasons that have already been outlined (because it would be playing against itself). It's even possible that it turns out that Black 'wins' chess played perfectly, and that there is an algorithm guaranteeing a win for Black against any opposition. If you mean 'an algorithm that always wins from either side' then I suggest using that terminology; 'optimal' already has a well-defined meaning. $\endgroup$
    – Steven Stadnicki
    Commented Dec 12, 2012 at 16:46
8
$\begingroup$

First of all, good chess algorithms look further than 1 or 2 levels. Rather than using naive tree search, they perform alpha-beta pruning to narrow down the number of options to consider. Note that for openings and end games, a large database of moves is used as it has better performance than tree search, which is used in the middle of the game.

To the question: what you are asking I believe is "Is chess solvable?". Hypothetically, it is, although opinions vary on whether this result will be achievable any time soon. Checkers was solved in 2007 for example, but has much fewer positions (around the square root of the number in chess). See the Wikipedia article for more information.

Incidentally, current best chess AIs nearly always defeat or draw with world champions; so while not currently perfect, the algorithms are pretty good at least!

Improve this answer
$\endgroup$
6
$\begingroup$

In principle, chess is solvable like any other game. As the other answers have pointed out, however, this is not expected to happen anytime soon.

Edit: it has been pointed out in the comments that [1] is a hoax so skip the rest of this answer.

That said, there has been some recent developments in this direction. [1] claims to have shown that the chess opening called King's Gambit is solved: there's only one move that draws for White, while all other opening moves lead to a win for Black. Note that [1] didn't explore the game tree in full depth, but only claims these results to hold with high probability.

[1] http://chessbase.com/newsdetail.asp?newsid=8047

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ Very interesting article indeed! $\endgroup$
    – Paresh
    Commented Dec 11, 2012 at 17:53
  • $\begingroup$ Then that is not an optimal algorithm. I am asking whether an optimal algorithm can ever exist (if we have the computing power) $\endgroup$
    – John Demetriou
    Commented Dec 11, 2012 at 18:39
  • 1
    $\begingroup$ Right, and considering your definition of "optimal algorithm" as an algorithm that always wins, such an algorithm cannot exist for both players, Black and White. Apart from the larger (but finite) game tree, there's nothing special about chess in this regard compared to other games like for example Hex, for which the solution is already known: If the first player uses the optimal (known) strategy for playing Hex, then the first player always wins, no matter what algorithm is used by the second player. $\endgroup$
    – Peter
    Commented Dec 12, 2012 at 3:33
  • $\begingroup$ The King's Gambit being solved article turned out to be a hoax. Note the article starts off "On March 31 the author of the Rybka program, Vasik Rajlich, and his family moved from Warsaw, Poland to a new appartment in Budapest, Hungary. The next day, in spite of the bustle of moving boxes and setting up phone and Internet connections Vas, kindly agreed to the following interview" - in other words, this was on April 1st... $\endgroup$
    – Joe K
    Commented Dec 14, 2012 at 0:43
-1
$\begingroup$

Whether it is possible to always win a game of chess or not depends on the rules of the game. However, there is an technic/algorithm named Minimax (for details, view https://en.wikipedia.org/wiki/Minimax). The algorithm consists in trying to predict which player has the upper hand in different scenarios with a recursive function. Here is an clear explanation of how this works with a simpler game: Tic-tac-toe https://www.neverstopbuilding.com/blog/2013/12/13/tic-tac-toe-understanding-the-minimax-algorithm13.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Although other answer don't explicitly refer to minimax, some do refer to links that eventually lead to them or alpha-beta pruning, an algorithm to implement minimax more efficiently. What does this answer add that hasn't yet been said? $\endgroup$
    – Discrete lizard ♦
    Commented Mar 8, 2018 at 8:44
-3
$\begingroup$

will add another answer that emphasizes the massive state space, not really conceptualized in the question or pointed out in other answers. must disagree with your premise:

Let's say that we have the computing power to develop an algorithm that predicts all possible movements of the opponent in a chess game.

see info on shannons 1950 paper, "Programming a Computer for Playing Chess" which introduced the field of computer based chess playing/algorithms and which its analysis is basically unchanged & still sound (even by the subsequent computer revolution and Moores law). it estimates the number of moves. its absolutely astronomical. in the range of "never within conceivable hardware even with revolutionary unforeseen advances".

its a documented psychological fact [3], probably one of the many psychological biases [2], that humans have trouble understanding numbers of this magnitude. see also counterfactual thinking.[4] while supercomputers compute massive problems, its uncontroversially not within the range of any supercomputer that is currently built or could ever be built. (and many chess aficionados would argue this "combinatorial explosion" in move/position possibilities is an intrinsic aspect of the games "flavor" that seems to be intentionally designed into the millenia-old game).

therefore chess is fundamentally different than some games which have smaller "solvable" state spaces [of which there is some study in computer science & game theory etc] and in some key ways cannot be evaluated within that framework.

Allis also estimated the game-tree complexity to be at least $10^{123}$, "based on an average branching factor of 35 and an average game length of 80". As a comparison, the number of atoms in the observable universe, to which it is often compared, is estimated to be between $4×10^{79}$ and $10^{81}$.

now, that said, it is conceivable (but unlikely) that there may be theoretical insights into the game that could be used to prune the search space substantially. that has happened since 1950 but not really in any fundamentally breakthrough ways.

see also

[1] what is the computational complexity of solving chess, tcs.se

[2] human biases in judgement and decision making

[3] Psychology students publish research on conceptualizing numbers

[4] counterfactual thinking

Improve this answer
$\endgroup$
4
  • $\begingroup$ well in theory my question started as let's say we have the computing power, we combine half the computers of the world to work as a cluster for white and the other half for black.... $\endgroup$
    – John Demetriou
    Commented Dec 12, 2012 at 18:30
  • 1
    $\begingroup$ dude, it holds even if hook up every supercomputer that now exists, or ever exists. your question then amounts to "in theory, if theory was false..." theory (incl from physics) basically says obviously you cant compute (far) more paths than there are atoms in the universe, now or ever in the future... $\endgroup$
    – vzn
    Commented Dec 12, 2012 at 18:32
  • 3
    $\begingroup$ true, but the question starts with LET'S SAY WE HAVE THE COMPUTING POWER, can it this be done? this is the actual question, if we have the power, can there be an algorithm? $\endgroup$
    – John Demetriou
    Commented Dec 12, 2012 at 18:41
  • $\begingroup$ +1 for stating the fact that its physically impossible to achieve the computational power needed to solve chess exactly. Also, don't know why all the -1 with this answer, I think its fair and adds good insight to the other answers. $\endgroup$
    – Alejandro Piad
    Commented May 22, 2013 at 15:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.