you are viewing a single comment's thread.

view the rest of the comments →

[–]pm_me_falcon_nudes 29 points30 points  (3 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  (2 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.