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.

>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.

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.