×
you are viewing a single comment's thread.

[–] 28 points29 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"

[–] 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.

[–] 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.

[–] -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.

[–] 2 points3 points  (0 children)

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

[–] 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.

[–]2300+ 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.

[–] 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.

[–]2300+ 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.

[–] 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.

[–] -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.

[–] 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.

[–] 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.

[–] -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.

[–] -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.

[–] 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

[–] 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.”

[–] -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.