Unit3:Informed and Uninformed search

Problem solving by Intelligent agent by searching

1. Unit 3: Informed and Uninformed Search LH 8
Presented By : Tekendra Nath Yogi
[email protected]
College Of Applied Business And Technology

2. Contd…
•Unit3:InformedandUninformedSearch LH8
–3.1WhysearchinAI?
–3.2Blindsearch(Un-informedsearch)
•3.2.1Breadthfirstsearch(BFS)
–Variations:Uniformcostsearch
•3.2.2Depthfirstsearch(DFS)
–Variations:Depthlimitedsearch,IterativedeepeningDFS
–3.3Heuristicsearch(Informedsearch)
•3.3.1Hillclimbing
–TheFoothillsProblem
–ThePlateauProblem
–TheRidgeProblem
•3.3.2Greedy(Best-first)search
•3.3.3A*algorithmsearch
•3.3.4Means-EndsAnalysis:HouseholdROBOT,MonkeyBananaProblem
212/25/2018 By: Tekendra Nath Yogi

3. Contd…
•Unit3:InformedandUninformedSearchcontd…
–3.4GeneralProblemSolving(GPS):Problemsolvingagents
•3.4.1Constraintsatisfactionproblem
–ConstraintSatisfactionSearch
–AND/ORtrees
–Thebidirectionalsearch
–Crypto-arithmatics
–3.5GameplayingandAI
•3.2.1GameTreesandMini-maxEvaluation
•3.2.2HeuristicEvaluation
•3.2.3Min-maxalgorithm(search)
•3.2.4Min-maxwithalpha-beta
•3.2.5Gamesofchance
•3.2.6Gametheory
312/25/2018 By: Tekendra Nath Yogi

4. Four General steps in problem solving
•Problemsolvingisasystematicsearchthrougharangeofpossibleactionsin
ordertoreachsomepredefinedgoalorsolution.
•Forproblemsolvingakindofgoalbasedagentcalledproblemsolvingagents
areused.
•Thisagentfirstformulatesagoalandaproblem,searchesforasequenceof
actionsthatwouldsolvetheproblem,andthenexecutestheactionsoneata
time.Whenthisiscomplete,itformulatesanothergoalandstartsover.
•Thisoverallprocessisdescribedinthefollowingfoursteps:
–Goalformulation
–Problemformulation
–Search
–Execute
412/25/2018 By: Tekendra Nath Yogi

5. Contd…
•Goalformulation:
–Intelligentagentmaximizetheirperformancemeasurebyadaptingagoal
andaimatsatisfyingit.
–Goalhelporganizebehaviorbylimitingtheobjectivesthattheagentis
tryingtoachieveandhencetheactionsitneedstoconsider.
–Goalarethesetofworldstatesinwhichthegoalissatisfied.
–Therefore,duringgoalformulationstep,specifywhatarethesuccessful
worldstates.
512/25/2018 By: Tekendra Nath Yogi

6. Contd…
•ProblemFormulation:
–Problemformulationistheprocessofdecidingwhatactionsandstatesto
consider,givenagoal.
–Therefore,theagent‟staskistofindouthowtoact,nowandinthefuture,
sothatitreachesagoalstate.
–Beforeitcandothis,itneedstodecide(orweneedtodecideonits
behalf)whatsortsofactionsandstatesitshouldconsider.
612/25/2018 By: Tekendra Nath Yogi

7. Contd…
•Searchasolution:
–Theprocessoflookingforasequenceofactionsthatreachesthegoalis
calledasearching.
–searchalgorithmtakesaproblemasainputandreturnsasolutioninthe
formofanactionsequence.
712/25/2018 By: Tekendra Nath Yogi

8. Contd…
•Execution:
–onceasolutionisfound,theactionsitrecommendscanbecarriedout.
Thisiscalledtheexecutionphase.
–onceasolutionhasbeenexecuted,theagentwillformulateanewgoal.
812/25/2018 By: Tekendra Nath Yogi

9. Problem Formulation
•A problem can be defined formally by five components:
–Initial state
–Actions
–Transition model
–Goal Test
–Path Cost
912/25/2018 By: Tekendra Nath Yogi

10. Contd…
•Initialstate:Thestatefromwhichagentstart.
•Actions:Adescriptionofthepossibleactionsavailabletotheagent.During
problemformulationweshouldspecifytheallpossibleactionsavailablefor
eachstate„s‟.
•Transitionmodel:Adescriptionofwhateachactiondoesiscalledthe
transitionmodel.Forformulatingtransitionmodelinproblemformulationwe
takestate„s‟andaction„a‟forthatstateandthenspecifytheresultingstate
„s‟
•GoalTest:Determinewhetherthegivenstateisgoalstateornot.
•PathCost:Sumofcostofeachpathfrominitialstatetothegivenstate
1012/25/2018 By: Tekendra Nath Yogi

11. One way to formally define a problem: State space Representation
•Thesetofallstatesreachablefromtheinitialstatebyanysequenceofactionsis
calledstatespace.
•Thestatespaceformsadirectedgraphinwhichnodesarestatesandthelinks
betweennodesareactions.
•AStatespacerepresentationallowsfortheformaldefinitionofaproblemwhich
makesthemovementfrominitialstatetogoalstatequiteeasy.
•Disadvantage:itisnotpossibletovisualizeallstatesforagivenproblem.Also,
theresourcesofthecomputersystemarelimitedtohandlehugestatespace
representation.
1112/25/2018 By: Tekendra Nath Yogi

12. Contd…
•StateSpacerepresentationofVacuumWorldProblem:Vacuumworld
canbeformulatedasaproblemasfollows:
–States:Thestateisdeterminedbyboththeagentlocationandthedirtlocations.The
agentisinoneoftwolocations,eachofwhichmightormightnotcontaindirt.
–Initialstate:Anystatecanbedesignatedastheinitialstate.
–Actions:Inthissimpleenvironment,eachstatehasjustthreeactions:Left,Right,
andSuck.LargerenvironmentmaymightalsoincludeUpandDown.
–TransitionModel:Theactionshavetheirexpectedeffects,exceptthatmoving
Leftinleftmostsquare,movingRightintherightmostsquare,andsuckingina
cleansquarehavingnoeffect.Thecompletestatespaceisshowninfigurebelow.
–GoalTest:Thischeckswhetherallthesquaresareclean.
–Pathcost:Eachstepcosts1,sothepathcostisthenumberofstepsinthepath.
1212/25/2018 By: Tekendra Nath Yogi

13. Contd…
1312/25/2018 By: Tekendra Nath Yogi
Fig: State space representation for the vacuum world
Here, links denote actions: L: left, R= Right, S= Suck

14. Searching For Solution
•Havingformulatedsomeproblems,wenowneedtosolvethem.
•Tosolveaproblemweshouldperformasystematicsearchthrougharangeof
possibleactionsinordertoreachsomepredefinedgoalorsolution.
•Asolutionisanactionsequence,sosearchalgorithmsworksbyconsidering
variouspossibleactionsequences.
•Thepossibleactionsequencesstartingattheinitialstateformasearchtree
withtheinitialstateattheroot;thebranchesareactionsandthenodes
correspondtostatesinthestatespaceoftheproblem.
1412/25/2018 By: Tekendra Nath Yogi

15. Contd…
•Generalsearch:
–Thesearchingprocessstartsfromtheinitialstate(rootnode)and
proceedsbyperformingthefollowingsteps:
•Checkwhetherthecurrentstateisthegoalstateornot?
•Expand the current state to generate the new sets of states.
•Choose one of the new states generated for search depending upon search
strategy.
•Repeat step 1 to 3 until the goal state is reached or there are no more state to
be expanded.
1512/25/2018 By: Tekendra Nath Yogi

16. Contd…
•TheImportanceofSearchinAI:
–ManyofthetasksunderlyingAIcanbephrasedintermsofasearchfor
thesolutiontotheproblemathand.
–Manygoalbasedagentsareessentiallyproblemsolvingagentswhich
mustdecidewhattodobysearchingforasequenceofactionsthatleadto
theirsolutions.
–Fortheproductionsystems,needtosearchforasequenceofrule
applicationsthatleadtotherequiredfactoraction.
–Forneuralnetworksystems,needtosearchforthesetofconnection
weightsthatwillresultintherequiredinputtooutputmapping.
1612/25/2018 By: Tekendra Nath Yogi

17. Contd…
•MeasuringproblemSolvingPerformance:
–Theperformanceofthesearchalgorithmscanbeevaluatedinfourways:
–Completeness:Analgorithmissaidtobecompleteifitdefinitelyfinds
solutiontotheproblem,ifexist.
–Timecomplexity:Howlongdoesittaketofindasolution?Usually
measuredintermsofthenumberofnodesexpandedduringthesearch.
–SpaceComplexity:Howmuchspaceisusedbythealgorithm?Usually
measuredintermsofthemaximumnumberofnodesinmemoryatatime
–Optimality/Admissibility:Ifasolutionisfound,isitguaranteedtobean
optimalone?Forexample,isittheonewithminimumcost?
1712/25/2018 By: Tekendra Nath Yogi

18. Classes of Search methods
•Therearetwobroadclassesofsearchmethods:
•Uninformed(orblind)searchmethods:
–Strategieshavenoadditionalinformationaboutstatesbeyondthatprovidedin
theproblemdefinition.Alltheycandoisgeneratesuccessorsanddistinguisha
goalstatefromanon-goalstate.
–Allsearchstrategiesaredistinguishedbytheorderinwhichnodesareexpanded.
•Heuristicallyinformedsearchmethods.
–Strategiesthatknowwhetheronenon-goalstateis“morepromising”thananother
arecalledinformedorheuristicsearchstrategies.
–I.e.,Inthecaseoftheheuristicallyinformedsearchmethods,oneusesdomain-
dependent(heuristic)informationinordertosearchthespacemoreefficiently.
1812/25/2018 By: Tekendra Nath Yogi

19. Uninformed (Or Blind) Search Methods:
•Blindsearchdonothaveadditionalinformationaboutstatebeyondthe
problemdefinitiontosearchasolutioninthesearchspace.
•Itproceedssystematicallybyexploringnodeseitherrandomlyorin
somepredeterminedorder.
•Basedontheorderinwhichnodesareexpanded,itisofthefollowing
types:
–BreadthFirstsearch(BFS)
•Variation:Uniformcostsearch
–DepthFirstsearch(DFS)
•Variations:Depthlimitsearch,IterativedeepeningDFS.
–Bidirectionalsearch
19Presented By: Tekendra Nath YogiIT 228 -Intro to AI

20. Breadth First Search
•BreadthFirstsearchisasimplestrategyinwhichtherootnodeisexpanded
first,thenallthesuccessorsoftherootnodeareexpandednext,thentheir
successors,andsoon.
•Ingeneral,Allnodesareexpendedatagivendepthinthesearchtreebefore
anynodesatthenextlevelareexpandeduntilthegoalreached.
–I.e.,Expandshallowestunexpendednode.
•The search tree generated by the BFS is shown in figure below:
Fig: search Tree For BFS
Note: We are using the convention that the alternatives are tried in the left to right
order.
20Presented By: Tekendra Nath YogiIT 228 -Intro to AI

21. Breadth-first search
21Presented By: Tekendra Nath YogiIT 228 -Intro to AI

22. Breadth-first search
22Presented By: Tekendra Nath YogiIT 228 -Intro to AI

23. Breadth-first search
23Presented By: Tekendra Nath YogiIT 228 -Intro to AI

24. Uniform Cost Search
•Thesearchbeginsatrootnode.Thesearchcontinuesbyvisitingthenextnode
whichhastheleasttotalcostfromtherootnode.Nodesarevisitedinthis
manneruntilagoalisreached.
•Nowgoalnodehasbeengenerated,butuniformcostsearchkeepsgoing,
choosinganode(withlesstotalcostfromtherootnodetothatnodethanthe
previouslyobtainedgoalpathcost)forexpansionandaddingasecondpath.
•Nowthealgorithmcheckstoseeifthisnewpathisbetterthantheoldone;ifit
issotheoldoneisdiscardedandnewoneisselectedforexpansionandthe
solutionisreturned.
24Presented By: Tekendra Nath YogiIT 228 -Intro to AI

25. Uniform cost search example1 (Find path from A to E)
•Expand A to B,C,D
•The path to B is the cheapest one with path cost 2.
•Expand B to E
–Total path cost = 2+9 =11
•This might not be the optimal solution since the path
AC as path cost 4 ( less than 11)
•Expand C to E
–Total path cost = 4+5 =9
•Path cost from A to D is 10 ( greater than path cost, 9)
Hence optimal path is ACE
25Presented By: Tekendra Nath YogiIT 228 -Intro to AI

26. •Thegraphbelowshowsthestep-costs
fordifferentpathsgoingfromthe
start(S)tothegoal(G).
•Useuniformcostsearchtofindthe
optimalpathtothegoal.
Presented By: Tekendra Nath Yogi 26
Home work: Uniform cost search
IT 228 -Intro to AI

27. Depth First Search
•DFSalsobeginsbyexpandingtheinitialnode.
•Looksforthegoalnodeamongallthechildrenofthecurrentnodebeforeusing
thesiblingofthisnode
•i.e.expanddeepestunexpandednode(expandmostrecentlygenerateddeepest
nodefirst.).
•The search tree generated by the DFS is shown in figure below:
27Presented By: Tekendra Nath YogiIT 228 -Intro to AI

28. Depth-first search example
•Expand deepest unexpanded node
•Here initial state is A and goal state is M
28Presented By: Tekendra Nath YogiIT 228 -Intro to AI

29. Depth-first search example
•Expand deepest unexpanded node
29Presented By: Tekendra Nath YogiIT 228 -Intro to AI

30. Depth-first search example
•Expand deepest unexpanded node
30Presented By: Tekendra Nath YogiIT 228 -Intro to AI

31. Depth-first search example
•Expand deepest unexpanded node
31Presented By: Tekendra Nath YogiIT 228 -Intro to AI

32. Depth-first search example
•Expand deepest unexpanded node
32Presented By: Tekendra Nath YogiIT 228 -Intro to AI

33. Depth-first search example
•Expand deepest unexpanded node
33Presented By: Tekendra Nath YogiIT 228 -Intro to AI

34. Depth-first search example
•Expand deepest unexpanded node
34Presented By: Tekendra Nath YogiIT 228 -Intro to AI

35. Depth-first search example
•Expand deepest unexpanded node
35Presented By: Tekendra Nath YogiIT 228 -Intro to AI

36. Depth-first search example
•Expand deepest unexpanded node
36Presented By: Tekendra Nath YogiIT 228 -Intro to AI

37. Depth-first search example
•Expand deepest unexpanded node
37Presented By: Tekendra Nath YogiIT 228 -Intro to AI

38. Depth-first search example
•Expand deepest unexpanded node
38Presented By: Tekendra Nath YogiIT 228 -Intro to AI

39. Depth-first search example
•Expanddeepestunexpandednode
•Butthistypeofsearchcangoonandon,deeperanddeeperintotree
searchspaceandthus,wecangetlost.Thisisreferredtoasblindalley.
39Presented By: Tekendra Nath YogiIT 228 -Intro to AI

40. Presented By: TekendraNath Yogi 40
Depth-limited search(Same as DFS if L= ∞)
•Depthlimitsearchisdepth-firstsearchwithdepthlimitL.
–i.e.,nodesatdepthLaretreatedastheyhavenosuccessors.
•ThedepthlimitsolvestheinfinitepathproblemofDFSbyplacinglimitonthe
depth.
•Yetitintroducesanothersourceofproblemifweareunabletofindgoodguess
ofL.Letdisthedepthofshallowestsolution.
–IfL<dthenincompletenessresultsbecausenosolutionwithinthedepthlimit.
–IfL>dthennotoptimal.
IT 228 -Intro to AI

41. Presented By: Tekendra Nath Yogi 41
Depth-limited search Example 1
•Depth limited search= DFS+ limit for the depth
–Let goal node= 11 and limit= 2
–Trace the path to the goal node using Depth limited search .
IT 228 -Intro to AI

42. Presented By: Tekendra Nath Yogi 42
Depth-limited search Example 1
•Depth limited search= DFS+ limit for the depth
•No path is found from root node to goal node because L< d.
IT 228 -Intro to AI

43. Iterative deepening search
•ItisageneralstrategytofindbestdepthlimitL.
•ItbeginbyperformingDFStoadepthofzero,thendepthofone,depthof
two,andsoonuntilasolutionisfoundorsomemaximumdepthisreached.
•ItissimilartoBFSinthatitexploresacompletelayerofnewnodesateach
iterationbeforegoingtonextlayer.
•ItissimilartoDFSforasingleiteration.
•Itispreferredwhenthereisalargesearchspaceandthedepthofasolutionis
notknown.
•Butitperformsthewastedcomputationbeforereachingthegoaldepth.
4312/25/2018 By: Tekendra Nath Yogi

44. Iterative Deepening search example
•Here initial state is A and goal state is M.
•Let we don‟t know the depth of M then the Iterative deepening search proceeds
as follows:
44Presented By: TekendraNath YogiIT 228 -Intro to AI

45. Presented By: Tekendra Nath Yogi 45
Iterative deepening search l =0
IT 228 -Intro to AI

46. Presented By: Tekendra Nath Yogi 46
Iterative deepening search l =1
IT 228 -Intro to AI

47. Presented By: TekendraNath Yogi 47
Iterative deepening search l =2
IT 228 -Intro to AI

48. Presented By: TekendraNath Yogi 48
Iterative deepening search l =3
IT 228 -Intro to AI

49. Bidirectional search
•Thissearchisusedwhenaproblemhasasinglegoalstatethatisgiven
explicitlyandallthenodegenerationoperatorshaveinverses.
•Soitisusedtofindshortestpathfromaninitialnodetogoalnode
insteadofgoalitselfalongwithpath.
•Itworksbysearchingforwardfromtheinitialnodeandbackwardfrom
thegoalnodesimultaneously,byhopingthattwosearchesmeetinthe
middle.
•Checkateachstageifthenodesofonehavebeengeneratedbythe
other,.i.e.,theymeetinthemiddle.
•Ifso,thepathconcatenationisthesolution.
Presented By: Tekendra Nath Yogi 49IT 228 -Intro to AI

50. Bidirectional search contd..
•Advantages:
–OnlyslightmodificationofDFSand
BFScanbedonetoperformthis
search.
–Theoreticallyeffectivethan
unidirectionalsearch.
•Disadvantage:
–Problemiftherearemanygoalstates.
–Practicallyinefficientduetoadditional
overheadtoperformintersection
operationateachpointofsearch
Presented By: Tekendra Nath Yogi 50IT 228 -Intro to AI

51. Drawbacks of uninformed search :
•Criteriontochoosenextnodetoexpanddependsonlyonaglobalcriterion:
level.
•Doesnotexploitthestructureoftheproblem.
51Presented By: Tekendra Nath YogiIT 228 -Intro to AI

52. Heuristic Search:
•HeuristicSearchUsesdomain-dependent(heuristic)informationbeyondthe
definitionoftheproblemitselfinordertosearchthespacemoreefficiently.
•Waysofusingheuristicinformation:
–Decidingwhichnodetoexpandnext,insteadofdoingtheexpansioninastrictly
breadth-firstordepth-firstorder;
–Inthecourseofexpandinganode,decidingwhichsuccessororsuccessorsto
generate,insteadofblindlygeneratingallpossiblesuccessorsatonetime;
–Decidingthatcertainnodesshouldbediscarded,orpruned,fromthesearch
space.
5212/25/2018 By: Tekendra Nath Yogi

53. Contd…
•InformedSearchDefineaheuristicfunction,h(n),thatestimatesthe
"goodness"ofanoden.
•Theheuristicfunctionisanestimate,basedondomain-specificinformation
thatiscomputablefromthecurrentstatedescription,ofhowclosewearetoa
goal.
•Specifically,h(n)=estimatedcost(ordistance)ofminimalcostpathfrom
state„n‟toagoalstate.
5312/25/2018 By: Tekendra Nath Yogi

54. Contd…
•A) Best-First Search:
–Best first searchuses an evaluation function f(n) that gives an indication
of which node to expand next for each node.
–Akeycomponentoff(n)isaheuristicfunction,h(n),whichisaadditional
knowledgeoftheproblem.
–Basedontheevaluationfunctionbestfirstsearchcanbecategorizedinto
thefollowingcategories:
•Greedybest-firstsearch
•A*search
5412/25/2018 By: Tekendra Nath Yogi

55. Contd…
•Greedy Best First Search :
–Greedybestfirstsearchexpandsthenodethatseemstobeclosesttothe
goalnode.
–EvaluationfunctionbasedonHeuristicfunctionisusedtoestimate
whichnodeisclosesttothegoalnode.
–Therefore,Evaluationfunctionf(n)=heuristicfunctionh(n)=estimated
costofthepathfromnodentothegoalnode.
–E.g.,h
SLD(n)=straight-linedistancefromntogoal
–Note:g(root)=0andh(goal)=0
5512/25/2018 By: Tekendra Nath Yogi

56. Contd…
•Example1ToillustrateGreedyBest-FirstSearch:
–For example consider the following graph
–Straight Line distances to node G (goal node) from other nodes is given below:
–Let H(n)= Straight Line distance
–Now Greedy Search operation is done as below:
5612/25/2018 By: Tekendra Nath Yogi

57. Contd…
•Start at node „s‟, the start state
•Children of s= {B(4), D(5)}
•Therefore, best = B
5712/25/2018 By: Tekendra Nath Yogi

58. Contd…
•Children of B= {E(7), C(3)}
•Considered= {D(5), E(7), C(3)}
•Therefore, Best= C
5812/25/2018 By: Tekendra Nath Yogi

59. Contd…
•Children of C= {D(5), G(0)}
•Considered= {D(5), E(7), G(0)}
•Therefore, Best= G, is the goal node.
5912/25/2018 By: Tekendra Nath Yogi

60. Contd…
•A * Search :
–A*isabestfirst,informedsearchalgorithm.Thesearchbeginsatrootnode.
Thesearchcontinuesbyvisitingthenextnodewhichhastheleast
evaluation.
–Itevaluatesnodesbyusingthefollowingevaluationfunction
•f(n)=h(n)+g(n)=estimatedcostofthecheapestsolutionthroughn.
•Where,g(n):theactualshortestdistancetraveledfrominitialnodetocurrent
node,Ithelpstoavoidexpandingpathsthatarealreadyexpensive
•h(n):theestimated(or"heuristic")distancefromcurrentnodetogoal,itestimate
whichnodeisclosesttothegoalnode.
–Nodesarevisitedinthismanneruntilagoalisreached.
6012/25/2018 By: Tekendra Nath Yogi

61. Contd…
•ExampletoillustrateA*Search:
–For example consider the following graph
–Straight Line distances to node G (goal node) from other nodes is given
below:
–Labels in the graph shows actual distance.
–Let H(n)= Straight Line distance
–Now A* Search operation is done as below
6112/25/2018 By: Tekendra Nath Yogi

62. Contd…
•A* algorithm starts at s, the start state.
•Children of S={B, D}
•Now, evaluation function for each child of S is:
–f(B) =g(B) + h(B) =9+4=13
–f(D)=g(D)+h(D)= 8+6=14
•Here, candidate node for expansion are{B, D}, among these candidate nodes
the node B is least evaluated, so it is selected for expansion.
6212/25/2018 By: Tekendra Nath Yogi

63. Contd…
•Child of B ={E, C}
•Now, evaluation for each child of B are
–F(E)= (9+8)+7=24
–F(c)=(9+7)+3=19
•Here, candidate nodes for expansion are{E,C, and D}
•Among these candidate the node D is least evaluated, so it is selected for expansion
63Presented By: Tekendra Nath Yogi
f(n)= 14H(n)= 4
IT 228 -Intro to AI

64. Contd….
•Child of D={G, C}
Evaluation for the child of D are
•Here, the candidate nodes for expansion are{ E, C,G and C}.
•Among these candidate the node C child of D is least
evaluated, so It is selected for expansion.
64Presented By: Tekendra Nath Yogi
H(n)= 6
IT 228 -Intro to AI

65. Contd…
•Child of C= {G,B}
Evaluation for the child of C are
•Here the candidate for expansion are{E,C,G,G, and B}.
•Among these candidate the node G, which is child of D is least evaluated, so
it is selected for expansion, but it is the goal node, hence we are done
65Presented By: Tekendra Nath Yogi
H(n)= 6
H(n)= 3
IT 228 -Intro to AI

66. Contd…
66Presented By: Tekendra Nath Yogi
H(n)= 6
H(n)= 3
IT 228 -Intro to AI

67. Contd…
•B)Localsearchalgorithms:
–Localsearchalgorithmsoperateusingasinglecurrentnodeandmove
onlytoneighborsofthisnoderatherthansystematicallyexploringpaths
fromaninitialstate.E.g.Hillclimbing.
–Thesealgorithmsaresuitableforproblemsinwhichallthatmatteristhe
solutionstate,notthepathcosttoreachit.Typically,thepathsfollowed
bythesearcharenotretained.
–Althoughlocalsearchalgorithmsarenotsystematic,theyhavetwokey
advantages:
•Theyuseverylittlememory.
•Theycanoftenfindreasonablesolutionsinlargeorinfinitestatespacesfor
whichsystematicalgorithmsareunsuitable.
6712/25/2018 By: Tekendra Nath Yogi

68. Contd…
•HillClimbingSearch:
–Hillclimbingcanbeusedtosolveproblemsthathavemanysolutions,
someofwhicharebetterthanothers.
–Itstartswitharandom(potentiallypoor)solution,anditerativelymakes
smallchangestothesolution,eachtimeimprovingitalittle.Whenthe
algorithmcannotseeanyimprovementanymore,itterminates.
–Ideally,atthatpointthecurrentsolutionisclosetooptimal,butitisnot
guaranteedthathillclimbingwillevercomeclosetotheoptimalsolution.
–Note:Thealgorithmdoesnotmaintainasearchtreeanddoesnotlook
aheadbeyondtheimmediateneighborsofthecurrentstate.
6812/25/2018 By: Tekendra Nath Yogi

69. Contd…
6912/25/2018 By: Tekendra Nath Yogi

70. Contd…
•Hillclimbingsuffersfromthefollowingproblems:
–TheFoot-hillsproblem(localmaximum)
–ThePlateauproblem
–TheRidgeproblem
7012/25/2018 By: Tekendra Nath Yogi

71. Contd…
•Foot-Hillproblem:
–Localmaximumisastatewhichisbetterthanallofitsneighborsbutis
notbetterthansomeotherstateswhicharefartheraway.
–Atlocalmaxima,allmovesappeartomakethethingsworse.
–Thisproblemiscalledthefoothillproblem.
–Solution:Backtracktosomeearliernodeandtrygoingtodifferent
direction.
7112/25/2018 By: Tekendra Nath Yogi

72. Contd…
•ThePlateauproblem:
–Plateauisaflatareaofthesearchspaceinwhichawholesetof
neighboringstateshavethesamevalue.
–Onplateau,itisnotpossibletodeterminethebestdirectioninwhichto
movebymakinglocalcomparison.
–Suchaproblemiscalledplateauproblem.
–Solution:Makeabigjumpinsomedirectiontotrytogetanewsection
ofthesearchspace.
7212/25/2018 By: Tekendra Nath Yogi

73. Contd…
•TheRidgeproblem:
–Ridgeisanareaofthesearchspacewhichishigherthanthesurroundingareas
andthatitselfhasaslope.
–Duetothesteepslopesthesearchdirectionisnottowardsthetopbuttowardsthe
side(oscillatesfromsidetoside).
–SuchaproblemiscalledRidgeproblem.
•Solution:Applytwoormorerulessuchasbi-directionsearchbeforedoing
thetest.
7312/25/2018 By: Tekendra Nath Yogi

74. Mean-End Analysis
•Meanendanalysisisaproblemsolvingtechnique.Allowsustosolvethemajor
partsofaproblemfirstandthengobackandsolvethesmallerproblemsthat
arisewhileassemblingthefinalsolution.
•Technique:
–TheMeanEndanalysisprocessfirstdetectsthedifferencesbetweencurrent
stateandthegoalstate.
–Oncesuchadifferenceisisolated,anoperatorthatcanreducethedifference
hastobefound.
–Butsometimesitisnotpossibletoapplythisoperatortothecurrentstate.
So,wetrytogetasub-problemoutofitandtrytoapplyouroperatortothis
newstate.
–Ifthisalsodoesnotproducethedesiredgoalstatethenwetrytogetsecond
sub-problemandapplythisoperatoragain.Thisprocessmaybecontinued.
7412/25/2018 By: Tekendra Nath Yogi

75. Contd…
•Problem:
•Solution:
7512/25/2018 By: Tekendra Nath Yogi

76. Contd…
•Whyitiscalledmeanendanalysis?
–Givenadescriptionofthedesiredstateoftheworld(theend).
–Itworksbyselectingandusingoperatorsthatwillachieveit(themeans).
–Hencethename,meanendanalysis(MEA).
7612/25/2018 By: Tekendra Nath Yogi

77. Contd…
•MeanEndAnalysis(HouseholdRobot):
–Considerasimplehouseholdrobotdomain.ProblemGiventotherobot
is:Moveadeskwithtwothingsonitfromoneroomtoanother.The
objectsontopmustalsobemoved.
7712/25/2018 By: Tekendra Nath Yogi

78. Contd…
•Theavailableoperatorsareshownbelowalongwiththeirpre-conditionsandresults.
•Tablebelowshowswheneachoftheoperatorsisappropriate:
7812/25/2018 By: Tekendra Nath Yogi

79. Contd…
Therobotsolvesthisproblemasfollows:
•Themaindifferencebetweentheinitialstateandthegoalstatewouldbethe
locationofthedesk.
•Toreducethisdifference,eitherPUSHorCARRYcouldbechosen.
•IfCARRYischosenfirst,itspreconditionsmustbemet.Thisresultsintwo
moredifferencesthatmustbereduced:
–Thelocationoftherobotandthesizeofthedesk.
–ThelocationoftherobotishandledbyapplyingWALK,butthereareno
operatorsthatcanchangethesizeofanobject,Sothispathleadstoadead-end.
7912/25/2018 By: Tekendra Nath Yogi

80. Contd…
•Followingtheotherbranch,weattempttoapplyPUSH.Figurebelowshows
therobot‟sprogressatthispoint.
Fig:Theprogressofmeanendanalysismethod.
•NowthedifferencesbetweenAandBandBetweenCandDmustbereduced.
8012/25/2018 By: Tekendra Nath Yogi

81. Contd…
•PUSHhaspreconditions:
–therobotmustbeatthedesk,and
–thedeskmustbeclear.
•TherobotcanbebroughttothecorrectlocationbyusingWALK.
•AndthesurfaceofthedeskcanbeclearedbytwousesofthePICKUP,.
•ButafteronePICKUP,Anattempttodothesecondresultsinanother
difference(thearmmustbeempty).
•PUTDOWNcanbeusedtoreducethedifference.
8112/25/2018 By: Tekendra Nath Yogi

82. Contd…
•OncePUSHisperformed,theproblemstateisclosedtothegoalstate,butnot
quite.Theobjectmustbeplacedbackonthedesk.PLACEwillputthem
there.Theprogressoftherobotatthispointisasshowninfigurebelow:
Fig:Moreprogressonthemeanendanalysismethod.
•ThefinaldifferencebetweenCandEcanbereducedbyusingWALKtoget
therobotbacktotheobjectfollowedbyPICKUPandCARRY.
8212/25/2018 By: Tekendra Nath Yogi

83. Contd…
•Mean-EndAnalysis:(MonkeyBananaProblem):
–ThemonkeyisinaclosedroominwhichthereisasmallBox.
–Thereisabunchofbananashangingfromtheceilingbutthemonkeycannotreach
them.
–AssumingthatthemonkeycanmovetheBoxandifthemonkeystandsontheBox
themonkeycanreachthebananas.
–Establishamethodtoinstructthemonkeyonhowtocapturethebananas.
8312/25/2018 By: Tekendra Nath Yogi

84. Contd…
•RepresentingtheWorld:
–IntheMonkeyBananaproblemwehave:
•objects:amonkey,abox,thebananas,andafloor.
•locations:we‟llcallthema,b,andc.
•relationsofobjectstolocations.Forexample:
–themonkeyisatlocationa;
–themonkeyisonthefloor;
–thebananasarehanging;
–theboxisinthesamelocationasthebananas.
–FormallyRepresentingtherelationsofobjectstolocationsas:
–at(monkey,a).
–on(monkey,floor).
–status(bananas,hanging).
–at(box,X),at(bananas,X).
8412/25/2018 By: Tekendra Nath Yogi

85. Contd…
•InitialState:
at(monkey,a),
on(monkey,floor),
at(box,b),
on(box,floor),
at(bananas,c),
status(bananas,hanging).
•GoalState:
on(monkey,box),
on(box,floor),
at(monkey,c),
at(box,c),
at(bananas,c),
status(bananas,grabbed).
8512/25/2018 By: Tekendra Nath Yogi

86. Contd…
•AllOperators:
8612/25/2018 By: Tekendra Nath Yogi
OperatorPreconditions Results
go(X,Y) at(monkey,X) at(monkey, Y)
on(monkey, floor)
push(B,X,Y)at(monkey,X) at(monkey, Y)
at(B,X) at(B,Y)
on(monkey, floor)
on(B,floor)
climb_on(B)at(monkey,X) on(monkey, B)
at(B,X)
on(monkey,floor)
on(B,floor)
grab(B) on(monkey,box) status(B, grabbed)
at(box,X)
at(B,X)
status(B, hanging)

87. Contd…
•InstructionsTotheMonkeytoGrabthebanana:
–FirstofallMonkeyshouldmoveformlocationatolocationb.
•Go(a,b)
–ThenpushtheBoxformlocationbtolocationa.
•Push(B,b,a)
–PushtheBoxagainfromlocationatolocationc.
•Push(B,a,c)
–MonkeyshouldclimbontheBox
•Climb_on(B)
–ThenGrabthebanana.
•Grab(B)
8712/25/2018 By: Tekendra Nath Yogi

88. Constraint satisfaction problems
•ACSPconsistsofthreecomponents:X,DandC
–XisaFinitesetofvariables{X
1,X
2,…,X
n}
–DisasetofNonemptydomainofpossiblevaluesforeachvariable{D
1,
D
2,…D
n}
–CisaFinitesetofconstraints{C
1,C
2,…,C
m}
–EachconstraintC
ilimitsthevaluesthatvariablescantake,e.g.,X
1≠X
2
8812/25/2018 By: Tekendra Nath Yogi

89. Contd…
•InCSP:
–State:Astateisdefinedasanassignmentofvaluestosomeorall
variables.
–Consistentassignment:consistentassignmentisanassignmentthatdoes
notviolatetheconstraints.
–Anassignmentiscompletewheneveryvariableisassignedavalue.
–AsolutiontoaCSPisacompleteassignmentthatsatisfiesallconstraints
i.e.,completeandconsistentassignment.
8912/25/2018 By: Tekendra Nath Yogi

90. Contd…
•Example(Map-Coloringproblem):Given,amapofAustraliashowing
eachofstatesandterritories.Thetaskiscoloreachregioneitherred,green,
orblueinsuchawaythatnoneighboringregionshavethesamecolor.
9012/25/2018 By: Tekendra Nath Yogi
•ThisproblemcanbeformulatedasCSPas
follows:
–Variables:WA,NT,Q,NSW,V,SA,T
–Domains:D
i={red,green,blue}
–Constraints:adjacentregionsmusthavedifferent
colors
•e.g.,WA≠NT

91. Contd…
•Solutionsare completeand consistentassignments,
–e.g., WA = red, NT = green, Q = red, NSW = green, V = red, SA = blue,
T = green
9112/25/2018 By: Tekendra Nath Yogi

92. Contd…
•CSPasastandardsearchproblem:
–ACSPcaneasilyexpressedasastandardsearchproblem,as
follows:
•InitialState:theemptyassignment{},inwhichallvariablesare
unassigned..
•Successorfunction:Assignvaluetounassignedvariableprovidedthat
thereisnotconflict.
•Goaltest:thecurrentassignmentiscompleteandconsistent.
•Pathcost:aconstantcostforeverystep.
9212/25/2018 By: Tekendra Nath Yogi

93. Contd…
•Constraintsatisfactionsearch:
–ForsearchingasolutionofCSPsfollowingalgorithmscanbeused:
•Backtrackingsearch:Worksonpartialassignments.
•LocalsearchforCSPs:worksoncompleteassignment.
9312/25/2018 By: Tekendra Nath Yogi

94. Contd…
•Backtrackingsearch:
–Thetermbacktrackingsearchisusedforadepthfirstsearchthatchooses
valuesforonevariableatatimeandbacktrackswhenavariablehasno
legalvalueslefttoassign.
–Thealgorithmrepeatedlychooseanunassignedvariable,andthentriesall
valuesinthedomainofthatvariableinturn,tryingtofindasolution.
–Ifaninconsistencyisdetected,thenbacktrackreturnsfailure,causingthe
previouscalltotrytoanothervalues.
9412/25/2018 By: Tekendra Nath Yogi

95. 95
Backtracking example
Presented By: Tekendra Nath YogiIT 228 -Intro to AI

96. 96
Backtracking example
Presented By: Tekendra Nath YogiIT 228 -Intro to AI

97. 97
Backtracking example
Presented By: Tekendra Nath YogiIT 228 -Intro to AI

98. 98
Backtracking example
Presented By: Tekendra Nath YogiIT 228 -Intro to AI

99. Contd…
•LocalsearchforCSPs:
–Theyuseacompletestateformulation:
•Theinitialstateassignsavaluetoeveryvariable,andthesearch
changesthevalueofonevariableatatimebecausetheinitialguess
violatesseveralconstraints.
–E.g.:
•Firstrandomlyselectanyconflictedvariable.
•Thenchoosethevalueofthatconflictedvariablethatviolatesthe
fewestconstraints.
9912/25/2018 By: Tekendra Nath Yogi

100. Crypt-arithmetic Problem
•ManyproblemsinAIcanbeconsideredasproblemsofconstraintsatisfaction,
inwhichthegoalstatesatisfiesagivensetofconstraint.
ExampleofsuchaproblemisCrypt-Arithmeticproblem(amathematical
puzzle),inwhichthegoalstate(solution)satisfiesthefollowingconstraints:
–Valuesaretobeassignedtolettersfrom0to9only.
–Notwolettersshouldhavethesamevalue.
–Ifthesameletteroccursmorethanonce,itmustbeassignedthesamedigiteach
time.
–Thesumofthedigitsmustbearithmeticallycorrectwiththeaddedrestrictionthat
noleadingzeroesareallowed.
10012/25/2018 By: Tekendra Nath Yogi

101. Contd…
•Example1: Solve the following puzzle by assigning numeral (0-9) in such a
way that each letter is assigned unique digit which satisfy the following
addition.
10112/25/2018 By: Tekendra Nath Yogi

102. Contd…
•Solution:Here,
•Variables:{F, T, U, W, R, O, c
1,c
2, C3 }
•Domains: {0,1,2,3,4,5,6,7,8,9}
•Constraints: Alldiff(F,T,U,W,R,O)
•where c1, c2, and c3 are auxiliary variables representing the digit (0 or 1) carried over
into the next column.
10212/25/2018 By: Tekendra Nath Yogi
c3 c2 c1

103. Contd…
•Hereweareaddingtwothreeletterswordsbutgettingafourlettersword.Thisindicates
thatF=c3=1
•Now,c2+T+T=O+10…….Becausec3=1
•C2canbe0or1.Letc2=0thenTshouldbe>5i.eTcanbe{6,7,8,9}
•LetT=9thenC2+T+T=O+10 0+9+9=O+10fromthisO=8
•NowO+O=R+10 8+8=R+10FromthisR=6
•Now,c1+W+W=U herec1=1andUandWcanbe{2,3,4,5,7}
•But,c2=0soletW=2then1+2+2=Ui.e.,U=5
•Nowreplacingeachletterinthepuzzlebyitscorrespondingdigitandtestingtheir
arithmeticcorrectness:
•Thisassignmentsatisfiesalltheconstraintsothisisthefinalsolution
10312/25/2018 By: Tekendra Nath Yogi

104. Contd…
•Example2:Solvethefollowingpuzzlebyassigningnumeral(0-
9)insuchawaythateachletterisassigneduniquedigitwhich
satisfythefollowingaddition.
•Solution:Here,
•Variables:{F,O,U,R,E,I,G,H,T, c
1,c
2, C3 ,c4}
•Domains: {0,1,2,3,4,5,6,7,8,9}
•Constraints: Alldiff(F,O,U,R,E,I,G,H,T)
•where c1, c2, and c3 are auxiliary variables representing the digit (0 or 1) carried over
into the next column.
10412/25/2018 By: Tekendra Nath Yogi

105. Contd…
•Hereweareaddingtwothreeletterswordsbutgettingafourlettersword.This
indicatesthatE=c4=1…..BecauseEisleftmostlettersoitshouldnotbe0.
•Nowc3+F+F=I+10,herec3canbe0or1andFshouldbegreaterthan5.i.e
{6,7,8,9}
•Letc3=0andF=9then0+9+9=I+10fromthisI=8
•Now,c2+O+O=G……sincec3=0
•C2canbe0or1andOcanbe{2,3,4}.Letc2=0andO=2ThenG=4.
•R+R=T hereRcanbe{3,5,6,7}
•IfweletR=3thisleadstodeadendsoletR=5thenT=0andc1=1
•C1+U+U=Hherec1=1andc2=0andUcanbe{3}
•FormthisU=3thenH=7
10512/25/2018 By: Tekendra Nath Yogi

106. Contd…
•Initial problem state:
–S = ? M= ? C1 = ?
–E = ? O = ? C2 = ?
–N = ? R = ? C3 = ?
–D = ? E = ? C4 = ?
•Goalstates:Agoalstateisaproblemstateinwhichalllettershavebeenassigneda
digitinsuchawaythatallconstraintsaresatisfied
10612/25/2018 By: Tekendra Nath Yogi

107. Contd…
10712/25/2018 By: Tekendra Nath Yogi

108. Contd…
10812/25/2018 By: Tekendra Nath Yogi

109. Contd…
10912/25/2018 By: Tekendra Nath Yogi

110. Contd…
11012/25/2018 By: Tekendra Nath Yogi

111. Home Work
•Solvethefollowingpuzzlesbyassigningnumeral(0-9)insuchawaythat
eachletterisassigneduniquedigitwhichsatisfythefollowingaddition.
1.
2.
3.
4.
11112/25/2018 By: Tekendra Nath Yogi

112. Problem Reduction: AND/ OR Tree
•Thebasicintuitionbehindthemethodofproblemreductionis:
–Reduceahardproblemtoanumberofsimpleproblemsand,wheneachof
thesimpleproblemsissolved,thenthehardproblemhasbeensolved.
•To represent problem reduction we can use an AND-OR tree. AnAND–OR
treeis a graphical representationof the reduction of problems to conjunctions
and disjunctions of sub-problems.
•Example:
112Presented By: Tekendra Nath YogiIT 228 -Intro to AI
represents thesearch spacefor solving the
problem P, using the problem-reduction
methods:
P if Q and R
P if S
Q if T
Q if U

113. Contd…
•Example1
•Example2:
113Presented By: Tekendra Nath YogiIT 228 -Intro to AI

114. Contd….
•SearchingAND/ORTree:
•TofindasolutioninAND–ORtree,analgorithmsimilartoBestfirstsearch
algorithmisusedbutwiththeabilitytohandleANDarcappropriately.
•Thisalgorithmevaluatesthenodesbasedonthefollowingevaluationfunction.
•IfthenodeisORnodethencostfunctionf(n)=h(n)
•IfthenodeisANDnodethencostfunctionisthesumofcostsinANDnode.
–f(n)=f(n
1)+f(n
2)+….+f(n
k)=h(n
1)+h(n
2)+….+h(n
k)
–Where,n
1,n
2,….N
kareANDnodes.
114Presented By: Tekendra Nath YogiIT 228 -Intro to AI

115. Contd…
•Here,thenumbershowthevalueoftheheuristicfunctionatthatnode.
•InthefiguretheminimalisBwhichisthevalueof3.ButBformsapartoftheAND
treesoweneedtoconsidertheotherbranchalsoofthisANDtreei.e.,Cwhichhasa
weightof4.So,ourestimatenowis(3+4)=7.
•NowthisestimateismorecostlierthanthatofbranchDi.e.,5.Soweexplorenode
DinsteadofBasithasthelowestvalue.
•Thisprocesscontinuesuntileitherasolutionisfoundorallpathsledtodeadends,
indicatingthatthereisnosolution.
115Presented By: Tekendra Nath YogiIT 228 -Intro to AI

116. Adversarial Search(Game Playing)
•Competitiveenvironmentsinwhichtheagentsgoalsareinconflict,giverise
toadversarialsearch,oftenknownasgames.
•InAI,gamesmeansdeterministic,fullyobservableenvironmentsinwhich
therearetwoagentswhoseactionsmustalternateandinwhichutilityvalues
attheendofthegamearealwaysequalandopposite.
–E.g.,Iffirstplayerwins,theotherplayernecessarilyloses
•ThisOppositionbetweentheagent‟sutilityfunctionsmakethesituation
adversarial.
11612/25/2018 By: Tekendra Nath Yogi

117. Contd…
•GamesasAdversarialSearch:
–AGamecanbeformallydefinedasakindofsearchproblemwiththe
followingelements:
•States:boardconfigurations.
•Initialstate:theboardpositionandwhichplayerwillmove.
•Successorfunction:returnslistof(move,state)pairs,eachindicating
alegalmoveandtheresultingstate.
•Terminaltest:determineswhenthegameisover.
•Utilityfunction:givesanumericvalueinterminalstates
–(e.g.,-1,0,+1forloss,tie,win)
11712/25/2018 By: Tekendra Nath Yogi

118. Contd…
•GameTrees:Problemspacesfortypicalgamesrepresentedastrees,inwhich:
–Rootnode:Representsthestatebeforeanymoveshavebeenmade.
–Nodes:Representspossiblestatesofthegames.Eachlevelofthetreehas
nodesthatareallMAXorallMIN;nodesatleveliareoftheoppositekind
fromthoseatleveli+1.and
–Arcs:Representsthepossiblelegalmovesforaplayer.Movesare
representedonalternatelevelsofthegametreesothatalledgesleading
fromrootnodetothefirstlevelrepresentmovesforthefirst(MAX)player
andedgesfromthefirstleveltosecondrepresentsmovesforthe
second(MIN)playerandsoon.
–Terminalnodesrepresentend-gameconfigurations.
11812/25/2018 By: Tekendra Nath Yogi

119. Contd…
•Evaluation Function:
–Anevaluationfunctionisusedtoevaluatethe"goodness"ofagame
position.
–i.e.,estimateoftheexpectedutilityofthegameposition
–Theperformanceofagameplayingprogramdependsstronglyonthe
qualityofitsevaluationfunction.
–Aninaccurateevaluationfunctionwillguideanagenttowardpositions
thatturnouttobelost.
11912/25/2018 By: Tekendra Nath Yogi

120. Contd…
•Agoodevaluationfunctionshould:
•Ordertheterminalstatesinthesamewayasthetrueutilityfunction:
•i.e.,Statesthatarewinsmustevaluatebetterthandraws,whichin
turnmustbebetterthanlosses.Otherwise,anagentusingthe
evaluationfunctionmighterrevenifitcanseeaheadallthewayto
theendofthegame.
•Fornon-terminalstates,theevaluationfunctionshouldbestrongly
correlatedwiththeactualchancesofwinning.
•Thecomputationmustnottaketoolongi.e.,evaluatefaster.
12012/25/2018 By: Tekendra Nath Yogi

121. Contd…
•Anexample(partial)gametreeforTic-Tac-Toe:
12112/25/2018 By: Tekendra Nath Yogi
•f(n) = +1 if the position is a win for
X.
•f(n) = -1 if the position is a win for
O.
•f(n) = 0 if the position is a draw.

122. Contd…
•TherearetwoplayersdenotedbyXandO.Theyarealternativelywritingtheirletterin
oneofthe9cellsofa3by3board.Thewinneristheonewhosucceedsinwritingthree
lettersinline.
•Thegamebeginswithanemptyboard.Itendsinawinforoneplayerandalossforthe
other,orpossiblyinadraw.
•Acompletetreeisarepresentationofallthepossibleplaysofthegame.Therootnodeis
theinitialstate,inwhichitisthefirstplayer'sturntomove(theplayerX).
•Thesuccessorsoftheinitialstatearethestatestheplayercanreachinonemove,their
successorsarethestatesresultingfromtheotherplayer'spossiblereplies,andsoon.
•TerminalstatesarethoserepresentingawinforX,lossforX,oradraw.
•Eachpathfromtherootnodetoaterminalnodegivesadifferentcompleteplayofthe
game.FiguregivenaboveshowsthesearchspaceofTic-Tac-Toe.
12212/25/2018 By: Tekendra Nath Yogi

123. Mini-max search algorithm
•Mini-maxsearchalgorithmisagamesearchalgorithmwiththeapplicationof
DFSprocedure.
•Itassumes:
•Boththeplayerplayoptimallyfromtheretotheendofthegame.
•Asuitablevalueofstaticevaluation(utility)isavailableontheleafnodes.
•Giventhevalueoftheterminalnodes,thevalueofeachnode(MaxandMIN)is
determinedby(backupfrom)thevaluesofitschildrenuntilavalueis
computedfortherootnode.
–ForaMAXnode,thebackedupvalueisthemaximumofthevaluesassociated
withitschildren
–ForaMINnode,thebackedupvalueistheminimumofthevaluesassociatedwith
itschildren
12312/25/2018 By: Tekendra Nath Yogi

124. Contd…
•Mini-maxsearchExample:
12412/25/2018 By: Tekendra Nath Yogi

125. Contd…
12512/25/2018 By: Tekendra Nath Yogi

126. Contd…
12612/25/2018 By: Tekendra Nath Yogi

127. Contd…
12712/25/2018 By: Tekendra Nath Yogi

128. Contd…
•LimitationsofMini-maxsearch:
–Mini-max search traverse the entire search tree but it is not always
feasible to traverse entire tree.
–Time limitations
12812/25/2018 By: Tekendra Nath Yogi

129. Alpha-beta pruning
•Wecanimproveontheperformanceofthemini-maxalgorithmthrough
alpha-betapruning.
•Basicidea:Ifamoveisdeterminedworsethananothermovealready
examined,thenthereisnoneedforfurtherexaminationofthenode.
12912/25/2018 By: Tekendra Nath Yogi
•For Example:Consider node nin thetree.
•If player has a better choice at:
–Parent node of n
–Or any choice point further up
•Then nis never reached in play.
•So,When that much is known about n, it can
be pruned.

130. Contd…
•Example:
13012/25/2018 By: Tekendra Nath Yogi

131. Contd…
•Alpha-Betapruningprocedure:
–Traversethesearchtreeindepth-firstorder.DuringtraversingAlphaand
Betavaluesinheritedfromtheparenttochildneverfromthechildren.
Initiallyalpha=-infinityandalwaystrytoincrease,andbeta=+infinityand
alwaystrytodecrease.Alphavalueupdatesonlyatmaxnodeandbetavalue
updateonlyatminnode.
–Maxplayer:
•Val>Alpha?(valisValuebackupformthechildrenofmaxplayer)
–UpdateAlpha
•IsAlpha>=Beta?
–Prune(calledalphacutoff)
•ReturnAlpha
–MINplayer:
•Val<Beta?(valisValuebackupformthechildrenofminplayer)
–UpdateBeta
•IsAlpha>=Beta?
–Prune(calledbetacutoff)
•ReturnBeta
13112/25/2018 By: Tekendra Nath Yogi

132. Contd…
•Alpha-Betapruningexample:
13212/25/2018 By: Tekendra Nath Yogi

133. Contd…
13312/25/2018 By: Tekendra Nath Yogi

134. Contd…
13412/25/2018 By: Tekendra Nath Yogi

135. Contd…
13512/25/2018 By: Tekendra Nath Yogi

136. Contd…
13612/25/2018 By: Tekendra Nath Yogi

137. Contd…
13712/25/2018 By: Tekendra Nath Yogi

138. Contd…
13812/25/2018 By: Tekendra Nath Yogi

139. Contd…
13912/25/2018 By: Tekendra Nath Yogi

140. Contd…
14012/25/2018 By: Tekendra Nath Yogi

141. Contd…
14112/25/2018 By: Tekendra Nath Yogi

142. Contd…
14212/25/2018 By: Tekendra Nath Yogi

143. Contd…
14312/25/2018 By: Tekendra Nath Yogi

144. Contd…
14412/25/2018 By: Tekendra Nath Yogi

145. Contd…
14512/25/2018 By: Tekendra Nath Yogi

146. Contd…
14612/25/2018 By: Tekendra Nath Yogi

147. Contd…
14712/25/2018 By: Tekendra Nath Yogi

148. Contd…
14812/25/2018 By: Tekendra Nath Yogi

149. Contd…
14912/25/2018 By: Tekendra Nath Yogi

150. Contd…
15012/25/2018 By: Tekendra Nath Yogi

151. Contd…
15112/25/2018 By: Tekendra Nath Yogi

152. Contd…
15212/25/2018 By: Tekendra Nath Yogi

153. Contd…
15312/25/2018 By: Tekendra Nath Yogi

154. Contd…
15412/25/2018 By: Tekendra Nath Yogi

155. Contd…
15512/25/2018 By: Tekendra Nath Yogi

156. Contd…
15612/25/2018 By: Tekendra Nath Yogi

157. Contd…
15712/25/2018 By: Tekendra Nath Yogi

158. Contd…
15812/25/2018 By: Tekendra Nath Yogi

159. Contd…
15912/25/2018 By: Tekendra Nath Yogi

160. Contd…
16012/25/2018 By: Tekendra Nath Yogi

161. Contd…
16112/25/2018 By: Tekendra Nath Yogi

162. Contd…
16212/25/2018 By: Tekendra Nath Yogi

163. Contd…
16312/25/2018 By: Tekendra Nath Yogi

164. Contd…
16412/25/2018 By: Tekendra Nath Yogi

165. Contd…
16512/25/2018 By: Tekendra Nath Yogi

166. Contd…
16612/25/2018 By: Tekendra Nath Yogi

167. Contd…
16712/25/2018 By: Tekendra Nath Yogi

168. Contd…
16812/25/2018 By: Tekendra Nath Yogi

169. Contd…
16912/25/2018 By: Tekendra Nath Yogi

170. Contd…
17012/25/2018 By: Tekendra Nath Yogi

171. Contd…
17112/25/2018 By: Tekendra Nath Yogi

172. Games of Chance
•InthegamewithuncertaintyPlayersincludearandomelement(rolldice,flip
acoin,etc.)todeterminewhatmovestomake
•i.e.,Dicearerolledatthebeginningofaplayer‟sturntodeterminethe
legalmoves.Suchgamesarecalledgameofchance.
•Chancegamesaregoodforexploringdecisionmakinginadversarial
problemsinvolvingskillandluck.
17212/25/2018 By: Tekendra Nath Yogi

173. Contd…
•GameTreeswithChanceNodes:
•Thegametreeinthechancegameincludechancenodesinadditionto
MAXandMINnodes.Chancenodes(shownascircles)representthedice
rolls.
•Thebranchesleadingfromeachchancenodedenotethepossibledicerolls;
eachbranchislabeledwiththerollanditsprobability.
17312/25/2018 By: Tekendra Nath Yogi
Max
min
Chance
Terminal node
Chance

174. Contd…
•Algorithm for chance Games:
•Generalization of minimaxfor games with chance nodes. Also known as
Expectiminimaxgive perfect play
–IfthestateisterminalnodethenReturntheutilityvalue.
–ifstateisaMAXnodethenreturnhighestExpectiminimax–Valueof
Successors
–ifstateisaMINnodethenreturnlowestExpectiminimax–Valueof
Successors
–ifstateisaCHANCEnodethen
•Forchancenodes„C‟overamaxnode,compute:epectimax(C)=
Sum
i(P(d
i)*maxvalue(i))
•Forchancenodes„C‟overaminnodecompute:epectimin(C)=
Sum
i(P(d
i)*minvalue(i))
17412/25/2018 By: Tekendra Nath Yogi

175. Contd…
•Example:
17512/25/2018 By: Tekendra Nath Yogi

176. What is Game Theory?
•Gametheoryisastudyofhowtomathematicallydeterminethebeststrategy
forgivenconditionsinordertooptimizetheoutcome
•Findingacceptable,ifnotoptimal,strategiesinconflictsituations.
•Abstractionofrealcomplexsituation
•Gametheoryishighlymathematical
•Gametheoryassumesallhumaninteractionscanbeunderstoodandnavigated
bypresumptions.
17612/25/2018 By: Tekendra Nath Yogi

177. Contd…
•Why is game theory important?
–Allintelligentbeingsmakedecisionsallthetime.
–AIneedstoperformthesetasksasaresult.
–Helpsustoanalyzesituationsmorerationallyandformulatean
acceptablealternativewithrespecttocircumstance.
–Usefulinmodelingstrategicdecision-making
•Gamesagainstopponents
•Gamesagainstnature
–Providesstructuredinsightintothevalueofinformation
17712/25/2018 By: Tekendra Nath Yogi

178. Homework
•Explainthedifferencesandsimilaritiesbetweendepth-firstsearchand
breadth-firstsearch.Giveexamplesofthekindsofproblemswhereeach
wouldbeappropriate.
•Explainwhatismeantbythefollowingtermsinrelationtosearchmethods:
–complexity
–completeness
–Optimality
•Provideadefinitionoftheword“heuristic.”Inwhatwayscanheuristicsbe
usefulinsearch?Namethreewaysinwhichyouuseheuristicsinyour
everydaylife.
•Explainthecomponentsofthepathevaluationfunctionf(node)usedby
A*.Doyouthinkitisthebestevaluationfunctionthatcouldbeused?To
whatkindsofproblemsmightitbebestsuited?Andtowhatkindsof
problemswoulditbeworstsuited?
12/25/2018 By:TekendraNathYogi 178

179. Contd…
•What is alpha-beta pruning procedure? Solve the following problem by using
this procedure
17912/25/2018 By: Tekendra Nath Yogi

180. Contd…
•What are the different steps involved in simple problem solving?
•What is the main difference between Uninformed Search and
Informed Search strategies?
•What are the advantages and disadvantages of bidirectional
search strategy?
•What are the advantages of local search?
18012/25/2018 By: Tekendra Nath Yogi

181. Thank You !
181By: Tekendra Nath Yogi12/25/2018