4 ms·
Out of curiosity, is chess solvable yet by computers? Meaning, is it possible to simply brute force every possible legal game up to n moves and determine all th
by bane 12y ago
Out of curiosity, is chess solvable yet by computers? Meaning, is it possible to simply brute force every possible legal game up to n moves and determine all the winning and losing move sets? What's this number look like theoretically?
(I'm sure in the general sense games with a very large n aren't as I suppose a game could be played in perpetuity)
- patrickmay 12y agoNo, it is not yet possible to brute force all chess games. The largest extant endgame database has full solutions for seven pieces on the board. Once you get to that point, chess is solved. ;-)
- rmrfrmrf 12y agoJust to clarify what you alluded to, it's theoretically possible for chess to be solved, and progress is being made slowly, but surely (it took around 7 years for chess to be solved up to 7 pieces). Of course, with each additional piece comes an exponentially larger set of positions, so progress from 7 to 8 pieces should take much longer assuming there aren't any massive breakthroughs in computing speed.
- ThrustVectoring 12y ago>every possible legal game up to n moves That's easily above 10^30 positions. 10^30 is a very low lower bound, too. So, uh, no.
- bane 12y agoWell, that's why I specified n moves. Entire games can take 2 moves. So for n=2, it's probably pretty easily solvable. Probably for n=3 and maybe 4 as well. It's also not strictly exponential as n increases, pieces are removed from the board for example restricting the number of legal moves as the game progresses. There's probably interesting solvable subsets up to large numbers of n, like maximum captures as the game progresses, or all games where there are zero captures or some such. It's not a simple matter of calculating every possible theoretical legal or non-legal state of the board with all the pieces.
- pbhjpbhj 12y ago>as n increases, pieces are removed from the board for example restricting the number of legal moves // As the pawns are moved to make way for the back row the number of legal moves increases very quickly. For example if white plays d2-d3 then it frees the King, Queen and Bishop to move; 2 possible moves are removed and 8 are added.
- bane 12y agoRight, but eventually the number of possible next moves starts to drop. A game with a King, Queen, and Two Bishops has more possible valid next moves than a game with just a King and a Bishop left.
- fgp 12y agoAFAIK, the most complex board game solved to date is checkers http://en.wikipedia.org/wiki/Chinook_(draughts_player) http://en.wikipedia.org/wiki/Chinook_(draughts_player). Chess is also solvable, but researchers are far from solving it yet
- szierk 12y agoAn important distinction here is that checkers is also only weakly solved (Connect Four, by contrast, is strongly solved). https://en.wikipedia.org/wiki/Solved_game https://en.wikipedia.org/wiki/Solved_game This means that Chinook can play perfectly from the start position against any set of opposing moves, but if you play a move on Chinook's side that it wouldn't play for itself, the resulting position is probably not solved by Chinook. An arbitrary position is in fact very unlikely to have been solved.