Knuth's first large program

was a tic-tac-toe that learned to play by remembering the relative desirability or undesirability of each position that it had ever encountered. The hardest part, as Knuth writes, was figuring out how to keep one digit of memory for each possible configuration of the board. The machine had just 2000 words of memory, each 10 digits long, plus a sign bit.

N ECPIN O XETOS!!

Also, that's stupid because it is very easy to make an optimal Tic-tac-toe AI. It just needs to block its opponent's attempts at lines and start in the center.