Artificial Intelligence Notes | B.Sc. (Computer Science) Semester 5 | Mumbai University | munotes

The Turing test, read out of Turing's own paper

Alan Turing opened his 1950 paper with a refusal. He would not ask "Can machines think?", because that needs definitions of "machine" and "think" that nobody agrees on. He replaced the question with a game.

The imitation game. Three participants: a man, a woman, and an interrogator in a separate room who communicates with both by writing. The interrogator has to say which is which. The man's job is to make the interrogator get it wrong; the woman's job is to help. Turing's question is then:

What will happen when a machine takes the part of A in this game? Will the interrogator decide

wrongly as often when the game is played like this as he does when the game is played between a

man and a woman?

Three points about the test that are worth marks and are usually got wrong:

1. It is a test of behaviour, not of thought. Turing designed it precisely so that the machine's internals do not matter. It belongs in the bottom-left box of the grid above.
2. It is deliberately verbal, and Turing says why. The answers are to be typewritten, over a teleprinter between two rooms, "in order that tones of voice may not help the interrogator". The arrangement has, in his words, "the advantage of drawing a fairly sharp line between the physical and the intellectual capacities of a man": there would be "little point in trying to make a thinking machine more human by dressing it up in such artificial flesh."
3. Turing predicted the objections and answered nine of them, in this order: the Theological Objection, the "Heads in the Sand" Objection, the Mathematical Objection (from Godel's theorem), the Argument from Consciousness, Arguments from Various Disabilities, Lady Lovelace's Objection, the Argument from Continuity in the Nervous System, the Argument from Informality of Behaviour, and the Argument from Extrasensory Perception. His own estimate was that "in about fifty years' time" a machine would play the game so well that an average interrogator "will not have more than 70 per cent chance of making the right identification after five minutes of questioning."

The test is a historical landmark, not a working goal. Almost no modern AI research aims at it, for a plain engineering reason: imitating a person means imitating a person's slowness and mistakes, which nobody wants to pay for. Its value is that it forced the field to define success by what a system does rather than by what it is made of.

The four things a modern AI system is asked to do

A definition is easier to remember when it is attached to capabilities. Almost everything in this paper falls under one of four headings, and each is a later row of MU's own syllabus.

Strong and weak AI, narrow and general

Three pairs of words get used loosely. They are cheap marks when kept straight.

Weak against strong is about what the machine IS. Narrow against general is about what it can DO. A system could in principle be general and still have no mind at all.

What AI is not

This section exists because a chapter that only enthuses leaves a reader unable to say where the subject stops.

• It is not a synonym for machine learning. Learning is one row of Module 2. Search, logic and planning are AI and contain no learning at all. A chess program using minimax learns nothing.
• It is not a synonym for statistics, though Module 2 is largely statistical. AI asks what to DO; statistics asks what is TRUE of the data. The difference is the performance measure.
• It is not automation. A washing machine's timer automates a task and chooses nothing. An agent chooses.
• It is not consciousness, and no result in this paper bears on the question. Every algorithm here would work identically whether or not anything was going on inside.
• It is not magic, and it is not new. Every method in this paper is arithmetic on numbers or symbol manipulation on structures, published between 1950 and 1997 in papers you could read.

Distinctions

Quick revision

• AI is the study and construction of agents that perceive an environment and act to achieve the best expected outcome.
• The phrase was coined in the 1955 Dartmouth proposal (McCarthy, Minsky, Rochester, Shannon) for a 1956 summer project.
• Four definitions, on two axes: thinking or acting, humanly or rationally. This syllabus takes acting rationally, the intelligent agent view.
• The Turing test (Turing, 1950) replaces "can machines think" with the imitation game. It tests behaviour, is deliberately conducted in writing, and Turing answered nine objections to it.
• Weak or narrow AI does one task; strong AI is the claim that the machine would truly have a mind; AGI is the engineering goal of one broadly competent system.
• Four capability headings: acting, reasoning, coping with uncertainty, learning. They are MU's four rows of Module 1 plus the whole of Module 2.
• AI is not the same as machine learning, not the same as statistics, not automation, and says nothing about consciousness.

Test yourself

1. Define artificial intelligence in one sentence fit for an examination. Artificial Intelligence is the study and construction of agents that perceive their environment and act so as to achieve the best expected outcome, performing tasks that normally require human intelligence such as reasoning, learning, perception and decision making under uncertainty.

2. Give the four definitions of AI as a grid and say which one this subject uses. The axes are thought against behaviour, and human against rational. Thinking humanly is cognitive modelling; thinking rationally is the logic tradition; acting humanly is the Turing test; acting rationally is the intelligent agent approach. This syllabus uses acting rationally.

3. Describe the Turing test and state what it tests. An interrogator communicates in writing with a machine and a person and must identify which is which. If the interrogator does no better than chance, the machine passes. It tests external behaviour only, and says nothing about how the machine reached its answers.

4. Why did Turing replace the question "Can machines think?" Because answering it requires agreed definitions of "machine" and "think", which do not exist. He substituted a question that can be settled by observation.

5. Distinguish weak AI from strong AI. Weak or narrow AI is a system built to perform a particular task, and is what exists today. Strong AI is the philosophical claim that a suitably programmed machine would actually possess a mind and understanding rather than simulating them.

6. Is a program that uses minimax to play chess an example of artificial intelligence, given that it learns nothing? Yes. Learning is one family of AI methods, not the definition of the field. Minimax is a rational decision procedure over a game tree and sits squarely in the acting-rationally box.

7. Name the two documents that fix the field's starting point and the year of each. Turing's "Computing Machinery and Intelligence", 1950, which gave it a test; and the Dartmouth summer research project proposal, 1955, which gave it its name.

The rational-agent programme

The goal is a system that acts well. "Well" is not left vague; it is defined, and the definition is the one this syllabus uses everywhere after this chapter.

An agent is rational when, for each possible percept sequence, it selects the action that is expected to maximise its performance measure, given the evidence the percept sequence provides and whatever built-in knowledge the agent has.

Read that in five pieces, because every piece is doing work and each one is worth marks.

1. "For each possible percept sequence": rationality is about the action chosen in a situation, not about a fixed plan. The same agent may rightly do different things on different days.
2. "Expected to maximise": expected, not guaranteed. An agent that takes the best bet and loses was still rational. This is the single most misunderstood word in the definition.
3. "Its performance measure": the standard is external and stated in advance. Rationality is always relative to a measure; change the measure and the rational action changes.
4. "Given the evidence the percept sequence provides": the agent is judged on what it could know, not on what was true. Missing a car that was invisible is not irrational.
5. "And whatever built-in knowledge the agent has": the designer's knowledge counts as the agent's.

What rationality is not

This section exists because three separate things get confused with rationality, and each confusion loses marks.

It is not omniscience. An omniscient agent knows the actual outcome of every action. No real agent does. Rationality asks for the best decision from the available evidence, and a bad outcome from a good decision is not irrationality. Crossing a road after looking both ways is rational even if a cargo door falls from an aircraft.

It is not perfection. Perfection maximises actual performance; rationality maximises expected performance. Only the second is achievable, which is why it is the standard.

It is not the same as thinking. The definition mentions no internal process whatever. A lookup table that always happens to choose the best action is rational by this definition. Whether that is satisfying is a philosophical question; whether it is what MU examines is not.

Where each programme leads on this syllabus

Every following row of Module 1 is a tool for the second column. Search finds the action sequence that reaches a goal; logic works out what is true so the goal can be chosen; probability lets the agent act when it does not know. Module 2 is how the agent improves its own choices from experience. Not one of them claims to be how a person does it.

The one place the human side still earns its keep

Two arguments for studying human cognition survive even inside an engineering programme, and they are worth knowing because they are fair.

People are the only working example of general intelligence. Every narrow system in this paper does one task. If the goal is breadth, the only existing proof that breadth is possible is a person, so how people do it is evidence.

Some tasks are defined by human judgement. A translation is good if a speaker of the language accepts it. A recommendation is good if the person likes it. In these tasks the performance measure itself refers to people, so human behaviour cannot be left out of the specification.

Distinctions

Quick revision

• Rational agent: for each percept sequence, selects the action expected to maximise its performance measure, given the evidence of the percepts and its built-in knowledge.
• The five load-bearing parts of that definition: per percept sequence, expected, its performance measure, the evidence available, built-in knowledge.
• Human thinking is cognitive modelling: the standard is resemblance to a person, validated by psychology, and a program that does the task perfectly can fail that standard.
• Rationality is not omniscience, not perfection and not a claim about internal thought.
• A good decision with a bad outcome is rational. A lucky guess is not.
• This syllabus takes the rational-agent view from here to the end.
• The human side still matters for two honest reasons: people are the only working general intelligence, and some performance measures refer to people by definition.

Test yourself

1. Define a rational agent. An agent that, for each possible percept sequence, selects the action expected to maximise its performance measure, given the evidence provided by the percept sequence and whatever built-in knowledge the agent has.

2. Distinguish rationality from omniscience. An omniscient agent knows the actual outcome of its actions; a rational agent maximises the expected outcome from the evidence it has. Omniscience is impossible, which is why rationality is defined on expectation.

3. An agent crosses a road after looking both ways and is hit by debris falling from an aircraft. Was it rational? Yes. The decision was the best available on the evidence. Rationality judges the decision, not the outcome.

4. Why would a program that performs a task perfectly count as a failure in the human-thinking programme? Because that programme's standard is resemblance to human reasoning, including human slowness and human errors. Perfect performance is evidence that the program is not doing what a person does.

5. Give two honest reasons for studying human cognition even if you only want to build systems. People are the only existing example of general intelligence, so their methods are evidence that breadth is achievable; and in tasks such as translation or recommendation the performance measure is defined by human acceptance, so people are part of the specification.

6. Rationality is always relative to something. To what? To the performance measure. Change the measure and the rational action can change, so the measure must be stated before any agent can be called rational.

7. Which of the four definitions of AI does this syllabus adopt, and give one piece of evidence from the syllabus itself. Acting rationally. The evidence is that the very next labels are agent architectures, search, logic and probability, all of which are means of choosing a good action, and none of which claims to model human thought.

The performance measure is the whole game

This is the sentence to remember: an action is not right or wrong in itself, it is right or wrong against a stated measure. The measure is chosen by the designer, and choosing it badly is the commonest way a working system does the wrong thing.

Take the vacuum cleaner and measure it on amount of dirt sucked up in eight hours. That measure looks reasonable and it is a disaster. The highest-scoring agent sucks up the dirt, dumps it back on the floor, and sucks it up again. It maximises the measure exactly as instructed.

Now measure it on having a clean floor, say one point per clean square per time step, with a penalty for electricity used. The dump-and-resuck agent scores nothing extra for the second suck and pays for the power. The behaviour we actually wanted is now the winning behaviour.

The lesson generalises. A measure on outcomes in the world is safer than a measure on the agent's own activity, because the agent can always manufacture more of its own activity.

The agent function made literal

The definition says the function is a table from percept sequence to action. Written out, it looks like this. The vacuum world has two squares, A and B, and each is Clean or Dirty, so there are four possible percepts.

# A table on the LAST percept only. This is a reflex agent.
REFLEX = {
    ("A", "Dirty"): "Suck",
    ("A", "Clean"): "Right",
    ("B", "Dirty"): "Suck",
    ("B", "Clean"): "Left",
}

def reflex_agent(percept_sequence):
    return REFLEX[percept_sequence[-1]]

history = []
for percept in [("A", "Dirty"), ("A", "Clean"), ("B", "Dirty"), ("B", "Clean")]:
    history.append(percept)
    print("%-16s -> %s" % (str(percept), reflex_agent(history)))

('A', 'Dirty')   -> Suck
('A', 'Clean')   -> Right
('B', 'Dirty')   -> Suck
('B', 'Clean')   -> Left

Four rows, and that agent is completely specified. Now write the table the definition actually asks for, on the whole percept sequence, and count the rows.

# Rows needed for a table on the WHOLE percept sequence, up to T steps.
# 4 possible percepts, so 4**k sequences of length k.
def rows(T, percepts=4):
    return sum(percepts ** k for k in range(1, T + 1))

for T in (1, 2, 4, 10, 30):
    print("lifetime of %2d steps: %d rows" % (T, rows(T)))

print()
print("a taxi camera at 27 MB/s for one hour of video:")
bits = 27_000_000 * 8 * 3600
print("  %d bits of percept, so 2**%d possible histories" % (bits, bits))

lifetime of  1 steps: 4 rows
lifetime of  2 steps: 20 rows
lifetime of  4 steps: 340 rows
lifetime of 10 steps: 1398100 rows
lifetime of 30 steps: 1537228672809129300 rows

a taxi camera at 27 MB/s for one hour of video:
  777600000000 bits of percept, so 2**777600000000 possible histories

Read the second column. A vacuum cleaner that runs for thirty steps needs a table with more rows than there are seconds in fifty billion years. A taxi's table cannot be written down in this universe.

That is the whole justification for the rest of the paper. The agent function is the right definition of behaviour and the wrong implementation of it. Every technique in Module 1 and Module 2 is a way to COMPUTE the agent function instead of storing it: rules in the next chapter, search after that, logic, probability, and finally a learned model.

The interaction, step by step

An agent and its environment run in a loop, and the order matters.

1. The environment is in some state.
2. The agent's sensors produce a percept from that state.
3. The agent program computes an action from the percept and whatever it has stored.
4. The actuators apply the action, and the environment moves to a new state.
5. The performance measure records something about the new state.
6. Go to 1.

Here is that loop with a real environment on the other side of it, so the agent is not the only thing in the program.

REFLEX = {("A", "Dirty"): "Suck", ("A", "Clean"): "Right",
          ("B", "Dirty"): "Suck", ("B", "Clean"): "Left"}

world = {"A": "Dirty", "B": "Dirty"}   # the environment's state
at = "A"                               # where the agent is
score = 0

for step in range(1, 7):
    percept = (at, world[at])                    # 2. sensors
    action = REFLEX[percept]                     # 3. the agent program
    if action == "Suck":                         # 4. actuators change the world
        world[at] = "Clean"
    elif action == "Right":
        at = "B"
    elif action == "Left":
        at = "A"
    clean = sum(1 for sq in world.values() if sq == "Clean")
    score += clean                               # 5. the performance measure
    print("step %d  percept %-16s action %-6s world %s  clean %d  score %d"
          % (step, str(percept), action, world, clean, score))

step 1  percept ('A', 'Dirty')   action Suck   world {'A': 'Clean', 'B': 'Dirty'}  clean 1  score 1
step 2  percept ('A', 'Clean')   action Right  world {'A': 'Clean', 'B': 'Dirty'}  clean 1  score 2
step 3  percept ('B', 'Dirty')   action Suck   world {'A': 'Clean', 'B': 'Clean'}  clean 2  score 4
step 4  percept ('B', 'Clean')   action Left   world {'A': 'Clean', 'B': 'Clean'}  clean 2  score 6
step 5  percept ('A', 'Clean')   action Right  world {'A': 'Clean', 'B': 'Clean'}  clean 2  score 8
step 6  percept ('B', 'Clean')   action Left   world {'A': 'Clean', 'B': 'Clean'}  clean 2  score 10

Both squares are clean by step 3 and the score keeps rising, which is correct: the measure rewards a clean floor at every step. But look at steps 4 to 6. The agent is walking back and forth across a clean house forever, burning electricity for nothing. The measure did not penalise movement, so the agent has no reason to stop. Add a penalty of one point per move and the same agent becomes the wrong agent, and the next chapter's problem appears: it cannot stop, because with only the current percept it cannot tell "both clean" from "this one clean".

Agent, program and architecture

Three words that get used as though they were one.

Agent = architecture + program. The program cannot ask for an action the actuators cannot perform, and cannot use a percept the sensors do not produce. A program that says "turn left gently" is useless on a robot whose only steering is full lock.

What it does not mean

An agent is not a program with a personality. It is any system with sensors and actuators. A thermostat is an agent. So is a reflex arc.

The agent function is not the agent program. The function is behaviour described from outside; the program is the implementation. Two completely different programs can compute the same function.

A percept is not a fact about the world. It is what the sensors reported. Sensors are limited and can be wrong, which is exactly why Module 1's fourth row exists.

The performance measure is not inside the agent. It is imposed from outside, by the designer, and the agent is judged against it. An agent that scores itself will always score well.

Rationality does not mean the same action every time in the same room. It means the best expected action given the whole percept sequence, and two visits to the same room with different histories can rightly get different actions.

Quick revision

• Agent: perceives through sensors, acts through actuators. Agent = architecture + program.
• Percept, percept sequence, action, agent function (percept sequence to action), agent program (its implementation).
• The function is defined on the whole history because that is the most general description and it covers agents with memory.
• PEAS: Performance measure, Environment, Actuators, Sensors. Write all four before building anything.
• The performance measure decides what "right" means. Measure outcomes in the world, not the agent's own activity, or the agent will manufacture activity.
• A table for the agent function is correct and unbuildable: 4 percepts and 30 steps need over 1.5 quintillion rows. Everything else in this paper is a way to compute the function instead of storing it.
• The loop: state, percept, action, new state, score, repeat.

Test yourself

1. Define an agent, the agent function and the agent program. An agent perceives its environment through sensors and acts on it through actuators. The agent function maps every possible percept sequence to an action, and describes the agent's behaviour from outside. The agent program is the code that computes that function on a particular architecture.

2. What does PEAS stand for, and give a PEAS specification for a spam filter. Performance measure, Environment, Actuators, Sensors. Performance: fraction of messages classified correctly, with a heavy penalty for losing a wanted message. Environment: a user's mailbox and incoming mail. Actuators: label as spam, label as inbox, delete. Sensors: message text, headers, sender address.

3. Why is the agent function defined on the percept sequence rather than the current percept? Because it is the most general description of behaviour and it covers agents that use memory. An agent that depends only on the current percept is a special case of it.

4. A vacuum cleaner is scored on dirt collected per hour. What behaviour does that reward, and what is the fix? It rewards dumping collected dirt back on the floor and collecting it again, because that maximises dirt collected. The fix is to measure the state of the world, a clean floor at each time step, with a penalty for energy used.

5. How many rows would a table-driven agent function need in a world with four possible percepts and a lifetime of ten steps? The sum of 4 to the power k for k from 1 to 10, which is 1,398,100 rows. The program in this chapter computes it.

6. Distinguish a percept from a fact about the environment. A percept is what the sensors reported at an instant; a fact is how the world actually is. Sensors are partial and can be wrong, so the two can differ, which is the whole reason for reasoning under uncertainty.

7. Two students write completely different programs and the two agents behave identically in every situation. Have they implemented the same agent function? Yes. The agent function is the mapping from percept sequences to actions; identical behaviour in every situation is the same mapping. They have implemented the same function with different programs.

Consequence for the agent. In a competitive setting the agent must reason about what the other will do, which is minimax. It may also become rational to behave randomly, to stop the opponent predicting you, which never pays in a single agent setting.

3. Deterministic or stochastic

Deterministic: the next state is fixed completely by the current state and the action taken.

Stochastic: it is not. The same action in the same state can lead to different next states, and the agent can at best have probabilities.

• Deterministic: chess, the 8-puzzle, the vacuum world as defined in the last chapter.
• Stochastic: driving (a tyre may burst), a robot's wheels slipping, any system with real sensors.

"Nondeterministic" is a third word and is not a synonym for stochastic. A nondeterministic environment has several possible outcomes but attaches no probabilities to them, so the agent has to succeed whatever happens. A stochastic one attaches probabilities, so the agent can maximise an expectation.

Consequence for the agent. Determinism is what makes a plan a sequence of actions. Once the environment is stochastic, a plan has to be a policy: what to do in each state that might arise. That is the whole of Module 2's Markov Decision Processes.

4. Episodic or sequential

Episodic: the agent's experience divides into independent episodes. The action taken in one episode has no effect on the next.

Sequential: the current decision affects all future decisions.

• Episodic: classifying a part on a conveyor belt; answering an exam question that stands alone; a spam filter judging one message.
• Sequential: chess, driving, a game of any kind, a course of medical treatment.

Consequence for the agent. In an episodic environment the agent need not think ahead at all, which makes it much easier. Almost all of Module 2's supervised learning is episodic: each prediction stands alone. Almost all of Module 1 is sequential, which is why it is full of search.

5. Static or dynamic

Static: the environment does not change while the agent is deciding.

Dynamic: it does, so time spent thinking is time in which the world moved.

Semidynamic: the environment is static but the agent's SCORE changes with time. Chess with a clock is the standard example: the board does not move while you think, but your remaining time does.

• Static: a crossword, an offline puzzle.
• Dynamic: driving, a robot in a room with people in it.
• Semidynamic: timed chess.

Consequence for the agent. In a dynamic environment the agent must act on incomplete deliberation, so an anytime algorithm that can give its best answer so far matters more than an optimal one that takes too long. This is the practical reason the search chapters report time complexity rather than only correctness.

6. Discrete or continuous

The distinction applies separately to the state, to time, and to the percepts and actions, and a question may ask about any of them.

• Discrete state and time: chess. Finitely many board positions, moves at distinct instants.
• Continuous state and time: driving. Position and speed are real numbers changing smoothly, and steering is a continuous action.
• Mixed: a camera is a discrete sensor sampling a continuous world, and what it delivers is a grid of integers.

Consequence for the agent. Every search algorithm in Module 1 assumes a discrete state space with a finite set of actions at each state. A continuous problem has to be discretised before those algorithms apply, and the discretisation is a design decision that can make the problem easy or impossible.

7. Known or unknown

This is not the same as observable, and mixing the two is the commonest mistake on this topic.

Known: the agent knows the rules. It knows what its actions do, and in a stochastic environment it knows the probabilities.

Unknown: it does not, and it must learn them.

Observability is about the state; knownness is about the laws. All four combinations exist:

Consequence for the agent. An unknown environment is the reason learning exists. It is also the difference between Module 2's Markov Decision Processes, where the model is known and the answer can be computed, and Q-Learning, where it is not and the agent has to find out by acting.

The classification, done

This table is the answer to "classify the following environment", and the six columns are the ones papers use.

Two entries in that table are worth defending, because a marker may disagree and a student should be able to argue.

Spam filter, fully observable. The message is entirely available to the filter; nothing about it is hidden. What is hidden is the sender's INTENTION, but intention is not part of the environment state the filter acts on. Some texts call it partially observable for that reason; say which you mean.

Part-picking robot, episodic. Each part is judged on its own and the bin it goes in does not change how the next part should be judged. If the bins can overflow, it becomes sequential.

The hardest case

The worst case on every dimension at once is partially observable, multi agent, stochastic, sequential, dynamic, continuous and unknown. That is driving in a city you have never visited. It is why the automated taxi is used as the running example of a hard task, and why no algorithm in this paper solves it on its own.

Distinctions

What it does not mean

Fully observable does not mean simple. Chess is fully observable and unsolved.

Deterministic does not mean predictable by the agent. A deterministic environment the agent does not understand is effectively unpredictable to it, which is why "known" is a separate dimension.

Multi agent does not mean many moving objects. It means another entity is choosing, and its choice responds to yours.

Dynamic does not mean fast. It means the state changes while the agent deliberates, however slowly.

Continuous does not mean infinite state only. Time can be continuous while the state is discrete, and the dimensions are asked separately.

Quick revision

• Seven dimensions: observable (fully or partially), agents (single or multi), deterministic or stochastic, episodic or sequential, static or dynamic, discrete or continuous, known or unknown.
• Partially observable forces internal state. Stochastic forces a policy instead of a plan. Sequential forces lookahead. Dynamic forces acting on incomplete deliberation. Continuous forces discretisation. Unknown forces learning. Multi agent forces reasoning about the other, and can make randomising rational.
• Semidynamic: the world is still but the score moves, as in timed chess.
• Nondeterministic is not stochastic: outcomes without probabilities, so the agent must cover every case.
• Observable is about the state; known is about the rules. All four combinations occur.
• Hardest case, and the standing example: partially observable, multi agent, stochastic, sequential, dynamic, continuous, unknown.

Test yourself

1. List the seven dimensions on which a task environment is classified. Fully or partially observable; single or multi agent; deterministic or stochastic; episodic or sequential; static or dynamic; discrete or continuous; known or unknown.

2. Classify the environment of a taxi driving in Mumbai. Partially observable, multi agent, stochastic, sequential, dynamic, continuous and, for an unfamiliar city, unknown. It is the hardest case on every dimension.

3. Distinguish a partially observable environment from an unknown one. Partially observable means part of the current state is hidden from the sensors; unknown means the agent does not know the laws by which the environment behaves. One is fixed by keeping state and reasoning under uncertainty, the other by learning.

4. What is a semidynamic environment? Give an example. One in which the environment itself does not change while the agent deliberates, but the agent's performance score does. Chess played with a clock: the board is still, your remaining time is not.

5. Why does a partially observable environment force an agent to keep internal state? Because the current percept no longer determines the right action, so two situations needing different actions can look identical. The only way to tell them apart is to remember what came before.

6. Is a stone falling towards a robot another agent? No. Its behaviour is not usefully described as maximising a measure that depends on the robot's choices, so it is part of the environment. A second robot that would swerve to avoid a collision is another agent.

7. Which dimension is the reason the whole of Module 2 exists, and why? Known or unknown. If the agent already knew the environment's laws and the right answers, it would need no experience. Learning is the response to not knowing.

The first three steps are perfect. The house is clean by step 3 and there is nothing left to do.

Read steps 4 to 8. The agent walks from B to A to B to A forever, paying a point each time. It cannot stop, and the reason is exactly the architecture: at step 4 its percept is (B, Clean), and the rule for (B, Clean) says Left. It has no way to know that A is also clean, because knowing that would mean remembering step 1, and it remembers nothing.

Final score after eight steps: 8. The next chapter runs the same world with a model and scores 13.

Failure one: it cannot act in a partially observable environment

This is the general statement of what just happened. If two different situations produce the same percept but require different actions, a simple reflex agent must get one of them wrong. It has one rule per percept and the two situations share a percept, so they share the rule.

In the vacuum world, (B, Clean) arises in two situations: A is dirty, so move; and A is clean, so stop. One percept, two right answers, and only one rule available.

This is not a defect in the rules and no better rule table fixes it. It is a limit of the architecture. The information needed is not in the percept, so no function of the percept can produce it.

Failure two: infinite loops

A simple reflex agent in a deterministic environment that returns to an identical percept will repeat exactly what it did last time, and so go round forever. The run above is the whole demonstration: (B, Clean) to Left to (A, Clean) to Right to (B, Clean).

There is one standard escape and it is worth knowing: randomise. A rule that says "if the square is clean, move in a randomly chosen direction" breaks the cycle, because the agent no longer does the same thing at the same percept. In the two-square vacuum world a randomising reflex agent will visit both squares eventually. This is the single case in Module 1 where a random choice is the rational choice, and it happens for the same reason as in a competitive game: predictability is the weakness.

Randomising is a patch and not a cure. It escapes the loop; it still cannot tell the two situations apart, so it still cannot decide to stop.

Where this architecture is the right answer

A simple reflex agent is adequate, and preferable, when the environment is fully observable, so nothing relevant is hidden; and either episodic or such that each percept determines the right action.

Real examples: a thermostat, a lift's door sensor, a traffic light on a timer with a vehicle detector, the collision reflex in a robot vacuum, and a spam filter that judges each message only on the message. Nobody should put a world model in a thermostat.

Distinctions

What it does not mean

"Simple" is not an insult and not a synonym for bad. For a fully observable task it is the correct design and the cheapest.

It is not the same as the table-driven agent. The table-driven agent is indexed by the whole percept sequence and is unbuildable; the reflex agent is indexed by the current percept and is tiny. Confusing the two is the commonest error on this topic.

It has no memory of any kind, not even of its own last action. If it seems to remember, something has been added and it is no longer this architecture.

It is not stateless in the programming sense only. The rules themselves are knowledge, put there by the designer. What it lacks is state that changes as it runs.

Randomising does not make it partially observable capable. It escapes loops and nothing more.

Quick revision

• Simple reflex agent: action from the current percept only, by condition-action rules, IF condition THEN action.
• Complete for the vacuum world in four rules.
• Failure one: two situations with the same percept needing different actions cannot both be handled. It fails whenever the environment is partially observable.
• Failure two: in a deterministic environment it can loop forever, because the same percept always produces the same action.
• The escape from loops is to randomise the choice. It is a patch: it breaks cycles, it does not add knowledge.
• Correct design when the environment is fully observable and the current percept determines the right action: thermostats, door sensors, per-message spam filters.
• On this chapter's world it scores 8; the model-based agent scores 13 on the same world, and the difference is that it can stop.

Test yourself

1. Define a simple reflex agent and give the general form of its rules. An agent that chooses its action from the current percept alone, ignoring history. Its rules have the form IF condition on the current percept THEN action.

2. Write the complete rule set for the two-square vacuum world. If A is dirty, Suck. If A is clean, move Right. If B is dirty, Suck. If B is clean, move Left.

3. Name the two failure modes and give an example of each. It cannot act correctly in a partially observable environment: the percept (B, Clean) arises both when A is dirty and when A is clean, and those need different actions. And it can loop forever: in the same world it moves Left, Right, Left, Right endlessly once both squares are clean.

4. Why can no better set of rules fix the first failure? Because a rule is a function of the percept, and the information needed to distinguish the two situations is not in the percept. No function of the percept can recover it.

5. What is the standard escape from an infinite loop, and what does it not fix? Randomising the action at the repeating percept, which breaks the cycle because the agent no longer does the same thing every time. It does not give the agent the missing information, so it still cannot tell that the work is finished.

6. Give three real systems for which this architecture is the right choice, and say what they have in common. A thermostat, a lift door sensor, a spam filter judging one message. In each case the environment is fully observable for the purposes of the decision, and the current percept determines the correct action.

7. A student says a simple reflex agent has no knowledge. Correct them. It has the knowledge its designer put into the rules, which can be substantial. What it lacks is internal state that changes as it runs, so it cannot accumulate knowledge from experience.

It running, on the same world

Both squares dirty, agent starts in A, one point per clean square per step, minus one per move. Identical to the previous chapter in every respect except the agent.

# A model-based reflex agent: it keeps a MODEL of the parts it cannot see.
class ModelBasedAgent:
    def __init__(self):
        self.model = {"A": "unknown", "B": "unknown"}

    def __call__(self, percept):
        here, dirt = percept
        self.model[here] = dirt                       # update state from percept
        if dirt == "Dirty":
            self.model[here] = "Clean"                # and from the action's effect
            return "Suck"
        other = "B" if here == "A" else "A"
        if self.model[other] == "Clean":
            return "NoOp"                             # nothing left to do: STOP
        return "Right" if here == "A" else "Left"

agent = ModelBasedAgent()
world, at, score = {"A": "Dirty", "B": "Dirty"}, "A", 0
for step in range(1, 9):
    percept = (at, world[at])
    action = agent(percept)
    if action == "Suck":
        world[at] = "Clean"
    elif action == "Right":
        at = "B"
    elif action == "Left":
        at = "A"
    score += sum(1 for v in world.values() if v == "Clean")
    if action in ("Left", "Right"):
        score -= 1
    print("step %d  %-16s %-6s  model %-36s  score %d"
          % (step, str(percept), action, str(agent.model), score))

step 1  ('A', 'Dirty')   Suck    model {'A': 'Clean', 'B': 'unknown'}        score 1
step 2  ('A', 'Clean')   Right   model {'A': 'Clean', 'B': 'unknown'}        score 1
step 3  ('B', 'Dirty')   Suck    model {'A': 'Clean', 'B': 'Clean'}          score 3
step 4  ('B', 'Clean')   NoOp    model {'A': 'Clean', 'B': 'Clean'}          score 5
step 5  ('B', 'Clean')   NoOp    model {'A': 'Clean', 'B': 'Clean'}          score 7
step 6  ('B', 'Clean')   NoOp    model {'A': 'Clean', 'B': 'Clean'}          score 9
step 7  ('B', 'Clean')   NoOp    model {'A': 'Clean', 'B': 'Clean'}          score 11
step 8  ('B', 'Clean')   NoOp    model {'A': 'Clean', 'B': 'Clean'}          score 13

Watch the model column, which is the agent's belief and not the world.

• Step 1: it is in A and sees Dirty. It records Dirty, decides to Suck, and immediately records Clean because it knows what sucking does. That is the transition model in one line.
• Step 2: the percept (A, Clean) is now not enough on its own, and it does not need to be. The model says B is unknown, so there is work to do and it moves right.
• Step 3: B is dirty. Suck, and record it.
• Step 4: the percept is (B, Clean), the identical percept that made the simple reflex agent move. This agent looks at its model, sees A recorded as Clean, and returns NoOp. It has worked out that it is finished.
• Steps 5 to 8: NoOp, costing nothing, scoring 2 every step.

Final score 13, against the simple reflex agent's 8 on the same world. The whole difference is that it can stop, and it can stop because it remembered.

What "unknown" is doing in the model

The initial model is not "both clean" or "both dirty". It is unknown, and that is the honest representation of an agent that has just been switched on. It matters twice.

It stops the agent concluding it is finished before it has looked. If the model started at Clean for both, step 1 would have sucked and step 2 would have returned NoOp with B still filthy.

And it is the first appearance of a theme that runs to the end of the book: an agent's state is a belief, not a fact, and the honest thing to store is what it actually knows. In Module 1's fourth row that belief becomes a probability distribution; in Module 2 it becomes a fitted model. The structure is the same.

Where the model can be wrong

A model-based agent acts on its belief, so a wrong belief produces a wrong action, confidently.

• The world changed and the agent did not see it. Somebody drops dirt in A at step 5. The model still says Clean and the agent sits doing NoOp on a dirty floor. This is what makes a dynamic environment hard.
• The action did not do what the model says. Sucking fails one time in five. The model records Clean, the square is dirty. This is a stochastic environment, and the fix is not a better model of this kind but a probabilistic one.
• The sensors were wrong. The dirt sensor misreports. Then even the directly perceived part of the model is unreliable.

None of these is an argument against keeping a model. They are the argument for keeping a model with probabilities in it, which is Module 1's fourth row, and for learning the model instead of being given it, which is Module 2.

The vocabulary, because two pairs get confused

Distinctions

What it does not mean

The model is not the world. It is what the agent believes. A chapter that blurs the two makes every later error in this book invisible.

It does not store the percept history. It stores a summary sufficient for the decision. Storing the history would be the table-driven agent.

It is still a reflex agent. The final step is still a rule applied to a situation. What changed is that the situation is now the internal state and not the raw percept, which is why the name keeps the word "reflex".

A model does not make the agent correct. It makes it correct as long as the model is. A stale or wrong model produces confident wrong actions.

"Unknown" is not the same as "clean". Initialising a model to a definite value the agent has not observed is a bug, and it is the specific bug that would make this agent stop before it started.

Quick revision

• Model-based reflex agent: keeps internal state, updates it from a transition model (how the world changes, including by its own actions) and a sensor model (how the world appears in percepts), then applies rules to the state.
• The update loop: predict from the last action, correct from the percept, decide, act and remember.
• It solves the simple reflex agent's first failure, because the missing information now comes from the past instead of from the percept.
• On the same vacuum world it scores 13 against the simple reflex agent's 8, and the difference is that it returns NoOp at step 4.
• The state must start as unknown, not as a guessed value.
• It fails when the world changes unseen, when an action does not do what the model says, or when the sensors lie. Those three failures are the reason for probability in Module 1 and learning in Module 2.
• It is still reflex: a rule applied to a situation. Only the situation changed.

Test yourself

1. Define a model-based reflex agent. An agent that maintains internal state representing the parts of the world its percepts do not reveal, updates that state using a transition model and a sensor model, and then applies condition-action rules to the state rather than to the percept.

2. What is the transition model, and what is the sensor model? The transition model says how the world changes, including as a result of the agent's own actions. The sensor model says how the state of the world is reflected in what the sensors report.

3. In this chapter's run, why does step 4 return NoOp when the simple reflex agent moved Left? Both see the percept (B, Clean). The model-based agent also has A recorded as Clean in its internal state, so it can conclude that nothing is left to do. The simple reflex agent has only the percept, which does not contain that fact.

4. Why is the model initialised to "unknown" rather than to "clean"? Because the agent has observed nothing yet. If it began by believing both squares clean, it would return NoOp after cleaning the first square and leave the second dirty.

5. Give three ways the model can become wrong, and name the environment property responsible in each case. The world changes without the agent seeing it, which is a dynamic environment. An action fails to have its expected effect, which is a stochastic environment. The sensors misreport, which is noise and makes even the perceived part unreliable.

6. Is a model-based agent still a reflex agent? Justify. Yes. Its final step is a condition-action rule applied to a situation, with no consideration of goals or of action sequences. What changed is that the situation is the internal state, not the raw percept.

7. Distinguish internal state from the state of the environment. The state of the environment is how the world actually is. Internal state is what the agent has stored about it, which may be incomplete, stale or wrong. The agent acts on the second and is judged on the first.

shortest plan found, length 3: Suck then Right then Suck
start ('A', 'Dirty', 'Dirty')  ->  end ('B', 'Clean', 'Clean')

Three things are worth noticing, and each one is a later chapter.

The plan was found by trying things. Nobody told the agent that sucking first was a good idea. It generated sequences and tested them. That is search in its crudest form.

It found the SHORTEST plan, because it tried short ones first. That is not an accident of this program, it is a property of searching by increasing depth, and it is the whole subject of Breadth First Search and Iterative Deepening Search.

It is wildly wasteful. With three actions, trying all sequences up to length 4 means 3 + 9 + 27 + 81 = 120 sequences, on a problem with only eight states. The rest of MU's second row is about not being this wasteful: keeping track of states already seen, expanding the most promising node first, and using an estimate of how far is left.

Changing the goal changes nothing else

Here is the payoff. To make the goal "both clean and back in A", one line changes:

def is_goal(state):
    return state[0] == "A" and state[1] == "Clean" and state[2] == "Clean"

The transition model, the action list and the search are untouched. A reflex agent would have needed every rule rewritten. That separation is what a goal buys, and it is why goal-based design is where anything resembling flexible behaviour begins.

What a goal cannot do

A goal is binary: a state either satisfies it or it does not. Three consequences follow, and all three are the argument for the next chapter.

It cannot choose between two plans that both succeed. In the run above, Suck then Right then Suck reaches the goal and so does Right then Suck then Left then Suck. The first is shorter and cheaper. The goal test cannot see the difference, because both end in a goal state.

It cannot trade off conflicting goals. Get there quickly and get there safely are both goals, and they disagree. A binary test cannot say how much speed is worth how much risk.

It cannot cope with a goal that cannot be reached with certainty. If sucking works only four times in five, no plan guarantees a clean house. A goal test asks whether the state is good; it has no way to say a 92 per cent chance is better than a 64 per cent chance.

Each of those needs a number on outcomes rather than a yes or no, and a number on outcomes is a utility function.

Goals, and the word planning

MU's third row names Planning basics (STRIPS concept), and this is where the connection is made once so it need not be repeated.

Search and planning are the same activity described at two levels. In search, states are opaque: the algorithm knows only that one state differs from another and that the goal test accepts some of them. In planning, a state is a set of facts and an action says which facts it requires and which it changes. That structure lets a planner reason about a problem far too large to enumerate. Planning and STRIPS is that chapter; the vacuum plan found above is the same idea with the structure thrown away.

Distinctions

What it does not mean

A goal-based agent is not slower than a reflex agent by nature. It does more work per decision, but it can also plan once and then execute. The cost is deliberation, not motion.

Having a goal is not the same as having a plan. The goal is the destination; the plan is the route, and finding it is the work.

The goal test is not a rule. A rule says what to do; the goal test says whether a state is acceptable and says nothing about how to get there.

"Goal-based" does not mean one goal. A goal is a set of acceptable states, which may be described by several conditions. What it cannot do is rank the acceptable ones.

Search is not a synonym for trial and error in the real world. The agent tries sequences in its model, not in the environment. Nothing is sucked while the plan is being found, which is exactly why a transition model is needed.

Quick revision

• Goal-based agent: holds an explicit goal, a description of desirable states, and finds a sequence of actions reaching one, using its transition model. Finding the sequence is search; with structured states and actions it is planning.
• Three parts: current state, transition model, goal test.
• What it buys: the objective is separated from the method, so changing the goal leaves the search machinery untouched.
• On the vacuum world the shortest plan is Suck then Right then Suck, found by trying sequences in increasing length.
• Trying all sequences up to length 4 costs 120 of them on an eight-state problem. Module 1's second row is about doing better.
• What a goal cannot do: rank two plans that both succeed, trade off conflicting objectives, or prefer a higher chance of success. All three need a number on outcomes.
• Search and planning are the same activity: planning is search with states as sets of facts.

Test yourself

1. Define a goal-based agent. An agent holding an explicit representation of a goal, a description of desirable states of the world, which chooses its actions by considering the consequences of sequences of actions under its transition model and selecting a sequence that reaches a goal state.

2. What three components does it need? A representation of the current state, a transition model saying what each action does, and a goal test saying whether a state is acceptable.

3. Why does having a goal force the agent to consider sequences rather than single actions? Because a goal is generally not reachable in one action. To tell whether an action is useful the agent must ask where it leads, and that means evaluating what follows it.

4. What is the shortest plan for the two-square vacuum world starting dirty in A, and how was it found? Suck, then Right, then Suck. It was found by generating sequences of increasing length and testing whether each one ended in a goal state, so the first found is the shortest.

5. Name the three things a goal cannot do, and say what is needed instead. It cannot rank two plans that both reach the goal, cannot trade off conflicting objectives, and cannot prefer a plan with a higher probability of success. All three require a numerical measure of how good an outcome is, which is a utility function.

6. What changes in a goal-based agent if the requirement becomes "clean both squares and finish in square A"? Only the goal test. The transition model, the set of actions and the search procedure are unchanged. In a reflex agent every rule would have to be rewritten.

7. Explain the relationship between search and planning. They are the same activity at different levels of description. In search the algorithm treats states as opaque objects distinguished only by identity and the goal test. In planning a state is a set of facts and each action declares which facts it requires and which it changes, which allows reasoning about problems far too large to enumerate.

The 0.2 subtracted at the end is the electricity. That figure, 3.8, appears in the table below as the expected utility of the one-action plan Suck, so the hand arithmetic and the program agree.

Comparing whole plans

The program pushes a probability distribution over states through each action of a plan, accumulates the cost as it goes, and then computes the expected value of the squares that are clean at the end.

# A utility-based agent. It puts a NUMBER on every outcome, so it can compare two
# plans that BOTH reach the goal, which a goal-based agent cannot.
# Sucking works with probability 0.8. A clean square at the end is worth 5.
# Every move costs 1 and every suck costs 0.2 in electricity.
P_WORKS, MOVE_COST, SUCK_COST, CLEAN_VALUE = 0.8, 1.0, 0.2, 5.0

def step(dist, action):
    """Push a probability distribution over states through one action."""
    out, cost = {}, 0.0
    for (at, a, b), p in dist.items():
        if action == "Suck":
            cost += p * SUCK_COST
            here = a if at == "A" else b
            if here == "Dirty":
                done = (at, "Clean", b) if at == "A" else (at, a, "Clean")
                out[done] = out.get(done, 0.0) + p * P_WORKS
                out[(at, a, b)] = out.get((at, a, b), 0.0) + p * (1 - P_WORKS)
            else:
                out[(at, a, b)] = out.get((at, a, b), 0.0) + p
        elif action in ("Left", "Right"):
            cost += p * MOVE_COST
            nxt = ("A" if action == "Left" else "B", a, b)
            out[nxt] = out.get(nxt, 0.0) + p
        else:
            out[(at, a, b)] = out.get((at, a, b), 0.0) + p
    return out, cost

def expected_utility(plan, start):
    dist, spent = {start: 1.0}, 0.0
    for action in plan:
        dist, cost = step(dist, action)
        spent += cost
    value = sum(p * CLEAN_VALUE * sum(1 for s in st[1:] if s == "Clean")
                for st, p in dist.items())
    return value - spent

start = ("A", "Dirty", "Dirty")
PLANS = [("Suck", "Right", "Suck"),
         ("Suck", "Suck", "Right", "Suck", "Suck"),
         ("Right", "Suck", "Left", "Suck"),
         ("Suck",),
         ()]
print("plan                                           P(goal)  expected utility")
for plan in PLANS:
    d = {start: 1.0}
    for action in plan:
        d, _ = step(d, action)
    pgoal = sum(p for st, p in d.items() if st[1] == "Clean" and st[2] == "Clean")
    label = " then ".join(plan) if plan else "do nothing"
    print("%-44s %7.3f  %15.3f" % (label, pgoal, expected_utility(plan, start)))
print()
best = max(PLANS, key=lambda pl: expected_utility(pl, start))
print("chooses: %s" % (" then ".join(best) if best else "do nothing"))

plan                                           P(goal)  expected utility
Suck then Right then Suck                      0.640            6.600
Suck then Suck then Right then Suck then Suck   0.922            7.800
Right then Suck then Left then Suck            0.640            5.600
Suck                                           0.000            3.800
do nothing                                     0.000            0.000

chooses: Suck then Suck then Right then Suck then Suck

Read the table row by row, because every row settles one of the three things a goal could not do.

Row 1 and row 3 both reach the goal with probability 0.640, and they are exactly the two plans the previous chapter could not choose between. Utility separates them: 6.600 against 5.600. The difference is one extra move, costing 1.

Row 2 is the agent's choice, and it is the interesting one. It sucks twice in each square. That is pointless if sucking always works, and it is the right thing when sucking works four times in five: the probability of finishing rises from 0.640 to 0.922, and the two extra sucks cost only 0.4 between them. A goal-based agent would never have considered it, because one suck already "reaches the goal" in its model.

Row 4 is the single action worked by hand above, 3.800, and it confirms the arithmetic.

Row 5 is doing nothing, worth 0.000, which is the baseline every other row is measured against.

Why utility is the definition of rationality used from here on

The definition in Acting Rationally, or Thinking Like a Human said an agent is rational when it selects the action expected to maximise its performance measure. This chapter is where that sentence becomes computable. Expected utility IS the expected performance measure, and maximum expected utility is the rule that implements the definition.

That is why the same quantity reappears three more times in this book under three more names:

Utility against money, and why the function is not linear

One subtlety that is worth 5 marks and is usually missed. Utility is not the same as the quantity being measured.

Offered a certain 500 rupees or a coin flip for 1,000, most people take the 500, although the expected rupees are identical. That is not irrational. It means their utility for money is not linear: the first 500 rupees is worth more to them than the second 500. An agent whose utility function bends this way is called risk averse; one whose function bends the other way is risk seeking; a straight line is risk neutral.

So a utility function is where an agent's attitude to risk lives. Two agents with the same probabilities and the same money can rationally make opposite choices, because their utility functions differ. There is no single correct utility function to be discovered; there is a designer's choice to be justified.

Distinctions

What it does not mean

Utility is not the performance measure. The performance measure is how the designer judges the agent from outside. The utility function is inside the agent and is what it uses to choose. A well-designed agent has one that leads to a good score on the other, and confusing them makes it impossible to say what went wrong when they diverge.

Maximum expected utility does not mean the best outcome happens. It means the best average over what might happen. An agent that takes the highest expected utility and gets an unlucky result was still rational.

Utility numbers are not probabilities. They are not between 0 and 1 and they do not add to 1. Any scale will do, because only the ordering and the ratios of differences matter.

A higher probability of success is not automatically better. Row 2 of the table wins because the extra certainty is worth more than the extra electricity. Change the electricity cost to 2 per suck and row 1 wins instead. The numbers decide, not the story.

Risk aversion is not a bias to be corrected. It is a shape of utility function, and it is perfectly rational.

Quick revision

• Utility-based agent: uses a utility function from outcomes to real numbers, and where outcomes are uncertain chooses the action of maximum expected utility.
• Expected utility: sum over outcomes of probability times utility. Written out: EU(a) = sum P(outcome) * U(outcome).
• It needs two given things: a utility function and probabilities. Both are design decisions.
• It can do the three things a goal cannot: rank two successes, trade off conflicting objectives, and prefer a better chance.
• On this chapter's world it chooses Suck, Suck, Right, Suck, Suck, which raises the chance of finishing from 0.640 to 0.922 for 0.4 in extra electricity. A goal-based agent could not have considered it.
• Utility is the agent's internal measure; the performance measure is the designer's external one.
• Utility is not linear in the underlying quantity. A curve that bends down is risk averse, a straight line risk neutral, one that bends up risk seeking, and all three are rational.

Test yourself

1. Define a utility-based agent and state the principle it acts on. An agent that maps outcomes to real numbers with a utility function and, where outcomes are uncertain, selects the action whose expected utility is greatest. The principle is maximum expected utility.

2. Write the formula for expected utility and explain each part. EU(a) is the sum over possible outcomes of P(outcome given a) times U(outcome). P is how likely the outcome is, U is how desirable it is, and the sum is the average desirability weighted by likelihood.

3. Compute the expected utility of one Suck on a dirty square, given a success probability of 0.8, a clean square worth 5, and a suck costing 0.2. 0.8 times 5 plus 0.2 times 0, minus 0.2, which is 4.0 minus 0.2, that is 3.8.

4. Two plans both clean the house. Why can a goal-based agent not choose between them, and how does a utility-based agent do so? A goal test returns only yes or no, and both plans end in a goal state, so it is indifferent. A utility function assigns a number that includes the cost of each move, so the shorter plan scores higher, 6.600 against 5.600 in this chapter's run.

5. Why does the agent in this chapter choose to suck twice in the same square? Because sucking succeeds only four times in five. Sucking twice raises the probability of finishing the job from 0.640 to 0.922, and the two extra sucks cost 0.4 in total, which is far less than the extra expected value.

6. Distinguish the utility function from the performance measure. The utility function is internal to the agent and is what it uses to choose actions. The performance measure is external, chosen by the designer, and is what the agent is judged by. A good design makes maximising the first produce a high score on the second.

7. A person prefers a certain 500 rupees to a fair coin flip for 1,000. Is this irrational? Explain in terms of utility. No. The expected number of rupees is the same, but the person's utility for money is not linear: the second 500 rupees adds less utility than the first, so the certain amount has the higher expected utility for them. This shape of utility function is called risk aversion.

# A learning agent. It does NOT know how often Suck works. The CRITIC watches the
# result, the LEARNING ELEMENT updates the estimate, and the PERFORMANCE ELEMENT
# decides from it. Sucking costs 2 and a clean square is worth 5, so sucking is
# worth attempting only while the estimated success rate is above 2/5 = 0.4.
TRUE_P = 0.6          # the environment's real rate. The agent is never told it.
SUCK_COST, CLEAN_VALUE = 2.0, 5.0
THRESHOLD = SUCK_COST / CLEAN_VALUE

def pseudo_random(seed):
    """A deterministic generator, so this book's printed run is reproducible.
    The constants are the ones Numerical Recipes uses for a 32-bit LCG."""
    x = seed
    while True:
        x = (1664525 * x + 1013904223) % (2 ** 32)
        yield x / 2 ** 32

stream = pseudo_random(7)
attempts = successes = 0
print("sucking pays while the estimate is above %.2f" % THRESHOLD)
print()
print("trial  worked?  estimate  the performance element decides")
for trial in range(1, 13):
    worked = next(stream) < TRUE_P                  # the environment decides
    attempts += 1                                   # the critic reports
    successes += 1 if worked else 0
    estimate = (successes + 1) / (attempts + 2)     # the learning element, smoothed
    decision = "Suck" if estimate > THRESHOLD else "do not Suck"
    print("%5d  %-7s  %8.3f  %s" % (trial, "yes" if worked else "no", estimate, decision))
print()
print("after %d trials the estimate is %.3f and the truth is %.1f"
      % (attempts, estimate, TRUE_P))

sucking pays while the estimate is above 0.40

trial  worked?  estimate  the performance element decides
    1  yes         0.667  Suck
    2  no          0.500  Suck
    3  no          0.400  do not Suck
    4  no          0.333  do not Suck
    5  yes         0.429  Suck
    6  no          0.375  do not Suck
    7  yes         0.444  Suck
    8  yes         0.500  Suck
    9  yes         0.545  Suck
   10  no          0.500  Suck
   11  no          0.462  Suck
   12  yes         0.500  Suck

after 12 trials the estimate is 0.500 and the truth is 0.6

Four things in that output, and every one of them is an honest property of learning rather than a defect in the program.

The decision changes as the estimate changes. At trials 3, 4 and 6 the agent has seen enough failures that sucking no longer looks worth the electricity, and it stops. At trial 5 it changes its mind again. The learning element is not producing a number for its own sake; it is changing what the performance element does.

The estimate is wrong, and it should be. After twelve trials it says 0.500 and the truth is 0.6. Twelve observations cannot pin down a probability. A learner's output is an estimate from a sample, and a book that showed it converging neatly on 0.6 in twelve steps would be lying about what learning is like. This is the first appearance of what Bias and Variance makes precise.

Early estimates swing wildly and later ones do not. From 0.667 to 0.333 in three trials, then hardly moving after trial 8. Each new observation is a smaller fraction of the total, so it moves the average less. That is the whole reason more data helps.

The plus one and plus two are doing real work. The estimate is (successes + 1) / (attempts + 2) rather than successes / attempts. With the plain fraction, one failure at trial 1 would give an estimate of exactly 0, the agent would conclude sucking never works, stop trying, and never get another observation to correct itself. This is Laplace smoothing, and The Naive Bayes Classifier uses it again for exactly the same reason: a probability of zero taken from a small sample is a trap that cannot be escaped.

Where the other four architectures sit inside this one

The learning agent does not replace the previous four. The performance element is one of them, and the diagram is the same whichever one it is.

The run above is a learning agent whose performance element is utility-based: it has a utility function it was given and a probability it has to learn.

Where the whole of Module 2 fits in this diagram

This is the table to hold on to, because it is the answer to a Q.3 that crosses the two modules. Every one of MU's Module 2 labels is a piece of machinery for the learning element.

The three forms of learning MU names in her first Module 2 label are three kinds of critic, and that is the cleanest way to hold them apart: supervised has a critic that says what the right answer was, reinforcement has a critic that says only how good the result was, unsupervised has no critic.

What the critic is not

The critic is not a part of the environment and it is not a part of the performance element.

The performance standard the critic applies has to come from outside the agent, and this is a point of substance rather than pedantry. An agent that could rewrite its own standard would improve its score by lowering the bar, which is why the standard is fixed. In supervised learning the standard arrives as labelled data; in reinforcement learning it arrives as a reward signal; in both cases the agent cannot alter it.

The critic is also not the performance measure the designer uses to judge the agent. The critic's standard is a signal inside the agent's learning loop. They should agree, and when they do not, the agent will optimise the one it can see.

Distinctions

What it does not mean

A learning agent is not a separate fifth architecture that replaces the others. It is a wrapper. The performance element is one of the four, and the diagram is the same in each case.

Learning is not only about improving performance on the same task. It is often about discovering what the task actually is, which is what an unknown environment means.

The critic is not the sensors. Percepts say what happened; the critic says whether that was good, by applying a standard the percepts do not contain.

More experience does not guarantee a better estimate on any particular run. It guarantees that the estimate stops swinging. Look at trial 10: a failure moved the estimate down, away from the truth, and that is normal.

The problem generator is not a bug or a source of noise. Deliberately taking a worse action to learn something is the only escape from a local answer, and an agent without it is stuck with whatever it happened to believe first.

Quick revision

• Learning agent: four components. Performance element (chooses actions, and is one of the other four architectures), critic (scores outcomes against a fixed external performance standard), learning element (modifies the performance element), problem generator (proposes informative but suboptimal actions).
• Learning is needed because the designer cannot foresee everything, may not know the answers, and because the environment may be unknown.
• The critic's standard must be external and fixed, or the agent optimises its own scorekeeping.
• The problem generator is the exploration half of exploration against exploitation, which returns in Q-Learning.
• In the run: the estimate changes the decision at trials 3, 4 and 6; the final estimate is 0.500 against a truth of 0.6; early estimates swing and later ones do not.
• Laplace smoothing, the plus one over plus two, stops an early run of failures producing an estimate of exactly zero from which the agent could never recover.
• The three forms of learning are three kinds of critic: supervised says what the right answer was, reinforcement says only how good the result was, unsupervised says nothing.
• The whole of Module 2 is machinery for the learning element.

Test yourself

1. Name the four components of a learning agent and give each one's job. The performance element chooses actions. The critic observes outcomes and reports how well the agent did against a fixed performance standard. The learning element modifies the performance element using that feedback. The problem generator suggests exploratory actions that are informative although not currently best.

2. Why must the performance standard be outside the agent? Because an agent able to change its own standard would raise its score by lowering the standard rather than by acting better. Fixing it externally means the only way to score higher is to improve.

3. What does the problem generator contribute, and what is the problem it addresses called? It proposes actions taken for what they reveal rather than for their immediate value, so the agent can discover options better than its current belief. The problem is exploration against exploitation.

4. In this chapter's run the final estimate is 0.500 while the true rate is 0.6. Is the learner broken? No. Twelve observations are far too few to determine a probability closely. An estimate from a finite sample differs from the truth, and the honest property to expect from more data is that the estimate stops swinging, not that it lands exactly.

5. Why is the estimate computed as (successes + 1) divided by (attempts + 2)? It is Laplace smoothing. The plain ratio would return exactly zero after an early failure, the agent would conclude that sucking never works and stop attempting it, and it would then never observe anything that could correct the belief.

6. How do the three forms of learning map onto the critic? They are three kinds of critic. Supervised learning has a critic that supplies the correct answer for each case. Reinforcement learning has a critic that supplies only a reward saying how good the outcome was. Unsupervised learning has no critic.

7. A student says the learning agent is the fifth and best architecture, replacing the other four. Correct them. The learning agent wraps one of the other four rather than replacing it. Its performance element is a simple reflex, model-based, goal-based or utility-based agent, and what the learning element modifies depends on which: the rules, the transition model, the search model or the utility function and its probabilities.

Two roads in that table are deliberately unusual and both will matter.

Amba to Erandol costs 33 km for a straight-line distance of 12.65. It is the old ghat road, and it goes a long way round a hill. Erandol is genuinely close to the goal and the road to it is terrible. Greedy Best First Search walks straight into it.

Hivra to Jalna costs 16 km for a straight-line distance of 3.16. There is a river between them and the bridge is upstream. Hivra is three km from the goal as the crow flies and seven km from it by road, through Fanas.

Formulated:

• Initial state: in Amba.
• Actions: take any road leaving the current town.
• Transition model: the town at the other end.
• Goal test: is the town Jalna.
• Step cost: the road's length in km. Path cost: the sum.

The state space has nine states, one per town. Note what a state is NOT: it is not the route taken so far. Two agents standing in Chinch, one having come by Amba and one by Bori, are in the same state. That is the single most useful fact about state spaces and the reason The Search Tree, and How an Algorithm Is Judged can talk about avoiding repeated work.

Problem two: the 8-puzzle

Eight numbered tiles in a three by three frame with one blank. A tile next to the blank can slide into it. The goal is a fixed arrangement.

# The 8-puzzle formulated as a search problem. A state is the nine squares read
# left to right, top to bottom, with 0 for the blank.
START = (7, 2, 4,
         5, 0, 6,
         8, 3, 1)
GOAL = (0, 1, 2,
        3, 4, 5,
        6, 7, 8)

def show(state):
    return "\n".join(" ".join("_" if v == 0 else str(v) for v in state[r * 3:r * 3 + 3])
                     for r in range(3))

def actions(state):
    """The blank can move Up, Down, Left or Right, if it stays on the board."""
    i = state.index(0)
    row, col = divmod(i, 3)
    out = []
    if row > 0: out.append("Up")
    if row < 2: out.append("Down")
    if col > 0: out.append("Left")
    if col < 2: out.append("Right")
    return out

def result(state, action):
    i = state.index(0)
    j = i + {"Up": -3, "Down": 3, "Left": -1, "Right": 1}[action]
    lst = list(state)
    lst[i], lst[j] = lst[j], lst[i]
    return tuple(lst)

def is_goal(state):
    return state == GOAL

print("initial state"); print(show(START))
print()
print("actions available:", actions(START))
print()
for action in actions(START):
    print("after %s:" % action)
    print(show(result(START, action)))
    print("   goal reached?", is_goal(result(START, action)))
    print()
print("step cost is 1 for every move, so path cost = number of moves")

initial state
7 2 4
5 _ 6
8 3 1

actions available: ['Up', 'Down', 'Left', 'Right']

after Up:
7 _ 4
5 2 6
8 3 1
   goal reached? False

after Down:
7 2 4
5 3 6
8 _ 1
   goal reached? False

after Left:
7 2 4
_ 5 6
8 3 1
   goal reached? False

after Right:
7 2 4
5 6 _
8 3 1
   goal reached? False

step cost is 1 for every move, so path cost = number of moves

Three formulation decisions in that code are worth defending, because a paper may ask you to justify one.

The actions move the BLANK, not the tiles. Eight tiles with up to four moves each would be thirty-two actions, most of them illegal. The blank has at most four, and every one of them is legal. The two formulations describe the same puzzle and one of them is four times smaller.

A state is a tuple, not a list. A tuple can be put in a set or used as a dictionary key, which is what every search algorithm needs in order to remember where it has been. A list cannot.

Every step costs 1, so the path cost is the number of moves and finding the cheapest path is finding the shortest solution.

Abstraction: what to leave out

A formulation is an abstraction, and choosing it is the real skill.

The road from Amba to Bori has a surface, a gradient, traffic, potholes and a tea stall halfway along. The formulation above keeps one number. That is not laziness; it is a claim, and the claim is testable: any route that is good in the abstract problem can actually be driven. If the abstraction dropped something that made a road impassable, the claim fails and the formulation is wrong.

Two properties make an abstraction valid:

1. Every abstract solution corresponds to a real solution. A sequence of towns can be turned into a real drive.
2. Every abstract action is easier to carry out than the original problem. Driving from Amba to Bori is a smaller problem than driving from Amba to Jalna, and it can be solved without search.

An abstraction that fails the first property produces plans that cannot be executed, and no amount of searching detects it. This is the commonest way a formulation goes wrong in practice and the reason the first property is worth stating explicitly.

How big a state space gets

The state count is what bounds the work, so it is worth being able to compute.

# How big is a state space? Counted, so the reader need not take it on trust.
import math

print("the vacuum world with n squares")
for n in (2, 3, 10):
    print("  %2d squares: %d positions x 2**%d dirt patterns = %d states"
          % (n, n, n, n * 2 ** n))
print()
print("the sliding-tile puzzles")
for tiles, side in ((8, 3), (15, 4), (24, 5)):
    total = math.factorial(side * side)
    print("  %2d-puzzle: %d! = %d arrangements, of which %d are reachable"
          % (tiles, side * side, total, total // 2))

the vacuum world with n squares
   2 squares: 2 positions x 2**2 dirt patterns = 8 states
   3 squares: 3 positions x 2**3 dirt patterns = 24 states
  10 squares: 10 positions x 2**10 dirt patterns = 10240 states

the sliding-tile puzzles
   8-puzzle: 9! = 362880 arrangements, of which 181440 are reachable
  15-puzzle: 16! = 20922789888000 arrangements, of which 10461394944000 are reachable
  24-puzzle: 25! = 15511210043330985984000000 arrangements, of which 7755605021665492992000000 are reachable

Only half the arrangements of a sliding-tile puzzle are reachable from any given one. The set of arrangements splits into two halves and no sequence of legal moves crosses between them, which is why a puzzle bought in a shop with two tiles swapped can never be solved. The 8-puzzle has 181,440 reachable states, which a computer can enumerate; the 24-puzzle has about 7.8 times ten to the twenty-fourth, which it cannot.

Toy problems and real problems

MU's row is taught on toy problems for a reason worth stating: a toy problem has an exact, agreed formulation, so two algorithms can be compared on it. Real problems have no agreed formulation, which makes them useless for comparing algorithms and is why every textbook uses puzzles.

Distinctions

What it does not mean

A state is not a path. Standing in Chinch is one state however you got there. A formulation that put the route into the state would make the state space infinite and the search pointless.

The goal test is not a single goal state. It is a test. "Any arrangement with the blank in the middle" is a perfectly good goal test with many satisfying states.

The path cost is not always the number of steps. It is for the 8-puzzle because each step costs 1. On the map it is kilometres, and the cheapest route has more steps than the shortest one, which is the whole subject of Uniform Cost Search.

Actions are not the same as their effects. The action is the name, "take the road to Bori"; the effect is what the transition model returns. Keeping them separate is what lets the same algorithm solve both problems in this chapter.

Abstraction is not approximation. The abstract problem must be exactly solvable and every abstract solution must be realisable. If the answer is merely close, the formulation is wrong rather than approximate.

Quick revision

• Five components: initial state, actions, transition model (successor function), goal test, path cost (a sum of step costs).
• State space: the graph of states and actions. Expanding a state means generating its successors.
• A state is a configuration, not a route. Two different routes into the same town are the same state.
• The standing map: nine towns, start at Amba, goal Jalna. Two deliberate oddities: Amba to Erandol is 33 km for a 12.65 km straight line, and Hivra to Jalna is 16 km for 3.16.
• The 8-puzzle: a nine-tuple with 0 for the blank; the actions move the blank, which gives at most four legal actions instead of thirty-two mostly illegal ones; a tuple is used so states can be stored in a set.
• Abstraction is valid when every abstract solution is realisable and every abstract action is easier than the whole problem.
• The 8-puzzle has 181,440 reachable states, half of 9!. Only half the arrangements are reachable from any one of them.

Test yourself

1. List the five components of a search problem. The initial state; the actions available in each state; the transition model giving the result of an action; the goal test; and the path cost, normally a sum of step costs.

2. Formulate the district map problem. Initial state: in Amba. Actions: take any road leaving the current town. Transition model: the town at the far end of the road taken. Goal test: is the current town Jalna. Step cost: the road's length in kilometres, and the path cost is their sum.

3. Why do the 8-puzzle's actions move the blank rather than the tiles? Because the blank has at most four moves and every one of them is legal, whereas eight tiles would give thirty-two candidate actions of which most are illegal in any given state. The two formulations describe the same puzzle and the first is four times smaller.

4. What are the two conditions for a valid abstraction? Every solution of the abstract problem must correspond to a solution of the real one, and every abstract action must be easier to carry out than solving the original problem.

5. Two travellers stand in Chinch, one having come from Amba and one from Bori. Are they in the same state? Yes. A state is the configuration of the world, here simply which town you are in. How they arrived is a property of the path, not of the state.

6. How many states does the vacuum world with ten squares have? Ten possible agent positions times two to the power ten dirt patterns, which is 10,240.

7. A shopkeeper's 15-puzzle has two tiles swapped and nobody can solve it. Explain. The arrangements split into two halves and no legal move crosses between them, so exactly half of all arrangements are reachable from the goal. Swapping two tiles moves the puzzle into the unreachable half.

• Frontier, also called the open list: the paths generated but not yet expanded. It is the boundary between the explored and the unexplored.
• Reached or explored set, also called the closed list: the states already dealt with, kept so the search does not do the same work twice.
• Expand: take a node, generate all its children, and put them on the frontier.

A node is not a state, and a node carries four things

A node is a bookkeeping record. To return a route rather than merely announce that one exists, each node must carry:

The programs in this book keep the whole path in a list instead of a parent pointer. That is slightly wasteful of memory and much easier to read, and for a book the second consideration wins. A production implementation keeps the pointer.

Repeated states, and why they must be handled

A search that does not notice it has been somewhere before will, on the district map, generate Amba to Bori to Amba to Bori to Amba forever. Three levels of care are possible and a paper may ask for the difference.

1. Do nothing. Correct only on a tree-shaped state space, where there is exactly one route to each state.
2. Do not go back to the state you just came from, and do not revisit a state already on this path. Cheap, and it removes all cycles. This is what Iterative Deepening Search does.
3. Keep a reached set of every state ever reached. Removes all repeated work, at the cost of memory proportional to the number of states reached.

Option 3 is what makes graph search different from tree search, and the names are examinable: tree search keeps no reached set, graph search does.

The four measures

Completeness. If a solution exists, is the algorithm guaranteed to find it? Depth first search on an infinite space is not complete: it can go down one branch forever while the answer sits on the next branch.

Optimality. Is the solution returned guaranteed to be the cheapest? Note the word cheapest, not shortest. Breadth first search finds the route with the fewest steps, which is not the cheapest whenever steps have different costs. On the district map it finds a 3-hop 26 km route while the cheapest is a 4-hop 25 km route, and that is not a bug in breadth first search: it is optimal in the number of steps and is not claiming anything else.

Time complexity, counted in nodes generated rather than seconds, because seconds depend on the machine and nodes do not.

Space complexity, counted in nodes held at once. This is the measure that decides which algorithms are usable in practice, and students routinely ignore it. An algorithm that needs a hundred million nodes in memory is unusable on a laptop no matter how fast it is, which is exactly why Recursive Best First Search exists.

The three symbols

Every complexity statement in the following chapters is in terms of these, so they are defined once.

For the district map, b is 4, because Chinch, Erandol and Fanas each have four roads. For the 8-puzzle, b is between 2 and 4 depending on where the blank is, and its average is about 2.67.

Why the tree explodes

The number of nodes in a tree of branching factor b down to depth d is 1 plus b plus b squared and so on, which comes to (b**(d+1) - 1) / (b - 1). Written out for real values:

# How big the search tree gets. b is the branching factor, d the depth.
print(" b    d   nodes in the tree   if 100000 nodes a second")
for b in (2, 3, 10):
    for d in (2, 4, 8, 12, 16):
        n = (b ** (d + 1) - 1) // (b - 1)
        secs = n / 100000
        if secs < 60:
            when = "%.1f seconds" % secs
        elif secs < 3600:
            when = "%.1f minutes" % (secs / 60)
        elif secs < 86400 * 365:
            when = "%.1f days" % (secs / 86400)
        else:
            when = "%.0f years" % (secs / 86400 / 365)
        print("%2d %4d %19d   %s" % (b, d, n, when))

 b    d   nodes in the tree   if 100000 nodes a second
 2    2                   7   0.0 seconds
 2    4                  31   0.0 seconds
 2    8                 511   0.0 seconds
 2   12                8191   0.1 seconds
 2   16              131071   1.3 seconds
 3    2                  13   0.0 seconds
 3    4                 121   0.0 seconds
 3    8                9841   0.1 seconds
 3   12              797161   8.0 seconds
 3   16            64570081   10.8 minutes
10    2                 111   0.0 seconds
10    4               11111   0.1 seconds
10    8           111111111   18.5 minutes
10   12       1111111111111   128.6 days
10   16   11111111111111111   3523 years

Read down the last block. At a branching factor of 10, depth 8 takes about twenty minutes and depth 12 takes four months. Four more levels multiplied the work by ten thousand. No faster computer fixes this: a machine a thousand times faster buys three more levels. The only thing that helps is not generating most of the tree, and that is what the heuristic chapters are for.

The table every following chapter fills in

Two rows of that table are the whole story of the row. Breadth first search has O(bd) SPACE, and that is what kills it: at b of 10 and d of 12, a hundred gigabytes of frontier. Iterative deepening has O(b*d) space** for the same time complexity, which is why it is the standard uninformed search rather than breadth first.

Distinctions

What it does not mean

Optimal does not mean shortest. It means least total path cost. Breadth first search finds the fewest steps; that is only the cheapest when all steps cost the same.

Complete does not mean it will finish quickly. A complete algorithm on a large space may take longer than the age of the universe and still be complete.

The search tree is not drawn in advance. It is generated as the algorithm runs, and a good algorithm generates only a small part of it.

b is the branching factor of the STATE SPACE, not of the tree drawn. It does not change when you change algorithms.

A node is not a state. One state can appear in many nodes, one per route reaching it, and it is precisely because of that that the reached set exists.

Quick revision

• State space: nodes are states, a property of the problem. Search tree: nodes are paths, a property of the search, and can be infinite where the state space is finite.
• The general algorithm: put the start on the frontier, then repeatedly take a path off it, goal-test it, and expand. The only difference between the six algorithms is which path is taken off the frontier.
• A node carries state, parent, action and path cost g.
• Tree search keeps no reached set and can loop; graph search keeps one and cannot.
• Four measures: completeness, optimality (cheapest, not shortest), time in nodes generated, space in nodes held at once.
• b branching factor, d depth of the shallowest goal, m maximum depth.
• Tree size is (b(d+1) - 1) / (b - 1). At b of 10, depth 8 takes minutes and depth 12 takes months: four levels cost a factor of ten thousand.**
• Space is usually the binding constraint. Breadth first is O(b**d) in space; iterative deepening is O(b*d) for the same time.

Test yourself

1. Distinguish the state space from the search tree. The state space is the graph of states and actions belonging to the problem; it has one node per state and does not depend on the algorithm. The search tree has one node per path examined, is built as the search runs, and can be infinite on a state space with cycles.

2. Give the general form of a search algorithm and say what distinguishes the individual algorithms. Put the initial path on the frontier; repeatedly remove a path, test its final state against the goal, and expand it by adding extended paths to the frontier. The algorithms differ only in which path is removed from the frontier.

3. What four things does a node carry, and why each? The state, to test the goal and find the actions; the parent, to reconstruct the path; the action taken, so the answer can be given as actions; and the path cost so far, needed by uniform cost search and A*.

4. Name the four evaluation criteria and define each. Completeness, whether a solution is found if one exists. Optimality, whether the solution found has least cost. Time complexity, the number of nodes generated. Space complexity, the number of nodes held in memory at once.

5. Breadth first search returns a 26 km route on the district map when a 25 km route exists. Is it broken? No. It is optimal in the number of steps, and it returns the route with fewest steps, which is three. The 25 km route has four steps. Breadth first search is only cost-optimal when every step costs the same.

6. Define b, d and m, and give b for the district map. b is the branching factor, the largest number of successors of any node; d is the depth of the shallowest goal; m is the maximum depth of the space. For the district map b is 4, since Chinch, Erandol and Fanas each have four roads.

7. Why is space complexity usually the binding constraint rather than time? Because memory runs out before patience does. Breadth first search at branching factor 10 and depth 12 would need of the order of a hundred gigabytes for its frontier, so it cannot be run at all, whereas an algorithm with the same time complexity and linear space can be left to run.

 1  expand Amba     frontier now                                        reached 1
 2  expand Bori     frontier now Chinch Erandol                         reached 4
 3  expand Chinch   frontier now Erandol Devi                           reached 5
 4  expand Erandol  frontier now Devi Gokul                             reached 6
 5  expand Devi     frontier now Gokul Fanas                            reached 7
 6  expand Gokul    frontier now Fanas Hivra                            reached 8

route found: Amba > Chinch > Gokul > Jalna
hops: 3  cost: 26 km

Follow it as levels, because that is the behaviour to be able to describe.

• Step 1, depth 0. Amba is expanded and its three neighbours Bori, Chinch and Erandol go on the queue. reached becomes 4.
• Steps 2 to 4, depth 1. Bori, Chinch and Erandol are expanded, in the order they were queued. Their new neighbours Devi and Gokul are added behind them.
• Steps 5 and 6, depth 2. Devi and Gokul. When Gokul is expanded, one of its neighbours is Jalna, the early goal test fires, and the search stops.

Six expansions, and Hivra was never expanded at all. The route returned has three hops, which is the fewest possible, and costs 26 km.

The 1 km that matters

The cheapest route on this map is Amba, Bori, Devi, Fanas, Jalna at 25 km, and breadth first search did not find it. It has four hops, and breadth first search stopped as soon as it found a three-hop route.

That is not a defect. Breadth first search promises the fewest steps and delivered it. It promises least COST only when every step costs the same, and on this map they do not: roads are 2 km to 33 km. When a paper asks "is breadth first search optimal", the full-mark answer is: yes in the number of steps, and in cost only if all step costs are equal.

The 1 km gap looks small and the general case is not small. Change Amba to Chinch to 100 km and breadth first search still returns the same three-hop route, now at 119 km against an unchanged 25 km. The size of the error is unbounded; only the number of steps is controlled.

Memory is the real problem

The frontier at depth k holds up to bk nodes, so the peak is O(bd). The time is the same order, and those two facts are not equally bad.

Take the figures from The Search Tree, and How an Algorithm Is Judged at a branching factor of 10 and a depth of 12: about 1.1 million million nodes. At a hundred thousand nodes a second that is 128 days, which is merely annoying. Holding a thousand million million nodes in memory is impossible.

So breadth first search is beaten by memory long before it is beaten by time, and that is the single most useful thing to say about it. It is the reason Iterative Deepening Search exists: the same time complexity, O(b*d) space instead of O(b**d).

Where it is the right choice

• The state space is small enough to fit, which includes most examination questions.
• Every step costs the same, so it is genuinely optimal. This is common: the 8-puzzle, a word ladder, the fewest-moves version of any puzzle.
• You want the shallowest solution specifically, for instance the smallest number of moves rather than the lowest total cost.
• The branching factor is small.

Distinctions

What it does not mean

Breadth first search is not optimal in general. It is optimal in the number of steps, and in cost only when every step costs the same. Saying "BFS is optimal" without that condition is a lost mark.

It does not use less memory than depth first search. It uses vastly more: exponential in the depth against linear.

The queue does not hold states. It holds paths, or nodes carrying a parent pointer. A frontier of bare states cannot return the route.

It does not stop at the first node it generates that happens to be a goal in some other branch. It stops at the first goal generated at all, and because it works level by level, that goal is at minimum depth.

Reaching a state is not the same as expanding it. In the run above Hivra was reached but never expanded, and the distinction is what reached counts.

Quick revision

• Breadth first search: expand the shallowest unexpanded node. Frontier is a FIFO queue.
• Level order follows from the queue: children are newer than everything on the frontier, so depth k is finished before depth k plus 1 begins.
• Early goal test, applied when a child is generated. Safe here; not safe for uniform cost search.
• Add a state to reached when it is generated, not when it is expanded.
• Complete if b is finite. Optimal in the number of steps, and in cost only if every step cost is equal.
• Time O(bd), space O(bd). Memory is what defeats it, not time.
• On the standing map: 6 expansions, route Amba, Chinch, Gokul, Jalna, 3 hops, 26 km, against a cheapest route of 25 km in 4 hops.
• Right choice when the space is small, the step costs are uniform, or the shallowest solution is what is wanted.

Test yourself

1. Define breadth first search and name its frontier data structure. It expands the shallowest unexpanded node. The frontier is a first in, first out queue, so nodes are expanded in the order they were generated.

2. Prove that breadth first search expands nodes in order of depth. A node's children are generated when it is expanded, so they are newer than everything already on the frontier. A queue serves the oldest first, so no node at depth k plus 1 is served while any node at depth k remains. Hence all of depth k is expanded before any of depth k plus 1.

3. Is breadth first search optimal? State the condition exactly. It is optimal in the number of steps, always. It is optimal in path cost only when every step has the same cost.

4. On the standing district map breadth first search returns a 26 km route while a 25 km route exists. Explain. It returns the route with fewest hops, which is Amba, Chinch, Gokul, Jalna at three hops and 26 km. The cheaper route, Amba, Bori, Devi, Fanas, Jalna, costs 25 km but takes four hops, so the search finished before reaching it. The road costs on this map are unequal, so the optimality condition does not hold.

5. What are its time and space complexities, and which one rules it out in practice? Both are O(b**d). Space rules it out: at a branching factor of 10 and depth 12 the time is months, which is tolerable, while the memory required is far beyond any machine.

6. What is the early goal test and why is it safe here but not for uniform cost search? The early test checks each child for being a goal as it is generated, saving a level of expansion. It is safe here because the first goal generated is at minimum depth. In uniform cost search the first goal generated need not be the cheapest, so the test must wait until the node is selected for expansion.

7. In this chapter's run, reached ends at 8 but only 6 nodes were expanded. What is the difference? A state is reached when a path to it has been generated and put on the frontier. It is expanded when it is taken off the frontier and its own children are generated. Fanas and Hivra were reached and never expanded, because the search stopped first.

 1  expand Amba     depth 0  path Amba
 2  expand Bori     depth 1  path Amba > Bori
 3  expand Chinch   depth 2  path Amba > Bori > Chinch
 4  expand Erandol  depth 3  path Amba > Bori > Chinch > Erandol
 5  expand Fanas    depth 4  path Amba > Bori > Chinch > Erandol > Fanas
 6  expand Devi     depth 5  path Amba > Bori > Chinch > Erandol > Fanas > Devi
 7  expand Hivra    depth 6  path Amba > Bori > Chinch > Erandol > Fanas > Devi > Hivra
 8  expand Jalna    depth 7  path Amba > Bori > Chinch > Erandol > Fanas > Devi > Hivra > Jalna

route found: Amba > Bori > Chinch > Erandol > Fanas > Devi > Hivra > Jalna
hops: 7  cost: 68 km

Read the depth column: 0, 1, 2, 3, 4, 5, 6, 7. It never goes back up once, because on this small map every town it reaches has an unvisited neighbour. That is depth first search in its purest form.

The route it returns is seven hops and 68 km. The cheapest is 25 km and the fewest hops is three. It went from Fanas to Devi to Hivra to Jalna when it was standing next to Jalna at Fanas with a 5 km road to it: at step 5 the stack's newest entry was the Devi branch, so that is where it went.

It also passed within one road of the goal at step 5 and did not notice, because the goal test is applied when a node is expanded and Jalna was not expanded until step 8. That is not a bug to be fixed by testing children early. Testing early in depth first search would make it return the first goal it stumbles on, which is still not optimal and would hide nothing.

Why depth first search is in the syllabus at all

The answer is one column of the table, and it is worth being precise about.

Space is O(b*m), linear. The frontier holds only the untried siblings along the current path: at most b siblings at each of at most m levels. At a branching factor of 10 and a depth of 12 that is about 120 nodes, against breadth first search's thousand million million.

That is the whole case, and it is a strong one. Depth first search can run on a problem breadth first search cannot be started on. Every good uninformed algorithm in this row is a way of keeping that memory behaviour while recovering the properties depth first search throws away, and Iterative Deepening Search is the one that succeeds.

The two failures, exactly stated

It is not optimal. It returns the first goal on the first branch that reaches one, and that branch has nothing to recommend it. Here: 68 km against 25.

It is not complete in tree search. Two separate cases, and both should be named.

• On an infinite space it can descend forever down a branch with no goal on it, and the answer sitting one step to the right is never examined.
• On a finite space with cycles it can loop: Amba to Bori to Amba to Bori, forever. The run above avoided this only because of the visited set.

So there are really three algorithms wearing this name, and papers distinguish them:

The program above is the third. It is complete on this map, and its space is no longer linear, which costs the algorithm its one advantage. The middle row is the useful compromise and is exactly what Iterative Deepening Search uses.

Depth limited search

The obvious patch for the infinite branch is to refuse to go below a fixed depth L. That is depth limited search, and it has its own properties:

• Complete only if L is at least d. Set the limit too low and it reports failure when a solution exists.
• Not optimal, for the same reason as before.
• Time O(b**L), space O(b*L).

Its return value has three cases, not two, and the third is the one that matters: solution, failure (no solution exists), or cutoff (none was found within the limit, and one may exist deeper). A program that merges cutoff with failure will report that a solvable problem has no answer.

Depth limited search is the building block of the next chapter, which removes the need to guess L at all.

Distinctions

What it does not mean

Depth first search is not faster than breadth first search. Its time complexity is worse, O(bm) against O(bd), because m can be much larger than d. Its advantage is memory only.

It is not complete just because it terminated once. Termination on one problem says nothing. In tree search on a cyclic or infinite space it is not complete, and that is a property of the algorithm.

The visited set is not part of plain depth first search. Adding it makes the algorithm complete on a finite space and destroys its linear space, which is the trade-off to state, not to hide.

Backtracking is not a separate algorithm. It is what depth first search does when a branch is exhausted.

A bad answer is not a bug here. Depth first search never promised a good one. Judging it by the route it returned is judging it against a promise it did not make.

Quick revision

• Depth first search: expand the deepest unexpanded node. Frontier is a LIFO stack. Recursively, the call stack is the frontier.
• Not optimal. Not complete in tree search: it can descend an infinite branch forever, and it can cycle on a finite graph.
• Time O(bm), space O(b*m). The linear space is its entire justification**: about 120 nodes where breadth first search needs a thousand million million.
• Three variants: tree search (incomplete, linear space), cycle checking on the current path (complete on a finite space, still linear), graph search with a visited set (complete, space proportional to the number of states).
• On the standing map: 8 expansions, seven hops, 68 km, passing one road from the goal at step 5 without noticing, because the goal test is applied on expansion.
• Depth limited search: refuse to go below L. Complete only if L is at least d, not optimal, time O(bL), space O(b*L). Its answer has three cases: solution, failure, cutoff**.

Test yourself

1. Define depth first search and give its frontier data structure. It always expands the deepest unexpanded node. The frontier is a last in, first out stack; in the recursive form the machine's own call stack serves as the frontier.

2. State its four properties with the conditions. Not optimal. Not complete in tree search, either on an infinite space or on a finite space with cycles. Time O(b**m) where m is the maximum depth. Space O(b*m), which is linear.

3. Why is it in the syllabus at all, given that it is neither complete nor optimal? Because of its memory. It holds only the untried siblings along one path, at most b at each of m levels, so it can be run on problems where breadth first search cannot even be started.

4. In this chapter's run the search stood at Fanas, one 5 km road from the goal, and went to Devi instead. Explain. The goal test is applied when a node is expanded, not when it is generated, and the stack served the most recently pushed branch, which was Devi. Jalna was not expanded until step 8.

5. Give the three variants of depth first search and the property each has. Tree search, which keeps nothing and is not complete but uses linear space. Cycle checking against the current path, which is complete on a finite space and still uses linear space. Graph search with a set of every visited state, which is complete but uses space proportional to the number of states.

6. What are the three possible results of depth limited search, and why does the third matter? A solution, failure, or cutoff. Cutoff means no solution was found within the limit although one may exist deeper. Merging cutoff with failure makes the program report that a solvable problem has no solution.

7. A student claims depth first search is faster than breadth first search because it goes straight down. Correct them. Speed is measured in nodes generated. Depth first search is O(bm) and breadth first search is O(bd), and m can be far larger than d, so depth first search is generally slower. Its advantage is space, not time.

 1  expand Amba     g= 0  cheapest waiting:
 2  expand Chinch   g= 7  cheapest waiting: Bori(8) Erandol(33)
 3  expand Bori     g= 8  cheapest waiting: Amba(14) Erandol(14) Bori(19) Gokul(20) and 1 more
 4  expand Devi     g=13  cheapest waiting: Amba(14) Erandol(14) Amba(16) Bori(19) and 3 more
 5  expand Erandol  g=14  cheapest waiting: Amba(16) Bori(18) Bori(19) Chinch(20) and 4 more
 6  expand Fanas    g=20  cheapest waiting: Gokul(20) Gokul(20) Chinch(21) Hivra(22) and 3 more
 7  expand Gokul    g=20  cheapest waiting: Gokul(20) Chinch(21) Hivra(22) Hivra(22) and 6 more
 8  expand Hivra    g=22  cheapest waiting: Hivra(22) Fanas(23) Jalna(25) Erandol(26) and 6 more
 9  expand Jalna    g=25  cheapest waiting: Erandol(26) Jalna(26) Devi(27) Erandol(29) and 5 more

route found: Amba > Bori > Devi > Fanas > Jalna
hops: 4  cost: 25 km

Read the g column: 0, 7, 8, 13, 14, 20, 20, 22, 25. It never decreases, and that is the invariant the whole proof rests on. The algorithm expands states in increasing order of their cheapest cost from the start.

Four moments are worth naming.

Step 2 expands Chinch at 7, not Bori at 8. Breadth first search would have taken Bori first because it was generated first. Order here is by cost, and 7 beats 8.

Step 5 expands Erandol at g of 14, having reached it by Chinch, not by the 33 km ghat road from Amba. That road is still sitting on the frontier at 33 and will never be used.

Steps 6 and 7 are both at g of 20. Fanas and Gokul tie, and which goes first is arbitrary. It does not matter: both are expanded before anything dearer.

Step 8 expands Hivra at 22, and Jalna is already on the frontier at 25. This is the exact moment the late goal test earns its place. A route to the goal has been FOUND, at 25, and the algorithm does not take it, because 22 is cheaper than 25 and the Hivra branch might still reach the goal for less. It cannot, as it happens: Hivra to Jalna is the 16 km river road, giving 38. But the algorithm does not know that until it looks, and looking is what makes it optimal.

Why it is optimal

The argument is three lines and is worth being able to write.

1. Whenever a node is selected for expansion, every remaining path on the frontier costs at least as much, because the queue is ordered on g and the cheapest was taken.
2. Since every step cost is greater than zero, extending any of those paths can only make it dearer.
3. So no cheaper path to the selected node can exist anywhere, found or unfound. In particular the first time the GOAL is selected, its g is the cost of the cheapest route to it.

Step 2 is where the condition lives. If a step could cost zero, or less, the argument fails, because extending a path would not increase its cost and a cheaper route could still appear. That is why the completeness and optimality of uniform cost search are stated with "every step cost is positive", and why a road of zero length would break the algorithm rather than merely being odd.

The relationship with three other algorithms

Uniform cost search sits at the centre of this row, and saying how it relates to its neighbours is a strong answer to a Q.3.

With breadth first search. If every step costs the same, ordering by cost is ordering by depth, and the two algorithms expand nodes in the same order. So breadth first search is uniform cost search with uniform step costs, and that is where its optimality in steps comes from.

With Dijkstra's algorithm. Uniform cost search IS Dijkstra's algorithm, arrived at from the direction of agent design instead of graph theory. The difference is in emphasis: Dijkstra's algorithm computes the cheapest route from the start to every node, while uniform cost search stops as soon as the one node it wants has been selected. On a large graph with one destination, stopping early is the whole saving.

With A. Uniform cost search orders on g(n). A orders on g(n) + h(n). So uniform cost search is A with h equal to zero everywhere, and since zero never overestimates, it is A with a trivially admissible heuristic. Three chapters from now that sentence explains why A* inherits optimality.

Its complexity

Time and space are not naturally expressed in b and d here, because the algorithm counts cost rather than steps. The standard statement uses the cheapest solution cost C* and the smallest step cost e:

Read that as: the effective depth is not the number of steps in the answer but the number of cheapest possible steps that would fit inside the answer's cost. It can be much worse than O(bd).** With a solution costing 25 and a smallest step of 2, the exponent is 13 even though the answer is only four steps long, because the algorithm must rule out every route made of very cheap steps before it can be sure.

That is the real cost of optimality, and it is the honest reason to reach for a heuristic: A* gets the same optimality while expanding fewer nodes.

Distinctions

What it does not mean

It is not breadth first search with a priority queue bolted on. The goal test moved too, and moving it is half the algorithm.

"Uniform" does not describe the costs. It describes the contour the search expands: it grows outwards in uniform bands of equal cost. The step costs are precisely what is allowed to be non-uniform.

Optimal does not mean it expands few nodes. It expanded nine here against breadth first search's six, and its complexity can be far worse than O(b**d). It buys correctness with work.

A zero-cost step is not a harmless special case. It breaks the optimality argument and can make the search fail to terminate.

It does not need to know the total cost in advance. C* appears in the complexity statement as an analysis of the algorithm, not as an input to it.

Quick revision

• Uniform cost search: expand the node of lowest path cost g(n), frontier a priority queue on g.
• Late goal test: on selection, never on generation. The early test returns 26 km on the standing map instead of 25.
• Discard a route to a state already settled more cheaply.
• Complete and optimal provided every step cost is positive. Zero-cost steps break the argument.
• The g of expanded nodes never decreases; that invariant is the proof.
• Complexity O(b (1 + floor(C/e))) where C is the cheapest solution cost and e the smallest step cost. Can be much worse than O(bd).
• Breadth first search is this algorithm with uniform step costs. A* is this algorithm with h added to g. It is Dijkstra's algorithm that stops early.
• On the standing map: 9 expansions, route Amba, Bori, Devi, Fanas, Jalna, 25 km in 4 hops.

Test yourself

1. Define uniform cost search and give the ordering of its frontier. It expands the node with the lowest path cost from the start, g(n). The frontier is a priority queue ordered on g.

2. Why must the goal test be applied on selection rather than on generation? Because the first goal generated need not be the cheapest one. On the standing map Gokul generates Jalna at a cost of 26 before Fanas generates it at 25, so an early test returns the dearer route. Testing on selection guarantees that no cheaper route remains.

3. Prove that uniform cost search is optimal. When a node is selected, every path left on the frontier costs at least as much, since the cheapest was taken. Every step cost is positive, so extending any of those paths only increases its cost. Therefore no cheaper route to the selected node exists, and in particular the first selection of the goal is by the cheapest route.

4. What condition does that proof need, and what breaks without it? Every step cost must be strictly positive. With a zero or negative step cost, extending a frontier path need not make it dearer, so a cheaper route to an already-selected node could still appear and the algorithm would not be optimal.

5. At step 8 of the run, Jalna is already on the frontier at 25 and the algorithm expands Hivra at 22 instead. Why is that correct? Because 22 is less than 25 and the Hivra branch might still reach the goal more cheaply. The algorithm cannot know that it will not without looking, and looking is what guarantees optimality.

6. State the relationship between uniform cost search, breadth first search and A. With every step cost equal, ordering by cost is ordering by depth, so breadth first search is uniform cost search with uniform costs. A orders on g plus a heuristic estimate h, so uniform cost search is A* with h equal to zero everywhere.

7. Give the complexity of uniform cost search and explain why it can be worse than O(bd). O(b (1 + floor(C/e))), where C is the cost of the cheapest solution and e the smallest step cost. The effective depth is how many minimum-cost steps would fit inside the solution's cost, which can far exceed the number of steps the solution actually has, because every route made of cheap steps must be ruled out first.

limit 0:   0 nodes generated, running total   0, cut off with no solution
limit 1:   3 nodes generated, running total   3, cut off with no solution
limit 2:  11 nodes generated, running total  14, cut off with no solution
limit 3:  16 nodes generated, running total  30, Amba > Chinch > Gokul > Jalna

route found: Amba > Chinch > Gokul > Jalna
hops: 3  cost: 26 km
total nodes generated over all four passes: 30
the last pass alone generated: 16 so the repeated work was 14 nodes, 47% of the total

Why repeating the work costs less than it looks

This is the part that seems wrong and is not, and it is the highest-value thing in the chapter.

Look at where the nodes are in a tree. A tree of branching factor b has bd nodes at the bottom level, b(d-1) at the level above, and so on. The bottom level holds more nodes than all the levels above it put together whenever b is 2 or more. Iterative deepening generates the bottom level once, the level above it twice, the level above that three times, and the root d plus 1 times.

So the total is

and the dominant term is the last one, bd, exactly as for breadth first search. The extra passes multiply the SMALL levels many times and the BIG level once, which is why the total stays O(bd).

At a branching factor of 10 and a depth of 5 the standard figures are 111,111 nodes for breadth first search against 123,456 for iterative deepening, which is about 11 per cent more. That is the price, and it buys a reduction in memory from O(b**d) to O(b*d).

On the nine-town map the repeated work is 47 per cent of the total, not 11, and the chapter prints that honestly. The reason is that b is small and d is small, so the "bottom level dominates" argument barely applies. The asymptotic result is about large problems, and quoting it on a nine-node example would be quoting a theorem outside its range.

What Korf actually proved

Korf's 1985 paper is titled Depth-first iterative-deepening: an optimal admissible tree search, and the claim worth stating precisely is stronger than "it is a reasonable compromise":

Among brute-force tree searches, that is among searches using no information about the problem beyond the goal test, depth first iterative deepening is asymptotically optimal in time, in space, and in the cost of the solution found. There is nothing better to be had without a heuristic.

Two conditions in that sentence and both matter. Brute-force: the moment a heuristic is available, A is better, and Korf's own later paper gives the heuristic version, IDA. Tree search: it keeps no reached set, so on a graph with many routes to the same state it re-derives them; that is the price of the linear memory.

Cycle checking, and what this algorithm keeps

The program above contains if child in path: continue. That is the middle of the three options from The Search Tree, and How an Algorithm Is Judged: it checks the current path only, not every state ever seen.

That choice is exactly right for this algorithm and worth being able to defend. Checking the current path costs nothing extra in memory, because the path is already held, and it removes every cycle. Keeping a full reached set would remove more repeated work and would destroy the O(b*d) space that is the entire reason for using iterative deepening at all.

Where it stands in the row

Iterative deepening is the default uninformed search, and the reason can be given in one sentence: it is the only algorithm in the row with breadth first search's guarantees and depth first search's memory. Breadth first search is used when the space is small enough not to care, and depth first search when the answer's quality does not matter.

It shares breadth first search's limitation exactly: it finds the shallowest goal, so it is optimal in the number of steps and not in cost. On the standing map it returns the same 26 km three-hop route breadth first search found, not the 25 km four-hop route. The cost-aware version exists and is called iterative lengthening search, which iterates on a cost bound instead of a depth bound; MU does not set it, and the heuristic answer in A* is better anyway.

Distinctions

What it does not mean

It is not wasteful in the way it looks. The repeated passes re-generate the small levels, not the big one, so the total stays the same order as breadth first search. On a small problem the fraction is large; the result is about large ones.

It is not optimal in cost. It is optimal in the number of steps. On the standing map it returns 26 km, not 25.

It does not keep a reached set, and adding one would remove the very property it exists for.

The limit is not a guess that might be wrong. Every limit is tried in order, so the first solution found is at the shallowest depth any solution occupies.

IDA is not in this chapter. It is the heuristic version of this idea, and the estimate it iterates on is f, not depth. The relevant chapters here are A and Recursive Best First Search.

Quick revision

• Iterative deepening: depth limited search at limit 0, 1, 2, and so on until a goal is found.
• Complete if b is finite; optimal in the number of steps if step costs are equal; time O(b**d); space O(b*d).
• The three-way return of depth limited search, solution, failure, cutoff, is what makes the loop terminate.
• Repeating work is cheap because the bottom level of a tree holds more nodes than all the levels above it together: the extra passes multiply the small levels, not the big one. About 11 per cent extra at b of 10, d of 5.
• On the nine-town map the repeated work is 47 per cent, because b and d are both tiny. The asymptotic result does not apply at that size, and the chapter does not pretend it does.
• Korf 1985: among brute-force tree searches it is asymptotically optimal in time, space and solution cost. Conditions: brute force, and tree search.
• It checks cycles against the current path only, because a full reached set would destroy its linear space.
• It is the default uninformed search. On the standing map: route Amba, Chinch, Gokul, Jalna, 3 hops, 26 km, 30 nodes generated over four passes.

Test yourself

1. Define iterative deepening search. It performs depth limited search with a limit of 0, then 1, then 2, and so on, until a solution is found, thereby finding the shallowest goal while each individual pass uses only linear memory.

2. State its four properties with conditions. Complete if the branching factor is finite. Optimal in the number of steps if every step costs the same. Time O(b**d). Space O(b*d).

3. Why does repeating the work not make the time complexity worse? Because in a tree with branching factor two or more, the deepest level holds more nodes than all shallower levels combined. Iterative deepening generates the deepest level once and the shallow levels several times, so the dominant term is still b**d.

4. On the nine-town map the repeated work was 47 per cent of the total. Does that contradict the previous answer? No. The argument is asymptotic and depends on the deepest level dominating, which needs b and d to be reasonably large. With b of 4 and d of 3 the shallow levels are a large share of a small tree, so the fraction is high. At b of 10 and d of 5 the overhead is about 11 per cent.

5. What did Korf prove about it in 1985, and under what two conditions? That depth first iterative deepening is asymptotically optimal among brute-force searches in time, in space and in the cost of the solution found. The conditions are that no heuristic information is used, and that it is a tree search keeping no set of reached states.

6. Why does the algorithm check for cycles against the current path rather than keeping every state it has seen? Because the current path is already held in memory, so checking it is free, whereas a full set of reached states would make the space proportional to the number of states and destroy the O(b*d) memory that is the algorithm's whole purpose.

7. Is iterative deepening optimal on the standing district map? Justify with the numbers. Not in cost. It returns Amba, Chinch, Gokul, Jalna at 26 km, which is the route with the fewest hops, three. The cheapest route costs 25 km and has four hops. It is optimal in the number of steps, which is all it claims.

the board
7 2 4
5 _ 6
8 3 1

the goal
_ 1 2
3 4 5
6 7 8

h0, guess nothing      : 0
h1, misplaced tiles    : 8
h2, Manhattan distance : 18

tile  at (row,col)  wants (row,col)  rows+cols to travel
   7       (0, 0)           (2, 1)  3
   2       (0, 1)           (0, 2)  1
   4       (0, 2)           (1, 1)  2
   5       (1, 0)           (1, 2)  2
   6       (1, 2)           (2, 0)  3
   8       (2, 0)           (2, 2)  2
   3       (2, 1)           (1, 0)  2
   1       (2, 2)           (0, 1)  3

h2 total: 18  and this board needs 26 moves, found by search
so h0 <= h1 <= h2 <= 26: all three never overestimate, and h2 is closest

Read the three numbers against the truth. The board genuinely needs 26 moves. h0 says 0, h1 says 8, h2 says 18. All three are under 26, which is the property called admissibility and is the subject of chapter 20. And 18 is a far more useful guess than 8, which is the property called dominance.

The blank is not counted as a tile in either heuristic. Counting it breaks the guarantee: the blank moves on every single move, so including it would let the estimate exceed the real number of moves.

Dominance: one heuristic is better than another

h2 is at least as large as h1 at every single state, because a misplaced tile is at least one row or column from home, so it contributes at least 1 to the Manhattan sum as well as 1 to the count. When that holds everywhere, h2 dominates h1.

A dominating heuristic is always the better one to use, provided it is still cheap to compute. The reason is worth one line and comes back in A*: a larger estimate that still never overestimates lets the algorithm rule out more branches, and it can never cause a wrong answer.

That claim is a measurement, so here is the measurement. The program finds a board whose optimal solution is exactly 14 moves, then solves it three times with the same algorithm and three different heuristics, counting the nodes generated each time.

# Measure the effect of a heuristic on the 8-puzzle. A* with h0 (which makes it
# uniform cost search), h1 (misplaced tiles) and h2 (Manhattan distance), on a
# board whose optimal solution is 14 moves.
import heapq
from collections import deque
GOAL = (0, 1, 2, 3, 4, 5, 6, 7, 8)

def succ(s):
    i = s.index(0)
    r, c = divmod(i, 3)
    for dr, dc in ((-1, 0), (1, 0), (0, -1), (0, 1)):
        nr, nc = r + dr, c + dc
        if 0 <= nr < 3 and 0 <= nc < 3:
            j = nr * 3 + nc
            board = list(s)
            board[i], board[j] = board[j], board[i]
            yield tuple(board)

def h0(s):
    return 0

def h1(s):
    return sum(1 for i, v in enumerate(s) if v and v != GOAL[i])

def h2(s):
    total = 0
    for i, v in enumerate(s):
        if v:
            g = GOAL.index(v)
            total += abs(i // 3 - g // 3) + abs(i % 3 - g % 3)
    return total

def astar(start, h):
    generated = 1
    frontier = [(h(start), 0, start)]
    best = {start: 0}
    while frontier:
        f, g, s = heapq.heappop(frontier)
        if best.get(s, 10 ** 9) < g:
            continue
        if s == GOAL:
            return g, generated
        for m in succ(s):
            ng = g + 1
            if ng < best.get(m, 10 ** 9):
                best[m] = ng
                generated += 1
                heapq.heappush(frontier, (ng + h(m), ng, m))
    return None, generated

# find a board whose optimal solution is 14 moves, by walking out from the goal
depth = {GOAL: 0}
queue = deque([GOAL])
board14 = None
while queue:
    s = queue.popleft()
    if depth[s] == 14:
        board14 = s
        break
    for m in succ(s):
        if m not in depth:
            depth[m] = depth[s] + 1
            queue.append(m)

print("a board at optimal depth 14:", board14)
for name, h in (("h0 none (= uniform cost)", h0), ("h1 misplaced tiles", h1),
                ("h2 Manhattan distance", h2)):
    cost, gen = astar(board14, h)
    print("  %-26s solution %d moves, %8d nodes generated" % (name, cost, gen))

a board at optimal depth 14: (7, 6, 2, 4, 3, 5, 0, 1, 8)
  h0 none (= uniform cost)   solution 14 moves,     4767 nodes generated
  h1 misplaced tiles         solution 14 moves,      394 nodes generated
  h2 Manhattan distance      solution 14 moves,       87 nodes generated

Four thousand seven hundred and sixty-seven nodes, down to eighty-seven. All three found the same 14-move answer, so nothing was given up. A cheap count of how far each tile is from home did the work of examining fifty-four times as many states.

These are this book's own figures on one board, using a reached set, and they are smaller than the averages usually published, which are taken over many random instances and often without one. The shape is what matters and it is the same: no heuristic, thousands; a weak one, hundreds; a dominating one, tens.

The straight-line heuristic on the standing map

For the district map, relaxation deletes the roads: fly in a straight line. The coordinates are in Formulating a Problem for Search, and the resulting estimate to Jalna, rounded down, is:

Every h is at most the true cost, in every row. That is not luck: the map was built so that every road's length is at least the straight-line distance between its ends, so no road journey can be shorter than flying. Admissibility, and Why A* Is Optimal turns this table into a proof.

Two rows are worth staring at, because they are where the next two chapters get their teeth.

Fanas and Gokul are exact: h equals the truth, 5 and 6. A heuristic that is exact everywhere would let a search walk straight to the answer with no wasted work at all.

Hivra is badly wrong: h is 3 and the truth is 7, because the river makes the direct road 16 km. h is still not an overestimate, so nothing breaks, but the estimate is misleading. Erandol is the same trap and worse: h is 8, the truth is 12, and the ROAD to Erandol from Amba costs 33. The next chapter follows a heuristic that trusts this row and pays 47 km for a 25 km journey.

What makes a heuristic good

Four properties, and a real heuristic trades them against each other.

1. It never overestimates. Formally, admissibility, chapter 20. Without it A* loses its guarantee.
2. It is as large as possible. Dominance. A bigger admissible estimate does more work for you.
3. It is cheap. A perfect heuristic could be computed by solving the problem, which is useless. The whole saving is that h is computed in microseconds and the search it prunes would take hours. A heuristic that costs more than the branches it saves is a loss.
4. h(goal) is 0, and h is never negative.

Property 2 and property 3 pull in opposite directions, and that tension is the practical art of it. Manhattan distance is a better estimate than misplaced tiles and costs about the same, so it wins outright. A heuristic that solved a relaxed problem by search at every node would estimate beautifully and be slower than searching.

Distinctions

What it does not mean

A heuristic is not a rule of thumb about what to do. It is a number estimating remaining cost. The everyday sense of the word is different and leads students to write about "using heuristics to decide", which earns nothing.

A heuristic is not a guarantee. It can be wrong at any state. Hivra's estimate is off by more than half.

Bigger is not always better. Bigger is better among heuristics that never overestimate. An estimate that overestimates can be very large and makes the search return wrong answers.

h is not the same as f. h is the estimate of what remains; f is g plus h, the estimate of the whole journey. Greedy best first search orders on h, A* on f, and that difference is the next two chapters.

The blank is not a tile. Both 8-puzzle heuristics exclude it, and including it destroys the guarantee.

A perfect heuristic is not the goal. It would cost as much as solving the problem. The goal is a good estimate that is almost free.

Quick revision

• h(n): an estimate of the cheapest cost from n to a goal. Problem specific, cheap, h(goal) = 0, never negative.
• g(n) looks backwards and is exact; h(n) looks forwards and is a guess; f(n) = g(n) + h(n) estimates the whole route.
• Relaxation is where a heuristic comes from: delete a constraint and solve the easier problem exactly. The answer can never exceed the real cost, so relaxation gives an admissible heuristic automatically.
• 8-puzzle heuristics: misplaced tiles (relax so a tile may teleport home) and Manhattan distance (relax so tiles may pass through each other). The blank is not a tile in either.
• On the standing board: h1 is 8, h2 is 18, and the truth is 26 moves.
• Dominance: h2 is at least h1 everywhere, so h2 dominates and is the better choice while still being cheap.
• District map: h is the straight-line distance. Exact at Fanas and Gokul; off by 4 at Hivra because of the river, and off by 4 at Erandol, whose road from Amba is 33 km. Those two rows are the traps the next chapters spring.
• Four properties of a good heuristic: never overestimates, as large as possible, cheap, and zero at the goal. The second and third pull against each other.

Test yourself

1. Define a heuristic function and state its three requirements. h(n) estimates the cost of the cheapest path from the state at n to a goal. It must be problem specific, cheap to compute, and zero at any goal state, and it is never negative.

2. Distinguish g, h and f. g(n) is the exact cost of the path already travelled from the start to n. h(n) is an estimate of the cost still to come from n to a goal. f(n) is g(n) plus h(n), an estimate of the total cost of a route through n.

3. What is relaxation, and why does it produce a heuristic that never overestimates? Relaxation deletes a constraint from the problem and solves the easier problem exactly. Every solution of the real problem is still a solution of the relaxed one, so the relaxed optimum is at most the real optimum, and the estimate can never exceed the truth.

4. Compute both 8-puzzle heuristics for the board 7 2 4 / 5 blank 6 / 8 3 1 against the goal blank 1 2 / 3 4 5 / 6 7 8. Misplaced tiles is 8, since every tile is out of place. Manhattan distance is 18, the sum of 3, 1, 2, 2, 3, 2, 2 and 3 for tiles 7, 2, 4, 5, 6, 8, 3 and 1. The board actually needs 26 moves, so both are under it.

5. Why is the blank excluded from both heuristics? Because the blank moves on every single move. Counting its displacement would allow the estimate to exceed the true number of moves, destroying the guarantee that the heuristic never overestimates.

6. What does it mean for one heuristic to dominate another, and why is the dominating one preferred? h2 dominates h1 when h2(n) is at least h1(n) at every state and both are admissible. The dominating one is preferred because a larger estimate that still never overestimates lets the search discard more branches, and it cannot cause a wrong answer.

7. On the standing map h(Hivra) is 3 while the true cheapest road distance to Jalna is 7. Is the heuristic broken? No. A heuristic is an estimate and is allowed to be wrong; what matters is that it does not exceed the truth, and 3 is less than 7. The estimate is misleading rather than invalid, and the direct road is long because a river lies between Hivra and Jalna.

Read the two columns together and the whole lesson is in them. The h column falls beautifully: 20, 8, 5, 0. Every step looks like progress. The g column tells the truth: 0, 33, 42, 47.

Step 2 is where it goes wrong, and it goes wrong in exactly one decision. From Amba the three options are Bori (h 15), Chinch (h 15) and Erandol (h 8). Erandol looks much the closest to the goal, and it is: it is 8 km from Jalna in a straight line. What the algorithm does not look at is that the road to Erandol from Amba is the 33 km ghat road round a hill. It pays 33 km to move 8 km closer, and 33 km is more than the entire optimal route.

It then cannot recover. Greedy best first search never reconsiders g, so nothing later in the run can notice that the journey started badly. It arrives at Jalna for 47 km.

The two things it is very good at

Do not leave the chapter with the impression that the algorithm is useless. It is not, and a paper asking "when would you use greedy best first search" expects these.

It is the fewest expansions in this row. Four, against six for breadth first search, eight for depth first search, nine for uniform cost search and eight for A*. When a good-enough answer is wanted quickly on a very large space, that matters.

Its answer had three hops. Greedy search often finds a short-in-steps route quickly, and on a problem where any solution is valuable and no solution is disastrous, it is the cheapest way to get one.

So it belongs in the toolbox for satisficing rather than optimising: problems where finding some answer fast beats finding the best answer eventually.

Why it is not complete

Two separate failures, and both are examinable.

In tree search it can loop. Suppose from X the lowest-h neighbour is Y, and from Y the lowest-h neighbour is X. Without a visited set the search goes X, Y, X, Y forever, exactly as depth first search does. The program above avoids it only because of visited.

Even in graph search it can go the wrong way on an infinite space. Following h downhill can lead into an infinite region with no goal in it, while the goal sits behind a state whose h is momentarily high. On a finite space with a visited set it is complete, because it eventually visits everything.

Comparing it with its two neighbours

This table is the answer to a question that asks for the difference between greedy search, uniform cost search and A*, and every figure in it is from this book's own runs on one map.

The two one-eyed algorithms each see half the problem. Uniform cost search knows exactly what the journey has cost and nothing about where the goal is, so it spreads out in every direction. Greedy best first search knows roughly where the goal is and nothing about what the journey has cost, so it walks into expensive roads. A* adds the two numbers, and the next chapter is what that buys.

When does greedy search happen to be optimal

Worth knowing because a paper can ask it. Greedy best first search returns an optimal route when the heuristic is perfect, that is when h(n) is the exact cheapest cost from n to the goal at every state. Then following the smallest h is following the optimal path by definition.

That is not a practical condition; computing a perfect heuristic means solving the problem. It is useful only as the statement of what greedy search would need: the algorithm has no error correction of its own, so all the accuracy has to be in h.

Distinctions

What it does not mean

"Greedy" is not a criticism of the programmer. It is the technical name for taking the locally best option without reconsidering, and it names a whole family of algorithms across computer science.

It is not A without the heuristic. It is A without the g. Dropping h instead gives uniform cost search.

It is not always worse than uniform cost search. It expanded fewer than half as many nodes here. It is worse at finding the cheapest route and better at finding some route quickly.

A falling h is not progress. Every step of the run above reduced h and the journey got more expensive each time. h measures what remains, and reducing it says nothing about what has been spent.

Best first search is not a synonym for greedy best first search. Best first search is the family; greedy is the member that orders on h alone. Uniform cost search and A* are also best first searches.

Quick revision

• Greedy best first search: expand the node with the smallest h(n). Frontier is a priority queue on h. g is ignored entirely.
• Not optimal. Not complete in tree search: it can oscillate between two states, and it can follow h downhill into an infinite region.
• On the standing map: 4 expansions, the fewest in the row, and 47 km against a cheapest route of 25 km.
• It fails at step 2, taking the 33 km ghat road to Erandol because Erandol's h is only 8. It pays 33 km to get 8 km closer and can never reconsider.
• Its strength is satisficing: some answer, fast, on a large space.
• It is optimal only if h is perfect, which would mean already having solved the problem.
• Best first search is the family, ordered on any evaluation function; greedy orders on h, uniform cost on g, A* on g + h.

Test yourself

1. Define greedy best first search. A best first search that expands the node with the smallest heuristic estimate h(n) of the remaining cost, holding its frontier in a priority queue ordered on h, and taking no account of the path cost already incurred.

2. What exactly does it ignore, and what does that cost it? It ignores g(n), the cost of the path already travelled. Because of that it cannot notice that a branch began expensively, so it is neither optimal nor able to recover from a bad first step.

3. Trace its first two decisions on the standing map and say where it goes wrong. From Amba the options are Bori with h 15, Chinch with h 15 and Erandol with h 8, so it takes Erandol. The road from Amba to Erandol is the 33 km ghat road, so it has paid 33 km, more than the whole optimal route of 25 km, to get 8 km nearer in a straight line.

4. State its completeness and give both reasons it can fail. It is not complete in tree search. It can oscillate between two states, each of which has the other as its lowest-h neighbour, and on an infinite space it can follow h downhill into a region containing no goal. With a visited set on a finite space it is complete.

5. Give two situations in which it is the right algorithm. When a good-enough answer is needed quickly on a very large state space, because it expands the fewest nodes in the row; and when any solution has value and finding the cheapest one is not worth the extra work, which is called satisficing.

6. Under what condition is greedy best first search optimal, and why is that condition useless in practice? If h is perfect, giving the exact cheapest remaining cost at every state, then following the smallest h follows the optimal path. It is useless because computing a perfect heuristic means already solving the problem.

7. In the run, h fell from 20 to 8 to 5 to 0 while g rose from 0 to 33 to 42 to 47. What does that show? That a falling heuristic is not evidence of a good route. h measures the distance still to go and says nothing about what has been spent getting there, so a search ordered on h alone can make every step look like progress while the journey becomes steadily more expensive.

Nothing else differs from uniform cost search at all. Swap g for g + h in the queue key and you have A. That is worth stating because it makes the relationship exact: uniform cost search is A with h equal to zero everywhere.

It running on the district map

import heapq
ROAD = {
    "Amba":    {"Bori": 8, "Chinch": 7, "Erandol": 33},
    "Bori":    {"Amba": 8, "Chinch": 12, "Devi": 5},
    "Chinch":  {"Amba": 7, "Bori": 12, "Erandol": 7, "Gokul": 13},
    "Devi":    {"Bori": 5, "Fanas": 7, "Hivra": 9},
    "Erandol": {"Amba": 33, "Chinch": 7, "Fanas": 9, "Gokul": 6},
    "Fanas":   {"Devi": 7, "Erandol": 9, "Hivra": 2, "Jalna": 5},
    "Gokul":   {"Chinch": 13, "Erandol": 6, "Jalna": 6},
    "Hivra":   {"Devi": 9, "Fanas": 2, "Jalna": 16},
    "Jalna":   {"Fanas": 5, "Gokul": 6, "Hivra": 16},
}
SLD = {"Amba": 20, "Bori": 15, "Chinch": 15, "Devi": 11, "Erandol": 8,
       "Fanas": 5, "Gokul": 6, "Hivra": 3, "Jalna": 0}

def a_star(start, goal):
    frontier = [(SLD[start], 0, [start])]    # ordered on f = g + h
    best = {}
    step = 0
    while frontier:
        f, g, path = heapq.heappop(frontier)
        node = path[-1]
        if node in best and best[node] <= g:
            continue
        best[node] = g
        step += 1
        top = sorted(frontier)[:3]
        waiting = " ".join("%s f=%d" % (p[-1], c) for c, _, p in top)
        if len(frontier) > 3:
            waiting += " +%d" % (len(frontier) - 3)
        print("%2d  expand %-8s g=%2d h=%2d f=%2d   waiting: %s"
              % (step, node, g, SLD[node], f, waiting))
        if node == goal:
            return g, path
        for child, cost in sorted(ROAD[node].items()):
            heapq.heappush(frontier, (g + cost + SLD[child], g + cost, path + [child]))
    return None, None

cost, route = a_star("Amba", "Jalna")
print()
print("route found:", " > ".join(route))
print("hops:", len(route) - 1, " cost:", cost, "km")

 1  expand Amba     g= 0 h=20 f=20   waiting:
 2  expand Chinch   g= 7 h=15 f=22   waiting: Bori f=23 Erandol f=41
 3  expand Erandol  g=14 h= 8 f=22   waiting: Bori f=23 Gokul f=26 Amba f=34 +2
 4  expand Bori     g= 8 h=15 f=23   waiting: Gokul f=26 Gokul f=26 Fanas f=28 +5
 5  expand Devi     g=13 h=11 f=24   waiting: Gokul f=26 Gokul f=26 Fanas f=28 +7
 6  expand Fanas    g=20 h= 5 f=25   waiting: Hivra f=25 Gokul f=26 Gokul f=26 +9
 7  expand Hivra    g=22 h= 3 f=25   waiting: Hivra f=25 Jalna f=25 Gokul f=26 +12
 8  expand Jalna    g=25 h= 0 f=25   waiting: Gokul f=26 Gokul f=26 Fanas f=28 +13

route found: Amba > Bori > Devi > Fanas > Jalna
hops: 4  cost: 25 km

The f column never decreases: 20, 22, 22, 23, 24, 25, 25, 25. That is the invariant, and it is what the next chapter's proof is about. Five moments repay attention.

Step 1 gives f(Amba) = 20, which is g of 0 plus h of 20. And the true cheapest route is 25 km, so the very first estimate is already within 5 km of the answer. A heuristic tells you something immediately.

Look at the frontier after step 1: Erandol sits at f of 41. Greedy best first search took Erandol at step 2 because its h was 8. A* sees g of 33 plus h of 8 and puts it forty-first in the queue. The trap that cost greedy search 22 km is simply not entered, and it is the g term that closes it.

Step 3 expands Erandol anyway, at f of 22, by a different route. Amba to Chinch to Erandol costs 7 plus 7, so g is 14 and f is 22. This is the point of keeping both: the algorithm has not banned Erandol, it has banned the dear road to it.

Steps 6 to 8 all have f of 25, which is the cost of the optimal route. Once f reaches the optimal cost, everything remaining at that value is expanded and nothing above it is touched. That band is exactly the set of nodes A* cannot avoid looking at.

Step 8 expands Jalna at f of 25 with the frontier still holding Gokul at 26. The late goal test did its work: a route to Jalna at 26 km had been generated at step 7 and was not taken, because 25 beat it.

What the sum buys, in numbers

On a nine-town map the saving over uniform cost search is one expansion, which is not impressive, and pretending otherwise would be dishonest. The saving grows with the problem, and this book measured that too: in Heuristics: Estimating What Is Left To Do, the same algorithm on the same 8-puzzle board generated 4,767 nodes with h of zero and 87 with Manhattan distance, for the same 14-move answer. That is the fifty-four-fold version of the one expansion saved here.

The honest limits

Two of them, and both are why the two chapters after next exist.

A keeps every node it generates. Its space complexity is the number of nodes with f below the optimal cost, and on a large problem that is exponential. A runs out of memory long before it runs out of time, which is the same sentence that was true of breadth first search and for the same reason. Recursive Best First Search is the answer.

Its time complexity depends entirely on the heuristic. The standard statement is in terms of the absolute error, h(n) - h(n), the amount by which the estimate falls short of the truth. If the absolute error grows no faster than the logarithm of the true cost, A runs in time polynomial in the solution depth. Otherwise the growth is exponential. So "A* is efficient" is not a property of the algorithm; it is a property of the heuristic you gave it.

Two named relatives, briefly

Neither is on MU's syllabus and both are one line, and knowing the names prevents confusion.

• IDA*: iterative deepening applied to f instead of to depth. Each pass is a depth first search that cuts off where f exceeds a bound, and the bound for the next pass is the smallest f that exceeded it. Linear memory, and it is Korf's heuristic sequel to Iterative Deepening Search.
• Weighted A: order on g + Wh with W greater than 1. Faster and no longer optimal, but the answer is provably within a factor of W of the best. Useful when a guarantee of "no worse than 20 per cent off" is worth having.

Distinctions

What it does not mean

A is not optimal unconditionally. It needs h admissible for tree search and consistent for graph search. The next two chapters are those conditions, and stating A is optimal without one of them is an incomplete answer.

The star is not a wildcard or a footnote. It is part of the name given in the 1968 paper, distinguishing the algorithm A used with an admissible heuristic.

A* does not avoid expanding useless nodes. It expands every node whose f is below the optimal cost. On the standing map that includes Erandol and Hivra, neither of which is on the answer.

A bigger h is not always better here either. A bigger admissible h is better. An h that overestimates can make A* fast and wrong.

A* is not a different algorithm from uniform cost search. It is the same algorithm with h added to the queue key, which is why it inherits the late goal test and the discarding of dearer routes.

Quick revision

• A*: expand the node with the smallest f(n) = g(n) + h(n). f estimates the total cost of the cheapest route through n.
• Frontier is a priority queue on f. Late goal test, on selection. Dearer routes to settled states are discarded.
• Uniform cost search is A with h = 0. Greedy best first search is A with g dropped.
• Complete, and optimal with an admissible h in tree search, a consistent h in graph search.
• On the standing map: 8 expansions, 25 km, route Amba, Bori, Devi, Fanas, Jalna. f never decreases: 20, 22, 22, 23, 24, 25, 25, 25.
• It refuses the greedy trap because Erandol by the ghat road has f of 41; it still reaches Erandol at f of 22 by Chinch. It bans the dear road, not the town.
• Space is its real limit: it keeps every generated node, exponential on a large problem. Time depends on the heuristic's absolute error, h*(n) - h(n): logarithmic error gives polynomial time, worse error gives exponential.
• Relatives: IDA (iterative deepening on f, linear memory), weighted A (g + W*h, faster, within a factor W of optimal).

Test yourself

1. Write the evaluation function A* uses and say what each term is. f(n) = g(n) + h(n). g(n) is the cost of the path from the start to n, which is known exactly. h(n) is the heuristic estimate of the cheapest cost from n to a goal. f(n) is therefore an estimate of the total cost of the cheapest route through n.

2. State the relationship between A, uniform cost search and greedy best first search. All three are best first searches differing only in the queue key. Uniform cost search uses g, so it is A with h zero everywhere. Greedy best first search uses h, so it is A with g dropped. A uses their sum.

3. Why must the goal test be applied on selection rather than on generation? Because a goal reached by an expensive route can be generated before the cheap route to it is found. On the standing map Gokul generates Jalna with f of 26 while the optimal route gives 25, so an early test would return the dearer route.

4. Greedy best first search took the 33 km road to Erandol and A did not. Explain using the numbers. Greedy ordered on h(Erandol) of 8, the lowest available. A orders on g plus h, which for that road is 33 plus 8, giving f of 41, so it sits far down the queue. A* still expands Erandol later at f of 22, reached by Chinch for a g of 14, so the town was never banned, only the expensive road to it.

5. What is A's real practical limitation, and what is done about it? Memory. It keeps every node it generates, and the number of nodes with f below the optimal cost is exponential on a large problem, so it exhausts memory before time. The answer is a linear-space variant such as recursive best first search or IDA.

6. On what does A's running time depend, and how is that usually stated? On the accuracy of the heuristic, measured by the absolute error h(n) - h(n), the amount by which the estimate falls short of the true remaining cost. If that error grows no faster than the logarithm of the true cost, the time is polynomial in the depth of the solution; otherwise it is exponential.

7. In the run, steps 6, 7 and 8 all have f of 25. What does that tell you? That 25 is the optimal cost. A* expands every node whose f is below the optimal cost and then works through the nodes whose f equals it, stopping when the goal is selected. The band at f of 25 is the set of nodes it cannot avoid examining.

Two kilometres of over-optimism at one town out of nine costs the optimal answer. That is how tight the condition is, and it is why the word appears in MU's own label. Admissibility is not a nicety; it is the hypothesis of the theorem, and losing it loses the conclusion immediately.

Why the straight-line distance is admissible without checking every town

The program checked nine towns. The general argument is two lines and is what makes the heuristic safe on a map of nine thousand towns.

Every road between two towns is at least as long as the straight line between them, because a straight line is the shortest path between two points. So any journey by road from n to the goal is at least as long as the straight line from n to the goal. Therefore the straight-line distance is at most the cheapest road distance, which is the definition.

That is the argument the 1968 paper itself gives, in its own example of cities connected by roads, and it is also the general reason relaxation works: the straight line is the exact answer to the relaxed problem in which you may fly.

It depends on a property of the map, not of geometry. If a road could be shorter than the straight line, the argument fails. The standing map was built with every winding factor at least 1 precisely so that it holds, and that construction is declared in Formulating a Problem for Search rather than assumed here.

The proof that A* is optimal

Tree search, admissible h. Proof by contradiction, and it is short enough to reproduce in an examination.

Suppose A returns a suboptimal goal node t, with g(t) greater than C, the cost of an optimal solution.

1. Let n be a node on an optimal path that is still on the frontier at the moment t is selected. Such an n must exist: the start is on the optimal path, and the optimal path's nodes cannot all have been expanded, because then the optimal goal would have been generated and, being cheaper, would have been selected before t.
2. Because n is on an optimal path, g(n) is the true cheapest cost to n, and the remaining cost from n is h(n). So g(n) + h(n) = C*.
3. By admissibility, h(n) <= h(n). So f(n) = g(n) + h(n) <= g(n) + h(n) = C*.
4. For the goal t, h(t) = 0, so f(t) = g(t), which by assumption is greater than C*.
5. Hence f(n) <= C < f(t), so n had a strictly smaller f than t and A would have selected n rather than t. That contradicts the assumption.

Step 3 is the only place admissibility is used, and it is used exactly once. That is the answer to "where does admissibility come in": it is what lets f(n) be bounded above by C* for a node on the optimal path, and everything else is bookkeeping.

Step 4 uses h(goal) = 0. A heuristic that reported a positive value at the goal would break the proof at that step, which is why that requirement is part of the definition and not a convention.

Optimally efficient, which is a different and stronger claim

The 1968 paper proves something beyond optimality, and it is worth knowing because it explains why nothing has replaced A*.

Section III shows that A is not only admissible but optimal in the sense that no other admissible algorithm expands fewer nodes using the same information. The paper's own words: A is not only admissible but optimal, in the sense that no other admissible algorithm expands fewer nodes.

The claim has a condition, the paper's consistency assumption, and that condition is the whole of the next chapter. What it means in practice: given the same heuristic, any algorithm that guarantees an optimal answer must expand every node whose f is below C, because any one of them might hide a cheaper route, and A expands exactly those and no more. There is no cleverer ordering to be found.

What admissibility does not give you

Three things it is routinely assumed to guarantee and does not.

It does not make A fast. The 8-puzzle heuristic h0 = 0 is admissible and makes A into uniform cost search. Admissibility guarantees the answer, not the work.

It does not survive graph search on its own. With a reached set that never reconsiders a settled node, an admissible but inconsistent heuristic can make A* return a suboptimal route. That is the next chapter, and it is why MU prints both words.

It does not mean the estimate is good. Look at the slack column: the heuristic is short by 5 km at Amba and by 4 at three more towns. It is admissible everywhere and mediocre in several places.

Distinctions

What it does not mean

Admissible does not mean accurate. It means never too high. A heuristic can be admissible and useless, and h = 0 is the extreme case.

It is not a property of the algorithm in modern usage, although it was in 1968. Both usages exist and mean different things.

It does not require h to be a lower bound on the cost of the particular path found. It is a lower bound on the cost of the CHEAPEST remaining path, which is a smaller number and therefore a stronger requirement.

Overestimating a little is not a little wrong. Two kilometres at one town lost the optimal route on a nine-town map. The guarantee is all or nothing.

Admissibility alone is not enough for graph search. The commonest error on this topic, and the reason the next chapter exists.

Quick revision

• Admissible: h(n) <= h*(n) at every node. Never overestimates; optimistic; a lower bound.
• Two consequences: h(goal) = 0, and h = 0 everywhere is admissible, which makes uniform cost search a special case of A*.
• Straight-line distance is admissible because no road is shorter than the straight line, so no road journey is shorter than flying. That argument, and this book's map, are both in the 1968 paper's own example.
• Proved on the standing map by computing h* at all nine towns. Slack ranges from 0 at Fanas and Gokul to 5 at Amba.
• Breaking it by 2 km at one town changes the answer from 25 km to 26 km. The guarantee is all or nothing.
• The proof: if A returned a suboptimal t, some node n on the optimal path is still on the frontier, f(n) = g(n) + h(n) <= g(n) + h(n) = C* < g(t) = f(t), so n would have been chosen. Admissibility is used once, in the middle inequality.
• Optimally efficient: no admissible algorithm using the same heuristic expands fewer nodes, subject to the consistency assumption.
• Admissibility does not give speed, and does not suffice for graph search.

Test yourself

1. Define an admissible heuristic. A heuristic h is admissible if h(n) is at most h*(n), the true cost of the cheapest path from n to a goal, at every node n. It never overestimates the remaining cost.

2. Show that h(n) = 0 for all n is admissible, and say what A becomes. True remaining costs are never negative, so 0 is a lower bound everywhere and the heuristic is admissible. A then orders on g alone, which is uniform cost search.

3. Why is straight-line distance admissible on a road map? Because a straight line is the shortest path between two points, so every road is at least as long as the straight line between its ends, and therefore any road journey from a town to the goal is at least the straight-line distance. The estimate is thus never above the true cost.

4. Prove that A with an admissible heuristic returns an optimal solution in tree search. Suppose it returns t with g(t) greater than the optimal cost C. Some node n on an optimal path remains on the frontier, and for it g(n) + h(n) equals C. By admissibility h(n) is at most h(n), so f(n) is at most C. Since h(t) is 0, f(t) equals g(t), which exceeds C*. So f(n) is less than f(t) and n would have been selected instead, a contradiction.

5. Where exactly is admissibility used in that proof, and what would happen without it? Only in the step bounding f(n) by C. Without it h(n) could exceed h(n), f(n) could exceed C, and there would be nothing to stop A selecting the dearer goal first.

6. This chapter overestimated one town's heuristic by 2 km out of nine towns. What happened, and what does it show? A* returned 26 km by Chinch, Erandol and Gokul instead of the optimal 25 km by Bori, Devi and Fanas. It shows that the guarantee is all or nothing: a small violation at a single node is enough to lose the optimal answer.

7. Does admissibility guarantee that A* is optimal in graph search? Explain. No. With a reached set that never reconsiders a state already settled, an admissible but inconsistent heuristic can cause a suboptimal route to be returned, because a state can be closed by an expensive route before the cheap route to it is found. Graph search needs consistency, or else the ability to reopen closed nodes.

The counter-example, built and run

Four nodes. The heuristic is checked for admissibility at every node, and for consistency on every edge, by the program rather than by inspection.

# An ADMISSIBLE but INCONSISTENT heuristic, and what it does to A* when a closed
# node is never reopened. Four nodes; the numbers are chosen so the failure is
# forced rather than lucky.
import heapq

EDGE = {"S": {"A": 2, "B": 5},
        "A": {"S": 2, "B": 2},
        "B": {"S": 5, "A": 2, "G": 2},
        "G": {"B": 2}}
H = {"S": 0, "A": 4, "B": 0, "G": 0}      # admissible, and NOT consistent
TRUE = {"S": 6, "A": 4, "B": 2, "G": 0}   # the real cheapest cost to G

print("admissible?  h(n) <= true cost to G, at every node")
for n in ("S", "A", "B", "G"):
    print("   %s: h=%d  true=%d  %s" % (n, H[n], TRUE[n], "yes" if H[n] <= TRUE[n] else "NO"))
print()
print("consistent?  h(u) <= cost(u,v) + h(v), for every edge")
bad = []
for u in EDGE:
    for v, c in EDGE[u].items():
        ok = H[u] <= c + H[v]
        if not ok:
            bad.append((u, v, c))
        print("   %s -> %s  c=%d   h(%s)=%d  c+h(%s)=%d   %s"
              % (u, v, c, u, H[u], v, c + H[v], "yes" if ok else "NO"))
print()
print("violated on:", bad)
print()

def a_star(reopen):
    frontier = [(H["S"], 0, ["S"])]
    closed = {}
    log = []
    while frontier:
        f, g, path = heapq.heappop(frontier)
        node = path[-1]
        if node in closed and not (reopen and g < closed[node]):
            continue
        closed[node] = g
        log.append("%s(g=%d,f=%d)" % (node, g, f))
        if node == "G":
            return g, path, log
        for child, c in sorted(EDGE[node].items()):
            heapq.heappush(frontier, (g + c + H[child], g + c, path + [child]))
    return None, None, log

for reopen in (False, True):
    cost, path, log = a_star(reopen)
    print("%-28s cost %d  route %s" % ("reopening closed nodes: " + str(reopen),
                                       cost, " > ".join(path)))
    print("    expanded: " + "  ".join(log))
print()
print("the cheapest route is S > A > B > G at 2 + 2 + 2 = 6")

admissible?  h(n) <= true cost to G, at every node
   S: h=0  true=6  yes
   A: h=4  true=4  yes
   B: h=0  true=2  yes
   G: h=0  true=0  yes

consistent?  h(u) <= cost(u,v) + h(v), for every edge
   S -> A  c=2   h(S)=0  c+h(A)=6   yes
   S -> B  c=5   h(S)=0  c+h(B)=5   yes
   A -> S  c=2   h(A)=4  c+h(S)=2   NO
   A -> B  c=2   h(A)=4  c+h(B)=2   NO
   B -> S  c=5   h(B)=0  c+h(S)=5   yes
   B -> A  c=2   h(B)=0  c+h(A)=6   yes
   B -> G  c=2   h(B)=0  c+h(G)=2   yes
   G -> B  c=2   h(G)=0  c+h(B)=2   yes

violated on: [('A', 'S', 2), ('A', 'B', 2)]

reopening closed nodes: False cost 7  route S > B > G
    expanded: S(g=0,f=0)  B(g=5,f=5)  A(g=2,f=6)  G(g=7,f=7)
reopening closed nodes: True cost 6  route S > A > B > G
    expanded: S(g=0,f=0)  B(g=5,f=5)  A(g=2,f=6)  B(g=4,f=4)  G(g=6,f=6)

the cheapest route is S > A > B > G at 2 + 2 + 2 = 6

The heuristic is admissible at all four nodes and inconsistent on two edges, and the algorithm returns 7 instead of 6. Follow the four expansions in the first run, because the failure happens in one line.

1. S is expanded at f of 0. Its children go on the frontier: A with g 2 and f 2 plus 4 equals 6, and B with g 5 and f 5 plus 0 equals 5.
2. B is selected at f of 5, ahead of A at 6, and is settled with g of 5. That is the fatal step. B's estimate is over-optimistic, 0 against a true 2, and that made the dear route to it look cheap.
3. A is expanded at f of 6. It generates B again, now with g of 4, which is genuinely better. The closed set refuses it, because B is already settled.
4. G is reached from the settled, dearer B, and the answer is 7.

f decreased along a path, and that is the symptom. f(A) is 6 and f(B) by way of A is 4. A search that assumes f never decreases has had its assumption broken, and the second run shows the two possible repairs.

The two repairs, and which is used where

There are exactly two ways to make graph-search A* optimal, and a paper may ask for either.

Use a consistent heuristic. Then f never decreases, so the first time a state is selected it is by its cheapest route, and closing it is safe. This is what happens in practice, because almost every heuristic derived by relaxation is consistent.

Allow reopening. Keep the closed set, but when a strictly cheaper route to a closed node is found, put it back on the frontier. That is what the second run does, and what the 1968 paper's own step 7 prescribes: Remark as open any closed node n_i which is a successor of n and for which f(n_i) is smaller now than it was when n_i was marked closed. It restores optimality at the cost of re-expanding nodes, and in the run above it cost one extra expansion.

So the 1968 algorithm was written to handle inconsistency and the textbook version usually is not. When a paper asks "is graph-search A* optimal with an admissible heuristic", the correct answer is: not in general; it is optimal if the heuristic is consistent, or if closed nodes may be reopened.

Is the straight-line heuristic consistent

Yes, and the argument is the triangle inequality, which is the same argument the 1968 paper gives.

Let d(m, n) be the straight-line distance between towns m and n. Any road between them is at least as long, so c(m, n) >= d(m, n). And straight-line distances obey the triangle inequality, d(m, n) + d(n, goal) >= d(m, goal). Put the two together:

which is the consistency condition. Note what it rests on: that no road is shorter than the straight line. That is a property of the map, and it is the property the standing map was constructed to have.

Rounding needs one word of care. This book's h is the straight-line distance rounded down, and rounding down can only make h smaller, which can only help both conditions. Rounding up could break admissibility, and is the kind of small decision that quietly loses a guarantee.

Where consistency can genuinely fail

Do not leave with the impression that inconsistency is only a textbook curiosity. It arises in real work in two ways.

A heuristic assembled from several sources. Take the maximum of two admissible heuristics and the result is admissible, and if both are consistent the maximum is consistent too. Take a heuristic that is computed differently in different regions of the state space, and consistency is easily lost, which is exactly the 1968 paper's constructed example: it computes h one way at odd-numbered nodes and another way at even-numbered ones, so that h(s) = 8 while a node six units away has h = 1.

A learned or estimated heuristic. Anything fitted from data, including the models of Module 2, is under no obligation to satisfy an edge condition. A learned heuristic is usually neither admissible nor consistent, and using one means giving up the guarantee knowingly or adding reopening.

Distinctions

What it does not mean

Consistency is not about the nodes. It is a condition on every edge, and that is what makes it checkable without knowing any true cost.

Monotonic does not mean h is monotonic. h may rise and fall. It is f that never decreases, and the name refers to that.

An inconsistent heuristic is not necessarily wrong at any node. The one above is admissible everywhere. Inconsistency is an incoherence between neighbouring estimates, not an error at a point.

Reopening is not a hack. It is in the original published algorithm, and it is the correct repair when a consistent heuristic is not available.

Almost all does not mean all. Heuristics from relaxation are consistent, but heuristics stitched together from different rules, and heuristics learned from data, need not be.

Quick revision

• Consistent (monotonic): h(n) <= c(n, n') + h(n') for every edge. A triangle inequality on the estimates.
• Adding g(n) to both sides gives f(n) <= f(n'): f never decreases along a path. That is what the name monotonic refers to.
• Consistency implies admissibility, by summing the condition along the cheapest path to a goal and using h(goal) = 0. The converse is false.
• Admissible but inconsistent breaks graph search. In the four-node example the answer is 7 instead of 6: B is settled at g of 5 by the dear route because h(B) is over-optimistic, and the closed set then refuses the g of 4 route found through A.
• The symptom is f decreasing along a path: f(A) is 6 and f(B) through A is 4.
• Two repairs: use a consistent heuristic, or reopen a closed node when a strictly cheaper route to it appears. The 1968 algorithm's step 7 is the second.
• Straight-line distance is consistent, by c(m,n) + h(n) >= d(m,n) + d(n,goal) >= d(m,goal) = h(m). It rests on no road being shorter than the straight line, which is a property of the map.
• Rounding h down is safe; rounding up can break admissibility.

Test yourself

1. State the consistency condition and explain why it is called a triangle inequality. For every node n and successor n' reached at cost c(n, n'), h(n) is at most c(n, n') plus h(n'). It has the form of the triangle inequality because it says that going directly cannot be estimated as longer than going via an intermediate point.

2. Derive the monotonicity of f from consistency. Add g(n) to both sides of the condition: g(n) + h(n) is at most g(n) + c(n, n') + h(n'). The right-hand side is g(n') + h(n'), so f(n) is at most f(n'), and f does not decrease along any path.

3. Prove that consistency implies admissibility. Apply the condition along the cheapest path from n to a goal and add the inequalities. The result is that h(n) is at most the total cost of that path plus h at the goal. Since h at a goal is 0, h(n) is at most the cheapest remaining cost, which is admissibility.

4. Give an admissible but inconsistent heuristic and describe what it does to graph-search A. In the four-node example, h(S) is 0, h(A) is 4, h(B) is 0 and h(G) is 0, against true costs of 6, 4, 2 and 0, so it is admissible. It violates consistency on the edge from A to B, where h(A) of 4 exceeds the step cost of 2 plus h(B) of 0. Graph-search A settles B by the 5-cost route, then refuses the cheaper 4-cost route found through A, and returns a total of 7 rather than 6.

5. Name the two ways to make graph-search A* optimal. Use a consistent heuristic, so that f never decreases and the first selection of a state is by its cheapest route. Or allow a closed node to be reopened when a strictly cheaper route to it is found, which is what the 1968 algorithm's step 7 does.

6. Show that the straight-line heuristic is consistent on a road map. Every road is at least as long as the straight line between its ends, and straight-line distances satisfy the triangle inequality. So the road cost from m to n plus the straight-line distance from n to the goal is at least the straight-line distance from m to n plus that from n to the goal, which is at least the straight-line distance from m to the goal, namely h(m).

7. Why is "monotonic" a confusing name, and what exactly is monotonic? Because h itself is not monotonic and may rise and fall from node to node. What is monotonic, in the sense of non-decreasing, is f along any path, and that is a consequence of the edge condition on h.

The limit passed down is the minimum of the inherited limit and the best local alternative. The inherited limit is what an ancestor is prepared to spend; the local alternative is what this node could switch to. The branch is worth pursuing only while it beats both.

It running on the district map

ROAD = {
    "Amba":    {"Bori": 8, "Chinch": 7, "Erandol": 33},
    "Bori":    {"Amba": 8, "Chinch": 12, "Devi": 5},
    "Chinch":  {"Amba": 7, "Bori": 12, "Erandol": 7, "Gokul": 13},
    "Devi":    {"Bori": 5, "Fanas": 7, "Hivra": 9},
    "Erandol": {"Amba": 33, "Chinch": 7, "Fanas": 9, "Gokul": 6},
    "Fanas":   {"Devi": 7, "Erandol": 9, "Hivra": 2, "Jalna": 5},
    "Gokul":   {"Chinch": 13, "Erandol": 6, "Jalna": 6},
    "Hivra":   {"Devi": 9, "Fanas": 2, "Jalna": 16},
    "Jalna":   {"Fanas": 5, "Gokul": 6, "Hivra": 16},
}
SLD = {"Amba": 20, "Bori": 15, "Chinch": 15, "Devi": 11, "Erandol": 8,
       "Fanas": 5, "Gokul": 6, "Hivra": 3, "Jalna": 0}
INFINITY = float("inf")
calls = 0

def rbfs(path, g, f_limit, depth=0):
    """Returns (solution or None, the best f value beyond the limit)."""
    global calls
    calls += 1
    node = path[-1]
    print("%s%s  g=%2d  f_limit=%s" % ("  " * depth, node, g,
          "inf" if f_limit == INFINITY else "%d" % f_limit))
    if node == "Jalna":
        return path, g
    children = []
    for child, cost in sorted(ROAD[node].items()):
        if child in path:                    # never revisit on this path
            continue
        cg = g + cost
        # the BACKED-UP value: never less than the parent's own f
        cf = max(cg + SLD[child], g + SLD[node])
        children.append([cf, cg, child])
    if not children:
        return None, INFINITY
    while True:
        children.sort()
        best = children[0]
        if best[0] > f_limit:
            return None, best[0]
        alternative = children[1][0] if len(children) > 1 else INFINITY
        print("%s  best %s f=%d, next best f=%s"
              % ("  " * depth, best[2], best[0],
                 "inf" if alternative == INFINITY else "%d" % alternative))
        result, best[0] = rbfs(path + [best[2]], best[1], min(f_limit, alternative), depth + 1)
        if result is not None:
            return result, best[0]

route, cost = rbfs(["Amba"], 0, INFINITY)
print()
print("route found:", " > ".join(route))
print("hops:", len(route) - 1, " cost:", cost, "km")
print("recursive calls:", calls)

Amba  g= 0  f_limit=inf
  best Chinch f=22, next best f=23
  Chinch  g= 7  f_limit=23
    best Erandol f=22, next best f=26
    Erandol  g=14  f_limit=23
  best Bori f=23, next best f=26
  Bori  g= 8  f_limit=26
    best Devi f=24, next best f=35
    Devi  g=13  f_limit=26
      best Fanas f=25, next best f=25
      Fanas  g=20  f_limit=25
        best Hivra f=25, next best f=25
        Hivra  g=22  f_limit=25
        best Jalna f=25, next best f=37
        Jalna  g=25  f_limit=25

route found: Amba > Bori > Devi > Fanas > Jalna
hops: 4  cost: 25 km
recursive calls: 8

25 km, the same optimal answer A* gave, in eight recursive calls and with never more than four towns in memory. Read the trace at the points where it forgets and returns.

Amba chooses Chinch at f of 22, with Bori at 23 as the alternative, and passes down f_limit of 23. So the message to the Chinch branch is: you are worth following only while you stay under 23, because 23 is available elsewhere.

Chinch chooses Erandol at f of 22 and passes down the inherited 23, not its own local alternative of 26, because min(23, 26) is 23. The inherited limit is tighter and it wins.

Erandol is entered and immediately abandoned. Every route out of it has f above 23, so the recursion returns, reporting the best f it found. The whole Erandol subtree is now forgotten, and Chinch's record of Erandol has been raised from 22 to that reported value.

Amba now finds Bori the best at 23 and the search goes down the branch that actually contains the answer: Bori, Devi, Fanas, Hivra, Jalna. The f values climb 23, 24, 25, 25, 25, reaching 25, the cost of the optimal route.

What it costs

Nothing is free. The trade is stated precisely.

Memory falls from exponential to linear. A holds every generated node; RBFS holds the current path and the sibling list at each level, which is O(bd).

Some work is repeated. A forgotten subtree may be re-entered and re-expanded. On this nine-town map it happens once, to Erandol, and costs one call. On a large problem it can be substantial, and Korf's paper is explicit that the overhead depends on how often the search switches branches.

RBFS often generates more nodes than A and still finishes when A cannot start. That is the correct way to read the comparison, and it is the same reading as iterative deepening against breadth first search.

SMA*, named once

Not on MU's syllabus, and worth one line so the name is not a mystery. RBFS uses too little memory: it has linear space available and throws away information it could have afforded to keep. SMA, simplified memory-bounded A, is given a memory budget, fills it, and when it is full drops the worst leaf, backing up its value to its parent exactly as RBFS does. It uses whatever memory you give it and no more.

Distinctions

What it does not mean

It is not A* with less memory and no cost. It re-expands forgotten subtrees. The saving is in space and it is paid for in time.

The f_limit is not a depth limit. It is a value limit on f, and it comes from the best alternative an ancestor is holding, not from a level count.

Forgetting is not the same as pruning. A pruned branch is proved not to matter; a forgotten branch may be re-entered, and its backed-up value is what makes returning to it cheap.

f(child) is not always g(child) + h(child). In RBFS it is the maximum of that and the parent's f. Without the maximum, a forgotten subtree reports a value too low and the search oscillates.

It is not IDA. IDA restarts from the root at each new bound; RBFS unwinds only as far as it must and keeps the siblings at each level. Both have linear space.

Quick revision

• RBFS: explore the best child first, carrying an f_limit equal to the best alternative any ancestor holds. When the branch exceeds it, unwind, forget the subtree, and back up the best f found inside it.
• f(child) = max(g + cost + h(child), f(parent)). The maximum is what makes a forgotten subtree's reported value usable.
• The limit passed down is min(inherited limit, best local alternative).
• Space O(b*d). Complete and optimal with an admissible heuristic. Cost: a forgotten subtree can be re-expanded.
• Set by Computer Science Practical 5, Module 1, which requires it to be implemented alongside A* and compared, and named by no theory module label.
• On the standing map: 25 km in 8 recursive calls, the same answer A* gave, with at most four towns in memory. It enters Erandol at f of 22, abandons it against an inherited limit of 23, and then finds the answer through Bori.
• SMA* is the memory-budgeted relative: fill the memory you are given, then drop the worst leaf and back its value up.
• The right comparison: RBFS may generate more nodes than A and still finish where A cannot start.

Test yourself

1. Define recursive best first search and state its space complexity. A linear-space best first search that explores the most promising child first while carrying an f_limit equal to the best alternative available from any ancestor. When the current branch's f exceeds the limit it unwinds, forgetting the subtree and backing up the best f found within it. Space is O(b*d).

2. What problem with A does it solve? A keeps every node it generates, so the number of nodes with f below the optimal cost is exponential and it runs out of memory before it runs out of time. RBFS gives the same optimal answer in linear space.

3. Write the formula for a child's f and explain the maximum. f(child) = max(g(child) + h(child), f(parent)). The maximum stops a child's estimate falling below its parent's. Without it, a forgotten subtree would report a value too low, the search would return to it, repeat the same work and reach the same conclusion indefinitely.

4. What is the f_limit and where does it come from? It is the f value of the best alternative that some ancestor is holding in reserve. At each level the limit handed down is the smaller of the limit inherited from above and the second-best child at this node, so a branch is pursued only while it beats every alternative that has been given up for it.

5. Trace what happens to Erandol in this chapter's run. Chinch selects Erandol at f of 22 and passes down the inherited limit of 23. Every route out of Erandol has an f above 23, so the call returns immediately, reporting the best f it found. The Erandol subtree is forgotten and Chinch's stored value for it is raised, after which Amba prefers Bori at 23.

6. State the trade RBFS makes, and the right way to compare it with A. It trades time for space: memory falls from exponential to linear and a forgotten subtree may be re-expanded. The comparison to make is not which generates fewer nodes, since A usually does, but that RBFS finishes on problems A* cannot be started on.

7. Why is this chapter in a book on the theory paper at all? Because Computer Science Practical 5, Module 1, sets A* Search and Recursive Best-First Search by name and requires both to be implemented and compared for 15 marks, while no theory module label mentions it. The examination is the outer boundary of what the book must teach.

The comparison, measured

# The practical's own instruction: "Compare the performance and efficiency of both
# algorithms." Four algorithms, ONE problem, five measurements each, in the table
# a practical write-up needs.
import heapq
from collections import deque

ROAD = {
    "Amba":    {"Bori": 8, "Chinch": 7, "Erandol": 33},
    "Bori":    {"Amba": 8, "Chinch": 12, "Devi": 5},
    "Chinch":  {"Amba": 7, "Bori": 12, "Erandol": 7, "Gokul": 13},
    "Devi":    {"Bori": 5, "Fanas": 7, "Hivra": 9},
    "Erandol": {"Amba": 33, "Chinch": 7, "Fanas": 9, "Gokul": 6},
    "Fanas":   {"Devi": 7, "Erandol": 9, "Hivra": 2, "Jalna": 5},
    "Gokul":   {"Chinch": 13, "Erandol": 6, "Jalna": 6},
    "Hivra":   {"Devi": 9, "Fanas": 2, "Jalna": 16},
    "Jalna":   {"Fanas": 5, "Gokul": 6, "Hivra": 16},
}
SLD = {"Amba": 20, "Bori": 15, "Chinch": 15, "Devi": 11, "Erandol": 8,
       "Fanas": 5, "Gokul": 6, "Hivra": 3, "Jalna": 0}
START, GOAL = "Amba", "Jalna"
INF = float("inf")

def km(path):
    return sum(ROAD[path[i]][path[i + 1]] for i in range(len(path) - 1))

class Meter:
    """One counter object per run, so nothing is measured by hand."""
    def __init__(self):
        self.generated = 1       # the start node counts
        self.expanded = 0
        self.peak = 1

def bfs(m):
    frontier = deque([[START]])
    reached = {START}
    while frontier:
        m.peak = max(m.peak, len(frontier))
        path = frontier.popleft()
        m.expanded += 1
        for child in sorted(ROAD[path[-1]]):
            if child in reached:
                continue
            m.generated += 1
            if child == GOAL:
                return path + [child]
            reached.add(child)
            frontier.append(path + [child])
    return None

def ids(m):
    def dls(path, limit):
        if path[-1] == GOAL:
            return path
        if len(path) - 1 == limit:
            return None
        m.expanded += 1
        for child in sorted(ROAD[path[-1]]):
            if child in path:
                continue
            m.generated += 1
            m.peak = max(m.peak, len(path) + 1)
            found = dls(path + [child], limit)
            if found:
                return found
        return None
    for limit in range(0, 10):
        found = dls([START], limit)
        if found:
            return found
    return None

def astar(m):
    frontier = [(SLD[START], 0, [START])]
    best = {}
    while frontier:
        m.peak = max(m.peak, len(frontier))
        f, g, path = heapq.heappop(frontier)
        node = path[-1]
        if node in best and best[node] <= g:
            continue
        best[node] = g
        m.expanded += 1
        if node == GOAL:
            return path
        for child, cost in sorted(ROAD[node].items()):
            m.generated += 1
            heapq.heappush(frontier, (g + cost + SLD[child], g + cost, path + [child]))
    return None

def rbfs(m):
    def go(path, g, f_limit):
        node = path[-1]
        m.expanded += 1
        m.peak = max(m.peak, len(path))
        if node == GOAL:
            return path, g
        kids = []
        for child, cost in sorted(ROAD[node].items()):
            if child in path:
                continue
            m.generated += 1
            kids.append([max(g + cost + SLD[child], g + SLD[node]), g + cost, child])
        if not kids:
            return None, INF
        while True:
            kids.sort()
            best = kids[0]
            if best[0] > f_limit:
                return None, best[0]
            alt = kids[1][0] if len(kids) > 1 else INF
            found, best[0] = go(path + [best[2]], best[1], min(f_limit, alt))
            if found is not None:
                return found, best[0]
    return go([START], 0, INF)[0]

print("problem: %s to %s on the district map, 9 towns, 15 roads" % (START, GOAL))
print()
print("algorithm  cost  hops  generated  expanded  peak in memory  optimal?")
for name, fn in (("BFS", bfs), ("IDS", ids), ("A*", astar), ("RBFS", rbfs)):
    m = Meter()
    route = fn(m)
    print("%-9s %5d %5d %10d %9d %15d  %s"
          % (name, km(route), len(route) - 1, m.generated, m.expanded, m.peak,
             "yes" if km(route) == 25 else "NO, 25 exists"))
print()
print("route each one returned:")
for name, fn in (("BFS", bfs), ("IDS", ids), ("A*", astar), ("RBFS", rbfs)):
    print("  %-5s %s" % (name, " > ".join(fn(Meter()))))

problem: Amba to Jalna on the district map, 9 towns, 15 roads

algorithm  cost  hops  generated  expanded  peak in memory  optimal?
BFS          26     3          9         6               3  NO, 25 exists
IDS          26     3         31        13               4  NO, 25 exists
A*           25     4         25         8              18  yes
RBFS         25     4         17         8               5  yes

route each one returned:
  BFS   Amba > Chinch > Gokul > Jalna
  IDS   Amba > Chinch > Gokul > Jalna
  A*    Amba > Bori > Devi > Fanas > Jalna
  RBFS  Amba > Bori > Devi > Fanas > Jalna

Reading the table, which is what the marks are for

A write-up that prints the table and stops earns half the marks. The reading is the answer.

No column names one winner. BFS does the least total work of any of the four, 9 nodes generated, and returns the wrong route. A* returns the right route and holds eighteen nodes at once. There is no row that is best in every column, and that is the finding, not a failure of the experiment.

BFS against IDS: the same answer for three times the generation. Both return 26 km in three hops, because both are optimal in the number of steps and neither is optimal in cost. IDS generated 31 nodes against BFS's 9, which is its repeated passes. And its peak memory is 4 against 3, which on this tiny map is nothing, and on a problem at depth 12 with a branching factor of 10 is the difference between 120 nodes and a hundred gigabytes. The pair to compare is exactly the pair the practical sets, and this is what to say about it.

A against RBFS: the same answer, and the memory column is the whole story. Both return 25 km in four hops and both expanded 8 nodes. A generated 25 nodes and held 18 at its peak; RBFS generated 17 and held 5. On nine towns that is a curiosity. The peak frontier of A* grows exponentially with the depth of the solution and RBFS's grows linearly, so on a real instance the same two numbers become "runs" and "cannot be started". That is the comparison the practical wants and it is a sentence, not a table.

The optimal column is not a bonus, it is a promise. BFS and IDS are not broken: neither claims cost optimality on unequal step costs. Reporting them as failures would be misreading their contract, and a viva may test exactly that.

Writing it up, and what the viva asks

A practical write-up for this pair has six parts, and they follow from the table above.

1. The problem, stated exactly. Start, goal, the graph, and the step costs. Two algorithms compared on different instances have not been compared.
2. Both implementations, with the counters visible in the code rather than added by hand.
3. The table, one row per algorithm, the five measures.
4. The routes returned, in full. Two algorithms can agree on cost and disagree on route.
5. The reading: which measure each algorithm wins, and which measure decides the choice for this problem. Name the measure.
6. The limit of the experiment: one instance proves nothing about the general case. Say so.

Point 6 is the honest one and it is worth a mark. Nine towns is one instance. A* beating uniform cost search by one expansion here is not evidence of anything; the 8-puzzle measurement in Heuristics: Estimating What Is Left To Do, where the same algorithm went from 4,767 nodes to 87, is.

The viva questions this table answers directly: which algorithm used least memory and why; which found the cheapest route and why the others did not; what would change if every road were the same length; and why you did not report the time.

What changes if the step costs are equal

A good question to be ready for, because it is the quickest test of whether the four algorithms are understood.

If every road cost the same, then ordering by cost is ordering by depth. BFS and IDS become cost optimal, because fewest steps is now cheapest. Uniform cost search becomes BFS. A with a heuristic still expands fewer nodes than BFS, so it remains worth using, and RBFS still uses less memory than A. Two of the four rows change their optimal column and none of the work columns changes character.

Distinctions

What it does not mean

Fewer nodes generated is not the same as better. BFS generated the fewest of the four and returned the wrong answer.

Wall-clock time is not a measure of an algorithm. It measures the machine, the implementation and, on a small instance, the noise.

One instance is not a comparison of algorithms. It is a comparison of their behaviour on one instance, which is what a practical asks for and all it establishes.

An algorithm that is not optimal has not failed. It has to be judged against what it promises. BFS and IDS promise fewest steps.

Peak frontier is not the same as total memory used over the run. It is the most held at any one instant, which is what the machine has to supply.

Quick revision

• Five measures: solution cost, optimal or not, nodes generated, nodes expanded, peak frontier. The first two are the answer's quality, the last three the work.
• Peak frontier is the measure that decides real problems and the one usually omitted.
• Generated counts creation, expanded counts having children made. The gap is work thrown away: A* generated 25 and expanded 8.
• Do not report wall-clock time: it measures the machine, the implementation, and on a small instance the noise. Report node counts, which are machine independent.
• The measured table on the standing map: BFS 26 km / 9 generated / peak 3, IDS 26 km / 31 / peak 4, A* 25 km / 25 / peak 18, RBFS 25 km / 17 / peak 5.
• BFS against IDS: same answer, three times the generation, and one node more memory here, which becomes the whole difference at depth.
• A* against RBFS: same answer, same expansions, 18 against 5 in memory. That gap grows exponentially against linearly, so it becomes "runs" against "cannot start".
• A write-up has six parts and the last is the honest one: one instance proves nothing general.

Test yourself

1. Name the five things to measure when comparing two search algorithms. The cost of the solution found, whether it is optimal, the number of nodes generated, the number of nodes expanded, and the peak size of the frontier.

2. Distinguish nodes generated from nodes expanded, and say what the gap means. A node is generated when it is created and placed on the frontier; it is expanded when it is removed and its own children are generated. The difference is work the algorithm created and never used: A* generated 25 nodes here and expanded only 8.

3. Why is wall-clock time a poor measure for this write-up? Because it depends on the machine and on the implementation rather than on the algorithm, and on a nine-town problem the run-to-run variation is larger than the difference between the algorithms. Node counts are properties of the algorithm and the instance.

4. BFS returned 26 km and A* returned 25 km. Is BFS broken? No. BFS guarantees the fewest steps and returns a three-hop route; it guarantees least cost only when all step costs are equal, and the roads here are 2 km to 33 km. It kept the promise it makes.

5. A and RBFS returned the same route and expanded the same number of nodes. On what basis would you choose between them? On memory. A held 18 nodes at its peak and RBFS held 5. The peak for A grows exponentially with the depth of the solution and for RBFS linearly, so on a large instance A cannot be started while RBFS runs.

6. Which algorithm did the least total work here, and why is that not enough to recommend it? BFS, with 9 nodes generated. It is not enough because the route it returned was not the cheapest, so the least work bought the wrong answer.

7. What would change in the table if every road on the map were 10 km long? BFS and IDS would become cost optimal, because fewest steps would then be cheapest, so their optimal column would change to yes. Uniform cost search would behave exactly as BFS. A would still expand fewer nodes than BFS thanks to the heuristic, and RBFS would still use far less memory than A.

Zero sum, and what it licenses

A game is zero sum when the two players' utilities always add to the same constant, conventionally zero. Chess with win, draw and loss scored as plus one, zero and minus one is zero sum; so is any game with one winner.

Two consequences, and the second is the one that makes the next chapter possible.

What is good for one player is exactly as bad for the other. So there is no possibility of cooperation, which is what makes the setting purely competitive.

One number suffices. Instead of tracking a utility for each player, track a single value from one player's point of view, and the other player is simply trying to make that number small. That is why the next chapter has one function returning one number, and why the players are called MAX and MIN.

A game that is not zero sum cannot be handled this way. Two players who both lose if a deal fails have partly aligned interests, and the tree then needs a pair of utilities at each leaf and a different algorithm. MU sets the zero sum case and this book teaches it, naming the limit.

Why the tree cannot be searched to the end

Shannon settled this in 1950 with arithmetic, and quoting his own numbers is better than asserting that the tree is large.

He observes that the game is finite, so in principle one could work backward from every terminal position and determine whether each opening move wins, draws or loses. Then:

In typical chess positions there will be of the order of 30 legal moves.

That figure is not a guess: his Fig. 1 is built from De Groot's averages over a large number of master games, and he notes that it holds fairly constant until the endgame. So one move for White and one for Black gives about 1,000 continuations, and a game lasting about 40 moves gives, in his words,

there will be 10^120 variations to be calculated from the initial position. A machine operating at the rate of one variation per micro-second would require over 10^90 years to calculate the first move!

That number is now called the Shannon number. The consequences he draws are exactly the machinery of the next two chapters and of every game program since.

Shannon's two answers

Section by section, the 1950 paper gives the two things that make game playing possible, and both are named in later syllabuses by his labels.

An evaluation function. Since the leaves cannot be reached, stop at some depth and estimate the value of the position reached. Shannon's own proposal is a weighted sum of measurable features: material, mobility, pawn structure, king safety. Note the relationship to the previous nine chapters: an evaluation function is to a game what a heuristic is to a search problem, an estimate standing in for a value that cannot be computed. It is not the same thing: a heuristic estimates remaining cost to a goal, an evaluation function estimates who is winning. Confusing the two is a common error.

Type A and type B strategies. A type A program considers every legal move to a fixed depth and then evaluates. A type B program looks at only the promising moves and follows forcing sequences further, as Shannon observes a human player does: A certain number of variations are investigated move by move until a more or less quiescent position is reached. Type A is uniform and wasteful; type B is selective and can miss things. Modern programs are type B with type A guarantees bolted on.

Two more ideas the evaluation function forces

Both are consequences of stopping early rather than separate topics, and both are examinable in one line.

The horizon effect. A program that stops at depth d cannot see a disaster at depth d plus 1, and can be induced to make pointless moves that push the disaster just past its horizon. The program thinks it has avoided the problem; it has only stopped looking.

Quiescence. It is unsafe to evaluate a position in the middle of an exchange, because the material count is meaningless halfway through. A program therefore searches on past a noisy position until it is quiescent, and only then evaluates. Shannon's sentence above is the origin of the idea.

The standard classification of games

Worth a table because a paper can ask where a named game sits.

• Perfect information means every player can see the whole state. It is the fully observable row from Types of Environment.
• Chance means a die or a shuffle intervenes, which is the stochastic column. The tree then needs a third kind of node, a chance node, whose value is the expected value of its children, and the algorithm is called expectiminimax.
• Imperfect information means part of the state is hidden, which is partial observability, and it needs reasoning about what the opponent knows.

MU's label is Adversarial search: Minimax & Alpha-Beta pruning, which is the deterministic, perfect information box. This book teaches that box thoroughly and names the other three so a student knows what lies outside it.

Distinctions

What it does not mean

Adversarial does not mean the environment is hostile. It means another agent is optimising a measure opposed to ours. Weather is not adversarial however bad it is.

A game tree is not a search tree in the earlier sense. Its levels alternate in who chooses, and its leaves carry utilities rather than being goals or not.

The evaluation function is not the utility function. The utility is the real, exact outcome at a terminal state. The evaluation function is an estimate at a non-terminal state, used because the terminals are out of reach.

Zero sum is not a property of all games. It is an assumption, and MU's algorithms depend on it. Without it a single value per node is not enough.

Shannon's 10^120 is not the number of positions. It is his estimate of the number of variations, that is of distinct lines of play, from the initial position. The number of legal positions is a different and much smaller figure.

Quick revision

• Adversarial search: search where another agent chooses alternate actions to maximise an opposed measure.
• Six components: S0, PLAYER(s), ACTIONS(s), RESULT(s, a), TERMINAL(s), UTILITY(s, p).
• A solution is a STRATEGY, not a path. A path dies at the opponent's first unexpected move.
• Zero sum means the utilities sum to a constant, so one number suffices and the players can be called MAX and MIN. Not all games are zero sum.
• One level is a ply; a chess move is two ply. Say which you mean.
• Shannon 1950: about 30 legal moves in a typical position, from De Groot's averages, so about 10^120 variations from the start, and over 10^90 years at one variation per microsecond. Hence the two answers: an evaluation function and a depth cutoff.
• Type A searches every move to a fixed depth; type B searches selectively and follows forcing lines further.
• Stopping early causes the horizon effect and requires quiescence before evaluating.
• Games classify on two axes: deterministic or chance, perfect or imperfect information. MU sets the deterministic, perfect information box; chance nodes need expectiminimax.

Test yourself

1. List the six components of a game. The initial state, a PLAYER function saying whose turn it is, an ACTIONS function giving the legal moves, a RESULT transition model, a TERMINAL test, and a UTILITY function giving the numerical outcome at a terminal state.

2. Why is a solution to a game a strategy rather than a path? Because the opponent chooses every second move, so any fixed sequence of actions stops applying as soon as the opponent deviates from it. A strategy specifies what to do in every state the opponent can bring about.

3. What does zero sum mean and what does it license? That the players' utilities always sum to a constant, so one player's gain is exactly the other's loss. It licenses tracking a single number from one player's point of view, which is why the algorithms have one value per node and the players are named MAX and MIN.

4. Give Shannon's own figures for the size of the chess game tree. About 30 legal moves in a typical position, averaged by De Groot over master games, so about a thousand continuations per full move and about 10 to the power 120 variations from the initial position, which at one variation per microsecond would take over 10 to the power 90 years.

5. Distinguish an evaluation function from a heuristic. A heuristic estimates the remaining cost from a node to a goal and smaller is better. An evaluation function estimates how good a non-terminal game position is for a player and larger is better for MAX. Both are estimates standing in for a value that cannot be computed, but they estimate different things.

6. What are Shannon's type A and type B strategies? Type A considers every legal move to a fixed depth and then evaluates. Type B examines only promising moves and follows forcing sequences further, until a quiescent position is reached, which is what a human player does.

7. Name the horizon effect and say what causes it. A program searching to a fixed depth cannot see an event just beyond that depth, so it can be induced to make delaying moves that push an unavoidable loss past its horizon and then report the position as safe. It is caused by the depth cutoff, not by the evaluation function being wrong.

  MIN of [3, 12, 8]     =  3
  MIN of [2, 4, 6]      =  2
  MIN of [14, 5, 2]     =  2
MAX of [3, 2, 2]      =  3

minimax value of the root: 3
terminals examined: 9 [3, 12, 8, 2, 4, 6, 14, 5, 2]

so MAX plays the FIRST branch, and can guarantee at least 3

All nine terminals were examined, in left to right order. That is the fact the next chapter attacks: two of those nine could not possibly have changed the answer, and alpha-beta pruning is the observation that says which two.

Why the traversal is depth first

The recursion above reaches a leaf before it evaluates anything, which is depth first order, and that is not an accident of the code.

A MAX node's value needs all its children, so the whole subtree under each child must be finished before the parent can report. Depth first order finishes subtrees in the order they are needed and holds only the current path plus the siblings at each level, giving space O(b*m).

Breadth first order would be useless here. Minimax has no early exit of its own: the answer is not found when a good leaf is met, it is found when the last subtree reports. So there is nothing to gain from examining shallow nodes first and a great deal of memory to lose.

Its properties

O(bm) is the sentence that kills it on a real game**, and the figures are in Games as Search: Shannon's 30 legal moves and 40 moves of play give about 10 to the power 120 nodes. Minimax on a full chess tree is not slow, it is impossible. The two repairs are the subject matter of the rest of the topic.

The two repairs

Both are needed and they are independent, which is worth saying because students often think alpha-beta is what makes chess programs possible on its own. It is not.

Cut off the depth and evaluate. Replace TERMINAL(s) with a test that also stops at a fixed depth, and replace UTILITY there with an evaluation function estimating who is winning. This changes the answer from exact to approximate and is what makes any game program possible at all.

def minimax_cutoff(node, depth):
    if TERMINAL(node) or depth == 0:
        return EVALUATE(node)
    if PLAYER(node) is MAX:
        return max(minimax_cutoff(child, depth - 1) for child in children)
    return min(minimax_cutoff(child, depth - 1) for child in children)

Prune. Do not examine nodes that cannot affect the answer. This changes the work and not the answer at all, which is why it is the more elegant of the two and why it has its own chapter.

A program with a cutoff and no pruning reaches a shallow depth and plays weakly. A program with pruning and no cutoff still cannot finish. Chess programs use both, and Games as Search records Shannon's own third idea, quiescence, as the refinement of the first.

The three-player case, and why MU's algorithm stops at two

Brief, because a paper can ask whether minimax generalises. It does, and the generalisation is instructive.

With three or more players, a single number no longer suffices: each node must carry a vector of utilities, one per player, and each player maximises its own component. The game is generally no longer zero sum, alliances become rational, and the pruning of the next chapter largely stops working because a bound on one player's value says little about another's. So the two-player zero sum restriction in MU's label is doing real work, not simplifying for convenience.

Distinctions

What it does not mean

Minimax does not predict the game. It computes a guarantee under optimal opposition. A weak opponent gives MAX more than the minimax value.

MIN is not maximising a second number. Because the game is zero sum, minimising MAX's value is the whole of MIN's objective.

It is not a search for a good move by trial. It is an exact computation of a value, from which the move follows.

It does not stop when it finds a winning leaf. A MAX node cannot report until every child has reported, so a win at the first leaf proves nothing until the siblings are known. That is precisely what alpha-beta pruning changes.

The values on the leaves are not scores of the position in play. They are utilities of finished games. Numbers estimating an unfinished position come from an evaluation function, which is a separate idea.

Quick revision

• Minimax value: the utility reached under optimal play by both sides. Terminal: the utility. MAX node: the maximum of its children. MIN node: the minimum.
• All values are from MAX's point of view; zero sum is what allows one number.
• On the standing tree the three MIN nodes are worth 3, 2 and 2, and the root is 3. MAX plays the first branch and is guaranteed at least 3.
• A guarantee, not a prediction. A blundering MIN gives MAX more.
• Nine terminals examined, left to right. Two of them could not have changed the answer, which is the next chapter.
• Depth first traversal, because a node needs every child before it can report. Time O(b**m), space O(b*m).
• O(bm) makes full chess impossible: about 10 to the power 120 nodes. Two independent repairs: a depth cutoff with an evaluation function, which makes the answer approximate, and pruning**, which does not change the answer at all.
• Three or more players needs a vector of utilities per node, is generally not zero sum, and largely defeats pruning.

Test yourself

1. Define the minimax value of a node in all three cases. At a terminal node it is the utility to MAX. At a MAX node it is the maximum of the minimax values of its children. At a MIN node it is the minimum of them.

2. Compute the minimax value of the standing tree and say which move MAX plays. The three MIN nodes take the smallest of their terminals, giving 3, 2 and 2. The root MAX takes the largest of those, which is 3. MAX plays the first branch.

3. What does the value 3 actually guarantee? That by playing the first branch MAX finishes with at least 3 whatever MIN does, and that no other move guarantees more, since MIN can hold both remaining branches to 2.

4. Why does minimax not stop as soon as it finds a good leaf? Because a MAX node's value is the maximum over all its children, so it cannot be reported until every child has reported. A good leaf in the first subtree says nothing until the others are known. Pruning is the separate observation that some of them need not be examined.

5. Give minimax's time and space complexity and say why the time figure matters. Time O(b**m) and space O(b*m). The time figure matters because on chess, with about 30 legal moves per position and about 40 moves of play, it means of the order of 10 to the power 120 nodes, so the full computation is impossible rather than merely slow.

6. Name the two repairs and say precisely what each changes. A depth cutoff with an evaluation function, which stops the search early and estimates the value of the position reached, changing the answer from exact to approximate. And pruning, which avoids examining nodes that cannot affect the result, changing the amount of work and not the answer at all.

7. Why does MU's label restrict adversarial search to two players, and what breaks with three? With three or more players each node needs a vector of utilities, one per player, and each player maximises its own component. The game is then generally not zero sum, alliances can be rational, and a bound on one player's value tells you little about another's, so alpha-beta pruning largely stops working.

Two implementation points that decide correctness.

The cutoff is checked before alpha or beta is updated, and with >= rather than >. Using strict inequality still gives the right value but prunes less.

Alpha and beta are passed down, never up. What travels up is the node's value. A version that assigns to a shared global alpha prunes wrongly, and it is the commonest bug in a student implementation.

It running, on the same tree as minimax

# Alpha-beta pruning on the SAME tree as the minimax chapter, so the saving can
# be counted. alpha is the best value MAX can already guarantee anywhere above;
# beta is the best MIN can already guarantee. A node stops as soon as it cannot
# affect the value above it.
TREE = ["MAX", [
    ["MIN", [3, 12, 8]],
    ["MIN", [2, 4, 6]],
    ["MIN", [14, 5, 2]],
]]

INF = float("inf")
examined = []

def show(v):
    return "-inf" if v == -INF else ("+inf" if v == INF else "%d" % v)

def alphabeta(node, alpha, beta, depth=0):
    pad = "  " * depth
    if isinstance(node, int):
        examined.append(node)
        print("%sleaf %2d" % (pad, node))
        return node
    player, children = node
    if player == "MAX":
        value = -INF
        for i, child in enumerate(children):
            value = max(value, alphabeta(child, alpha, beta, depth + 1))
            if value >= beta:
                print("%sCUT: MAX has %d >= beta %s, skipping %d sibling(s)"
                      % (pad, value, show(beta), len(children) - i - 1))
                return value
            alpha = max(alpha, value)
        print("%sMAX = %2d   alpha = %s" % (pad, value, show(alpha)))
        return value
    value = INF
    for i, child in enumerate(children):
        value = min(value, alphabeta(child, alpha, beta, depth + 1))
        if value <= alpha:
            print("%sCUT: MIN has %d <= alpha %s, skipping %d sibling(s)"
                  % (pad, value, show(alpha), len(children) - i - 1))
            return value
        beta = min(beta, value)
    print("%sMIN = %2d   beta = %s" % (pad, value, show(beta)))
    return value

best = alphabeta(TREE, -INF, INF)
print()
print("value of the root:", best, " and minimax gave 3 on the same tree")
print("terminals examined:", len(examined), examined)
print("minimax examined 9, so", 9 - len(examined), "were never looked at")

    leaf  3
    leaf 12
    leaf  8
  MIN =  3   beta = 3
    leaf  2
  CUT: MIN has 2 <= alpha 3, skipping 2 sibling(s)
    leaf 14
    leaf  5
    leaf  2
  CUT: MIN has 2 <= alpha 3, skipping 0 sibling(s)
MAX =  3   alpha = 3

value of the root: 3  and minimax gave 3 on the same tree
terminals examined: 7 [3, 12, 8, 2, 14, 5, 2]
minimax examined 9, so 2 were never looked at

The value is 3, exactly as minimax gave, and two terminals were never looked at. Follow the one interesting moment.

The first branch is examined in full. Nothing has been established yet, so alpha is minus infinity and there is nothing to prune against. Its three terminals give MIN a value of 3, and the root's alpha rises to 3: MAX can now guarantee 3.

The second branch is cut after ONE terminal. Its first terminal is 2. This is a MIN node, so its value can only fall from 2; and 2 is already at or below alpha, which is 3. So MAX will never choose this branch, and the 4 and the 6 are never examined. Whatever they were, even a thousand, this MIN node could not exceed 2.

The third branch is examined in full and is cut on its last child, which saves nothing here but is the same rule firing. Its terminals 14, 5 and 2 drive its value down to 2, which reaches alpha at the last moment.

Move ordering decides everything

The saving above is two nodes out of nine, which is small, and it is small because of the order the branches happened to be in. That is the most important practical fact about alpha-beta and it is measurable.

# Move ordering decides how much alpha-beta saves. Same nine leaf values, all six
# orderings of the three branches, with the leaves examined counted each time.
# Then the best case in theory, which is what a chess program is chasing.
INF = float("inf")

def alphabeta(node, alpha, beta, count):
    if isinstance(node, int):
        count[0] += 1
        return node
    player, children = node
    if player == "MAX":
        value = -INF
        for child in children:
            value = max(value, alphabeta(child, alpha, beta, count))
            if value >= beta:
                return value
            alpha = max(alpha, value)
        return value
    value = INF
    for child in children:
        value = min(value, alphabeta(child, alpha, beta, count))
        if value <= alpha:
            return value
        beta = min(beta, value)
    return value

BRANCH = {"A": ["MIN", [3, 12, 8]], "B": ["MIN", [2, 4, 6]], "C": ["MIN", [14, 5, 2]]}
print("order   value   leaves examined of 9")
for order in ("ABC", "ACB", "BAC", "BCA", "CAB", "CBA"):
    count = [0]
    value = alphabeta(["MAX", [BRANCH[k] for k in order]], -INF, INF, count)
    print("  %s       %d           %d" % (order, value, count[0]))

print()
print("in theory, with b moves at each of d levels:")
print("  d   plain minimax   alpha-beta, worst   alpha-beta, best")
for b, d in ((3, 4), (3, 6), (30, 4), (30, 6), (30, 10)):
    plain = b ** d
    best = b ** (d // 2) * 2 - 1 if d % 2 == 0 else b ** ((d + 1) // 2) + b ** (d // 2) - 1
    print("b=%2d d=%2d %14d %19d %18d" % (b, d, plain, plain, best))
print()
print("the best case examines about b**(d/2) nodes instead of b**d, which is the")
print("same as searching TWICE AS DEEP for the same work. Shannon 1950 measured")
print("about 30 legal moves in a typical chess position, so b = 30 is his figure.")

order   value   leaves examined of 9
  ABC       3           7
  ACB       3           7
  BAC       3           9
  BCA       3           9
  CAB       3           7
  CBA       3           7

in theory, with b moves at each of d levels:
  d   plain minimax   alpha-beta, worst   alpha-beta, best
b= 3 d= 4             81                  81                 17
b= 3 d= 6            729                 729                 53
b=30 d= 4         810000              810000               1799
b=30 d= 6      729000000           729000000              53999
b=30 d=10 590490000000000     590490000000000           48599999

the best case examines about b**(d/2) nodes instead of b**d, which is the
same as searching TWICE AS DEEP for the same work. Shannon 1950 measured
about 30 legal moves in a typical chess position, so b = 30 is his figure.

Every ordering returns 3, which is the correctness claim: pruning cannot change the answer.

The work varies from 7 to 9 out of 9. The two orderings that examine everything are the ones beginning with branch B, whose MIN value is 2: starting with a weak branch sets alpha low, and a low alpha prunes nothing. The rule that follows is the practical one: try the best-looking move first.

The theoretical table is the reason this matters. In the worst order alpha-beta examines every node and saves nothing at all, O(bd). In the best order it examines about b(d/2), which at b of 30 and d of 10 is 48 million instead of 590 thousand million: about twelve thousand times less work.

And the right way to state that saving is Shannon's way: b(d/2) instead of bd means the same work buys twice the depth. A chess program that could see five moves ahead can now see ten, and depth is strength.

How the ordering is actually obtained

Worth one paragraph, because "try the best move first" is circular: knowing which move is best is the problem being solved.

Real programs approximate it, and three techniques are standard. Cheap static rules: in chess, try captures and checks before quiet moves. Iterative deepening: search to depth 1, then 2, then 3, and at each new depth try the moves in the order the previous depth preferred. That is the same iterative deepening as in the uninformed row, used here for a completely different purpose, and it is why chess programs are built on it. Remembering: a transposition table stores the value found for a position, so a position reached by a different order of moves is not searched again.

Its properties

The random-ordering figure is the standard published result and this book has not measured it, so it is given as the known figure rather than as a measurement of ours. What this book does measure is the six orderings above.

Distinctions

What it does not mean

Alpha-beta does not change the answer. It returns the minimax value exactly. Any implementation that returns something else is wrong.

It is not a different algorithm from minimax. It is minimax with two bounds carried down and an early return.

alpha is not "the value of the current node". It is the best MAX can guarantee anywhere on the path above, which is why it is inherited and not computed locally.

Pruning does not always save anything. In the worst ordering it examines every node. Two of the six orderings measured above save nothing.

The best case is not typical. It requires the best move examined first at every node, which is exactly what is not known. Programs approximate it with static rules, iterative deepening and transposition tables.

Twice as deep is not twice as good in a trivial sense. It means the same computation reaches twice the depth, and since strength grows with depth, that is where the practical gain lies.

Quick revision

• Alpha-beta pruning returns exactly the minimax value while examining fewer nodes.
• alpha: the best MAX can already guarantee above; starts at minus infinity, only rises. beta: the best MIN can already guarantee; starts at plus infinity, only falls.
• Cut at a MIN node when its value is alpha or less; at a MAX node when its value is beta or more. The reasoning is about the parent's choice, not this node's quality.
• Bounds pass down; values pass up. A shared global alpha is the classic bug.
• On the standing tree: value 3, 7 terminals against minimax's 9. The second branch is cut after one terminal, because 2 is already at or below alpha of 3 and a MIN value can only fall.
• Move ordering decides everything. Measured over all six orderings: 7, 7, 9, 9, 7, 7 of 9. The two that save nothing begin with the weakest branch.
• Worst order O(bd), no saving. Best order O(b(d/2)), which at b of 30 and d of 10 is 48 million against 590 thousand million. The same work buys twice the depth.
• Ordering is approximated by static rules, iterative deepening reusing the previous depth's preference, and a transposition table.

Test yourself

1. Define alpha and beta. alpha is the value of the best choice found so far for MAX at any point along the current path from the root; it begins at minus infinity and only increases. beta is the best found so far for MIN along that path; it begins at plus infinity and only decreases.

2. Give both cutoff conditions and justify one of them. A MIN node stops when its value is alpha or less; a MAX node stops when its value is beta or more. For the first: a MIN node's value can only fall as more children are examined, it is already at or below a value MAX can obtain elsewhere, so MAX will never choose this branch and the remaining children cannot matter.

3. On the standing tree, why is the second branch cut after a single terminal? Its first terminal is 2. The node is a MIN node, so its value can only fall below 2, and alpha is already 3 from the first branch. MAX can guarantee 3 elsewhere, so it will never choose a branch worth at most 2, and the remaining two terminals are irrelevant.

4. Does pruning ever change the value returned? What does it change? Never. It returns exactly the minimax value. It changes only the number of nodes examined.

5. State the best and worst case time complexities and what determines which you get. Worst case O(bd), the same as plain minimax, with no saving. Best case O(b(d/2)). Which you get is determined entirely by the order in which moves are examined at each node; the best case needs the best move examined first everywhere.

6. Why is "try the best move first" circular, and how do real programs get round it? Because identifying the best move is the problem being solved. Programs approximate the order with cheap static rules such as trying captures first, with iterative deepening that reuses the previous shallower search's preferred order, and with a transposition table that remembers values already computed for a position.

7. Express the best-case saving in the way that shows why it matters in practice. Examining about b(d/2) nodes instead of bd means the same amount of work reaches twice the depth. Since playing strength grows with search depth, alpha-beta roughly doubles the depth a program can reach, which at Shannon's branching figure of 30 and a depth of 10 is 48 million nodes instead of 590 thousand million.

The agent has walked square 1,1 and felt no breeze; then square 2,1 and felt a breeze. It has never seen a pit, because a pit cannot be seen, only felt from next door.

That is the whole point of the setting: the conclusions the agent needs are not in its percepts. The percept at 2,1 is "breeze". The question is "which squares are safe", and no percept says anything about a square the agent has not stood in.

Working out what follows

The mechanical way to answer an ASK is to enumerate the worlds. A world is an assignment of pit or no pit to each of the six squares, so there are 2 to the power 6, that is 64 of them. Keep the ones consistent with what has been felt, then look at what is true in all of them.

# The knowledge-based agent, in the smallest world where something has to be
# DEDUCED rather than seen. Six squares, pits somewhere, and a breeze is felt in
# any square next to a pit. The agent has walked 1,1 (no breeze) and 2,1 (breeze)
# and has never seen a pit. What does it now know?
from itertools import product

SQUARES = ["1,1", "1,2", "2,1", "2,2", "3,1", "3,2"]

def neighbours(sq):
    x, y = (int(v) for v in sq.split(","))
    out = []
    for dx, dy in ((1, 0), (-1, 0), (0, 1), (0, -1)):
        nx, ny = x + dx, y + dy
        if 1 <= nx <= 3 and 1 <= ny <= 2:
            out.append("%d,%d" % (nx, ny))
    return out

VISITED = {"1,1", "2,1"}
BREEZE = {"2,1"}                 # felt a breeze here
NO_BREEZE = {"1,1"}              # felt none here

def possible(pits):
    if pits & VISITED:
        return False             # the agent stood there and did not fall in
    for sq in BREEZE:
        if not any(n in pits for n in neighbours(sq)):
            return False         # a breeze needs a pit next door
    for sq in NO_BREEZE:
        if any(n in pits for n in neighbours(sq)):
            return False         # no breeze means no pit next door
    return True

worlds = []
for bits in product([False, True], repeat=len(SQUARES)):
    pits = {sq for sq, has in zip(SQUARES, bits) if has}
    if possible(pits):
        worlds.append(pits)

print("visited 1,1 with no breeze, and 2,1 with a breeze. no pit ever seen.")
print("%d of the %d conceivable worlds are consistent with that:"
      % (len(worlds), 2 ** len(SQUARES)))
for w in worlds:
    print("   pits at", " ".join(sorted(w)))
print()
print("now ASK the knowledge base about each square:")
for sq in SQUARES:
    always = all(sq in w for w in worlds)
    never = all(sq not in w for w in worlds)
    verdict = ("a pit is CERTAIN, it is ENTAILED" if always else
               "a pit is IMPOSSIBLE, safe" if never else
               "UNKNOWN: a pit in some worlds and not in others")
    print("   %-4s %s" % (sq, verdict))
print()
print("1,2 is provably safe although the agent has never been there, and 2,2 and")
print("3,1 are genuinely unknown. A knowledge base answers three ways, not two.")

visited 1,1 with no breeze, and 2,1 with a breeze. no pit ever seen.
6 of the 64 conceivable worlds are consistent with that:
   pits at 3,1
   pits at 3,1 3,2
   pits at 2,2
   pits at 2,2 3,2
   pits at 2,2 3,1
   pits at 2,2 3,1 3,2

now ASK the knowledge base about each square:
   1,1  a pit is IMPOSSIBLE, safe
   1,2  a pit is IMPOSSIBLE, safe
   2,1  a pit is IMPOSSIBLE, safe
   2,2  UNKNOWN: a pit in some worlds and not in others
   3,1  UNKNOWN: a pit in some worlds and not in others
   3,2  UNKNOWN: a pit in some worlds and not in others

1,2 is provably safe although the agent has never been there, and 2,2 and
3,1 are genuinely unknown. A knowledge base answers three ways, not two.

Square 1,2 is provably safe and the agent has never been there. That is the whole value of a knowledge base in one line. Nothing the agent perceived said anything about 1,2; the conclusion comes from the sentence "no breeze at 1,1 means no pit next to 1,1", which the agent was told once and applies here.

And 2,2 and 3,1 are genuinely unknown. In some consistent worlds 2,2 has a pit and in others 3,1 does. The knowledge base does not guess, and an agent that read unknown as safe would have a one-in-two chance of dying. What to do when the answer is unknown is Module 1's fourth row, and this is where the need for it appears.

The three ways an ASK is answered, mechanically

The enumeration above is the definition of entailment made into a procedure, and it is worth seeing as a general recipe.

1. List every world, that is every assignment of true or false to every symbol.
2. Discard the worlds in which the knowledge base is false.
3. For the query: true in all survivors means yes; false in all means no; otherwise unknown.

This is called model checking and it is correct and unusable at scale: with n symbols there are 2 to the power n worlds. Sixty-four here; a knowledge base about a chessboard has 2 to the power 64. Inference in Propositional Logic and Conjunctive Normal Form and Resolution are how it is done without enumerating.

The knowledge level and the implementation level

A distinction worth 5 marks and easy to state.

At the knowledge level you say only what the agent knows: "no breeze at 1,1", "a breeze means a pit next door". This is the specification, and it can be written before any code.

At the implementation level you say how it is stored and searched: as a list of clauses, as a set of Python tuples, in a database.

The knowledge level is where the agent is designed, and the point of the separation is that the same knowledge can be implemented many ways, and the agent's behaviour is determined by the knowledge rather than by the implementation. That is the property the previous architectures did not have: changing a reflex agent's behaviour meant changing its code.

Declarative and procedural

The same distinction under its other name, which papers also use.

The honest version of this: real systems are both. A knowledge-based agent's inference engine is procedural code; what it reasons over is declarative. The claim of this row is only that the KNOWLEDGE should be declarative, so that it can be added to, inspected and explained.

Distinctions