But I'm getting ahead of the story.
The first approach that's taken in AI are what are called "weak methods": essentially, brute-force search, appropriately tailored, but without regarding to specific knowledge of the domain. This is easy for simple games like Tic-Tac-Toe, which only has 765 different possible board configurations. It's easy to develop a perfect strategy for the game, as any child discovers. But checkers has roughly 5E18 (5 billion billion) possible configurations, which makes it much more difficult to find a brute-force solution. (More on this later.)
For more complicated games like this, most brute-force machines do a form of look-ahead search: you compute n moves into the future, keeping in mind the alternating nature of the game, rate all of the board positions left at that point, and then choose the move which gives you the best chance of winning. Obviously, the quality of your evaluation metric is critical, as is the value of n. Larger n gives you better information, but at exponential cost.
In two-player games like chess and checkers, experts develop pre-determined strategies for the beginning of games (called "openings") and ends of games (called "endgames"). There are fewer states in these to explore than the vast middle-of-game state space, so that's where a lot of mid-level research goes into.
Anyways ... back to the story.
Schaeffer builds what he thinks is a great program ... and manages to talk some folks into letting it play in the U.S. checkers championship in 1990 against master-level players. He ends up coming in second place, behind the reigning world champion. The world champion agrees to play the machine in a master-level match ... and the world sits up and takes notice.
Go back to the link above and look for the story of the 1994 match between the man and machine, and you'll get a taste of the human pathos, the intrigue, the glory, the ignominy, the triumph and tragedy. Listening to Schaeffer describe it was utterly incredible; you can see what this quest has cost him.
Ever since then, Schaeffer has been working on making the machine better ... in part with better algorithms, but largely by precomputing more and more openings and endgames. Now, 18 years later, the quest is almost over.
In 3-5 months, Schaeffer expects to announce that Chinook is complete. That is, their team of researchers and computers will have fully explored the 5E18 state space of checkers, and found the optimal move to make in every situation. They already have half the proof done, for Black (the player who moves first). That is, if Chinook goes first, it can't lose: it'll either draw (if you play it perfectly), or it might win (if you make a mistake), but you'll never beat it. They're still finishing the details on what happens when Chinook plays White (the player who moves second).
That is utterly amazing. It's taken 18 years to explore the state space fully, but it's almost done. And a milestone in computer science will have been reached.