Symbolic AI: Search, Knowledge and the Expert-Systems Boom

From the late 1950s to the late 1980s, most AI research assumed that intelligence is the manipulation of symbols according to rules. This approach, later nicknamed GOFAI ("good old-fashioned AI", a term coined by philosopher John Haugeland in 1985), produced programming languages, search algorithms and planning methods that every computer scientist still learns, and in the 1980s it produced a commercial boom in expert systems. It then hit limits that taught the field its most important lesson about knowledge. If you have ever used a route planner, a rules engine, a type checker or a knowledge graph, you have used GOFAI's descendants.

The intuition: a very literal clerk

Imagine a clerk who cannot see or hear, who reads only cards with symbols on them, and who follows a thick rulebook exactly: "If the card says infection and gram-negative and rod-shaped, write E. coli likely on a new card." Given enough cards and a good rulebook, the clerk can perform impressive feats, such as diagnosing infections or configuring computers, without understanding anything. Symbolic AI bet that intelligence is essentially this: the right symbols, the right rules, and an efficient way to search among the possible rule applications.

Newell and Simon stated the bet formally in their 1976 Turing Award lecture as the physical symbol system hypothesis: a physical symbol system has the necessary and sufficient means for general intelligent action.

Timeline

Search: the engine of symbolic AI

State spaces

Most early AI framed problems as search through a state space. A state is a description of the world (a chess position, a partial proof, a set of block positions). Operators transform one state into another. The task is to find a sequence of operators from a start state to a goal state. The difficulty is combinatorial explosion: with branching factor $b$ (choices per step) and solution depth $d$, a naive search may examine on the order of $b^d$ states. For chess, with roughly 35 legal moves per position, looking 10 moves (plies) ahead means about $35^{10} \approx 2.8 \times 10^{15}$ positions.

The General Problem Solver (1957–59)

Newell, Shaw and Simon generalized Logic Theorist into the General Problem Solver. Its key idea was means-ends analysis: compare the current state with the goal, identify the most important difference, pick an operator known to reduce that difference, and if that operator cannot yet be applied, set up a subgoal to make it applicable. GPS solved puzzles such as the Towers of Hanoi and logic problems, and Newell and Simon compared its traces with transcripts of people thinking aloud. Its limitation was in the name: it was general only for problems someone had already formalized with clean states and operators. Real-world problems rarely arrive that way.

A*: optimal heuristic search (1968)

Peter Hart, Nils Nilsson and Bertram Raphael at SRI published "A Formal Basis for the Heuristic Determination of Minimum Cost Paths" in 1968, developed in connection with the Shakey robot project. A* expands nodes in order of

where $g(n)$ is the cost of the cheapest known path from the start to node $n$, and $h(n)$ is a heuristic estimate of the remaining cost from $n$ to the goal. If $h$ never overestimates the true remaining cost (it is admissible), A* is guaranteed to find a cheapest path.

Worked example: A* by hand

Graph: start S, goal G. Edges with costs: S→A (1), S→B (4), A→B (2), A→G (5), B→G (1). Heuristic estimates: $h(S)=4$, $h(A)=3$, $h(B)=1$, $h(G)=0$. (Check admissibility: true remaining costs are S: 4 via S→A→B→G, A: 3 via A→B→G, B: 1. No estimate exceeds these.)

1. Start: open list {S: $g=0, f=0+4=4$}. Expand S.
2. Add A ($g=1$, $f=1+3=4$) and B ($g=4$, $f=4+1=5$). Lowest $f$ is A (4). Expand A.
3. From A: B via A has $g=1+2=3$, better than 4, so update B ($f=3+1=4$). G via A has $g=1+5=6$, $f=6$. Open: {B: 4, G: 6}. Expand B.
4. From B: G via B has $g=3+1=4$, $f=4$, better than 6, update. Open: {G: 4}. Expand G: goal reached.

Result: path S→A→B→G with cost 4. Note that the direct-looking route S→A→G (cost 6) was never chosen, because the heuristic steered the search well. A* and its variants still power route planning in games, robotics and logistics.

STRIPS and planning (1971)

Richard Fikes and Nils Nilsson's STRIPS (Stanford Research Institute Problem Solver) planned actions for Shakey. Its lasting contribution is the representation: each action has preconditions (facts that must be true), an add list (facts it makes true) and a delete list (facts it makes false). For example, PickUp(box) requires HandEmpty and On(box, floor), adds Holding(box), and deletes HandEmpty and On(box, floor). This "STRIPS-style" representation is the ancestor of PDDL (Planning Domain Definition Language), used in automated-planning competitions since 1998, and of the way some modern AI agents describe tools with preconditions and effects.

Representing knowledge

LISP (1958–60)

John McCarthy created LISP (LISt Processor) at MIT, described in his 1960 Communications of the ACM paper "Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I." LISP made programs and data the same kind of object (lists), introduced garbage collection and conditional expressions in their modern form, and became AI's main language in the US for three decades. Prolog (1972), based on logic programming, played the same role in Europe and Japan.

ELIZA (1966): the illusion of understanding

Joseph Weizenbaum's ELIZA, published in CACM in 1966, matched keywords in a user's typed sentence and transformed them with templates. Its best-known script, DOCTOR, imitated a non-directive psychotherapist: "I am unhappy" becomes "Why do you say you are unhappy?" A few lines of Python capture the idea:

import re

RULES = [
    (r"i am (.*)", "Why do you say you are {0}?"),
    (r"i feel (.*)", "How long have you felt {0}?"),
    (r".*\bmother\b.*", "Tell me more about your family."),
]
SWAP = {"my": "your", "me": "you", "i": "you", "am": "are"}

def reflect(text):
    return " ".join(SWAP.get(w, w) for w in text.split())

def eliza(sentence):
    s = sentence.lower().strip(".!? ")
    for pattern, template in RULES:
        m = re.fullmatch(pattern, s)
        if m:
            return template.format(*[reflect(g) for g in m.groups()])
    return "Please go on."

print(eliza("I am worried about my exams"))
# Why do you say you are worried about your exams?

There is no model of the world here, only pattern matching and pronoun swapping. Yet Weizenbaum was disturbed to find people confiding in the program as if it understood them, and wrote the critical book Computer Power and Human Reason (1976). The tendency to attribute understanding to fluent text is now called the ELIZA effect, and it is directly relevant to how people relate to chatbots today.

SHRDLU (around 1970): understanding in a toy world

Terry Winograd's SHRDLU at MIT conversed in English about a simulated "blocks world" of coloured blocks and pyramids. It could follow commands ("Pick up a big red block"), answer questions about what it had done and why, resolve pronouns and learn new names for configurations. It was one of the most impressive demonstrations of its era because it integrated parsing, reasoning and planning. It also illustrated the core weakness of the approach: its competence did not extend beyond the tiny world it was built for. Winograd himself later turned away from the symbolic approach.

Frames, semantic networks and logic

Researchers proposed several ways to structure knowledge: semantic networks (nodes for concepts, labelled links such as is-a), Minsky's frames (1974; structured records with slots and default values, an ancestor of object-oriented classes), scripts for stereotyped situations, and formal logic with automated theorem provers. These debates fed directly into today's knowledge graphs, ontologies (such as OWL for the Semantic Web) and database schemas.

The expert-systems boom

The insight: knowledge is power

By the late 1960s, Edward Feigenbaum and colleagues at Stanford argued that general reasoning methods were weak, and that performance came from large amounts of domain-specific knowledge: the "knowledge is power" principle. An expert system encodes a specialist's knowledge as if-then rules in a knowledge base, separate from a generic inference engine that chains rules together (forward from facts to conclusions, or backward from a hypothesis to the facts needed to support it).

• DENDRAL (begun 1965, Stanford; Feigenbaum, Joshua Lederberg, Bruce Buchanan, Carl Djerassi) inferred the molecular structure of organic compounds from mass-spectrometry data. It is usually cited as the first expert system.
• MYCIN (early 1970s, Stanford; Edward Shortliffe's doctoral work, with Buchanan and others) diagnosed bacterial blood infections and recommended antibiotics using about 600 rules, with certainty factors from −1 to +1 to handle uncertainty. In a 1979 evaluation by Yu and colleagues, MYCIN's recommendations were judged acceptable 65% of the time, comparable to or better than the Stanford infectious-disease faculty evaluated in the same study (42.5%–62.5%). It was never used clinically, mainly because of integration problems (all patient data had to be typed in on a time-shared computer) and unresolved questions of legal responsibility. Its shell, EMYCIN, separated the inference engine from the medical knowledge so others could build new expert systems.
• R1/XCON (written from 1978 by John McDermott of Carnegie Mellon, in use at Digital Equipment Corporation from 1980) configured VAX computer orders, choosing compatible components and cables. Written in the rule language OPS5, it grew to about 2,500 rules and was reported to save DEC around $25 million a year. XCON was the commercial proof that convinced industry.

Boom and national programs

The early 1980s saw companies build AI groups, startups sell expert-system shells, and firms such as Symbolics and Lisp Machines Inc. sell dedicated Lisp machines. In 1982 Japan's Ministry of International Trade and Industry (MITI) launched the Fifth Generation Computer Systems project, run by the institute ICOT, aiming at massively parallel computers based on logic programming that would support knowledge processing and natural-language dialogue. The project alarmed Western governments and prompted responses including the UK's Alvey programme, the US Microelectronics and Computer Technology Corporation (MCC) consortium, and DARPA's Strategic Computing Initiative (1983). By the time it ended in the early 1990s, the Fifth Generation project had built parallel inference machines and trained a generation of researchers, but it had not met its original goals, and the commodity computers it was meant to leapfrog had overtaken specialized hardware.

Cyc: encoding common sense (1984–)

Douglas Lenat started Cyc in 1984 at MCC in Austin, Texas. The diagnosis was correct: expert systems failed at the edges because they lacked the vast background knowledge any person has ("water makes things wet", "a person cannot be in two places at once"). Cyc's answer was to hand-encode that knowledge in formal logic, assertion by assertion, for decades; the effort later continued at the company Cycorp. Cyc is the most ambitious test of the hand-coded approach. It produced a large, carefully engineered knowledge base and some commercial applications, but it did not deliver general common sense, and its slow progress is often cited as evidence that common sense cannot practically be written down by hand.

Why symbolic AI hit its limits

1. Brittleness. Rule-based systems performed well inside their designed scope and failed abruptly just outside it. A system that knows rules for bacterial infections has no idea that a patient who is pregnant, or a typing error in the age field, changes everything, unless someone wrote that rule.
2. The knowledge acquisition bottleneck. Expertise had to be extracted from experts by "knowledge engineers" through interviews. Experts often cannot articulate what they know (tacit knowledge), rules conflict, and the work is slow and expensive. Feigenbaum himself identified this bottleneck.
3. Maintenance. As rule bases grew to thousands of rules, interactions became hard to predict. XCON required a dedicated team to maintain as DEC's product line changed.
4. Combinatorial explosion. Search methods that worked on toy problems slowed exponentially on real ones, a criticism made central by the 1973 Lighthill report (lesson 3).
5. Common sense and the frame problem. Representing what does not change when an action happens (the frame problem, identified by McCarthy and Hayes in 1969) and the vast background of everyday knowledge proved intractable to write by hand.
6. Uncertainty. Real data are noisy. Ad hoc schemes like certainty factors lacked a principled basis; probability theory and Bayesian networks (lesson 4) handled this better.
7. Economics. Cheap, powerful Unix workstations and PCs made Lisp machines unnecessary, and the market for them collapsed around 1987, part of the second AI winter (lesson 3).

The deepest lesson is in point 2. Symbolic AI put the burden of knowledge on people. The approaches that eventually won, statistical machine learning and deep learning, moved that burden to data: instead of asking an expert for rules, show the system many examples and let it find the patterns.

Legacy: symbolic AI is everywhere, under other names

• Search and planning: A* and its descendants run route planners, game AI and robot motion planning; PDDL planners schedule logistics and space missions.
• Rules engines and business-rule systems in finance, insurance and compliance descend from expert-system shells.
• Programming languages: garbage collection, interactive REPLs, and functional programming owe much to LISP; logic programming survives in Prolog and Datalog, used in program analysis and databases.
• Knowledge graphs and ontologies: Google's Knowledge Graph, Wikidata, medical ontologies such as SNOMED CT.
• Verification: SAT/SMT solvers and theorem provers, used to verify chips and software, grew from automated reasoning research.
• Neuro-symbolic hybrids: modern AI agents combine neural networks with symbolic tools: a language model writes code that a deterministic interpreter executes, calls a calculator or database, or produces a formal proof that a proof checker (such as Lean) verifies. In such systems the neural part supplies flexible pattern recognition and the symbolic part supplies exactness and verifiability.

Common pitfalls

• Calling symbolic AI a failure. It failed at general intelligence but succeeded spectacularly at well-defined tasks, and its tools are now so ordinary they are no longer called AI (sometimes called the "AI effect").
• Mistaking ELIZA's fluency for understanding, and repeating the mistake with modern chatbots. Fluent output is evidence of fluency, not of a world model.
• Assuming the knowledge bottleneck is solved. LLMs absorb knowledge from text, but enterprise deployments still hit a version of it: undocumented company procedures, tacit expertise and exceptions that were never written down.
• Confusing A's optimality guarantee with speed.* A* is optimal only with an admissible heuristic, and it can still use exponential memory on hard problems.

In practice

Knowing this history helps you design better systems. When a task has hard constraints (tax rules, safety interlocks, access control), express them symbolically and let a neural model handle the fuzzy parts, such as reading the input documents. When you build an agent's tool layer, write tools with explicit preconditions and effects, as STRIPS did, so that the agent and its monitoring can reason about them. And when you estimate an AI project, remember the knowledge acquisition bottleneck: the hard part is often capturing the domain knowledge and edge cases, not the model.