3 ms·

Chess is estimated to have 10^120 possible games. Observable universe is estimated to have between 10^78 to 10^82 atoms. So, unless you had some way of dramati

Chess is estimated to have 10^120 possible games. Observable universe is estimated to have between 10^78 to 10^82 atoms. So, unless you had some way of dramatically compressing or simplifying this search space, you'd be needing to store 38 bits+ information, if you had every atom in the observable universe as your memory. Suffice to say, this has not yet been achieved.

kevincox 6y ago
You don't need to consider every state individually to solve a game. For example if you have a game on a 100x100 board and the only goal is to move your piece to the other side you can know you have found the optimal solution if you can do it in 99 moves (assuming that you move 1 per turn). In the chess scenario if you can prove that there is a set of moves where you win no matter what the other colour does then you have solved the game. You don't need to consider every possible game, just the games reachable within this set of moves. Solving chess would be proving that "From starting position black can win every time" (or the same for white). You don't need to prove how to win from every possible board state.
- pretendscholar 6y ago
  My money is on perfect play drawing every time.
  - kevincox 6y ago
    It would be interesting to take bets on the solution :)
- wizzwizz4 6y ago
  But you won't find a set of moves. You have to find a tree of moves, which is substantially larger.
  - kevincox 6y ago
    This is true. It is still a massive problem space but my point is that you don't need to consider every possible game or state.
    - wizzwizz4 6y ago
      Not to prove it always-winning; you only have to go down every possible branch for the other player for that (i.e. √ of the number of states you'd otherwise need). To find it, though? Well, unless you hit lucky, you're going to be considering pretty much every possible game or state, except where you can find shortcuts.
      - kevincox 6y ago
        It is a bit more than that as it is unlikely that the always win sequence would be a fixed list of moves. You would need to show that for you each move the other player makes you have a reaction that also wins.
- danielbarla 6y ago
  I agree, and kind of included this in the "so, unless you had some way of dramatically compressing or simplifying this search space..." disclaimer. Having said this, the nature of many chess endgames suggests that such a proof is not really possible, or at least would not be "simple". As an example, tempo / opposition flips games from draws to wins, etc.
altvali 6y ago
You don't need to care about possible games, but game states, what's the best result and the move to achieve it in each. Another user computed an upper bound at 8.7E+45 positions: https://github.com/lechmazur/ChessCounter https://github.com/lechmazur/ChessCounter . I pointed out that our planet has about 1E+50 atoms. And we can further compress the database by perhaps two orders of magnitude if we don't store symmetric positions or positions close to mate. A Kardashev 2 civilization could play perfect chess.
- goatlover 6y ago
  > A Kardashev 2 civilization could play perfect chess. Assuming they would want to waste part of a planet's worth of computing resources to play perfect chess. In any case, it's far beyond anything we can compute.

kevincox 6y ago

You don't need to consider every state individually to solve a game. For example if you have a game on a 100x100 board and the only goal is to move your piece to the other side you can know you have found the optimal solution if you can do it in 99 moves (assuming that you move 1 per turn). In the chess scenario if you can prove that there is a set of moves where you win no matter what the other colour does then you have solved the game. You don't need to consider every possible game, just the games reachable within this set of moves. Solving chess would be proving that "From starting position black can win every time" (or the same for white). You don't need to prove how to win from every possible board state.

pretendscholar 6y ago
My money is on perfect play drawing every time.
- kevincox 6y ago
  It would be interesting to take bets on the solution :)
wizzwizz4 6y ago
But you won't find a set of moves. You have to find a tree of moves, which is substantially larger.
- kevincox 6y ago
  This is true. It is still a massive problem space but my point is that you don't need to consider every possible game or state.
  - wizzwizz4 6y ago
    Not to prove it always-winning; you only have to go down every possible branch for the other player for that (i.e. √ of the number of states you'd otherwise need). To find it, though? Well, unless you hit lucky, you're going to be considering pretty much every possible game or state, except where you can find shortcuts.
    - kevincox 6y ago
      It is a bit more than that as it is unlikely that the always win sequence would be a fixed list of moves. You would need to show that for you each move the other player makes you have a reaction that also wins.
danielbarla 6y ago
I agree, and kind of included this in the "so, unless you had some way of dramatically compressing or simplifying this search space..." disclaimer. Having said this, the nature of many chess endgames suggests that such a proof is not really possible, or at least would not be "simple". As an example, tempo / opposition flips games from draws to wins, etc.

altvali 6y ago

You don't need to care about possible games, but game states, what's the best result and the move to achieve it in each. Another user computed an upper bound at 8.7E+45 positions: https://github.com/lechmazur/ChessCounter https://github.com/lechmazur/ChessCounter . I pointed out that our planet has about 1E+50 atoms. And we can further compress the database by perhaps two orders of magnitude if we don't store symmetric positions or positions close to mate. A Kardashev 2 civilization could play perfect chess.

goatlover 6y ago
> A Kardashev 2 civilization could play perfect chess. Assuming they would want to waste part of a planet's worth of computing resources to play perfect chess. In any case, it's far beyond anything we can compute.