State Space Search in ai

Artificial Intelligence: Introduction, Typical Applications. State Space Search: Depth Bounded
DFS, Depth First Iterative Deepening. Heuristic Search: Heuristic Functions, Best First Search,
Hill Climbing, Variable Neighborhood Descent, Beam Search, Tabu Search. Optimal Search: A
*

algorithm, Iterative Deepening A*
, Recursive Best First Search, Pruning the CLOSED and OPEN
Lists

1. Topic To Be Covered:
State Space Search in ai
Jagdamba Education Society's
SND College of Engineering & Research Centre
Department of Computer Engineering
SUBJECT: Artificial Intelligence & Robotics
Lecture No-04
Prof.Dhakane Vikas N

2. AI in gaming
Invideogames,artificialintelligence(AI)isusedtogenerateresponsive,
adaptiveorintelligentbehaviorsprimarilyinnon-playercharacters
(NPCs)similartohuman-likeintelligence.
Artificialintelligencehasbeenanintegralpartofvideogamessincetheir
inceptioninthe1950s.

3. AI in gaming
AlphaGO-AlphaZero-AlphaGodefeatedtheEuropeanGochampionFan
Hui,professional,fivetozero.ThiswasthefirsttimeacomputerGo
programhadbeatenaprofessionalhumanplayeronafull-sizedboard.
IBM'scomputerDeepBluebeatworldchesschampionGarryKasparovin
the1997match

4. AI in gaming
AlphaGoanditssuccessorsuseaMonteCarlotreesearchalgorithmto
finditsmovesbasedonknowledgepreviously"learned"bymachine
learning,specificallybyanartificialneuralnetwork(adeep
learningmethod)byextensivetraining,bothfromhumanandcomputer
play.

5. Problem solving in ai:state space search
Artificial Intelligence as a problem
solver
AccordingtoComputersciencemost
importantpartofArtificialintelligenceis
problemsolvingwhichcanbedoneby
usingvarioustechniquesandalgorithms
ofAI.
Ex:STATESPACESEARCH
TheaimofArtificialIntelligenceisto
developasystemwhichcansolvethe
variousproblemsonitsown.
VariousapplicationsofAIarenothingbut
satisfyingsomeconstraints(Finding
solution)tovariouskindsofrealworld
problems.

6. Problem solving in ai: state space search
state space search
SSSisthemostcommonlyused
techniqueinAIforproblemsolving
In,generalsearchingreferstoas
findinginformationoneneeds.
STATE SPACE
Thestatespaceofaproblemistheset
ofallstatesreachablefrominitial
statebyexecutinganysequenceof
actions.
Statespacespecifiestherelation
amongvariousproblemssatesthereby
formingdirectednetworkofgraphsin
whichthenodesarestatesandthe
linksbetweennodesrepresentactions.

7. Problem solving in ai: state space search
state space search
Statespacesearch:Itissearchingin
givenspaceofstatespertainingtoa
problemunderconsideration.
Statespacesearch:isaprocess
usedinthefieldofcomputerscience,
includingartificialintelligence
(AI),inwhich successive
configurationsorstatesofaninstance
areconsidered,withtheintentionof
findingagoalstatewithadesired
property.
Path:Apathissequenceofstates
connectedbysequenceofactions,ina
givenstatespace.

8. Problem solving in ai: state space search
Properties of search algorithm
I.Completeness
Asearchissaidtobecompleteifitguaranteetoreturnaatleastone
solutionforanyrandominput.
II.Optimality
Idasolutionfoundusingalgorithmisguaranteetobethebest
solution(lowestpathcost)amongallothersolutionsthensuchsolutionis
calledoptimalsolution.
III.TimeComplexity
Itisthemeasureofthetimeforanalgorithmtocompleteitstask.
IV.SpaceComplexity
Itismaximumstoragerequiredatanypointduringthesearchasthe
complexityofproblem.