A133046 - Starting from the standard 12 against 12 starting position in checkers...
A133046 - Starting from the standard 12 against 12 starting position in checkers, the sequence gives the number of unique move sequences after n moves
1, 7, 49, 302, 1469, 7361, 36768, 179740, 845931, 3963680, ...
A game tree is a tree that can be traversed downward to follow a game's progression. The root node represents the starting game condition, and it has a child for every one of the first player's possible legal moves. Tic-tac-toe has a pretty simple game tree (the subject of a recent XKCD comic) -- its game tree has 26,830 leaf nodes.
Checkers (known as "draughts" outside of the USA) is a game played on a board similar to chess, but with much simpler rules. But even those simple rules yield a complex game: the game tree has approximately 1031 leaf nodes. After each player has made two moves, there are already 1,469 different possibilities (a(4) in the above sequence).
Even with that many leaf nodes, however, Checkers was completely solved just a few years ago. The Chinook project knows every possible game, and can thus make the perfect move. Note that despite the fact that computer Chess players can reliably beat even the best humans, Chess is far from solved. In fact, there's some debate about whether solving Chess is even possible.
Related: A090224 - Number of possible positions for n men on a standard 7 X 6 board of Connect-Four
