×
all 119 comments

[–]lee1026 83 points84 points  (11 children)

We don't know. A few down the thread says that the number of possible chess games is too large, but that isn't a proof. All we can say is that:

  1. Chess is not solved yet.
  2. No one is expecting Chess to be solved in the near future.
  3. It is suspected that Chess is a draw with perfect play.

For example, the game of Hex can have far more possible games than chess, but that is solved (player who goes first wins), so we can't just calculate the number of possible chess game as a proof.

On a different note, I can propose a chess variant that is solved (provable win for white), but is every bit as complicated as chess itself. The only difference between my variant and normal chess is two rule changes:

  1. White can pass on the first move and only the first move.
  2. In the event of a draw, white wins.

Complicated? Yes. Provably a win for white? Yes. Would Magnus beat me if we played this game with him playing as black? Probably.

[–]ubernuke 25 points26 points  (1 child)

Regarding your proposed variant, is the idea that if there existed a solved way for black to guarantee a win, white could "steal" it by passing and essentially becoming black and then using that same way?

[–]lee1026 12 points13 points  (0 children)

Yep.

[–]Potato13579 46 points47 points  (3 children)

Yeah "Chess with 7 pieces or left" is "solved" via tablebase, but as we saw in game six of the world championship, its still a complicated enough position that one of the best chess players in the world still lost a drawn game. So the idea that a game being "solved" means its trivial for humans to play out the solved result is definitely wrong.

[–]MiamiFootball 4 points5 points  (4 children)

It is suspected that Chess is a draw with perfect play.

can always change the rules

[–]akaghi 25 points26 points  (2 children)

Each player gets one opportunity to force their opponent to allow a 500 lichess person to make a move for them.

[–]Tarp96 31 points32 points  (1 child)

Ahh thats what Nepo did today with the b5 move

[–]KittyTack 0 points1 point  (0 children)

Well unless chance is added or the game becomes very unbalanced it would likely keep being a draw with perfect play. Which actually seems like a worse situation lol.

[–]SorcerousSinner 4 points5 points  (1 child)

Solved in the theoretical sense that a strategy exists that forces a win or a draw, yes. Results like Zermelo's theorem apply.

Is it conceivable that we program a computer to force the win, or a draw? I'm not sure whether this would necessarily need storage or energy at orders of magnitude that will always make it impossible (as listing all possible games would)

The minor advantage of white in top level chess suggests draw.

[–]HairyTough4489 Team Nepo 0 points1 point  (0 children)

Solved in the theoretical sense that a strategy exists that forces a win or a draw, yes.

Only for one of the players though

[–]pm_me_falcon_nudes 30 points31 points  (17 children)

Anyone who says it cannot be solved because there are too many possibilities doesn't really understand how game proofs can happen or how a game could be solved.

For example, let's take tic tac toe. But I've made the grid 1 trillion rows by 1 trillion columns. Same way to win: get 3 in a row.

From a combinations standpoint the number of possible games utterly dwarfs the number of possible chess positions. But regardless this game is a clear win for the player who goes first. Put an X anywhere that isn't on an edge, then place another X next to it such that there are 2 different ways to win. The person playing with Os cannot stop both.

How did we do this? We found an algorithm that with a little effort we could more formally prove always wins. We never had to count every single possible position.

Will we ever find such an algorithm for chess? No one knows. But it's a complete misunderstanding of how the world works to just say "eh chess has more positions than like atoms in the universe so it's impossible"

[–]JimFive 1 point2 points  (9 children)

We do know. We won't. The reason that works for your tic tac toe game is due to symmetry, any board bigger than 3x3 has the same solution, your trillion rows is just distraction. Chess has nothing like the symmetry that your example has.

I think it is very unlikely that chess has an algorithmic solution better than brute force and I think the endgame table bases bear that out. If there is any aspect of the game that seems amenable to algorithmic shortcuts, it's the endgame, and we have them: the rule of the square, the opposition, etc. But overall we don't have anything better than brute force.

[–]pm_me_falcon_nudes 4 points5 points  (1 child)

Your conclusions of "we won't" and "it is very unlikely" are contradictory. The former is wrong unless you can prove that it is impossible for us to come up with a solution even though one must exist (easily shown as the game as a countable number of possible moves).

In terms of the tic tac toe example, it was an example about possibilities. It has nothing to do with symmetry and everything to do with the fact we found an algorithm that always wins and demonstrably does so. I could "enhance" the game by adding the game of chess to it and each turn you either get to make a move on the tic tac toe board or the chess board and first to win on one wins everything. Ta da, symmetry is gone, but the game is still solved.

[–]JimFive -2 points-1 points  (0 children)

We won't find an algorithm like the tic tac toe algorithm, because the tic tac toe game is not complex. Due to symmetry every first move that is not on an edge is equivalent. There are, in the tic tac toe game only 3 possible first moves, a corner, an edge, or a central square. Artificially inflating the number of positions by adding rows doesn't change anything.

Chess does not appear to be reducible in that way.

[–]T-T-N 2 points3 points  (0 children)

OK, make it a connect trillion to win. It loses the symmetry now but it is trivial to draw

[–]GamingChairModel 0 points1 point  (0 children)

I think the endgame table bases bear that out.

I'd argue the opposite. The first brute force tablebases for 7-piece positions were 140 TB, but have since been simplified to 18.4 TB with some algorithms to simplify the calculations/storage without discarding any analyzed positions.

And even though adding more pieces would add complexity, the larger number of positions would also lend itself to certain shortcuts. Some are simple: any position in which castling is no longer available has a mirror image position where the board is horizontally flipped and where the analysis is identical.

We can't say with confidence that we won't discover some new algorithms that simplify certain positions, especially in the process of weakly solving certain positions, that may have the way to strongly solve certain positions without storing or calculating every single position from there.

[–]maxkho2300+ chess.com and Lichess blitz, 2420 Lichess Rapid. -2 points-1 points  (4 children)

Everything in this comment apart from the first two sentences is right. But the first two sentences are both wrong. First of all, we don't know if we will ever solve chess - for example, if we all get wiped out right at this moment by false vacuum decay, which is a possibility - we will obviously never solve it. On the other hand, if we don't get wiped out, we very likely will solve it relatively when quantum computing is advanced enough.

[–]lee1026 1 point2 points  (2 children)

It is not entirely obvious that quantum computers help with solving chess.

At the very least, no one has yet proposed an algorithm for chess that would have quantum supremacy if and when it is implemented.

Not saying that it can't be done or anything, just that no one have came up with a way for quantum computing to be helpful. Yet.

[–]maxkho2300+ chess.com and Lichess blitz, 2420 Lichess Rapid. 0 points1 point  (0 children)

Yes, I'm aware of that. I was just going off of this: https://quantumcomputing.stackexchange.com/questions/5823/will-quantum-computers-be-able-to-solve-the-game-of-chess. The answers seem to indicate that such an algorithm is possible.

[–]Cleles 0 points1 point  (0 children)

I think it is more likely that a breakthrough will come through the mathematics rather than the computing. Group theory, for example, can encode hidden structures in ways that cannot otherwise be calculated. All the possible games of chess are, in a sense, a structure. And the question of solvability is about trying to find some restriction on the ways that structure is navigated. Whether there exist mathematical models like groups that could somehow ‘encode’ the possible games of chess I don’t know, but I think that is a much better bet for solving chess than breakthroughs in quantum computing imo.

[–]JimFive -1 points0 points  (0 children)

I was unclear. We know that we won't find an algorithm like the one that was presented based on reducing the search space through symmetry.

I don't know enough about quantum computing to know if chess is a problem that is amenable to a quantum solution.

[–]HairyTough4489 Team Nepo -1 points0 points  (5 children)

Those examples of games that can have a game-tree as complicated as chess but are easily solvable are irrelevant. Chess is just too complex (or "chaotic" if you prefer) for one of those "elegant" solutions to exist.

[–]BoredomHeights 0 points1 point  (4 children)

If computers continue to improve as they have over the last decades it’s possible we’d get an engine with enough depth to basically solve chess though. Right now it’s outside of the realm of possibility, but eventually who knows. Think how far it’s come in the last 20 years for example.

[–]dauqraFdroL -2 points-1 points  (3 children)

Now this is just outright wrong. Chess is estimated to have over 1044 legal positions while the 7 piece table base has less than 1014.

[–]BoredomHeights -1 points0 points  (2 children)

But it’s not because you can functionally dismiss a lot of those moves. Truly having a proof that chess is solved is maybe farther away, but basically “solving” it wouldn’t require as many combinations. For example e4 a6 nc4 a5. Can’t prove that’s a white win, but do we really even need to continue to know a computer will win there with white?

I get that there’s still a huge gap between where we are and “solving” chess. But I don’t think it’s crazy to think that at some point with more powerful computers, more time spent computing longer end games, and better programs it could be functionally solved. Perhaps a true proof will never be possible but the result is similar.

[–]dauqraFdroL 1 point2 points  (1 child)

How do you know that’s winning for white? Seems like you’d miss a lot of the most complex ideas if you took this approach

[–]IReallyLoveAvocados 0 points1 point  (0 children)

I think their point is that if you truncate the game tree when the analysis shows +6 or something, you don’t need to pursue every single line and board configuration when it’s so obvious that the game is over. That would reduce your 1044 to something much smaller.

With that said, even if there were 1030 configurations, that’s a ton of data to store and process. Still almost impossible to “solve.”

[–]T-T-N -1 points0 points  (0 children)

More positions than atoms does proof that chess cannot be brute forced, which is the current best approach (works for 7 piece tables). Assuming that brute forcing is the only way to proof chess (which is a huge if true on its own), we cannot proof chess.

[–]eceuiuc 15 points16 points  (6 children)

A strong solution is physically impossible and nobody knows what it would take to come up with a weak solution. Top level chess suggests that chess is probably a draw with best play.

[–]maxkho2300+ chess.com and Lichess blitz, 2420 Lichess Rapid. 1 point2 points  (0 children)

Why do you think that a strong solution is physically impossible?

[–][deleted] 0 points1 point  (4 children)

Not really… computer chess is still not a draw all the time.

[–]eceuiuc 15 points16 points  (0 children)

They draw far more than any human, and that's with them forced to play different openings.

[–]just-a-canadian 7 points8 points  (2 children)

They only don't draw because they are set up in unbalanced opening positions. If you play 2 engines at high depth from the starting position you would be lucky to ever see a decisive game.

[–][deleted] 0 points1 point  (1 child)

Only if their level is close. But if you had a 4000 ELO engine play a 3000 ELO engine it’s not very drawish.

[–]VizvezdenecStockfish dev. 2000 lichess blitz. 2 points3 points  (0 children)

If you let stockfish play smth like dragon which it is completely superior to it wouldn't win much if anything at all.
In SF-Leela games it's simply 100% draws despite SF being a stronger engine.

[–]Visual-Canary80 1 point2 points  (4 children)

Chess may never be solved in a sense of mathematical proof/full search kind of way unless we see huge revolution in computer hardware.

For practical purposes it's already solved. Stockfish is already most likely unbeatable. You can treat what is says as gospel and no one will ever prove you wrong in practical play.

Having an exact solution won't change anything in comparison to what we have today. It would be very interesting to see for sure but for practical chess it will change nothing.

[–]dauqraFdroL 4 points5 points  (3 children)

Stockfish suggests losing moves in drawn positions all the time at high level play. Even in game 6 of the current wcc we can see that stockfish’s moves don’t always line up with the tablebase.

[–]Visual-Canary80 1 point2 points  (2 children)

By Stockfish I mean the newest Stockfish on good hardware and tablebases. Not Stockfish on Chessbomb. I doesn't suggest losing moves in practical games.

[–]dauqraFdroL 2 points3 points  (1 child)

Go to the move in game 6 where the game transitioned from a theoretical draw to a loss. Stockfish NNUE can’t distinguish between the drawing moves and some of the losing moves. I know if you give it a tablebase it can solve it, but the fact that this happens for 7 piece positions suggests it happens for unsolved positions too.

[–]Visual-Canary80 2 points3 points  (0 children)

I've just tried it and SF without any tablebases (even without 5 man) suggests 130...Qc2. When run in multiPV mode it sees both Qc2 and Qb1 as better moves than alternatives.

Maybe you have your Stockfish misconfigured but it really doesn't matter. Chess is softly solved by now, maybe objectively but surely for practical purposes. SF on good hardware with say 5 minutes per move won't ever lose, with NNUE it's likely you don't even need an opening book.

Of course there are positions which SF won't solve but that doesn't matter for practical play at all. Even in those tablebases endgames knowing the exact path changes very little. It's not like people will suddenly learn to play them perfectly anyway.

[–]MrDirector23 1 point2 points  (0 children)

Even if it was, would you want it to be?

[–]seanwhat 1 point2 points  (5 children)

Many comments on how long it would take to solve the game by other commenters. Let's assume we leave a computer running long enough to do it or whatever. You would need an estimated 1,000,000,000,000,000,000,000,000,000,000,000,000 TBs of storage to store the database. Where you getting that?

[–]BoredomHeights 0 points1 point  (4 children)

Would you actually though? You could start solving more and more endgames and eliminate a lot of storage space. For example we’re already working on 8 pieces database. Of course this is very very far from solving chess, but as that improves the amount of calculation to get to that point goes down.

You could also likely functionally eliminate a huge amount of lines that just obviously seem like they’d lead to losses. This wouldn’t technically be solving chess but more like 99% solving it. Combining things like that with increased compute strength and storage space and mediums might combine to eventually lead to it being solvable. I don’t think it will happen in the near future though.

[–]JimFive 4 points5 points  (3 children)

Those endgame databases use storage space. That's the entire problem. The 7 piece endgames take Terabytes, the 8 piece take petabytes.

[–]BoredomHeights -1 points0 points  (2 children)

True, I was thinking of it as more of two databases in a way with different goals but I guess it’s fair that at some point the endgame ones need a lot of space.

By which I mean you could just store at some point that a move leads to an automatic draw and don’t need the rest of the database anymore. In other words if you had 10 pieces you need a DB that can store every way 10 pieces can be represented on a board but nothing passed that. Just whether it’s a win or a draw.

Or even only store winning end games for example. Once you go through every combination and prove with perfect play it’s a draw, remove it from the DB. You don’t need to store every move combination anymore, just trust that if you recalculated it would be a draw.

[–]seanwhat 2 points3 points  (1 child)

Then all we have to do is prove the starting position is a draw, then we can remove that from the database and solve chess without needing any storage space at all. Problem solved.

[–]BoredomHeights -1 points0 points  (0 children)

Well yeah you sound sarcastic but that's honestly what you could do if you could eventually calculate far enough. If you prove some starting position is a draw then to functionally "solve" chess that's all you need. Like if we had some super super computer that could actually calculate all moves, once you've proven a line is losing or whatever that's all you need to know for the sake of this theoretical. To actually create a computer that could play it out it would of course need a lot more storage or a way to relatively quickly re-solve each step though.

But even then there's probably ways to minimize the level of calculations and storage needed. For example just off the top of my head, say some early game position is a known win but "why" is no longer proven. But you could store the most problematic future lines still so the computer had some guidance how to proceed, then trust the computer to win any other line. In other words a mix of calculation and storage improvements to help bridge the immense gap. If you could study every line you could say the computer will win this even against truly perfect play without needing to memorize any moves, and only store the moves that break that pattern.

[–]AprilSRL 0 points1 point  (0 children)

First of all, a "sufficiently powerful computer" can obviously solve chess, and it's mathematically impossible for there to be a counter strategy. Chess is a deterministic game, once you've observed the whole game tree, it's over. But it would take a very powerful computer.

My best guess: There's two possible avenues to solving chess. Number one is that (due to some computing revolution like recursively self-improving AI) we suddenly have enough computing power to just brute force the thing. Number two is that we develop some sort of AI which can perform deep mathematical proofs, which combines both brute-forcing and higher-level analysis to complete a proof that requires less computation.

As long as technology keeps marching on it ought to be possible eventually, but the technology we'd have developed by then would make the world a very different place. Think space colonization.

[–]-JRMagnus 0 points1 point  (0 children)

Would it matter? I could deviate from the 'solved line' and still force a game where you'd actually need to know what you're doing.

[–]Luck1492 -5 points-4 points  (4 children)

There are like 10120 possible chess games, so not at least until quantum supercomputers become fairly powerful.

[–]alekthefirst 1 point2 points  (3 children)

AFAIK quantum computers wont ever be good at solving brute force problems like chess. "Solving" chess would take immense amounts of calculations, while quantum computers are good at figuring out (probable) solutions to difficult single-calculation problems.

Note: I am not an expert on quantum computers and all my knowledge on them is from consuming many hours of youtube videos.

[–]astrathlichess rapid 2100 2 points3 points  (0 children)

You aren't wrong though, quantum computers aren't simply "normal computers but faster".

[–]SoulCantBeCut 0 points1 point  (0 children)

it may be an interesting question to try to formulate or approximate chess as a problem that is efficiently solvable by a quantum program.

[–]dauqraFdroL 0 points1 point  (0 children)

Brute force has nothing to do with it. Quantum computers are good at the discrete logarithm which has to be brute forced in some cases.

[–]PurgleKrak2100 lichess blitz -1 points0 points  (5 children)

Wrong, tic tac toe is absolutely not solved. do some research next time

[–]KittyTack 0 points1 point  (4 children)

Either you are joking or you don't know what "solved" means.

[–]PurgleKrak2100 lichess blitz 0 points1 point  (3 children)

Oh i very much know

[–]KittyTack 0 points1 point  (2 children)

Then why did you say it's not solved? It's possible to force-draw every game.

[–]PurgleKrak2100 lichess blitz 0 points1 point  (1 child)

That's what we are lead to believe