Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Featured I Who would win a perfect game of chess?

  1. Jan 14, 2019 #1
    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.
     
  2. jcsd
  3. Jan 14, 2019 #2

    jedishrfu

    Staff: Mentor

  4. Jan 14, 2019 #3

    mfb

    Staff: Mentor

    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.
     
  5. Jan 14, 2019 #4

    BWV

    User Avatar

    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
     
  6. Jan 18, 2019 #5
    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:
     
  7. Jan 18, 2019 #6

    DaveC426913

    User Avatar
    Gold Member

    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?
     
  8. Jan 19, 2019 #7
    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?
     
    Last edited: Jan 19, 2019
  9. Jan 19, 2019 #8
    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.
     
  10. Jan 19, 2019 #9

    PeroK

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2018 Award

    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
     
  11. Jan 19, 2019 #10

    PeroK

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2018 Award

    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.
     
  12. Jan 19, 2019 #11

    lavinia

    User Avatar
    Science Advisor
    Gold Member

    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.
     
  13. Jan 19, 2019 #12

    PeroK

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2018 Award

    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.
     
  14. Jan 19, 2019 #13

    BWV

    User Avatar

    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
     
  15. Jan 19, 2019 #14

    lavinia

    User Avatar
    Science Advisor
    Gold Member

    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.
     
  16. Jan 19, 2019 #15

    PeroK

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2018 Award

    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.
     
  17. Jan 19, 2019 #16

    BWV

    User Avatar

    Last edited: Jan 19, 2019
  18. Jan 19, 2019 #17

    DaveC426913

    User Avatar
    Gold Member

    Exactly.

    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.
     
  19. Jan 19, 2019 #18

    mfb

    Staff: Mentor

    10120 is the estimated game tree complexity. It is not the number of states you would have to store, which is closer to 1047.

    What you can do, if you can store 1047 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 1047*1500 or 1050 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.
     
  20. Jan 20, 2019 #19

    Delta2

    User Avatar
    Homework Helper
    Gold Member

    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.
     
  21. Jan 23, 2019 #20

    fluidistic

    User Avatar
    Gold Member

    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.
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Have something to add?