Claude Shannon in a 1950 paper "Programming a Computer for Playing Chess" (as referenced on Wikipedia):

With chess it is possible, in principle, to play a perfect game or construct a machine to do so as follows: One considers in a given position all possible moves, then all moves for the opponent, etc., to the end of the game (in each variation). The end must occur, by the rules of the games after a finite number of moves (remembering the 50 move drawing rule). Each of these variations ends in win, loss or draw. By working backward from the end one can determine whether there is a forced win, the position is a draw or is lost. It is easy to show, however, even with the high computing speed available in electronic calculators this computation is impractical. In typical chess positions there will be of the order of 30 legal moves. The number holds fairly constant until the game is nearly finished as shown ... by De Groot, who averaged the number of legal moves in a large number of master games. Thus a move for White and then one for Black gives about 10^3 possibilities. A typical game lasts about 40 moves to resignation of one party. This is conservative for our calculation since the machine would calculate out to checkmate, not resignation. However, even at this figure there will be 10^120 variations to be calculated from the initial position. A machine operating at the rate of one variation per micro-second would require over 10^90 years to calculate the first move!

My idea is essentially to take a very strong chess AI and "patch" it to determine moves that will at least force a draw, creating a coded "solution". The algorithm for generating the program (as the starting player) would be something like this:

Code:

```
Take your AI, and have it play against every possible move the
opponent could make. (*)
Follow the 50-turn stalemate rule (no captures or pawn moves in 50 turns
results in stalemate), apply some kind of algorithms to reduce the number of
moves you have to compute in such situations.
If the game reaches a point where your AI has been checkmated:
While the AI is still being checkmated:
Retract one move.
Determine by brute force if any next move for your AI can lead to a
situation where it will not be checkmated.
If yes:
Save any game state where the AI must make a move contrary to
its coding, along with any moves it must make.
(*) This is essentially having the opponent brute force your AI.
Yes, this results in many, many possibilities.
```

After this, you'd have the AI play the game, but check as it plays whether it has reached a move it needs to play with alternate instructions, and if so, it would make the move indicated.

There are two main difficulties I see - one, there are a lot of computations that need to be done for the opponent to brute force the AI. However, this is many less than if you were to use two brute force players - the AI only has one move it makes on each turn (until it gets beaten, but more on that later), and many moves made by the opponent are likely to lead to it getting beaten early on.

My math is very rough here, but unless it's significant, I don't care. Assuming a game lasts on average 40 moves, and on each of the opponent's turns they have 30 available moves, this means we need to consider 30^(40/2), or about 3.5 x 10^29 variations to end-game. The number of moves would be the sum of a geometric series, something like (1-30^21)/(1-20) or 5.5 x 10^29 moves. That's a lot of moves, but also a lot less than 10^120. Using the given 10^90 years to compute 10^120 variations, or 10^30 moves/year, if we computed 1000 moves per second, this part of the process would be done in less than a year (though of course, needing to do calculations for the AI limits the number of moves we can compute per second, but perhaps not by that much with enough processing power)

Second, once the opponent has beaten the AI, it is possible that the AI must step back an unfeasable number of moves, for example, back to the start of the game. One way to try to get around this is to make a defensive AI, or perhaps have the first n moves be played defensively, to avoid needing to retract too far when trying to avoid a checkmate. Someone who knows more about chess than me might be able to shed some light on this. Perhaps with a very good AI, you would never end up in such a situation?

How many steps back would be likely be unfeasable, i.e. how many steps back before the brute-forcing of a way out takes too much time?

Also, it is possible (though I don't know whether it's probable) that the number of alternate solutions that would need to be stored is too large to realistically store, or realistically search through in the resulting program.

One should also consider that the solution needs to be made twice, once for white and once for black.

Considering all this, do you think coming up with a program that can guaruntee a draw in chess is feasable?