5 ms·

I don't know a lot about chess but I have one question: isn't chess a solved game (in the sense that given a board state we always can compute the right move)?

I don't know a lot about chess but I have one question: isn't chess a solved game (in the sense that given a board state we always can compute the right move)? why use a neural network that can introduce, a very small percentage of the time, mistakes? I guess it is for performance reasons?

elcomet 6y ago
Chess is definitely not a solved game. The end game is solved though, when you have only 7 pieces left on the board. See https://en.wikipedia.org/wiki/Endgame_tablebase#Computer_chess https://en.wikipedia.org/wiki/Endgame_tablebase#Computer_che...
mvanaltvorst 6y ago
You can imagine playing chess as a tree. You start with a game state, and every possible move is an edge to a new game state. Unfortunately, the amount of game states grows approximately exponentially (e.g. for every game state there are approximately 40 moves to play, thus every extra move multiplies #(game states) by 40, approximately). This neural engine is a trick so that Stockfish does not have to simulate all 40 moves every game states. The neural net outputs the moves that are most likely to be strong moves, and Stockfish will only consider those moves. Of course, this is a very basic explanation and there are many more optimisations Stockfish uses, though the ultimate goal of almost every optimisation is to reduce the amount of simulation Stockfish has to do.
- V-2 6y ago
  "This neural engine is a trick so that Stockfish does not have to simulate all 40 moves every game states." This optimization always done by chess engines, it's called pruning (they'd be quite crippled without it). Maybe the neural network component is now in charge of it, but it's not a new thing.
  - mvanaltvorst 6y ago
    Of course, I had accumulated all other pruning strategies under the "other optimisations".
- bbojan 6y ago
  >> The neural net outputs the moves that are most likely to be strong moves, and Stockfish will only consider those moves. I don't think this is correct. According to the article, they are only using the neural network for evaluating the value (strength) of the positions. The search is still the same. I believe Leela works in the manner you described.
- blt 6y ago
  From the article: > it’s a simple feedforward network with... a single scalar output to give a numerical score for the position, indicating how favourable it is for the player about to move. The search algorithm proposes moves, computes the board state resulting from them, and evaluates each state. This may seem like a trivial distinction, but it's important. The Stockfish method requires knowing the rules of the game; networks that output a move directly do not.
dan-robertson 6y ago
Chess is not a solved game (though I think the stalemate rules make it finite, there are far too many positions). All computer chess programs have to try to determine if positions will be good without playing out all possible ways the game could go. Usually this is some combination of search strategies and scoring positions (the article describes how stockfish scores positions).
- V-2 6y ago
  I agree it's finite, but why do you think it's specifically owed to the stalemate rule, of all things?
  - elcomet 6y ago
    I believe it's the repetition rule that makes the game finite, not the stalemate rule, since number of positions is finite. There is also the 50-move rule of course which limits more drastically the length of a game.
    - V-2 6y ago
      Right, that would make more sense to me. Although it should be stressed that neither threefold repetition nor the 50-move rule work automatically. They need to be claimed by one of the players. If neither player does, the game can go on.
      - jstanley 6y ago
        The 75-move rule does work automatically though, so the game is still finite.
        V-2 6y ago
        Frankly, I wasn't aware of the 75-move rule! This indeed caps the length of possible games. The threefold repetition rule doesn't have an equivalent (there's no, say, "fivefold repetition" draw that could be enforced despite the players' will), but it's really irrelevant from the perspective of solving chess, because there's no point in analyzing what happens if game goes through the same loop 1, 10 or 100 times. And the 75-move rule sets a hard limit anyway, so you couldn't loop infinitely, even if it mattered.
zone411 6y ago
No, it's not close to being solved. I made a new estimate recently at there are about 8.7E+45 unique positions: https://github.com/lechmazur/ChessCounter https://github.com/lechmazur/ChessCounter. You don't need to analyze all of them to generate the proof but it's still far beyond our computational and storage capacities to solve chess.
- altvali 6y ago
  For comparison, there are about 10E+49 atoms making up our planet.
aliceryhl 6y ago
No, it is not solved. To solve it, you would need to investigate all possible continuations of the game, all the way until the game ends, but there are so many continuations that this is impossible.
- nullc 6y ago
  A game could be solved even if its state space was too large to enumerate, for example if you could show that there was some latent structure that let you prove things about large parts of the state space without completely exploring it. This is, for example, why we have a concrete number for the number of legal go positions even though there are far too many to enumerate. https://en.wikipedia.org/wiki/Go_and_mathematics#Legal_positions https://en.wikipedia.org/wiki/Go_and_mathematics#Legal_posit... The rules of chess are so irregular that it seems likely that any latent structure would be tremendously complex, but you never know what some clever new analysis technique will do.
tspduck 6y ago
I have to disagree with the others. Since AlphaZero I think chess is closed to being solved. Technically it is not, but practically is is. Chess is a hard game to solve completely, and I think one reason is that there are many states in chess where there is not one superior move, but only a probable optimal move, in the sense that the game-tree for winning against the move is smaller than other moves. Then the agent/player has to guess what the opponents strategy is given that move, and that depends on the opponent. I plays are truly creative, and its results speak for itself. From wiki: "In AlphaZero's chess match against Stockfish 8 (2016 TCEC world champion), each program was given one minute per move. Stockfish was allocated 64 threads and a hash size of 1 GB,[1] a setting that Stockfish's Tord Romstad later criticized as suboptimal. AlphaZero was trained on chess for a total of nine hours before the match. During the match, AlphaZero ran on a single machine with four application-specific TPUs. In 100 games from the normal starting position, AlphaZero won 25 games as White, won 3 as Black, and drew the remaining 72. In a series of twelve, 100-game matches (of unspecified time or resource constraints) against Stockfish starting from the 12 most popular human openings, AlphaZero won 290, drew 886 and lost 24." source: https://en.wikipedia.org/wiki/AlphaZero#Chess https://en.wikipedia.org/wiki/AlphaZero#Chess
- hiq 6y ago
  > there are many states in chess where there is not one superior move, but only a probable optimal move I don't think this statement is true given [0], but maybe I understood you wrong. [0]: https://en.wikipedia.org/wiki/Zermelo%27s_theorem_(game_theory) https://en.wikipedia.org/wiki/Zermelo%27s_theorem_(game_theo...
  - magicalhippo 6y ago
    I think you misunderstood, and that the point was that in chess, especially during the mid-game phase, there's very often not a single clearly superior move but rather several moves that apparently improves your position by roughly the same amount. The uncertainty is due to the inability to scan the entire sub-tree for each move. The theorem you linked to would only be applicable in certain endgame situations.
hiq 6y ago
https://en.wikipedia.org/wiki/Solving_chess https://en.wikipedia.org/wiki/Solving_chess
danielbarla 6y ago
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.
T-hawk 6y ago
You're correct, in that given a board state the right move can always be exhaustively computed, because the game has no randomness or hidden information. But enough computing power doesn't exist on the planet to iterate through all the possible states. The word you're looking for is "deterministic", rather than solved. Solved is usually used to mean the exhaustive computation has been done. Deterministic would mean it could be if enough computing power existed, but for chess it doesn't.

elcomet 6y ago

Chess is definitely not a solved game. The end game is solved though, when you have only 7 pieces left on the board. See https://en.wikipedia.org/wiki/Endgame_tablebase#Computer_chess https://en.wikipedia.org/wiki/Endgame_tablebase#Computer_che...

mvanaltvorst 6y ago

You can imagine playing chess as a tree. You start with a game state, and every possible move is an edge to a new game state. Unfortunately, the amount of game states grows approximately exponentially (e.g. for every game state there are approximately 40 moves to play, thus every extra move multiplies #(game states) by 40, approximately). This neural engine is a trick so that Stockfish does not have to simulate all 40 moves every game states. The neural net outputs the moves that are most likely to be strong moves, and Stockfish will only consider those moves. Of course, this is a very basic explanation and there are many more optimisations Stockfish uses, though the ultimate goal of almost every optimisation is to reduce the amount of simulation Stockfish has to do.

V-2 6y ago
"This neural engine is a trick so that Stockfish does not have to simulate all 40 moves every game states." This optimization always done by chess engines, it's called pruning (they'd be quite crippled without it). Maybe the neural network component is now in charge of it, but it's not a new thing.
- mvanaltvorst 6y ago
  Of course, I had accumulated all other pruning strategies under the "other optimisations".
bbojan 6y ago
>> The neural net outputs the moves that are most likely to be strong moves, and Stockfish will only consider those moves. I don't think this is correct. According to the article, they are only using the neural network for evaluating the value (strength) of the positions. The search is still the same. I believe Leela works in the manner you described.
blt 6y ago
From the article: > it’s a simple feedforward network with... a single scalar output to give a numerical score for the position, indicating how favourable it is for the player about to move. The search algorithm proposes moves, computes the board state resulting from them, and evaluates each state. This may seem like a trivial distinction, but it's important. The Stockfish method requires knowing the rules of the game; networks that output a move directly do not.

dan-robertson 6y ago

Chess is not a solved game (though I think the stalemate rules make it finite, there are far too many positions). All computer chess programs have to try to determine if positions will be good without playing out all possible ways the game could go. Usually this is some combination of search strategies and scoring positions (the article describes how stockfish scores positions).

V-2 6y ago
I agree it's finite, but why do you think it's specifically owed to the stalemate rule, of all things?
- elcomet 6y ago
  I believe it's the repetition rule that makes the game finite, not the stalemate rule, since number of positions is finite. There is also the 50-move rule of course which limits more drastically the length of a game.
  - V-2 6y ago
    Right, that would make more sense to me. Although it should be stressed that neither threefold repetition nor the 50-move rule work automatically. They need to be claimed by one of the players. If neither player does, the game can go on.
    - jstanley 6y ago
      The 75-move rule does work automatically though, so the game is still finite.
      - V-2 6y ago
        Frankly, I wasn't aware of the 75-move rule! This indeed caps the length of possible games. The threefold repetition rule doesn't have an equivalent (there's no, say, "fivefold repetition" draw that could be enforced despite the players' will), but it's really irrelevant from the perspective of solving chess, because there's no point in analyzing what happens if game goes through the same loop 1, 10 or 100 times. And the 75-move rule sets a hard limit anyway, so you couldn't loop infinitely, even if it mattered.

zone411 6y ago

No, it's not close to being solved. I made a new estimate recently at there are about 8.7E+45 unique positions: https://github.com/lechmazur/ChessCounter https://github.com/lechmazur/ChessCounter. You don't need to analyze all of them to generate the proof but it's still far beyond our computational and storage capacities to solve chess.

altvali 6y ago
For comparison, there are about 10E+49 atoms making up our planet.

aliceryhl 6y ago

No, it is not solved. To solve it, you would need to investigate all possible continuations of the game, all the way until the game ends, but there are so many continuations that this is impossible.

nullc 6y ago
A game could be solved even if its state space was too large to enumerate, for example if you could show that there was some latent structure that let you prove things about large parts of the state space without completely exploring it. This is, for example, why we have a concrete number for the number of legal go positions even though there are far too many to enumerate. https://en.wikipedia.org/wiki/Go_and_mathematics#Legal_positions https://en.wikipedia.org/wiki/Go_and_mathematics#Legal_posit... The rules of chess are so irregular that it seems likely that any latent structure would be tremendously complex, but you never know what some clever new analysis technique will do.

tspduck 6y ago

I have to disagree with the others. Since AlphaZero I think chess is closed to being solved. Technically it is not, but practically is is. Chess is a hard game to solve completely, and I think one reason is that there are many states in chess where there is not one superior move, but only a probable optimal move, in the sense that the game-tree for winning against the move is smaller than other moves. Then the agent/player has to guess what the opponents strategy is given that move, and that depends on the opponent. I plays are truly creative, and its results speak for itself. From wiki: "In AlphaZero's chess match against Stockfish 8 (2016 TCEC world champion), each program was given one minute per move. Stockfish was allocated 64 threads and a hash size of 1 GB,[1] a setting that Stockfish's Tord Romstad later criticized as suboptimal. AlphaZero was trained on chess for a total of nine hours before the match. During the match, AlphaZero ran on a single machine with four application-specific TPUs. In 100 games from the normal starting position, AlphaZero won 25 games as White, won 3 as Black, and drew the remaining 72. In a series of twelve, 100-game matches (of unspecified time or resource constraints) against Stockfish starting from the 12 most popular human openings, AlphaZero won 290, drew 886 and lost 24." source: https://en.wikipedia.org/wiki/AlphaZero#Chess https://en.wikipedia.org/wiki/AlphaZero#Chess

hiq 6y ago
> there are many states in chess where there is not one superior move, but only a probable optimal move I don't think this statement is true given [0], but maybe I understood you wrong. [0]: https://en.wikipedia.org/wiki/Zermelo%27s_theorem_(game_theory) https://en.wikipedia.org/wiki/Zermelo%27s_theorem_(game_theo...
- magicalhippo 6y ago
  I think you misunderstood, and that the point was that in chess, especially during the mid-game phase, there's very often not a single clearly superior move but rather several moves that apparently improves your position by roughly the same amount. The uncertainty is due to the inability to scan the entire sub-tree for each move. The theorem you linked to would only be applicable in certain endgame situations.

hiq 6y ago

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

danielbarla 6y ago

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.

T-hawk 6y ago

You're correct, in that given a board state the right move can always be exhaustively computed, because the game has no randomness or hidden information. But enough computing power doesn't exist on the planet to iterate through all the possible states. The word you're looking for is "deterministic", rather than solved. Solved is usually used to mean the exhaustive computation has been done. Deterministic would mean it could be if enough computing power existed, but for chess it doesn't.