Checkers and Computers — From Samuel's Program to Solving the Game

Checkers: A Landmark in AI History

The history of computers playing checkers is the history of artificial intelligence itself. Checkers was the first game where a computer program learned to improve, the first complex game where a computer challenged a world champion, and the first non-trivial game to be completely solved.

Arthur Samuel’s Checkers Program (1959)

The Birth of Machine Learning

In 1959, Arthur Samuel at IBM created a checkers program that is widely credited as the first example of machine learning. His program:

• Evaluated board positions using a scoring function
• Learned from experience by adjusting its evaluation based on wins and losses
• Played itself thousands of times to improve
• Beat several amateur players — remarkable for the era

Samuel’s work introduced concepts that remain central to AI:

• Evaluation functions — assigning numerical scores to game positions
• Self-play — a program learning by playing against itself
• Feature weights — adjusting the importance of different factors through experience

“Machine Learning”

Samuel coined the term “machine learning” to describe his work. The term stuck and now defines an entire field of computer science.

Chinook: The Champion Challenger

Origins (1989)

Jonathan Schaeffer, a professor at the University of Alberta, began developing Chinook in 1989 with the goal of creating a world-championship-level checkers program.

Chinook used:

• Alpha-beta search — exploring millions of game positions per second
• Endgame databases — perfect play for all positions with 8 or fewer pieces
• Opening book — a library of studied opening positions
• Evaluation function — a hand-tuned function assessing position, material, and king advantage

Chinook vs. Tinsley (1992)

In 1992, Chinook challenged Marion Tinsley, the greatest human player in history, for the world championship. The result:

• Tinsley won 4, Chinook won 2, 33 draws
• Tinsley retained the title

This was a watershed moment — the first time a computer seriously challenged the world champion in checkers.

The 1994 Rematch

In 1994, an improved Chinook met Tinsley again. After 6 drawn games, Tinsley withdrew due to health issues (he was later diagnosed with cancer and passed away in 1995).

Chinook claimed the vacant title — the first computer to hold a world championship in a major board game.

Solving Checkers (2007)

The 18-Year Computation

After the Tinsley matches, Schaeffer’s team shifted focus from playing strength to solving checkers — proving the mathematical result of perfect play.

The project required:

• 39 trillion positions evaluated
• 18 years of computation (1989–2007)
• Hundreds of computers working in parallel
• Sophisticated algorithms to prune the search space

The Result

In 2007, the team announced: with perfect play from both sides, checkers is a draw.

This made checkers the most complex game ever solved — a title it still holds. The proof was published in the journal Science.

What “Solved” Means

• Every possible starting position has a known outcome (win, loss, or draw with perfect play)
• A perfect player can guarantee a draw against any opponent
• No strategy exists that can beat a perfect player

Significance

The solving of checkers was a landmark in:

• Artificial intelligence — demonstrating that complex games could be mathematically resolved
• Game theory — providing a complete game tree for an ancient game
• Computer science — showcasing distributed computing and algorithmic innovation

After the Solution

Impact on Competitive Play

The solving of checkers did not end competitive play:

• Humans don’t play perfectly — so human vs. human games are still interesting
• The three-move ballot system ensures variety in openings
• Endgame databases improved human understanding of the game

Modern AI Approaches

Since 2007, AI has continued to evolve:

• Neural networks have been applied to checkers (following the success of AlphaZero in chess)
• Deep learning approaches can play strong checkers without being explicitly programmed with strategies
• Checkers serves as a benchmark for testing new AI techniques

The Legacy

Checkers holds a unique place in the history of artificial intelligence:

From the first machine learning program to the complete mathematical solution of a game played for thousands of years — checkers has been at the frontier of AI for over 60 years.