Instructor’s Solution Manual v v
ArtificialIntelligence v
A Modern Approach
v v v
Fourth Edition v
Stuart J. Russell and Peter Norvig
v v v v v
with contributions from
v v
Nalin Chhibber, Ernest Davis, Nicholas J. Hay, Jared Moore, Alex Rudnick,
v v v v v v v v v v
Mehran Sahami, Xiaocheng Mesut Yang, and Albert Yu
v v v v v v v v
This vsolution vmanual vis vintended vfor vthe vinstructor vof va vclass. vStudents vshould vuse vthe
vonline vsite vfor vexercises vat vaimacode.github.io/aima-exercises. v That vsite vis
vopen vfor vanyone vto vuse. vIt voffers vsolutions vfor vsome vbut vnot vall vof vthe vexercises; van
vinstructor vcan vcheck vthere vto vsee vwhich vones vhave vsolutions. v The vexercises vare vonline
vrather vthan vin vthe vtextbook vitself vbecause v(a) vthe vtextbook vis vlong venough vas vis, vand v(b)
vwe vwanted vto vbe vable vto vupdate vthe vexercises vfrequently.
,EXERCISES 1
INTRODUCTION
Note vthat vfor vmany vof vthe vquestions vin vthis vchapter, vwe vgive vreferences vwhere vanswers vcan
vbe vfound vrather vthan vwriting vthem vout—the vfull vanswers vwould vbe vfar vtoo vlong.
1.1 What Is AI?
v v v
Exercise v1.1.#DEFA
Define vin vyour vown vwords: v (a) vintelligence, v(b) vartificial vintelligence, v(c) vagent, v(d) vra-
vtionality, v(e) vlogical vreasoning.
a. Dictionary vdefinitions vof vintelligence vtalk vabout v―the vcapacity vto vacquire vand vapply
vknowledge‖ vor v―the vfaculty vof vthought vand vreason‖ vor v―the vability vto vcomprehend
vand vprofit vfrom vexperience.‖ v These vare vall vreasonable vanswers, vbut vif vwe vwant
vsomething vquantifiable vwe vwould vuse vsomething vlike v―the vability vto vact vsuccessfully
vacross va vwide vrange vof vobjectives vin vcomplex venvironments.‖
b. We vdefine vartificial vintelligence vas vthe vstudy vand vconstruction vof vagent vprograms
vthat vperform vwell vin va vgiven vclass vof venvironments, vfor va vgiven vagent varchitecture;
vthey vdo vthe vright vthing. v An vimportant vpart vof vthat vis vdealing vwith vthe vuncertainty
vof vwhat vthe vcurrent vstate vis, vwhat vthe voutcome vof vpossible vactions vmight vbe, vand
vwhat vis vit vthat vwe vreally vdesire.
c. We vdefine van vagent vas van ventity vthat vtakes vaction vin vresponse vto vpercepts vfrom van
venvi- vronment.
d. We vdefine vrationality vas vthe vproperty vof va vsystem vwhich vdoes vthe v―right vthing‖
vgiven vwhat vit vknows. v See vSection v2.2 vfor va vmore vcomplete vdiscussion. v The vbasic
vconcept vis vperfect vrationality; vSection v?? vdescribes vthe vimpossibility vof vachieving
vperfect vrational- vity vand vproposes van valternative vdefinition.
e. We vdefine vlogical vreasoning vas vthe va vprocess vof vderiving vnew vsentences vfrom vold,
vsuch vthat vthe vnew vsentences vare vnecessarily vtrue vif vthe vold vones vare vtrue. v(Notice vthat
vdoes vnot vrefer vto vany vspecific vsyntax vor vformal vlanguage, vbut vit vdoes vrequire va vwell-
defined vnotion vof vtruth.)
Exercise v1.1.#TURI
Read vTuring‘s voriginal vpaper von vAI v(Turing, v1950). v In vthe vpaper, vhe vdiscusses vseveral
vobjections vto vhis vproposed venterprise vand vhis vtest vfor vintelligence. vWhich vobjections vstill vcarry
, Section v1.1 v v What vIs 3
AI?
weight? vAre vhis vrefutations vvalid? v Can vyou vthink vof vnew vobjections varising vfrom
vdevelop- vments vsince vhe vwrote vthe vpaper? vIn vthe vpaper, vhe vpredicts vthat, vby vthe vyear
v2000, va vcomputer vwill vhave va v30% vchance vof vpassing va vfive-minute vTuring vTest vwith van
vunskilled vinterrogator. vWhat vchance vdo vyou vthink va vcomputer vwould vhave vtoday? vIn
vanother v25 vyears?
See vthe vsolution vfor vexercise v26.1 vfor vsome vdiscussion vof vpotential vobjections.
The vprobability vof vfooling van vinterrogator vdepends von vjust vhow vunskilled vthe
vinterrogator vis. v A vfew ventrants vin vthe vLoebner vprize vcompetitions vhave vfooled vjudges,
valthough vif vyou vlook vat vthe vtranscripts, vit vlooks vlike vthe vjudges vwere vhaving vfun vrather
vthan vtaking vtheir vjob vseriously. vThere vcertainly vhave vbeen vexamples vof va vchatbot vor vother
vonline vagent vfooling vhumans. vFor vexample, vsee vthe vdescription vof vthe vJulia vchatbot vat
vwww.lazytd.com/lti/ vjulia/. v We‘d vsay vthe vchance vtoday vis vsomething vlike
v10%, vwith vthe vvariation vdepending vmore von vthe vskill vof vthe vinterrogator vrather vthan vthe
vprogram. v In v25 vyears, vwe vexpect vthat v the ventertainment vindustry v(movies, vvideo vgames,
vcommercials) vwill vhave vmade vsufficient vinvestments vin vartificial vactors vto vcreate vvery
vcredible vimpersonators.
Note vthat vgovernments vand vinternational vorganizations vare vseriously vconsidering vrules
vthat vrequire vAI vsystems vto vbe videntified vas vsuch. vIn vCalifornia, vit vis valready villegal vfor
vmachines vto vimpersonate vhumans vin vcertain vcircumstances.
Exercise v1.1.#REFL
Are vreflex vactions v(such vas vflinching vfrom va vhot vstove) vrational? vAre vthey vintelligent?
Yes, vthey vare vrational, vbecause vslower, vdeliberative vactions vwould vtend vto vresult vin
vmore vdamage vto vthe vhand. vIf v―intelligent‖ vmeans v―applying vknowledge‖ vor v―using
vthought vand vreasoning‖ vthen vit vdoes vnot vrequire vintelligence vto vmake va vreflex vaction.
Exercise v1.1.#SYAI
To vwhat vextent vare vthe vfollowing vcomputer vsystems vinstances vof vartificial vintelligence:
Supermarket vbar vcode vscanners.
Web vsearch vengines.
Voice-activated vtelephone vmenus.
Spelling vand vgrammar vcorrection vfeatures vin vword vprocessing vprograms.
Internet vrouting valgorithms vthat vrespond vdynamically vto vthe vstate vof vthe vnetwork.
• Although vbar vcode vscanning vis vin va vsense vcomputer vvision, vthese vare vnot vAI
vsystems. vThe vproblem vof vreading va vbar vcode vis van vextremely vlimited vand vartificial
vform vof vvisual vinterpretation, vand vit vhas vbeen vcarefully vdesigned vto vbe vas vsimple vas
vpossible, vgiven vthe vhardware.
• In vmany vrespects. vThe vproblem vof vdetermining vthe vrelevance vof va vweb vpage vto va
vquery vis va vproblem vin vnatural vlanguage vunderstanding, vand vthe vtechniques vare
vrelated vto vthose
, 4 Exercises v 1 v
Introduction
we vwill vdiscuss vin vChapters v23 vand v24. v Search vengines valso vuse vclustering
vtechniques vanalogous vto vthose vwe vdiscuss vin vChapter v20. vLikewise, vother
vfunctionalities vprovided vby va vsearch vengines vuse vintelligent vtechniques; vfor vinstance,
vthe vspelling vcorrector vuses va vform vof vdata vmining vbased von vobserving vusers‘
vcorrections vof vtheir vown vspelling verrors. vOn vthe vother vhand, vthe vproblem vof vindexing
vbillions vof vweb vpages vin va vway vthat vallows vretrieval vin vseconds vis va vproblem vin
vdatabase vdesign, vnot vin vartificial vintelligence.
• To va v limited v extent. v Such v menus v tends v to v use v vocabularies v which v are v very v limited v –
e.g. vthe vdigits, v―Yes‖, vand v―No‖ v— vand vwithin vthe vdesigners‘ vcontrol, vwhich vgreatly
vsimplifies vthe vproblem. vOn vthe vother vhand, vthe vprograms vmust vdeal vwith van
vuncontrolled vspace vof vall vkinds vof vvoices vand vaccents. vModern vdigital vassistants
vlike vSiri vand vthe vGoogle vAssistant vmake vmore vuse vof vartificial vintelligence
vtechniques, vbut vstill vhave va vlimited vrepetoire.
• Slightly vat vmost. vThe vspelling vcorrection vfeature vhere vis vdone vby vstring vcomparison vto
va vfixed vdictionary. vThe vgrammar vcorrection vis vmore vsophisticated vas vit vneed vto vuse va
vset vof vrather vcomplex vrules vreflecting vthe vstructure vof vnatural vlanguage, vbut vstill vthis
vis va vvery vlimited vand vfixed vtask.
The vspelling vcorrectors vin vsearch vengines vwould vbe vconsidered vmuch vmore
vnearly vinstances vof vAI vthan vthe vWord vspelling vcorrector vare, vfirst, vbecause vthe vtask
vis vmuch vmore vdynamic v– vsearch vengine vspelling vcorrectors vdeal vvery veffectively
vwith vproper vnames, vwhich vare vdetected vdynamically vfrom vuser vqueries v– vand, vsecond,
vbecause vof vthe vtechnique vused v– vdata vmining vfrom vuser vqueries vvs. vstring vmatching.
• This vis vborderline. vThere vis vsomething vto vbe vsaid vfor vviewing vthese vas vintelligent
vagents vworking vin vcyberspace. v The vtask vis vsophisticated, vthe vinformation vavailable vis
vpartial, vthe vtechniques vare vheuristic v(not vguaranteed voptimal), vand vthe vstate vof vthe
vworld vis vdynamic. vAll vof vthese vare vcharacteristic vof vintelligent vactivities. vOn vthe vother
vhand, vthe vtask vis vvery vfar vfrom vthose vnormally vcarried vout vin vhuman vcognition. vIn
vrecent vyears vthere vhave vbeen vsuggestions vto vbase vmore vcore valgorithmic vwork von
vmachine vlearning.
Exercise v1.1.#COGN
Many vof vthe vcomputational vmodels vof vcognitive vactivities vthat vhave vbeen vproposed
vinvolve vquite vcomplex vmathematical voperations, vsuch vas vconvolving van vimage vwith va
vGaussian vor vfinding va vminimum vof vthe ventropy vfunction. v Most vhumans v(and vcertainly
vall vanimals) vnever vlearn vthis vkind vof vmathematics vat vall, valmost vno vone vlearns vit vbefore
vcollege, vand valmost vno vone vcan vcompute vthe vconvolution vof va vfunction vwith va vGaussian
vin vtheir vhead. v What vsense vdoes vit vmake vto vsay vthat vthe v―vision vsystem‖ vis vdoing vthis
vkind vof vmathematics, vwhereas vthe vactual vperson vhas vno videa vhow vto vdo vit?
Presumably vthe vbrain vhas vevolved vso vas vto vcarry vout vthis voperations von vvisual vimages,
vbut vthe vmechanism vis vonly vaccessible vfor vone vparticular vpurpose vin vthis vparticular
vcognitive vtask vof vimage vprocessing. vUntil vabout vtwo vcenturies vago vthere vwas vno
vadvantage vin vpeople v(or vanimals) vbeing vable vto vcompute vthe vconvolution vof va vGaussian
vfor vany vother vpurpose.
The vreally vinteresting vquestion vhere vis vwhat vwe vmean vby vsaying vthat vthe v―actual
ArtificialIntelligence v
A Modern Approach
v v v
Fourth Edition v
Stuart J. Russell and Peter Norvig
v v v v v
with contributions from
v v
Nalin Chhibber, Ernest Davis, Nicholas J. Hay, Jared Moore, Alex Rudnick,
v v v v v v v v v v
Mehran Sahami, Xiaocheng Mesut Yang, and Albert Yu
v v v v v v v v
This vsolution vmanual vis vintended vfor vthe vinstructor vof va vclass. vStudents vshould vuse vthe
vonline vsite vfor vexercises vat vaimacode.github.io/aima-exercises. v That vsite vis
vopen vfor vanyone vto vuse. vIt voffers vsolutions vfor vsome vbut vnot vall vof vthe vexercises; van
vinstructor vcan vcheck vthere vto vsee vwhich vones vhave vsolutions. v The vexercises vare vonline
vrather vthan vin vthe vtextbook vitself vbecause v(a) vthe vtextbook vis vlong venough vas vis, vand v(b)
vwe vwanted vto vbe vable vto vupdate vthe vexercises vfrequently.
,EXERCISES 1
INTRODUCTION
Note vthat vfor vmany vof vthe vquestions vin vthis vchapter, vwe vgive vreferences vwhere vanswers vcan
vbe vfound vrather vthan vwriting vthem vout—the vfull vanswers vwould vbe vfar vtoo vlong.
1.1 What Is AI?
v v v
Exercise v1.1.#DEFA
Define vin vyour vown vwords: v (a) vintelligence, v(b) vartificial vintelligence, v(c) vagent, v(d) vra-
vtionality, v(e) vlogical vreasoning.
a. Dictionary vdefinitions vof vintelligence vtalk vabout v―the vcapacity vto vacquire vand vapply
vknowledge‖ vor v―the vfaculty vof vthought vand vreason‖ vor v―the vability vto vcomprehend
vand vprofit vfrom vexperience.‖ v These vare vall vreasonable vanswers, vbut vif vwe vwant
vsomething vquantifiable vwe vwould vuse vsomething vlike v―the vability vto vact vsuccessfully
vacross va vwide vrange vof vobjectives vin vcomplex venvironments.‖
b. We vdefine vartificial vintelligence vas vthe vstudy vand vconstruction vof vagent vprograms
vthat vperform vwell vin va vgiven vclass vof venvironments, vfor va vgiven vagent varchitecture;
vthey vdo vthe vright vthing. v An vimportant vpart vof vthat vis vdealing vwith vthe vuncertainty
vof vwhat vthe vcurrent vstate vis, vwhat vthe voutcome vof vpossible vactions vmight vbe, vand
vwhat vis vit vthat vwe vreally vdesire.
c. We vdefine van vagent vas van ventity vthat vtakes vaction vin vresponse vto vpercepts vfrom van
venvi- vronment.
d. We vdefine vrationality vas vthe vproperty vof va vsystem vwhich vdoes vthe v―right vthing‖
vgiven vwhat vit vknows. v See vSection v2.2 vfor va vmore vcomplete vdiscussion. v The vbasic
vconcept vis vperfect vrationality; vSection v?? vdescribes vthe vimpossibility vof vachieving
vperfect vrational- vity vand vproposes van valternative vdefinition.
e. We vdefine vlogical vreasoning vas vthe va vprocess vof vderiving vnew vsentences vfrom vold,
vsuch vthat vthe vnew vsentences vare vnecessarily vtrue vif vthe vold vones vare vtrue. v(Notice vthat
vdoes vnot vrefer vto vany vspecific vsyntax vor vformal vlanguage, vbut vit vdoes vrequire va vwell-
defined vnotion vof vtruth.)
Exercise v1.1.#TURI
Read vTuring‘s voriginal vpaper von vAI v(Turing, v1950). v In vthe vpaper, vhe vdiscusses vseveral
vobjections vto vhis vproposed venterprise vand vhis vtest vfor vintelligence. vWhich vobjections vstill vcarry
, Section v1.1 v v What vIs 3
AI?
weight? vAre vhis vrefutations vvalid? v Can vyou vthink vof vnew vobjections varising vfrom
vdevelop- vments vsince vhe vwrote vthe vpaper? vIn vthe vpaper, vhe vpredicts vthat, vby vthe vyear
v2000, va vcomputer vwill vhave va v30% vchance vof vpassing va vfive-minute vTuring vTest vwith van
vunskilled vinterrogator. vWhat vchance vdo vyou vthink va vcomputer vwould vhave vtoday? vIn
vanother v25 vyears?
See vthe vsolution vfor vexercise v26.1 vfor vsome vdiscussion vof vpotential vobjections.
The vprobability vof vfooling van vinterrogator vdepends von vjust vhow vunskilled vthe
vinterrogator vis. v A vfew ventrants vin vthe vLoebner vprize vcompetitions vhave vfooled vjudges,
valthough vif vyou vlook vat vthe vtranscripts, vit vlooks vlike vthe vjudges vwere vhaving vfun vrather
vthan vtaking vtheir vjob vseriously. vThere vcertainly vhave vbeen vexamples vof va vchatbot vor vother
vonline vagent vfooling vhumans. vFor vexample, vsee vthe vdescription vof vthe vJulia vchatbot vat
vwww.lazytd.com/lti/ vjulia/. v We‘d vsay vthe vchance vtoday vis vsomething vlike
v10%, vwith vthe vvariation vdepending vmore von vthe vskill vof vthe vinterrogator vrather vthan vthe
vprogram. v In v25 vyears, vwe vexpect vthat v the ventertainment vindustry v(movies, vvideo vgames,
vcommercials) vwill vhave vmade vsufficient vinvestments vin vartificial vactors vto vcreate vvery
vcredible vimpersonators.
Note vthat vgovernments vand vinternational vorganizations vare vseriously vconsidering vrules
vthat vrequire vAI vsystems vto vbe videntified vas vsuch. vIn vCalifornia, vit vis valready villegal vfor
vmachines vto vimpersonate vhumans vin vcertain vcircumstances.
Exercise v1.1.#REFL
Are vreflex vactions v(such vas vflinching vfrom va vhot vstove) vrational? vAre vthey vintelligent?
Yes, vthey vare vrational, vbecause vslower, vdeliberative vactions vwould vtend vto vresult vin
vmore vdamage vto vthe vhand. vIf v―intelligent‖ vmeans v―applying vknowledge‖ vor v―using
vthought vand vreasoning‖ vthen vit vdoes vnot vrequire vintelligence vto vmake va vreflex vaction.
Exercise v1.1.#SYAI
To vwhat vextent vare vthe vfollowing vcomputer vsystems vinstances vof vartificial vintelligence:
Supermarket vbar vcode vscanners.
Web vsearch vengines.
Voice-activated vtelephone vmenus.
Spelling vand vgrammar vcorrection vfeatures vin vword vprocessing vprograms.
Internet vrouting valgorithms vthat vrespond vdynamically vto vthe vstate vof vthe vnetwork.
• Although vbar vcode vscanning vis vin va vsense vcomputer vvision, vthese vare vnot vAI
vsystems. vThe vproblem vof vreading va vbar vcode vis van vextremely vlimited vand vartificial
vform vof vvisual vinterpretation, vand vit vhas vbeen vcarefully vdesigned vto vbe vas vsimple vas
vpossible, vgiven vthe vhardware.
• In vmany vrespects. vThe vproblem vof vdetermining vthe vrelevance vof va vweb vpage vto va
vquery vis va vproblem vin vnatural vlanguage vunderstanding, vand vthe vtechniques vare
vrelated vto vthose
, 4 Exercises v 1 v
Introduction
we vwill vdiscuss vin vChapters v23 vand v24. v Search vengines valso vuse vclustering
vtechniques vanalogous vto vthose vwe vdiscuss vin vChapter v20. vLikewise, vother
vfunctionalities vprovided vby va vsearch vengines vuse vintelligent vtechniques; vfor vinstance,
vthe vspelling vcorrector vuses va vform vof vdata vmining vbased von vobserving vusers‘
vcorrections vof vtheir vown vspelling verrors. vOn vthe vother vhand, vthe vproblem vof vindexing
vbillions vof vweb vpages vin va vway vthat vallows vretrieval vin vseconds vis va vproblem vin
vdatabase vdesign, vnot vin vartificial vintelligence.
• To va v limited v extent. v Such v menus v tends v to v use v vocabularies v which v are v very v limited v –
e.g. vthe vdigits, v―Yes‖, vand v―No‖ v— vand vwithin vthe vdesigners‘ vcontrol, vwhich vgreatly
vsimplifies vthe vproblem. vOn vthe vother vhand, vthe vprograms vmust vdeal vwith van
vuncontrolled vspace vof vall vkinds vof vvoices vand vaccents. vModern vdigital vassistants
vlike vSiri vand vthe vGoogle vAssistant vmake vmore vuse vof vartificial vintelligence
vtechniques, vbut vstill vhave va vlimited vrepetoire.
• Slightly vat vmost. vThe vspelling vcorrection vfeature vhere vis vdone vby vstring vcomparison vto
va vfixed vdictionary. vThe vgrammar vcorrection vis vmore vsophisticated vas vit vneed vto vuse va
vset vof vrather vcomplex vrules vreflecting vthe vstructure vof vnatural vlanguage, vbut vstill vthis
vis va vvery vlimited vand vfixed vtask.
The vspelling vcorrectors vin vsearch vengines vwould vbe vconsidered vmuch vmore
vnearly vinstances vof vAI vthan vthe vWord vspelling vcorrector vare, vfirst, vbecause vthe vtask
vis vmuch vmore vdynamic v– vsearch vengine vspelling vcorrectors vdeal vvery veffectively
vwith vproper vnames, vwhich vare vdetected vdynamically vfrom vuser vqueries v– vand, vsecond,
vbecause vof vthe vtechnique vused v– vdata vmining vfrom vuser vqueries vvs. vstring vmatching.
• This vis vborderline. vThere vis vsomething vto vbe vsaid vfor vviewing vthese vas vintelligent
vagents vworking vin vcyberspace. v The vtask vis vsophisticated, vthe vinformation vavailable vis
vpartial, vthe vtechniques vare vheuristic v(not vguaranteed voptimal), vand vthe vstate vof vthe
vworld vis vdynamic. vAll vof vthese vare vcharacteristic vof vintelligent vactivities. vOn vthe vother
vhand, vthe vtask vis vvery vfar vfrom vthose vnormally vcarried vout vin vhuman vcognition. vIn
vrecent vyears vthere vhave vbeen vsuggestions vto vbase vmore vcore valgorithmic vwork von
vmachine vlearning.
Exercise v1.1.#COGN
Many vof vthe vcomputational vmodels vof vcognitive vactivities vthat vhave vbeen vproposed
vinvolve vquite vcomplex vmathematical voperations, vsuch vas vconvolving van vimage vwith va
vGaussian vor vfinding va vminimum vof vthe ventropy vfunction. v Most vhumans v(and vcertainly
vall vanimals) vnever vlearn vthis vkind vof vmathematics vat vall, valmost vno vone vlearns vit vbefore
vcollege, vand valmost vno vone vcan vcompute vthe vconvolution vof va vfunction vwith va vGaussian
vin vtheir vhead. v What vsense vdoes vit vmake vto vsay vthat vthe v―vision vsystem‖ vis vdoing vthis
vkind vof vmathematics, vwhereas vthe vactual vperson vhas vno videa vhow vto vdo vit?
Presumably vthe vbrain vhas vevolved vso vas vto vcarry vout vthis voperations von vvisual vimages,
vbut vthe vmechanism vis vonly vaccessible vfor vone vparticular vpurpose vin vthis vparticular
vcognitive vtask vof vimage vprocessing. vUntil vabout vtwo vcenturies vago vthere vwas vno
vadvantage vin vpeople v(or vanimals) vbeing vable vto vcompute vthe vconvolution vof va vGaussian
vfor vany vother vpurpose.
The vreally vinteresting vquestion vhere vis vwhat vwe vmean vby vsaying vthat vthe v―actual
