See https://en.wikipedia.org/wiki/Endgame_tablebase#Computer_che...
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.
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.
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.
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.
> 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.
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.
There is also the 50-move rule of course which limits more drastically the length of a game.
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.
There is exactly such a rule. See the FIDE Laws of Chess [0], rule 9.6.1.
Kind of funny that your hypothetical example was exactly reality in this case.
It's a typical mistake to equate chess draws with a stalemate, possibly due to the broader, idiomatic meaning of "stalemate" in common speech.
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.
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_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.
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."
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 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_theo...
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.
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.
It says that if the game cannot end in a draw, then one of the two players must have a winning strategy (i.e. force a win).
It made me think it didn't apply in situations where the other player could force a draw.
Reading the linked article[1] though made it more clear what it's about, and I agree with what you said.
[1]: http://www.math.harvard.edu/~elkies/FS23j.03/zermelo.pdf
That uncertainty is specifically why chess is unsolved.
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.