19

Chess is a zero-sum game, of limited decisions. The number of possible moves at any given point, and the number of possible states of the board, are all finite.

Tic-Tac-Toe, is one of the easiest examples of a solved game. I can't remember how many years it's been since I last lost a Tic-Tac-Toe match. Does any such "optimal strategy", exist for chess?

Is there any strategy that will guarantee the player would grasp victory or, at worst, a draw?

If there is, please shed some light on it.

13 Answers 13

23

Because of the observation you make, that the tree of possible game paths for chess is finite, chess is indeed solvable in exactly the same sense that tic-tac-toe is. So optimal strategies for chess do exist; however, no one has any idea what they are. Whereas tic-tac-toe is solved thanks to a quite small space of possible games, chess is nowhere near solved because its space of possible games far outstrips what could be dealt with by current computing technology.

As noted in another answer, endgame tablebases exhibit optimal play for all positions with limited numbers of pieces. So in those settings, we have solutions that are as explicit and concrete as are those for tic-tac-toe. But it's important to note that while one can easily teach/remember the optimal strategy for tic-tac-toe and swiftly become a perfect unassisted tic-tac-toe player, the amount of information behind, say, the 7-piece Lomonosov tablebases, is 140 terabytes. There is no concise description of optimal 7-man strategy that one could learn/remember and then play perfectly without assistance.

  • 4
    It may help to mention that there is a lack of consensus as to whether the initial position is a forced win for white, a draw, or even (by some bizarrely complex zugzwang) a forced win for black. This means that we don't even know whether playing the optimal strategy can guarantee a draw. – Kevin Jan 24 '16 at 4:51
  • 4
    There is no "lack of consensus". Overwhelming consensus is "draw": en.wikipedia.org/wiki/First-move_advantage_in_chess. – Jeff Y Jan 24 '16 at 14:18
  • 1
    @JeffY Maybe there is some sense of consensus, but we can't know until we have 32-men tablebases. – 11684 Jan 24 '16 at 17:05
  • 4
    @JeffY, I think that instead of the distracting phrase about "lack of consensus," Kevin really meant to just focus on there being a "lack of proof." I think we all agree that, no matter any overwhelming consensus of opinion that exists (and I agree with you that most tend to believe the game is a theoretical draw), and no matter any empirical evidence from the many games played by humans and/or engines (both of which play sub-optimally), none of it rules out with certainty any of the theoretical possibilities for chess (win for white/draw/win for black). ..... – ETD Jan 24 '16 at 18:29
  • 4
    In short, I think JeffY is absolutely right that there is a sizable consensus of belief that chess is a theoretical draw, and that's perfectly consistent with the accurate point from Kevin and 11684 that we still don't know whether chess is a theoretical draw or not. I think you all probably see eye-to-eye more than the comments above suggest at first glance. – ETD Jan 24 '16 at 18:32
5

Chess games may be finite but the number of possible games is beyond imagining.

There is no known sequence of moves that guarantees either side a win or draw.

4

Chess hasn't been solved and it won't be in the next decades (barring ridiculous computing advancement involving quantum computing or such drastic changes).

You can calculate in your head for the first move: White has 20 options and black has 20 responses; we already have 400 possible positions. This number grows ridiculously fast, the number of possible positions for an 80 move game is unimaginably huge.

Also, if chess were solved, chess tournaments and championships would basically be exercises in memorisation, rendering it pointless. (EDIT: this is rather overstated, see comments.)

Currently, chess is solved for any position with six seven pieces (including kings). The latest estimate I heard for 7-men 8-men tablebases was somewhere in the 2020s, and of course the time needed for an additional piece grows exponentially. I don't expect to see chess anywhere near solved in my lifetime (again, barring truly exceptional computing advancements). (Credit for corrections to Tony Ennis.)

  • There are already 7-man tablebases. – Tony Ennis Jan 23 '16 at 23:49
  • Really? Where? Then I misremembered, please replace 6 with 7 and 7 with 8. @TonyEnnis – 11684 Jan 23 '16 at 23:50
  • 3
    Per ETD's comment, even if chess were solved, humans would not be able to memorize the solution. So the comment about "pointless" is incorrect. – Jeff Y Jan 24 '16 at 14:12
  • 3
    @11684 How so? Does having 7-piece tablebases drastically change the nature of endgame play in tournaments? I don't see it. – Jeff Y Jan 29 '16 at 11:54
  • 1
    @11684 All true. But how would that change tournaments? I can see that it might open a whole lot more opening lines (as non-losers), although I can't see having to memorize any less to play them. And I can see that it would change postmortems of games certainly. But I just don't see human-vs-human games being affected in any significant way, just as human-vs-human 7-piece endgames are not affected by presence of 7-piece tablebases. – Jeff Y Jan 29 '16 at 22:05
3

Another point is that the chess game is finite but only with the 75 move rule (the game is drawn if there are no captures or pawn moves for 75 moves). Before, this the rule with draw by consecutive threefold repetition of the position, the so-called 'German Rule', allowed an infinite number of games as shown by Max Euwe.

  • 3
    With the rule of three times the same position the game would be obviously finite. Just think that there is a finite number of possible positions and that every position can be repeated at most twice. The linked article shows that game can be infinite under the "German rule", which asks for the same sequence to be played from same position three times consecutively – sharcashmo Jan 17 '17 at 10:32
  • Thanks, i messed up with my explanation, it's three times the same sequence of moves :). – Sylvain Julmy Jan 17 '17 at 11:46
2

We know that an optimal strategy exists since when in a game there are a finite amount of players and a finite amount of strategies for each player, one can show that a Nash equilibra exists (so you are playing your optimal response to the other player's optimal response and viceversa).

The thing is that even if we know that such strategy exists, we don't know exactly which strategy is it because of computational limitations.

1

no

we cannot say who should win or if it should be a draw

there are way too many move combinations to even try to compute the answer with current technology by trying all possible moves and seeing the results

then we would have to prune backwards to see what the answer would be and if it were unique

and if we could the game would not be fun any longer

  • 4
    "if we could the game would not be fun any longer" --> People still play connect-4 and some other solved games. – Franck Dernoncourt Nov 27 '16 at 22:39
1

At the beginning of the 20th century, the belief that chess would be solved soon (called "the draw death of chess") was popular. The world champion J.-R. Capablanca tended to believe so. The games of the match Capablanca-Alekhine (almost all in the Queen's Gambit Declined) also confirmed this belief. See, for example: https://en.wikipedia.org/wiki/Capablanca_chess .

The revolution of modern openings (King's Indian etc), then the revolution of artificial intelligence provided intuitive proofs that solving chess is not so simple. Indeed, today grandmaster games are often analyzed using a program and this reveals lines that the players (even the best ones) oversaw during the game.

This being said, an "absolute computational power" can indeed solve chess in the sense of the theory of computation.

1

Here's an answer I originally wrote at https://cstheory.stackexchange.com/questions/6563/what-is-the-computational-complexity-of-solving-chess/38102#38102.

A perfect chess player will always force a win when they can force a win and force a draw when they can force a draw. Of course, at any point if they can force a win, they can also force a draw. Also when ever one player can't force a win, the other player can force a draw. Chess without the 50 move rule or 3 fold repetition rule might not be as hard to solve as you think. It can be shown that adding in the 3 fold repetition rule makes no difference to whether a player can force a win or a draw. The number of possible ways a game can go after n moves keeps growing exponentially with n. The number of states that can occur after n moves on the other hand doesn't keep on growing exponentially because it can't exceed the total number of possible states that can occur in a legal game. According to https://en.wikipedia.org/wiki/Game_complexity, there are about 10^47 states that can occur in a legal game of chess.

Chess can be solved as follows: take a set of states that we can prove contains all states that can occur in a legal game of chess without the 3-fold repetition rule or 50 move rule. Two different states could have the same arrangement of chess pieces and differ by whose turn it is, whether you have the right to capture by en passant, and whether a given king or rook has the right to ever castle again. Next, take all states where the minimum number of moves white can force a win in is 1 which must occur on white's turn. Next take all states where the minimum number of moves white can force a win in is 2, which means it's black's turn and no matter which move they can make, white can force a win in 1 move. Next take all states where the minimum number of moves white can force a win in is 3, which means white has a move that will give them a forced win in 2 moves but can't force a win in 1 move. Next take all states where the minimum number of moves white can force a win in is 4, which means it's black's turn and no matter which move they make, white can force a win in 3 moves but white can't currently force a win in 2 moves. Once we get to a number such that there are no states where the minimum number of moves white can force a win in is that number, we've already found all the states that white can force a win in. We can find all states that black can force a win in in a similar way. All the remaining states are ones where both players can force a draw.

Since there are about 10^47 states that can occur in a legal game of chess, it would take more than our lifetime to use brute force to build a computer that will play chess perfectly no matter how it's opponent plays. I believe it hasn't been proven that there's no much shorter algorithm that can tell you how to play perfectly no matter how your opponent plays. For instance maybe only a small fraction of states that can occur in a legal game can occur in a game where you play the way that algorithm tells you to play so that algorithm works even though it only tells you how to play perfectly in all states that can occur when you have always followed that algorithm since the beginning of the game but not in all states that can occur in a legal game. Maybe in addition to that, that algorithm is a complex algorithm that for each state that can occur in a game where you have always followed it, takes way fewer steps to compute an optimal move than the number of states that can occur in a game where you have always followed it. According to http://onlinelibrary.wiley.com/doi/10.1002/sres.2171/abstract, the evolutionary learning laboratories are planning to solve complex problems. Maybe some day, they'll figure out a complex strategy for playing chess perfectly. Maybe even if an algorithm that's very short and takes very few steps to compute an optimal move in any state that can occur in a game where you have always followed that algorithm doesn't exist, that still doesn't stop a human from being able to learn how to play chess perfectly. Maybe a human could continuously figure things out and retain what they figured out figure more things out from what they previously figured out and retain them by some complex method, be able to figure out from the pieces of information they previously figured out how to play perfectly with a 90 minute base time and 30 second increments in any state that can occur in a game where they play the way they play after learning way fewer bits of information than the number of states that can occur in a game where they play the way they do which they can learn in their life time especially if the technology to live 6000 years gets invented.

It's probably even simpler for a player to have a strategy that ensures that if their opponent plays perfectly, they will also play perfectly. I suspect both players have a forced draw from the beginning of the game. It's probably simpler to have a strategy that forces a draw than a strategy that guarantees that if your opponent gives you a forced win, you will not lose it. A strategy that forces a draw is also a strategy that ensures that if your opponent plays perfectly, you will play perfectly. If they play perfectly, they will not give you a forced win in the first place so you will not lose a forced win after they give you one.

  • The link to your answer on computer-science-SE is helpful. However, I am not sure it was worth copy-pasting its whole text. – Evargalo Nov 30 '17 at 17:21
1

In 1949 information scientist Shannon produced an estimate that it would take 10^90 years to solve chess with 1 MHz computer. Computer power and storage technology has improved considerably since then (aka Moore's law), where computer power and storage capacity doubles every year. That taken into account, it would take approximately 300 years to come up with a computer, that would be 10^90 times more powerful than Shannon's 1 MHz machine. There are no forseeable restraints in computer development. For example Intel's 4004 was made with 10 micrometer photolithography technology whereas current i9s are made with 14 nm technology. When the cores are becoming both more powerful and smaller, it is easy to stuff more cores in a same physical size than the previous years half as powerful ancestors. In photolithography we have just entered ultraviolet wavelength category of below 10 nm, but there exists wavelenghts such as gamma rays, whose wavelength is 1 picometer (that is 10.000 more smaller). A hydrogen atom is 0,1 nm in size, but i.e. quarks are about 200 times smaller than 1 picometer (that is 0.43 x 10^−15 mm, https://www.theguardian.com/science/life-and-physics/2016/apr/07/how-big-is-a-quark)

0

The human mind is much more complex than a tic-tac-toe game. So, you can find a good strategy for play such game.

Chess is quite diferent. Chess is a heuristic game.

you can not put a soldier in charge above a general. The mind of a general is much more complex than a soldier mind, in military terms. It is only a analogy.

Complexity, that is what matters.

You need to be more complex than chess. It is impossible, but you must try, you need to try. You can achieve it in several levels. Many factors are involved. Efforts are important, but many of us make great efforts with poor results. But there are people who made little efforts and achieve excellent results.

Nature is unfair.

But if you learn chess at age of five your chances will be better than if you learn the game at age of ten.

Of course, if you used to stay lots of hours in front of TV when you was a child you wasted your intelligence.

Last, but not least, sorry about my english.

-2

If white and black have at least two choices per move in a 20-move game, the possibilities are (2^20)^2 = 2^40. Good luck trying to calculate all of the variations.

  • 2^40 is still very feasible. Things start to get hard at around 2^60 and usually 2^80 is considered infeasible. – TMM May 9 '17 at 19:09
  • @TMM: Let's raise it up to at least four choices per move. That's 4^40 = (2*2)^40 = 2^80 (There's 40 pairs of twos, so 80 twos.) – Jossie Calderon May 10 '17 at 3:53
  • 2
    What's more reasonable is something like 20 choices per move. Especially in the opening, there are way more than 2 choices per move. And 20^40 > 2^160 is of course way too much to handle with current computing technologies. – TMM May 10 '17 at 12:01
-2

2000-3000 elos more to go until perfect play, so the current top engines could at least double their strength. Chess is actually closer to its infancy than to its later stages. For example, current top engines would guess only one out of 5 best opening moves. Still a long way to go.

  • 3
    How do you get to that number? – Annatar Dec 1 '17 at 9:56
  • Different tests have been conducted and reported on Talkchess forum, the most advanced chess forum on the Internet, but my observations also point in that direction. Also, by comparing the engine evaluations 20 years ago, now, and what could still be improved in that area. – Lyudmil Tsvetkov Dec 2 '17 at 7:50
-3

Chess is definitely a solved Game but with infinite Imagination and Intelligence only it can be termed as Solved . Humans of this Earth take years of Efforts to become a GM . So considering the complexity level and infinite Games you cannot say it is solved . May be for a Super Computer like Deep Blue can nod yes to it but Humans cannot accept it as something solved . It takes a lot of IQ,Skills,Pattern recognition,Openings & Creativity to reach at the top level and continuous practice to sustain .

protected by Phonon Sep 27 '18 at 15:39

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

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