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?
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. 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.
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.
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.
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.
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.
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.
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 . 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.
> 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.
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.
> 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.
>> 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.
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).
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.
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.
OK, so that's not a stalemate. A stalemate is a situation in which one of the players has no legal moves (but isn't in check, which would be checkmate).
It's a typical mistake to equate chess draws with a stalemate, possibly due to the broader, idiomatic meaning of "stalemate" in common speech.
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.
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.
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.
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.
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."
You're making a jump from "AlphaZero plays better than the best programs of its time" to "chess is close to being solved" but that's not justified without much more evidence. There are still a lot of improvements and new ideas added to the top programs and even if they reach a plateau, you'd have to show that increasing time per move 100x doesn't result in a significant improvement in playing strength. We don't know what would be the Elo difference between a 32-piece tablebase and the best existing program but I don't think anybody would bet that it's less than 200 Elo.
Here is a graph of Stockfish's progress since the end of 2015: https://camo.githubusercontent.com/f169f774996346ad146f96f74.... Self-play exaggerates strength differences but it's been a very good rate of progress, even without hardware improvements in the meantime.
A solved game is categorically different from merely teaching a machine to be better at it than humans are presently.
Cepheus [0] is approximately a solution to Heads-Up (two player) Limit (ie the amount you can bet is specified in the game, you don't get to just bet arbitrary money) Texas Hold 'em poker.
In contrast Libratus is an AI that plays Heads-Up No Limit Hold 'em very well against humans.
You can examine the Cepheus strategy for yourself, if you could memorize it (it's too complicated) and were capable of making truly random decisions (Poker is a game of chance and so your strategy needs random action) you could reproduce it and be exactly as good at the game as Cepheus is. You can examine individual strategy elements and reason about them. For example if Cepheus gets an 8 and a 3 and you open with a bet, it will call your bet if they're the same suit, otherwise it will fold. On the other hand if those suited cards were an 8 and a Queen, it would raise a bit more than nine times out of ten.
You can't do anything about it (you might be thinking surely knowing that e.g. Cepheus folds 8-3 off here is valuable so I can benefit from that, er, no, "hiding" that by sometimes playing it loses more money than Cepheus gives up by folding it that's why this is a perfect strategy), if playing Cepheus, even with an incrementally "more" approximate solution you're not going to win a significant amount of money reliably in reasonable time, that's why it's approximately solved.
But Libratus isn't like that, it's playing some strategy that we know beat world class human players, but a further incrementally better AI might crush Libratus just as badly.
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.
> there's very often not a single clearly superior move
Maybe it's not clear to human players or current engines, but that does not mean it doesn't exist, and indeed the theorem mentioned above states that at least one player has an optimal strategy (either forcing a draw or winning). Obviously, that does not necessarily mean that we'll ever be able to design an engine that can compute this strategy in a reasonable time.
I just think that OP meant something other than the usual definition of "solved", maybe they meant that engines are plateauing, but as others have pointed out, there is also little evidence for that for now.
Indeed, I was just being a bit pedantic by pointing it out.
edit: so to make it crystal clear, I didn't try to argue chess was solved, just to point out why I think that theorem doesn't really apply to most of chess.
The same could be argued for tic-tac-toe (which is obviously and trivially solved). There are many positions in which there's more than one move that is perfectly playable.
