In reply to:

From that link I find it cool that finding the next "safe" state from a given game state can be done in O(n) time



In a finite game that doesn't involve luck or information that's hidden from either player, there is always a safe state on every move, unless it is possible to tie. The game just becomes one giant math puzzle. Either player A is in a position to force a win or player B is in a position to force a win, or in a game with possible ties both players could be in a postion to force a tie.

In that pearls game the first player is in a winning position and able to force a win, but if you don't play it right then you put yourself in a losing position and the computer forces a win. Pearls is a theoretical win for player A [EDIT: Pearls 1 is. It looks like Pearls 2 is a win for player B.] Tic Tac Toe is a theoretical tie - both players can force a tie every game, regardless of who goes first. Chess is finite and doesn't involve luck or hidden information (eg. scrabble), so it is possible to solve the game of chess, just as someone solved the game of Nim. As I understand it, someone found a winning strategy for the game of Nim a hundred years ago more or less by chance and observation, and I could be wrong but I think it is still not fully understood why it works like it does. Perhaps it is, but I certainly don't understand it.

Chess and Checkers have too many possibilities to be solved by brute force, like you did with Pearls, but perhaps one day someone will stumble upon a winning (or drawing) strategy for Chess. Maybe that person won't tell anyone, and he'll play in international tournaments and never be defeated and win millions of dollars and then write AI programs that take over the world while people clone Secretariat and Seattle Slew and then all the nations of the world set off their nuclear payloads all at once and just finally get it over with. who knows....

I suppose my point is that in any game state, always one of the two players is in an indefensable position.