SOLUTION MANUAL
Artificial Intelligence: A Modern Approach, 4th edition
By Stuart Russell, Peter Norvig
M
PR
ES
SI
VE
G
R
AD
ES
, Table of Content
Introduction
Intelligent Agents
Solving Problems by Searching
Search in Complex Environments
M
Adversarial Search and Games
Constraint Satisfaction Problems
PR
Logical Agents
First-Order Logic
Inference in First-Order Logic
Knowledge Representation
ES
Automated Planning
Quantifying Uncertainty
Probabilistic Reasoning
Probabilistic Reasoning over Time
SI
Probabilistic Programming
Making Simple Decisions
Making Complex Decisions
VE
Multiagent Decision Making
Learning from Examples
Learning Probabilistic Models
G
Deep Learning
Reinforcement Learning
Natural Language Processing
R
Deep Learning for Natural Language Processing
Robotics
AD
Philosophy and Ethics of AI
The Future of AI
ES
, TREWQ
EXERCISES 1
M
INTRODUCTION
PR
Note that for many of the questions in this chapter, we give references where answers can be
found rather than writing them out—the full answers would be far too long.
1.1 What Is AI?
ES
Exercise 1.1.#DEFA
Define in your own words: (a) intelligence, (b) artificial intelligence, (c) agent, (d) ra-
tionality, (e) logical reasoning.
SI
a. Dictionary definitions of intelligence talk about “the capacity to acquire and apply
knowledge” or “the faculty of thought and reason” or “the ability to comprehend and
profit from experience.” These are all reasonable answers, but if we want something
VE
quantifiable we would use something like “the ability to act successfully across a wide
range of objectives in complex environments.”
b. We define artificial intelligence as the study and construction of agent programs that
perform well in a given class of environments, for a given agent architecture; they do
the right thing. An important part of that is dealing with the uncertainty of what the
current state is, what the outcome of possible actions might be, and what is it that we
G
really desire.
c. We define an agent as an entity that takes action in response to percepts from an envi-
ronment.
d. We define rationality as the property of a system which does the “right thing” given
R
what it knows. See Section 2.2 for a more complete discussion. The basic concept is
perfect rationality; Section ?? describes the impossibility of achieving perfect rational-
ity and proposes an alternative definition.
AD
e. We define logical reasoning as the a process of deriving new sentences from old, such
that the new sentences are necessarily true if the old ones are true. (Notice that does not
refer to any specific syntax or formal language, but it does require a well-defined notion
of truth.)
ES
Exercise 1.1.#TURI
Read Turing’s original paper on AI (Turing, 1950). In the paper, he discusses several
objections to his proposed enterprise and his test for intelligence. Which objections still carry
TREWQ
, TREWQ
Section 1.1 What Is AI? 3
weight? Are his refutations valid? Can you think of new objections arising from develop-
M
ments since he wrote the paper? In the paper, he predicts that, by the year 2000, a computer
will have a 30% chance of passing a five-minute Turing Test with an unskilled interrogator.
What chance do you think a computer would have today? In another 25 years?
PR
See the solution for exercise 26.1 for some discussion of potential objections.
The probability of fooling an interrogator depends on just how unskilled the interrogator
is. A few entrants in the Loebner prize competitions have fooled judges, although if you
look at the transcripts, it looks like the judges were having fun rather than taking their job
seriously. There certainly have been examples of a chatbot or other online agent fooling
humans. For example, see the description of the Julia chatbot at www.lazytd.com/lti/
ES
julia/. We’d say the chance today is something like 10%, with the variation depending
more on the skill of the interrogator rather than the program. In 25 years, we expect that
the entertainment industry (movies, video games, commercials) will have made sufficient
investments in artificial actors to create very credible impersonators.
Note that governments and international organizations are seriously considering rules that
SI
require AI systems to be identified as such. In California, it is already illegal for machines to
impersonate humans in certain circumstances.
Exercise 1.1.#REFL
VE
Are reflex actions (such as flinching from a hot stove) rational? Are they intelligent?
Yes, they are rational, because slower, deliberative actions would tend to result in more
damage to the hand. If “intelligent” means “applying knowledge” or “using thought and
reasoning” then it does not require intelligence to make a reflex action.
G
Exercise 1.1.#SYAI
To what extent are the following computer systems instances of artificial intelligence:
R
• Supermarket bar code scanners.
• Web search engines.
• Voice-activated telephone menus.
AD
• Spelling and grammar correction features in word processing programs.
• Internet routing algorithms that respond dynamically to the state of the network.
• Although bar code scanning is in a sense computer vision, these are not AI systems.
The problem of reading a bar code is an extremely limited and artificial form of visual
ES
interpretation, and it has been carefully designed to be as simple as possible, given the
hardware.
• In many respects. The problem of determining the relevance of a web page to a query
is a problem in natural language understanding, and the techniques are related to those
TREWQ
Artificial Intelligence: A Modern Approach, 4th edition
By Stuart Russell, Peter Norvig
M
PR
ES
SI
VE
G
R
AD
ES
, Table of Content
Introduction
Intelligent Agents
Solving Problems by Searching
Search in Complex Environments
M
Adversarial Search and Games
Constraint Satisfaction Problems
PR
Logical Agents
First-Order Logic
Inference in First-Order Logic
Knowledge Representation
ES
Automated Planning
Quantifying Uncertainty
Probabilistic Reasoning
Probabilistic Reasoning over Time
SI
Probabilistic Programming
Making Simple Decisions
Making Complex Decisions
VE
Multiagent Decision Making
Learning from Examples
Learning Probabilistic Models
G
Deep Learning
Reinforcement Learning
Natural Language Processing
R
Deep Learning for Natural Language Processing
Robotics
AD
Philosophy and Ethics of AI
The Future of AI
ES
, TREWQ
EXERCISES 1
M
INTRODUCTION
PR
Note that for many of the questions in this chapter, we give references where answers can be
found rather than writing them out—the full answers would be far too long.
1.1 What Is AI?
ES
Exercise 1.1.#DEFA
Define in your own words: (a) intelligence, (b) artificial intelligence, (c) agent, (d) ra-
tionality, (e) logical reasoning.
SI
a. Dictionary definitions of intelligence talk about “the capacity to acquire and apply
knowledge” or “the faculty of thought and reason” or “the ability to comprehend and
profit from experience.” These are all reasonable answers, but if we want something
VE
quantifiable we would use something like “the ability to act successfully across a wide
range of objectives in complex environments.”
b. We define artificial intelligence as the study and construction of agent programs that
perform well in a given class of environments, for a given agent architecture; they do
the right thing. An important part of that is dealing with the uncertainty of what the
current state is, what the outcome of possible actions might be, and what is it that we
G
really desire.
c. We define an agent as an entity that takes action in response to percepts from an envi-
ronment.
d. We define rationality as the property of a system which does the “right thing” given
R
what it knows. See Section 2.2 for a more complete discussion. The basic concept is
perfect rationality; Section ?? describes the impossibility of achieving perfect rational-
ity and proposes an alternative definition.
AD
e. We define logical reasoning as the a process of deriving new sentences from old, such
that the new sentences are necessarily true if the old ones are true. (Notice that does not
refer to any specific syntax or formal language, but it does require a well-defined notion
of truth.)
ES
Exercise 1.1.#TURI
Read Turing’s original paper on AI (Turing, 1950). In the paper, he discusses several
objections to his proposed enterprise and his test for intelligence. Which objections still carry
TREWQ
, TREWQ
Section 1.1 What Is AI? 3
weight? Are his refutations valid? Can you think of new objections arising from develop-
M
ments since he wrote the paper? In the paper, he predicts that, by the year 2000, a computer
will have a 30% chance of passing a five-minute Turing Test with an unskilled interrogator.
What chance do you think a computer would have today? In another 25 years?
PR
See the solution for exercise 26.1 for some discussion of potential objections.
The probability of fooling an interrogator depends on just how unskilled the interrogator
is. A few entrants in the Loebner prize competitions have fooled judges, although if you
look at the transcripts, it looks like the judges were having fun rather than taking their job
seriously. There certainly have been examples of a chatbot or other online agent fooling
humans. For example, see the description of the Julia chatbot at www.lazytd.com/lti/
ES
julia/. We’d say the chance today is something like 10%, with the variation depending
more on the skill of the interrogator rather than the program. In 25 years, we expect that
the entertainment industry (movies, video games, commercials) will have made sufficient
investments in artificial actors to create very credible impersonators.
Note that governments and international organizations are seriously considering rules that
SI
require AI systems to be identified as such. In California, it is already illegal for machines to
impersonate humans in certain circumstances.
Exercise 1.1.#REFL
VE
Are reflex actions (such as flinching from a hot stove) rational? Are they intelligent?
Yes, they are rational, because slower, deliberative actions would tend to result in more
damage to the hand. If “intelligent” means “applying knowledge” or “using thought and
reasoning” then it does not require intelligence to make a reflex action.
G
Exercise 1.1.#SYAI
To what extent are the following computer systems instances of artificial intelligence:
R
• Supermarket bar code scanners.
• Web search engines.
• Voice-activated telephone menus.
AD
• Spelling and grammar correction features in word processing programs.
• Internet routing algorithms that respond dynamically to the state of the network.
• Although bar code scanning is in a sense computer vision, these are not AI systems.
The problem of reading a bar code is an extremely limited and artificial form of visual
ES
interpretation, and it has been carefully designed to be as simple as possible, given the
hardware.
• In many respects. The problem of determining the relevance of a web page to a query
is a problem in natural language understanding, and the techniques are related to those
TREWQ
