Who would win a perfect game of chess?

[ScientificMind]

While chess hasn't been solved yet, other games have. For example, I know that in in some games, like connect four, if both players play perfectly, the player who goes first will always win. On the other hand, some games, like tic tac toe, a perfect game will result in a draw; in fact, I recently found out that this is true for checkers as well. What I'm wondering though, is if it's possible to predict which scenario a perfect game of chess would lead to even without having fully solved it yet, and if it is possible, what the answer is.

 

[jedishrfu]

The computer! (Spock hasn't been born yet.)



I did find this wiki article:

https://en.wikipedia.org/wiki/Solving_chess

and this stack exchange article though:

https://chess.stackexchange.com/questions/346/is-there-a-perfect-game

 

[mfb]

We don't know.
With increasing performance draws tend to get more common, but that doesn't have to mean perfect play will end in a draw.

 

[BWV]

72 of the 100 games between Alpha Zero and Stockfish were a draw and interestingly, the win/draw ratio was 25/25 when Alpha Zero played white but only 3/47 when it played black (Alpha Zero won every game). I have not seen any statistics released on the 44 million training games played regarding an advantage for white vs. black.https://arxiv.org/pdf/1712.01815.pdf

 

[lpetrich]

Previous link titled: Solving chess - Wikipedia. More generally, Game complexity - Wikipedia, Solved game - Wikipedia

Solutions can be

• ultraweak - the outcome of the game if both players play perfectly. In some cases, one can do the solution non-constructively, like with strategy-stealing.
• weak - an algorithm that gives one player the best outcome, no matter what the other player does, when starting from the initial position.
• strong - like the above, but starting from any position.

Tic-tac-toe is strongly solved, and it is easy to solve it with brute force. Connect Four is more difficult, but it has been solved in its classic configuration, 7 wide and 6 high, and other small sizes. Likewise, Go has been solved for 7*7 and smaller sizes, though Go is typically played on a 19*19 board.

The most difficult board-game solution so far is for checkers, and is required an enormous amount of computing power. Computers Solve Checkers—It's a Draw - Scientific American, Chinook - World Man-Machine Checkers Champion, Checkers Is Solved | Science The abstract:

The game of checkers has roughly 500 billion billion possible positions (5 × 10^20). The task of solving the game, determining the final result in a game with no mistakes made by either player, is daunting. Since 1989, almost continuously, dozens of computers have been working on solving checkers, applying state-of-the-art artificial intelligence techniques to the proving process. This paper announces that checkers is now solved: Perfect play by both sides leads to a draw. This is the most challenging popular game to be solved to date, roughly one million times as complex as Connect Four. Artificial intelligence technology has been used to generate strong heuristic-based game-playing programs, such as Deep Blue for chess. Solving a game takes this to the next level by replacing the heuristics with perfection.

 

[DaveC426913]

How can one define or determine a perfect game? Doesn't it require a limited number possible strategies?

I can see tic tac toe having a limited number of strategies, but how does one do that for chess?

 

[BeedS]

Stalemate due to insufficient material.
When only the two kings remain could be the result of a perfect game?
And the position the kings stalemate on will also be a major factor for a perfect game. Would the kings need to end the game on opposite squares of the board? Which squares would they end/finish on for a perfect game?

 

[suremarc]

How can one define or determine a perfect game? Doesn't it require a limited number possible strategies?

I can see tic tac toe having a limited number of strategies, but how does one do that for chess?

There is a threefold repetition rule in chess, whereby a draw is forced when the same position is reached thrice. Since there are a finite number of possible arrangements of a given set of pieces, after a sufficient number of moves there must either be a draw by threefold repetition, or some sort of event that prevents threefold repetition must occur. However, those types of events tend to be some kind of irreversible change in the game state, which collapses the number of possibilities for future moves. I feel pretty confident saying that one could prove along these lines that chess is finite.

 

[PeroK]

There is a threefold repetition rule in chess, whereby a draw is forced when the same position is reached thrice. Since there are a finite number of possible arrangements of a given set of pieces, after a sufficient number of moves there must either be a draw by threefold repetition, or some sort of event that prevents threefold repetition must occur. However, those types of events tend to be some kind of irreversible change in the game state, which collapses the number of possibilities for future moves. I feel pretty confident saying that one could prove along these lines that chess is finite.

The 50-move rule limits the maximum number of moves to just under 6000. There's a thread about it here:

https://www.physicsforums.com/threads/exact-number-of-possible-chess-games.730486

 

[PeroK]

How can one define or determine a perfect game? Doesn't it require a limited number possible strategies?

I can see tic tac toe having a limited number of strategies, but how does one do that for chess?

Chess, with enough time and computing power, is a solvable problem (*). The most likely solution, I imagine, is a draw with "perfect" play. And, I imagine, that a draw could result in many different ways. For example, if it is generally a draw, then most opening moves for White would be good (a few might be losing moves); and, likewise, for many of White's opening moves, Black may have a choice of several good moves; and so on.

There is also the possibility that the game has at least one forced win for White. And, of course, there could be a forced win for Black against any opening move, but that seems very unlikely.

(*) Note that the opening position is just a more difficult problem than a simplified position, where the draw/win/losing status can be proved by crunching all the possibilities.

 

[lavinia]

I wonder how Chess algorithms actually work. If they are like people but with a lot more ability to see tactical combinations then they have a method to evaluate a position without running through all of the possible consequences. It would seems that this makes them imperfect.

Forced tactical lines might be thought of as perfect subgames. From this point of view a perfect Chess game would have no evaluation method but would find all forced tactics in all possible lines. The perfect Chess game would be a tactically perfect game. Each side would find all possible outcomes by exhaustive trial and error and would never play a line that would lead to a tactical loss - if in fact there are such games.

 

[PeroK]

I wonder how Chess algorithms actually work. If they are like people but with a lot more ability to see tactical combinations then they have a method to evaluate a position without running through all of the possible consequences. It would seems that this makes them imperfect.

Forced tactical lines might be thought of as perfect subgames. From this point of view a perfect Chess game would have no evaluation method but would find all forced tactics in all possible lines. The perfect Chess game would be a tactically perfect game. Each side would find all possible outcomes by exhaustive trial and error and would never play a line that would lead to a tactical loss - if in fact there are such games.

The traditional chess playing algorithm looks at all possible moves and evaluates each position based on criteria provided by the human developers. It must also decide how far to analyse each line: a crude algorithm might analyse every line to the same depth; but, a more sophisticated algorithm will focus on the critical lines that determine whether the first move under consideration is good or bad.

AlphaZero is, of course, different in that it had no human input on how to assess a position; it was given only the rules.

In any case, the imperfections of the current chess engines are not really to do with not following up lines that are obviously bad, but in the imperfections of the assessment algorithm. That is what AlphaZero has exposed: that there is a deeper and better way to assess each position than the human-developed algorithms.

 

[BWV]

Chess is unsolvable with traditional computers

Claude Shannon noted that a true chess solution would require storing 10^120 moves. This gets into age of the universe type computational times and impossible storage requirements with any conceivable computer technology other than maybe a huge quantum computer

 

[lavinia]

Chess is unsolvable with traditional computers

Claude Shannon noted that a true chess solution would require storing 10^120 moves. This gets into age of the universe type computational times and impossible storage requirements with any conceivable computer technology other than maybe a huge quantum computer

So in principal there are perfect Chess games. But it seems impossible in practice to find all of them. But maybe finding a few of them would be.

 

[PeroK]

So in principal there are perfect Chess games. But it seems impossible in practice to find all of them. But maybe finding a few of them would be.

You can't find any of them. For example, it could be the case that White has a forced win. But, only with let's say 1. e4. Or, potentially, only with 1. c4. Or, both. Until you resolve that there is no way absolutely to judge white's first move as "perfect". In these cases, for example, 1. d4 would be a mistake, as that may not lead to a forced win.

If you are talking about a perfect game in practical terms, that just means a game where neither player made a clear mistake. But, I'd say that's more just an error-free game than one which is objectively perfect.

 

[BWV]

This is most often cited as a perfect game, as modern computers have not been able to find a better sequence of moves after move 4

http://www.chessgames.com/perl/chessgame?gid=1250160

 

[DaveC426913]

If you are talking about a perfect game in practical terms, that just means a game where neither player made a clear mistake. But, I'd say that's more just an error-free game than one which is objectively perfect.

Exactly.

This is most often cited as a perfect game, as modern computers have not been able to find a better sequence of moves after move 4

One perfect game is not the same as the set of perfect games.

It seems to me that, for the OP to be meaningful, it must be talking about the set of perfect games.

Look at the tic tac toe example. It is insufficient to examine a single game - one examines all possible games to determine that they always lead to a draw.

 

[mfb]

Chess is unsolvable with traditional computers

Claude Shannon noted that a true chess solution would require storing 10^120 moves. This gets into age of the universe type computational times and impossible storage requirements with any conceivable computer technology other than maybe a huge quantum computer

10¹²⁰ is the estimated game tree complexity. It is not the number of states you would have to store, which is closer to 10⁴⁷.

What you can do, if you can store 10⁴⁷ states and access them in reasonable time: Start with the existing database of 7-figure games where you know how each game ends with perfect play. Go through all other states. If the next move can go to a known winning position for the player who moves, mark them as winning. If the next move can only go to a known draw position, mark them as draw. If it has to go to a losing position mark them as loss. If the next move goes to some unknown state, don't mark them. Repeat. If you use rules that don't allow infinite cycles (50 move rule or similar) then this process stops after a number of iterations that corresponds to the maximal length of a game - something like 1500 for the 50 move rule if I remember correctly. That gives you 10⁴⁷*1500 or 10⁵⁰ steps. A huge number, but nowhere close to the game tree complexity of chess. If you can store every state with 10 atoms you need about the mass of Earth for that project. Practical? No. But within the computing capabilities of this universe.

The algorithm as described is very impractical, you can speed it up significantly by prioritizing states where you have a higher chance to assign labels to them. No need to consider boards with 20 figures on them (most board states have more than 20 figures) if you only know something about boards with 10 figures.

 

[Delta2]

We don't know yet with perfect (optimal ) play from both black and white whether it is a draw or win for some side.

During the 15th,16th , 17th and up to 18th century scholars of chess believe that with optimal play from both sides, white has a win.

From the 19th century where new defences were discovered for black (e.g Sicilian Defence) this view shifted and now we believe that with optimal play for both sides, the result will be a draw.

 

[fluidistic]

Chess is kind of weakly solved when 7 pieces (including the two kings) remain on the board (discarding the castling moves and en passant). I don't know if they're working on 8 pieces, etc. An idea to have another indication that chess may be a draw (or a win/loss) with perfect play is to set symmetrical starting positions with the few pieces on the board and see the outcome of perfect moves.

I also guess that it leads to a draw, but it's just a pure guess.
Some chess variants are easier to deal with than chess (giveaway or suicide chess), whilst others are more complicated (crazyhouse).

Another very interesting question is whether all starting position of chess 960 (Fischer random chess) lead to the same outcome than regular chess, with perfect play.

 

[phyzguy]

How can one define or determine a perfect game? Doesn't it require a limited number possible strategies?

Someone correct me if I'm wrong, but I think game theory has proved that a game of perfect information (which chess is) has an optimal strategy. So I think the OP was defining a perfect game as one where both players follow this optimal strategy, and asking what is the result. Of course, as many have said, the game is so complex that we don't know the optimal strategy, so we don't know the answer.

 

[jbriggs444]

Someone correct me if I'm wrong, but I think game theory has proved that a game of perfect information (which chess is) has an optimal strategy. So I think the OP was defining a perfect game as one where both players follow this optimal strategy, and asking what is the result. Of course, as many have said, the game is so complex that we don't know the optimal strategy, so we don't know the answer.

There is at least one optimal strategy for each player. There may be more than one.

 

[Helios]

It's going to be hard to define what an optimal strategy is. Maybe: make the best move each turn. Sometimes humans and computers can't know what that is. Also, like jbriggs444 said, there can be several moves, one as good as the other, so the optimal in the definition breaks down. When the finale of the game is too distant, humans and computers choose the most compelling move. Stockfish decides by an evaluation procedure that humans have crafted. AlphaZero ( the paramount supreme of all chess ) was left to invent its own evaluation procedure.

 

[Delta2]

In any given chess position of a normal chess game, there are (on average) 40-50 legal moves (moves that are allowed by the rules of chess), and from these moves only 4-5 are the optimal moves (this is an empirical law that one GM has told to me), so yes there can be more than one optimal choice.So if someone knows only the rules of chess that allow him to figure out the legal moves, and chooses totally randomly which move to play, he only has 10% probability to chose an optimal move.

 

[Helios]

that one GM has told to me

What is his name because this empirical law of 4-5 optimal moves is not well known.

 

[BWV]

I do think it’s telling that nearly all of alphazero’s victories (as opposed to draws - AZ did not lose a game) over Stockfish came when AZ played white.

 

[phyzguy]

It's going to be hard to define what an optimal strategy is.

I don't think so. As I said earlier, game theory has proven that at least one optimal strategy exists. This means that there exists a strategy that cannot be improved upon. All you can say is that it is very difficult to find the optimal strategy.

 

[mfb]

I do think it’s telling that nearly all of alphazero’s victories (as opposed to draws - AZ did not lose a game) over Stockfish came when AZ played white.

It tells us white has an advantage if the players are not perfect. Nothing new, you find the same for strong human players. Draws are common, white wins sometimes, black wins rarely.There might be 4-5 moves where grandmasters can’t tell which one is better, but that doesn’t mean they are equal.

 

[Delta2]

What is his name because this empirical law of 4-5 optimal moves is not well known.

Don't want to tell his name for various reasons.
This law let's better call it the law of 10% . In the opening its not so accurate because during the opening phase the optimal moves are usually 20-30% of the legal moves (and sometimes even more for example in the first move for white there are 20 legal moves for white, from those I know at least 8 that lead to well known openings, so it is at least 8/20=40%). It is mostly accurate during middle game. In the endgame again it is losing its accuracy.

 

[lpetrich]

Quote attributed to chess master Efim Bogolyubov: When I am White I win because I am White. When I am Black I win because I am Bogoljubow. -- he was overstating it by far, but it does seem that White has a greater chance of winning than Black, all other things being equal: First-move advantage in chess - Wikipedia states that White wins instead of Black 52% - 56% of the time.

 

[lpetrich]

Endgame tablebase - Wikipedia -- solution complete up to 7 pieces. Some positions previously thought to be drawn have turned out to be winnable, though sometimes with a lot more than 50 moves. The 50-move rule states that after 50 moves with no captures or pawn moves, the game is officially drawn. That is like having a timeout in an Internet connection -- if something takes too long, then one's software will quit.

IMO, it is telling that some victories require more than 50 moves, because that suggests that a complete solution for chess will include much longer games.

 

[BWV]

Quote attributed to chess master Efim Bogolyubov: When I am White I win because I am White. When I am Black I win because I am Bogoljubow. -- he was overstating it by far, but it does seem that White has a greater chance of winning than Black, all other things being equal: First-move advantage in chess - Wikipedia states that White wins instead of Black 52% - 56% of the time.

Interesting that is a far smaller margin than the 100 games between Alphazero and Stockfish

 

[mfb]

First-move advantage in chess - Wikipedia states that White wins instead of Black 52% - 56% of the time.

52% to 56% is the score for white. Using the chessgames.com database we have 37.5% win for white, 34.9% draws, and 27.6% win for black. If someone wins, it is white 37.5/(37.5+27.6) = 58% of the time. If we use the CEGT chess engines results we get 59%. If we use the 100 games of AlphaZero against Stockfish it is 25/(25+3) = 89%.

It is worth noting that AlphaZero did lose some games against Stockfish. It won 155 times and lost 6 times in a more recent match where both ran with the same hardware conditions for 1000 games. The publication splits it up by side in figure 2: Two losses were with white, four with black. 145 wins were with white, only 10 with black. 84% of the games were draws.

AlphaZero beats Stockfish even when playing exclusively black. It also beats Stockfish with 1/10 of the time and 50% white (but not with 1/30).

 

[lpetrich]

This may deserve its own thread, but something related, at least in overall subject matter, is the Eight queens puzzle - Wikipedia -- how many ways to place 8 chess queens on a board so that they do not attack each other. The solutions can be found with an in-place tree search that uses backtracking.

This problem can also be solved for different board sizes with corresponding numbers of queens. The number is observed to increase approximately factorially, but a general formula is not known and neither is its asymptotic behavior.

There are variations, like different chess pieces: rook, bishop, knight, king. Also boards with periodic boundary conditions and higher-dimension boards, like a n*n*n cubical board. On a n*n board, one can place at most n queens, n rooks, 2n-2 bishops, n*floor((n+1)/2) knights, and floor((n+1)/2)^2 kings.

 

[lpetrich]

I have decided to create another thread for this problem.