Disclaimer: Very dumbed down explanation incoming :) So if there is any CS guys out there, please cut me some slack.

What you describe is roughly how AI in computer games are implemented these days as far as I know. Again very roughly, there is a set of states, rules to transition between those states, and a "value" for each state; and then the computer uses a limited set of computational resources to search the state space to find a transition that results in the maximum value. One important thing to get this general design to work is to assign the values to states correctly, and since the rules of, say, a RTS game are extremely complex to represent and analyze in a formal manner, this process is often driven by developers pulling those values out of their ass :) Cheats and unfair advantages etc are then introduced to improve the situation during gameplay testing.

With a game like chess where the states (i.e., all possible positions and combination of the pieces on the board) and rules are well-defined and could be formalized, you could compute concrete values for each and every move, considering all future turns of the game, and save this in a data structure in the memory. Then all the computer needs to do is look at the current state, find paths from it to a winning state, pick the one with the highest probability of being successful (there may not be a 100% winning path, because the human player's future moves will affect the game state as well, so things are probabilistic), and execute it.

This means the computer can *in theory* play perfectly. But computers work with limited resources: that data structure would be huge, and searching the structure for the optimal move would take a loooooong time, etc. In short, this approach is computationally not feasible for chess. So optimizations and compromises are made, like limiting the look-ahead so that all this computation is made only considering the next few turns, or introducing time limits for the search (e.g., computer has to decide in 5 seconds max).

But implementing something even simpler with a small number of states in this way is totally possible, for example unbeatable tick-tock-toe is a common programming exercise for university AI classes.

Yeah, honestly before I considered this approach I had no idea how you'd program a Chess AI, and it seemed something of a miracle.

Also 3 moves in advance would be probably too many. If both sides still had all 16 pieces (with the opponent's pieces/move also considered), then:

1 move has 256 potential moves,
2 moves has 65536 potential moves,
3 moves has 16.7 million moves
4 moves has 4 Billion moves...
Etc.

That means on such a system like the atari with 1Mhz and you're likely waiting only a few seconds per move, it could consider no more than 2 moves in a timely manner. More advanced computers like the ones running Windows back when Chessmaster was introduced usually considered 3 moves, assuming you give it 2 minutes per move. (It was also curious to see a little window that had a peek at what move the AI was considering at that time and how far in it was considering).

Hmm actually the move count is probably much higher, as some pieces can move across the whole board, so rooks have up to 14 combinations, bishops have 14, queens have 28 I think, etc. So the board might be considered as...

(pawns 4, king 8, castling 2, knight 8) a whopping 78 (ignoring more advanced moves), so now the numbers become:

1 move has 6241 potential moves
2 moves has 38 million potential moves
3 moves has 243 billion potential moves
4 moves has 15+e14 potential moves

Wow... I remember reading about the first 10 moves in chess had this ginormous amount of combinations, but actually considering what engine is required to make it puts that more heavily into light. Naturally all this becomes super easy for the if you drop the time element, specifically if quantum computers become a thing; What was just a limit in time quickly becomes the unbeatable computer that instantly knows the best path all the time :P



As for Tick-Tack-Toe... Yeah I already figured the same thing with that game. Considering there is only 3[sup]9[/sup] states (about 20k), sorting all states you can either always tie or win.