A Short History of AI
From Dartmouth 1956 through two winters to the deep learning era.
AI's history is usually told as booms and winters. Underneath runs a story about algorithms: which ideas worked, why they hit walls, and what it took to get past them. This lesson retells the history through the machinery itself, with the proofs and the numbers that explain each turn.
What you’ll learn
- Prove that networks of McCulloch–Pitts threshold units can compute any Boolean function, and that a single threshold unit cannot compute XOR.
- Quantify the combinatorial explosion (branching factor, Shannon's chess estimate) and connect it to NP-completeness and the first AI winter.
- Describe the match–resolve–act cycle of a rule-based expert system, and explain the knowledge acquisition bottleneck.
- Explain why reverse-mode differentiation (backpropagation) made multilayer networks trainable, with a cost comparison against finite differences.
- Quantify the growth of training compute in the deep learning era, and place its landmark systems correctly in time.
1943–1956: neurons, logic and a name
In 1943 Warren McCulloch and Walter Pitts modeled a neuron as a threshold unit: it outputs 1 when a weighted sum of binary inputs reaches a threshold, . They argued that networks of such units could implement logic, and the artificial neuron was born more than a decade before the field had a name.
The name came at Dartmouth in the summer of 1956. There Allen Newell and Herbert Simon (with Cliff Shaw) presented the Logic Theorist, which went on to prove 38 of the first 52 theorems in chapter 2 of Whitehead and Russell's Principia Mathematica. By then Shannon (1950) had already described how a computer could play chess with minimax search and an evaluation function.
Single units give the basic gates: AND of inputs, OR, and NOT (a negative weight).
For each input row with , build a hidden unit that fires on and nowhere else; is the number of ones in . On the sum is exactly , and every bit in which differs from lowers it by 1.
The output unit ORs the hidden units. This is the disjunctive normal form of , wired as a network.
The catch is size: up to hidden units, and Shannon (1949) showed that most Boolean functions need exponentially large circuits of any kind. Representing functions was never the obstacle. Learning the weights was.
1956–1974: search, optimism and the combinatorial explosion
The first decades framed intelligence as heuristic search through a space of possibilities. Newell, Shaw and Simon's General Problem Solver (1959) used means–ends analysis. Arthur Samuel's checkers program learned its own evaluation function, and his 1959 paper put the phrase "machine learning" into its title. SRI's robot Shakey (1966–1972) gave rise to the A* algorithm (1968) and the STRIPS planner (1971).
Optimism ran high. In 1958 Simon and Newell predicted that within ten years a computer would be the world chess champion.
function MEANS-ENDS(state, goal, depth) returns a plan or failure
if state satisfies goal then return []
if depth = 0 then return failure
d ← the most important difference between state and goal
for each operator op relevant to reducing d:
pre ← MEANS-ENDS(state, preconditions(op), depth − 1) // make op applicable
if pre = failure then continue
s ← the state reached by executing pre, then op
rest ← MEANS-ENDS(s, goal, depth − 1)
if rest ≠ failure then return pre + [op] + rest
return failureA simplified rendering of GPS's means–ends analysis: reduce the most important difference, recursively setting up subgoals that make the chosen operator applicable. Every choice point multiplies the work.
A search tree with branching factor and depth has
Chess has about legal moves per position and games of roughly 80 plies, so its full game tree has around nodes. Shannon's 1950 estimate of about possible games is the famous "Shannon number".
Even a search only 12 plies deep, at a billion positions per second, would take about a century:
Theory explained the wall. Cook (1971) and Karp (1972) showed that satisfiability and dozens of combinatorial problems are NP-complete: unless P = NP, no algorithm escapes exponential time in the worst case. Methods that shone on toy problems did not scale to real ones.
An exhaustive chess search (branching factor about 35) moves to a computer twice as fast. How much deeper can it search in the same time?
- Twice as deep
- One full ply deeper
- About a fifth of a ply deeper
- No deeper at all
Show the answer
C. About a fifth of a ply deeper
Depth grows like the logarithm of compute: ply. Hardware alone cannot beat exponential growth. Alpha–beta pruning with good move ordering cuts the effective branching factor to about , which roughly doubles the depth reachable with the same work; that, plus custom hardware, is how chess programs eventually reached master depth.
1958–1987: perceptrons fall, knowledge rises
Frank Rosenblatt's perceptron (1958) learned the weights of a single threshold unit from examples: after each mistake, . Novikoff (1962) proved that this rule converges whenever the two classes are linearly separable. Minsky and Papert's Perceptrons (1969) mapped what single-layer perceptrons cannot compute, and the smallest casualty is XOR.
Suppose . The four rows of the truth table require
Add the two middle inequalities and use :
That contradicts the last inequality. One hidden layer fixes it: OR minus AND.
Multilayer threshold networks were known to be universal, so the real lesson was that nobody knew how to train hidden layers. Neural network research lost momentum, and the field turned to knowledge.
Expert systems encoded a specialist's know-how as if–then rules. DENDRAL inferred molecular structures from mass spectra (from 1965); MYCIN diagnosed blood infections with several hundred rules (mid-1970s); and R1, later called XCON, configured computer orders at Digital Equipment Corporation, which credited it with savings in the tens of millions of dollars a year by the mid-1980s.
function PRODUCTION-SYSTEM(facts, rules) returns facts
loop:
conflict_set ← { (r, θ) : the IF part of rule r holds in facts under bindings θ,
and (r, θ) has not fired before } // MATCH
if conflict_set is empty then return facts
(r, θ) ← SELECT(conflict_set) // RESOLVE: specificity, recency, priority
facts ← facts ∪ SUBST(θ, THEN part of r) // ACTThe match–resolve–act cycle of a forward-chaining rule engine, as in the OPS production-system languages used to build R1. A MYCIN-style rule: IF the organism is gram-negative AND rod-shaped AND anaerobic, THEN there is suggestive evidence (0.6) that it is Bacteroides.
1986–2011: learning and probability take over
In 1986 Rumelhart, Hinton and Williams showed that multilayer networks can be trained by gradient descent if the gradient is computed by backpropagation, a reverse-mode application of the chain rule. The method had precursors (Linnainmaa's reverse-mode differentiation in 1970, Werbos's 1974 thesis), but the 1986 paper showed hidden units learning useful internal representations, and it relaunched connectionism. Why was an efficient gradient such a big deal?
Let a network have weights, so one forward pass costs operations. Finite differences estimate one partial derivative per extra forward pass:
Reverse mode stores the activations during one forward pass, then sweeps backward once, propagating error signals with the chain rule:
Each weight is touched a constant number of times, so the whole gradient costs a small constant multiple of one forward pass (the "cheap gradient principle").
For a million weights, that is the difference between one backward pass and a million forward passes per training step.
Yet neural networks did not take over in the 1990s. Datasets were small, computers slow, and deep or recurrent networks suffered from vanishing gradients. Methods with convex training and strong theory often won instead: support vector machines (Cortes and Vapnik, 1995), boosting, hidden Markov models for speech, and Bayesian networks (Pearl, 1988). AI became statistical: learn from data, reason with probability.
In games, IBM's Deep Blue beat world champion Garry Kasparov in 1997 with alpha–beta search on custom chess chips, examining on the order of positions per second and scoring them with a carefully engineered evaluation function.
2012–today: the deep learning era
Three ingredients converged. Data: ImageNet (Deng et al., 2009) supplied over a million labeled training images in 1,000 classes for its annual challenge. Compute: graphics processors made dense linear algebra cheap. Refinements: ReLU activations, dropout and better initialization made deep networks trainable. In 2012 AlexNet, a convolutional network trained on two GPUs by Krizhevsky, Sutskever and Hinton, cut the top-5 error to 15.3%, against 26.2% for the next-best entry.
| Year | Milestone |
|---|---|
| 2013–2015 | word2vec embeddings; deep Q-networks learn Atari games from pixels; GANs; sequence-to-sequence models with attention; ResNet trains networks more than 100 layers deep |
| 2016 | AlphaGo defeats Lee Sedol 4–1 at Go, combining tree search with deep networks |
| 2017 | The transformer ("Attention Is All You Need"); AlphaZero masters chess, shogi and Go by self-play alone |
| 2018–2020 | BERT and GPT pretraining; GPT-3 (175 billion parameters) shows in-context learning; AlphaFold 2 transforms protein-structure prediction |
| 2022 | ChatGPT, a large language model fine-tuned with human feedback, brings conversational AI to a mass audience |
| 2024 | Nobel Prizes: Physics to John Hopfield and Geoffrey Hinton, for foundations of machine learning with artificial neural networks; Chemistry to David Baker, Demis Hassabis and John Jumper, for protein design and structure prediction |
If training compute doubles every months, it grows by this factor each year:
Sevilla et al. (2022) estimated a doubling time of about 20 months for milestone systems before 2010, in line with Moore's law, and about 6 months from 2010 to 2022:
Over a decade, that is six orders of magnitude versus less than two. Chips did not get a million times faster; most of the growth came from spending: more chips, running for longer.
Suppose training compute doubled every 4 months. By how many orders of magnitude (powers of ten) would it grow in five years?
Show the answer
4.5
Five years is 60 months, or 15 doublings: , about 4.5 orders of magnitude, since .
Key takeaways
- Threshold networks with one hidden layer compute every Boolean function (the DNF construction), but a single unit cannot compute XOR. The obstacle was learning hidden layers, not representing functions.
- Search hit the combinatorial explosion: nodes, around for chess. NP-completeness explained the wall, and overpromising plus the ALPAC and Lighthill reports brought the first winter.
- Expert systems (match–resolve–act over if–then rules) succeeded in narrow domains, but the knowledge acquisition bottleneck, rule interactions and brittleness brought the second winter.
- Backpropagation made a gradient cost rather than ; through the 1990s and 2000s AI turned statistical, with SVMs, HMMs and Bayesian networks.
- Since 2012, data, GPUs and a few refinements have made deep learning dominant, with training compute growing about fourfold per year (a six-month doubling time) from 2010 to 2022.
Check yourself
In the interactive lesson these are scored with your confidence, and what you miss comes back for review.
Minsky and Papert's 1969 limitations applied most directly to which networks?
- All neural networks, including multilayer ones
- Single-layer perceptrons: one layer of trainable weights on fixed features
- Networks trained by backpropagation
- Networks without bias terms
Show the answer
B. Single-layer perceptrons: one layer of trainable weights on fixed features
Their theorems concern what one layer of adjustable weights over fixed feature detectors can compute. Multilayer threshold networks were known to be universal (McCulloch and Pitts); what was missing was a way to train their hidden layers.
An exhaustive search with branching factor is extended by one more ply. Roughly how much more work does it do?
- Twice as much
- times as much
- times as much
- times as much
Show the answer
C. times as much
The tree has nodes, so going from depth to multiplies the work by about . That is why depth grows only logarithmically with computing power.
Why did backpropagation make it practical to train networks with millions of weights?
- It finds the global minimum of the loss
- It avoids computing derivatives altogether
- It needs no training data
- It computes all partial derivatives for a small constant multiple of the cost of one pass through the network, instead of one pass per weight
Show the answer
D. It computes all partial derivatives for a small constant multiple of the cost of one pass through the network, instead of one pass per weight
Reverse-mode differentiation reuses intermediate results, so the full gradient costs a small constant times a forward pass. Finite differences would need one pass per weight: a millionfold slowdown at a million weights.
What was the "knowledge acquisition bottleneck" of expert systems?
- Turning experts' know-how into rules was slow, costly and incomplete, and the rule bases became hard to maintain
- Computers of the 1980s lacked the memory to store rules
- Rules could not express uncertainty at all
- Experts refused to share their knowledge
Show the answer
A. Turning experts' know-how into rules was slow, costly and incomplete, and the rule bases became hard to maintain
Much expertise is tacit, so knowledge engineers had to coax rules out of experts one at a time, and every new rule could interact with all the others. The bottleneck was human, not hardware.
Which combination best explains the 2012 breakthrough in image recognition?
- A new learning principle that replaced backpropagation
- Better hand-designed features fed to a linear classifier
- A large labeled dataset, GPU computing and refinements such as ReLU and dropout, applied to a convolutional network trained with backpropagation
- Symbolic rules combined with a small neural network
Show the answer
C. A large labeled dataset, GPU computing and refinements such as ReLU and dropout, applied to a convolutional network trained with backpropagation
AlexNet used ideas going back to the 1980s (convolution, backpropagation), made to work at scale by ImageNet's data, GPUs and a few refinements.
Go deeper
- Expert Systems & the Knowledge Bottleneck · Why hand-written rules scaled so badly.
- Symbols vs. Connections · The long debate between logic and neural networks.
- The Scaling Era & the Bitter Lesson · Compute, data and why general methods keep winning.
Further reading
- N. J. Nilsson, The Quest for Artificial Intelligence: A History of Ideas and Achievements (Cambridge University Press, 2010).
- S. Russell & P. Norvig, Artificial Intelligence: A Modern Approach, 4th ed. (Pearson, 2020), section 1.3.
- W. S. McCulloch & W. Pitts, "A logical calculus of the ideas immanent in nervous activity," Bulletin of Mathematical Biophysics 5, 115–133 (1943).
- D. E. Rumelhart, G. E. Hinton & R. J. Williams, "Learning representations by back-propagating errors," Nature 323, 533–536 (1986).