Samuel's Checkers Program: The True Starting Point of Machine Learning

A Forgotten Milestone

When we talk about deep learning, large language models, and reinforcement learning, few people think back to where it all began. As early as the 1950s, IBM researcher Arthur Samuel wrote a program that could play Checkers, and it was this program that first demonstrated to the world that machines could "learn" — rather than merely execute pre-written instructions.

To understand how groundbreaking this work was, we need to return to the technological context of the time. Samuel initially developed this program on the IBM 701 computer — IBM's first commercial scientific computer, released in 1952, with only about 4KB of main memory (Williams tube storage) and a processing speed of approximately 14,000 floating-point operations per second. The program was later migrated to the IBM 704, which had about 32KB of memory — still negligible compared to any modern smartphone. Achieving "learning" capability under such hardware constraints is a testament to extraordinary engineering wisdom and algorithmic elegance.

Samuel himself is regarded as one of the founding figures of the machine learning field. In his 1959 paper, he first coined the term "machine learning," defining it as "the field of study that gives computers the ability to learn without being explicitly programmed." This definition is still widely cited more than half a century later. Notably, this definition implied a profound philosophical shift: computers were no longer mere "instruction executors" but possessed a certain potential for autonomous knowledge acquisition. This idea sparked widespread academic discussion at the time and was even questioned by some mathematicians and logicians.

A Self-Evolving Program

What made Samuel's checkers program revolutionary was that it didn't simply enumerate all possible moves. Under the hardware conditions of the 1950s, where memory was measured in kilobytes, exhaustively searching all possible board positions was impractical.

Here it's important to understand the game complexity of checkers. English checkers (8×8 board) has approximately 5×10²⁰ legal positions, with a game-tree complexity of about 10³¹. While this is much smaller than chess (approximately 10⁴⁷) or Go (approximately 10¹⁷⁰), it was still an astronomical number for 1950s computers. Precisely because checkers' complexity was "just right" — neither simple enough to be fully enumerated like tic-tac-toe, nor so complex as to be completely intractable like chess — it became the ideal testing ground for early AI research. It wasn't until 2007 that Jonathan Schaeffer's team at the University of Alberta finally "solved" checkers, proving that the game results in a draw under optimal play from both sides.

Samuel employed a series of techniques that remain classic to this day.

Evaluation Functions and Automatic Parameter Tuning

At the core of the program was an "evaluation function" used to judge whether a given board position was favorable. This function was a weighted combination of multiple features, including piece count, piece positions, and center control. The key innovation was that these weights were not fixed — they were automatically adjusted as the program played more games.

Specifically, Samuel's evaluation function took the form V(s) = w₁·f₁(s) + w₂·f₂(s) + ... + wₙ·fₙ(s), where f_i represents hand-designed features (such as the difference in piece count between sides, number of kings, row advancement of pieces, etc.), and w_i represents the corresponding weights. Samuel designed up to 38 features and let the program automatically adjust the magnitude and sign of these weights during play. This "feature engineering + parameter learning" paradigm remained the mainstream approach in machine learning for decades, until deep learning partially replaced it with "end-to-end learning" (where neural networks simultaneously learn feature extraction and decision-making). The shift from hand-crafted feature design to automatic feature learning represents one of the most important paradigm shifts in the history of machine learning.

In other words, the program gradually "learned" which board features mattered more through extensive gameplay, continuously optimizing its judgment. This is essentially the prototype of today's supervised learning and parameter optimization.

Memory Mechanisms and Look-Ahead Search

Samuel also introduced two learning mechanisms. One was "rote learning," where the program memorized previously encountered positions and their evaluation results to avoid redundant computation. This method essentially built an experience database — similar to what we now call a "transposition table" or, more broadly, a caching mechanism. As the number of games played increased, the program's accumulated "memory" grew richer, improving search efficiency since many previously analyzed positions could be looked up directly.

The other mechanism was more profound — the program used minimax search to look ahead several moves and corrected its current position evaluation using the evaluation results of future positions. The minimax algorithm is a classic application of game theory in computer science: in a two-player zero-sum game, one player tries to maximize gains (MAX layer) while the other tries to minimize the opponent's gains (MIN layer), and the algorithm recursively alternates expanding the game tree to find the optimal strategy. Samuel also employed an early form of Alpha-Beta pruning to reduce the search space — this optimization technique can reduce the number of branches searched from b^d to approximately b^(d/2) (where b is the branching factor and d is the search depth) without affecting the final result, effectively nearly doubling the search depth with the same computational resources.

This approach of "using future predictions to correct current estimates" essentially foreshadowed the Temporal Difference (TD) learning method in reinforcement learning. The core idea of TD learning can be expressed with a concise update formula: V(s) ← V(s) + α[r + γV(s') - V(s)], where α is the learning rate, r is the immediate reward, γ is the discount factor, and V(s') is the estimated value of the next state. The essence of this formula is that it doesn't need to wait for the final outcome to be revealed — it can update value judgments using estimation differences between adjacent states. Although Samuel's program didn't use this exact mathematical form, its practice of "using deep search results to correct shallow estimates" is highly consistent with TD learning in spirit.

Richard Sutton and others, when establishing modern reinforcement learning theory, have repeatedly cited Samuel's work as an important intellectual source. Sutton explicitly states in his classic textbook Reinforcement Learning: An Introduction that Samuel's checkers program was one of the earliest implementations of TD learning ideas, predating the formal theorization of TD(λ) by nearly 30 years.

Technical Lineage from Checkers to AlphaGo

Samuel's checkers program was not just a technical achievement but a conceptual breakthrough. In that era, computers were widely believed to be capable of doing only what humans explicitly told them to do. Samuel proved that machines could improve themselves through experience, and even play better than the programmer who wrote them. By the early 1960s, Samuel's program was reportedly able to defeat the Connecticut state checkers champion, causing enormous public sensation.

If we extend the timeline, we can trace a clear technical lineage from Samuel's checkers program, to Deep Blue's defeat of Kasparov in 1997, to AlphaGo's victory over Lee Sedol in 2016:

• Using evaluation functions to quantify position value
• Using search algorithms for look-ahead prediction
• Using self-play to generate training data

However, there are also important technical gaps and divergences among these three milestones. Deep Blue largely followed a "brute force search" approach: it relied on specialized hardware to achieve a search speed of 200 million positions per second, with an evaluation function manually tuned by human chess grandmasters across approximately 8,000 feature parameters — the learning component was relatively minimal. Deep Blue's success proved the power of hardware computing more than the advancement of learning capability. In contrast, AlphaGo returned to Samuel's "learning" approach but elevated it to entirely new heights: it replaced hand-crafted evaluation functions with deep convolutional neural networks containing millions of parameters, replaced traditional minimax search with Monte Carlo Tree Search (MCTS), and most crucially, trained from scratch through self-play in reinforcement learning, completely freeing itself from dependence on human expert knowledge. AlphaGo Zero's training process generated approximately 4.9 million self-play games, each providing new training samples for the neural network.

AlphaGo's self-play training is essentially the same idea as Samuel having his program "play against itself" to accumulate experience. Samuel realized a key problem in the 1950s: if the program only played against opponents of a fixed level, its capability would quickly hit a ceiling. To solve this, he had two copies of the program play against each other — one using the current best strategy and the other using a slightly earlier version — continuously pushing the upper limit through this "internal competition." This is identical to AlphaGo Zero's training strategy, except the latter replaced hand-designed evaluation functions with deep neural networks and replaced the meager computing resources of that era with massive computational power. From a few KB of memory to computing clusters with thousands of TPUs, hardware capability has increased by billions of times, but the core algorithmic ideas driving progress — self-play, value estimation, learning from experience — have not fundamentally changed.

Reassessing the Value of Classic Work

In today's world, where AI hype sweeps the globe and new concepts emerge endlessly, revisiting Samuel's checkers program holds special significance.

It tells us that many ideas that appear "new" today can often be traced back decades. Understanding these classic works is not just a matter of respecting history — it helps us see the essential patterns of technological evolution. What truly drives progress is often those simple yet profound core ideas, rather than superficial conceptual packaging.

This phenomenon is particularly prevalent in AI. The core idea of backpropagation can be traced to cybernetics research in the 1960s; the attention mechanism was inspired by neuroscience discoveries in the 1990s; even the self-attention mechanism in the Transformer architecture that current large language models depend on can find intellectual precursors in earlier memory networks and associative models. Technological development is not a linear accumulation of breakthroughs but rather a spiral ascent — old ideas are reactivated under new conditions (more data, stronger computing power, better engineering implementations), unleashing unprecedented power. Samuel's checkers program is a perfect illustration of this pattern: it achieved a proof of concept for "learning" with extremely limited resources in the 1950s, and the same core ideas, combined with deep learning and modern computing power sixty years later, gave birth to systems like AlphaGo that changed the world's understanding.

For anyone wanting to deeply understand machine learning, returning to Samuel's checkers program as the origin point is a worthwhile intellectual journey. It reminds us that while chasing the latest papers and largest models, we should not forget those foundational ideas. It is precisely these ideas that form the intellectual bedrock on which we stand today.

Key Takeaways