3 ms·

>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 ago
  Well, 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 ago
      Right, 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.