UNIT-2

SEARCHING

Searching for solutions

Search AlgorithmTerminologies (SearchStrategies):

1. Search
Searching is a step by step procedure to solve a search-problem in a given
searchspace.Asearchproblemcan havethreemainfactors:
 SearchSpace:Searchspacerepresentsasetofpossiblesolutions,whichasystemmayhave.
 StartState: It is astate fromwhere agent begins thesearch.
 Goaltest:Itisafunctionwhichobservethecurrentstateandreturnswhetherthegoalstateis
achieved ornot.
2. SearchTrees
AtreerepresentationofsearchproblemiscalledSearchtree.Therootofthesearchtreeistherootnode
which is corresponding to theinitialstate.
3. Actions
Itgivesthedescription ofalltheavailableactionstotheagent.
4. Transition Model
Adescriptionofwhateach action do, canbe represented as a transition model.
5. Path Cost
Itis a function whichassigns anumeric cost to eachpath.
6. Solution
It isan actionsequence whichleadsfromthestartnodetothegoalnode.
7. OptimalSolution
If a solutionhasthe lowest cost among all solutions.

Properties ofSearchAlgorithms:

Followingarethefouressentialpropertiesofsearchalgorithms:
Completeness: A search algorithm is said to be complete if it guarantees to returna solution if
atleastanysolution exists foranyrandominput.
Optimality:Ifasolutionfoundforanalgorithmisguaranteedtobethebestsolution(lowest path cost)
among all other solutions, then such a solution for is said to beanoptimal solution.
Time Complexity: Time complexity is a measure of time for an algorithm tocompleteitstask.
Space Complexity: It is the maximum storage space required at any point duringthesearch, as
thecomplexityoftheproblem.

1
Uniform search strategies:

Uninformed/BlindSearch:
The uninformed search does not contain any domain knowledge such as closeness,the
locationofthe goal.Itoperatesin abrute-force way asitonly includesinformation
abouthowtotraversethetreeandhow toidentifyleaf and goalnodes.Uninformed search applies a
way in which search tree is searched without anyinformation about the search space like initial
state operators and test for the goal,so it is also called blind search. It examines each node of the
tree until it achievesthegoalnode.
2
It can bedividedintofivemain types:

 Breadth-firstsearch
 Uniformcostsearch
 Depth-first search
 Iterativedeepening depth-firstsearch
 BidirectionalSearch

UninformedSearchAlgorithms

Uninformedsearchisaclassofgeneral-purposesearchalgorithmswhichoperatesinbruteforce-
way.Uninformedsearchalgorithmsdonothave
additionalinformationaboutstateorsearchspaceotherthanhowtotraversethetree,so it is also
calledblind search.
Followingarethe various typesofuninformed searchalgorithms:

1. Breadth-firstSearch
2. Depth-firstSearch
3. Depth-limitedSearch
4. Iterativedeepening depth-firstsearch
5. Uniformcostsearch
6. BidirectionalSearch

1. Breadth-firstSearch:
 Breadth-firstsearchis themostcommon
searchstrategyfortraversingatreeorgraph.Thisalgorithmsearchesbreadthwiseinatreeorgrap
h,soitiscalledbreadth-firstsearch.
 BFSalgorithmstartssearchingfromtherootnodeofthetreeandexpandsallsuccessornode at
thecurrent level beforemovingto nodesof nextlevel.
 The breadth-first search algorithm is an example of a general-graph searchalgorithm.
 Breadth-first search implemented using FIFO queue data
structure.Advantages:

 BFSwillprovideasolution ifanysolution exists.

 If there are more than one solutions for a given problem, then BFS
willprovidetheminimalsolutionwhichrequiresthe leastnumberofsteps.
Disadvantages:

 Itrequireslotsofmemorysinceeachlevelofthetreemustbesavedintomemorytoexpand
thenextlevel.
 BFS needs lots of time if the solution is far away from the root node.Example:
In the below tree structure, we have shown the traversing of the tree using BFSalgorithm from
the root node S to goal node K. BFS search algorithm traverse inlayers, so it will follow the path
which is shown by the dotted arrow, and thetraversedpath will be:
3
ss

Time Complexity: Time Complexity of BFS algorithm can be obtained by thenumber of nodes
traversed in BFS until the shallowest Node. Where the d= depthofshallowest solution andb is a
nodeat everystate.
T(b)= 1+b2+b3+ +bd= O(bd)
SpaceComplexity:SpacecomplexityofBFSalgorithmisgivenbytheMemorysizeof frontierwhichis
O(bd).
Completeness:BFSiscomplete,whichmeansiftheshallowestgoalnodeisatsomefinitedepth,then
BFSwill findasolution.
Optimality:BFSisoptimalifpathcostisanon-decreasingfunction ofthedepthofthenode.

2. Depth-firstSearch
 Depth-first search is a recursive algorithm for traversing a tree or graph datastructure.
 Itiscalledthedepth-firstsearchbecauseitstartsfromtherootnodeandfollowseach path to
itsgreatest depth nodebeforemovingtothenext path.
 DFSusesa stackdatastructure foritsimplementation.
 Theprocessofthe DFSalgorithmissimilartothe BFSalgorithm.

Advantage:

 DFSrequiresverylessmemoryasitonlyneedstostoreastackofthenodes onthepath
fromroot nodeto the current node.
 IttakeslesstimetoreachtothegoalnodethanBFSalgorithm(ifittraversesin therightpath).

Disadvantages:

 Thereisthepossibilitythatmanystateskeepre-occurring,andthereisnoguaranteeoffinding
thesolution.
 DFSalgorithm goesfordeepdownsearchingandsometimeitmay gototheinfiniteloop.
Example:

4
In the below search tree, we have shown the flow of depth-first search, anditwill follow
theorderas:
Rootnode--->Leftnode ----------- >rightnode.
It will start searching from root node S, and traverse A, then B, then D andE, after
traversing E, it will backtrack the tree as E has no other successorand still goal node is
not found. After backtracking it will traverse node Cand then G,andhereit will
terminateasit foundgoal node.

Completeness:DFSsearchalgorithmiscompletewithinfinitestatespaceasit willexpand everynode

withinalimited searchtree.

TimeComplexity:TimecomplexityofDFSwillbeequivalenttothenodetraversedbythe
algorithm.It is given by:
T(n)=1+ n2+ n3+ ............... +nm=O(nm)
Where, m= maximum depth of any node and this can be much larger than
d(Shallowestsolutiondepth)
Space Complexity: DFS algorithm needs to store only single path from theroot node,
hence space complexity of DFS is equivalent to the size of thefringeset, whichisO(bm).
Optimal: DFS search algorithm is non-optimal, as it may generate a largenumber
ofsteps orhigh cost to reach to thegoalnode.

3. Depth-LimitedSearchAlgorithm:
A depth-limited search algorithm is similar to depth-first search withapredetermined
limit. Depth-limited search can solve the drawback of theinfinitepathintheDepth-
firstsearch.Inthisalgorithm,thenodeatthedepthlimit will treatasithas no successor
nodesfurther.
Depth-limitedsearchcanbeterminatedwithtwo Conditionsof failure:

 Standardfailurevalue:Itindicatesthatproblemdoesnothaveanysolution.
 Cutofffailurevalue:Itdefinesnosolutionfortheproblemwithinagiven depthlimit.
Advantage:
Depth-limitedsearchisMemoryefficient.
5
Disadvantages:
o Depth-limitedsearchalsohasadisadvantage of incompleteness.
o It may not be optimal if the problem has more than one solution
Example:

Completeness:DLSsearchalgorithmiscompleteifthesolutionisabovethedepth-limit.
Time Complexity:TimecomplexityofDLSalgorithmisO(bℓ).

Space Complexity:Space complexityof DLSalgorithmis O(b×ℓ).

Optimal: Depth-limited search can be viewed as a special case of DFS, and it isalsonot optimal
evenif ℓ>d.

4. Uniform-costSearchAlgorithm:
Uniform-costsearchisasearchingalgorithmusedfortraversingaweightedtreeorgraph. This
algorithm comes into play when a different cost is available for
eachedge.Theprimarygoaloftheuniform-costsearchistofind
apathtothegoalnodewhichhasthelowestcumulativecost.Uniform-
costsearchexpandsnodesaccording to their path costs form the root node. It can be used to solve
anygraph/treewheretheoptimalcostisindemand.Auniform-
costsearchalgorithmisimplementedbythepriorityqueue.Itgivesmaximumprioritytothelowestcumu
lativecost.UniformcostsearchisequivalenttoBFSalgorithmifthepathcostofall edgesisthesame.

Advantage:
 Uniform costsearchisoptimalbecauseatevery statethepathwiththeleastcost is chosen.

Disadvantage:

6
 It does not care about the number of steps involve in searching and onlyconcerned
aboutpath cost. Due to which this algorithm may be stuck in aninfinite loop

Completeness:

Uniform-costsearchis complete,such asif thereis asolution, UCS will findit.

TimeComplexity:

LetC*isCostoftheoptimalsolution,andεiseachsteptogetclosertothegoalnode.Thenthenumberof
steps is=C*/ε+1.Herewehavetaken+1,aswestartfromstate0 and endto C*/ε.
Hence,theworst-case timecomplexityofUniform-costsearchisO( b1+[C*/ε])/.

SpaceComplexity:

Thesamelogicisforspacecomplexityso,theworst-casespacecomplexityofUniform-cost
searchis O(b1+[C*/ε]).

Optimal:Uniform-costsearchisalwaysoptimalasitonlyselectsapathwiththelowestpath cost.

5. Iterativedeepeningdepth-firstSearch:
TheiterativedeepeningalgorithmisacombinationofDFSandBFSalgorithms.This search
algorithm finds out the best depth limit and does it by graduallyincreasingthelimit until
agoalisfound.
This algorithm performs depth-first search up to a certain "depth limit", and
itkeepsincreasingthedepthlimitaftereachiterationuntilthegoalnodeisfound.
ThisSearchalgorithmcombinesthebenefitsofBreadth-firstsearch'sfastsearchanddepth-first
search's memoryefficiency.
Theiterativesearchalgorithmisusefuluninformedsearchwhensearchspaceislarge,and depth
ofgoal nodeis unknown.
Advantages:

7
 ItcombinesthebenefitsofBFSandDFSsearchalgorithmintermsoffastsearchand
memoryefficiency.
Disadvantages:

 ThemaindrawbackofIDDFSisthatitrepeatsalltheworkofthepreviousphase.

Example:

Following tree structure is showing the iterative deepening depth-first

search.IDDFSalgorithmperformsvariousiterationsuntilitdoesnotfindthegoalnode.The
iteration performed bythealgorithmisgiven as:

1'stIteration -------- > A

2'nd Iteration ------ >A,B, C
3'rdIteration---------- >A,B, D,E,C, F,G
4'thIteration --------- >A,B, D,H, I,E, C,F,K,G
In thefourth iteration,the algorithmwillfindthe goal node.

Completeness:

Thisalgorithmiscomplete isifthebranching factorisfinite.

TimeComplexity:

Let'ssupposebisthebranchingfactoranddepthisdthentheworst-casetimecomplexityis O(bd).

SpaceComplexity:

ThespacecomplexityofIDDFSwillbe O(bd).

Optimal:

8
IDDFSalgorithm is optimalif pathcost isanon- decreasingfunction of thedepthofthe node.

6. BidirectionalSearchAlgorithm:
Bidirectional search algorithm runs two simultaneous searches, one form initialstate called
as forward-search and other from goal node called as backward-search, to find the goal
node. Bidirectional search replaces one single searchgraph with two small subgraphs in
which one starts the search from an
initialvertexandotherstartsfromgoalvertex.Thesearchstopswhenthesetwographsintersecteacho
ther.
Bidirectionalsearchcan usesearchtechniquessuch asBFS, DFS, DLS, etc.

Advantages:

 Bidirectionalsearchis fast.
 Bidirectionalsearchrequireslessmemory

Disadvantages:

 Implementationofthe bidirectionalsearchtreeis difficult.

 Inbidirectional search,one should knowthegoal stateinadvance.

Example:

Inthebelowsearchtree,bidirectionalsearchalgorithmisapplied.Thisalgorithm divides one

graph/tree into two sub-graphs. It starts traversing fromnode 1 in the forward direction and
starts from goal node 16 in the backwarddirection.

9
Thealgorithmterminates atnode9 wheretwo searchesmeet.
Completeness:BidirectionalSearchiscompleteifweuseBFSinbothsearches.

TimeComplexity:TimecomplexityofbidirectionalsearchusingBFSisO(bd).

Complexity:Space complexityofbidirectio nalsearchis O(bd).

Optimal:BidirectionalsearchisOptimal.

Informed Search

Informedsearchalgorithmsusedomainknowledge.Inaninformedsearch,probleminformationisavail
ablewhichcanguidethesearch.Informedsearchstrategiescanfindasolutionmoreefficientlythananuni
nformedsearchstrategy.Informedsearchisalso called aHeuristicsearch.
A heuristic is a way which might not always be guaranteed for best solutions butguaranteedto
findagood solution inreasonabletime.
Informed search can solve much complex problem which could not be solved inanotherway.
Anexampleofinformedsearchalgorithmsisatravelingsalesmanproblem.

 GreedySearch
 A*Search
The informed search algorithm is more useful for large search space.
Informedsearchalgorithmusestheidea ofheuristic,so itis alsocalledHeuristicsearch.
Heuristicsfunction:Heuristicis afunctionwhichisused inInformedSearch,andit finds the most
promising path. It takes the current state of the agent as its inputand produces the estimation of
how close agent is from the goal. The
heuristicmethod,however,mightnotalwaysgivethebestsolution,butitguaranteedtofinda good
solution in reasonable time. Heuristic function estimates how close a stateis to the goal. It is
represented by h(n), and it calculates the cost of an optimal pathbetweenthepairof states. The
valueof theheuristicfunction isalways positive.

Admissibilityoftheheuristicfunction isgivenas:

h(n)<= h*(n)
Here h(n) is heuristic cost, and h*(n) is the estimated cost. Hence heuristic costshouldbeless
thanorequaltothe estimated cost.

PureHeuristic Search:

Pureheuristicsearchisthesimplestformofheuristicsearch
algorithms.Itexpandsnodesbasedontheirheuristicvalueh(n).Itmaintainstwolists,OPENandCLOSE
D list. In the CLOSED list, it places those nodes which have alreadyexpanded
andintheOPENlist,itplacesnodes whichhaveyetnotbeenexpanded.
On each iteration, each node n with the lowest heuristic value is expanded
10
andgeneratesallitssuccessorsandnisplacedtotheclosedlist.Thealgorithmcontinuesunit agoalstateis
found.
Intheinformedsearchwewilldiscusstwomainalgorithmswhicharegivenbelow:

 BestFirstSearchAlgorithm(Greedysearch)
 A*SearchAlgorithm

1.)Best-firstSearchAlgorithm(GreedySearch):
Greedybest-
firstsearchalgorithmalwaysselectsthepathwhichappearsbestatthatmoment.Itisthecombinationofde
pth-firstsearchandbreadth-firstsearchalgorithms. It uses the heuristic function and search. Best-
first search allows us totake the advantages of both algorithms. With the help of best-first
search, at eachstep,wecanchoosethe
mostpromisingnode.Inthebestfirstsearchalgorithm,weexpand the node which is closest to the
goal node and the closest cost is estimatedbyheuristic function,i.e.
f(n)=g(n).
Were,h(n)= estimatedcostfromnodentothegoal.
The greedybestfirstalgorithmisimplementedbythe priorityqueue.

Bestfirstsearchalgorithm:

Step 1: Place thestarting node intotheOPENlist.

Step 2: IftheOPENlist is empty,Stop and return failure.
Step3:Removethenoden,fromtheOPENlistwhichhasthelowestvalueofh(n),and places it in the
CLOSEDlist.
Step 4: Expand thenoden,andgeneratethesuccessorsofnoden.
Step 5: Check each successor of node n, and find whether any node is a goal nodeor not. If any
successor node is goal node, then return success and terminate thesearch,elseproceedto Step6.
Step6:Foreachsuccessornode,algorithmchecksforevaluationfunctionf(n),andthencheckifthenodeh
asbeenineitherOPENorCLOSEDlist.Ifthenodehasnotbeenin bothlist,thenaddittothe OPENlist.
Step7: Return toStep 2.

Advantages:

 BestfirstsearchcanswitchbetweenBFSandDFSbygainingtheadvantagesofboththealgorith
ms.
 Thisalgorithmismore efficientthanBFS andDFSalgorithms.

Disadvantages:

 It canbehaveasanunguideddepth-firstsearchinthe worstcasescenario.
11
 It can get stuck in a loop as DFS.This
algorithm is not optimal
.Example:
Considerthebelowsearchproblem,andwewilltraverseitusinggreedybest-
firstsearch.Ateachiteration,eachnodeisexpandedusingevaluationfunctionf(n)=h(n)
, which isgiven inthebelowtable.

Inthissearchexample,weareusingtwolistswhichareOPENandCLOSEDLists.Followingaretheiterationfortr
aversing theaboveexample.

Expand the nodes of S and put in the CLOSED

listInitialization:Open[A,B], Closed[S]
Iteration 1: Open [A], Closed [S,
B]Iteration2:Open[E,F,A],Closed[S,B]
12
: Open [E, A], Closed [S, B,
F]Iteration3:Open[I,G,E,A],Closed[S,B,F]
: Open [I,E, A], Closed [S, B, F, G]
Hencethe finalsolutionpathwill be:S---->B----->F ------------------ >G
TimeComplexity:TheworstcasetimecomplexityofGreedybestfirstsearchisO(bm)
SpaceComplexity:TheworstcasespacecomplexityofGreedybestfirst searchisO(bm). Where,
misthemaximumdepthofthesearchspace.
Complete:Greedybest-firstsearchisalsoincomplete,evenifthegivenstatespaceisfinite.
Optimal: Greedybest firstsearch algorithmisnot optimal.

2.)A*SearchAlgorithm:
A*searchisthemostcommonlyknownformofbest-
firstsearch.Itusesheuristicfunctionh(n),andcosttoreachthenodenfromthestartstateg(n).Ithascombinedfeatur
esofUCSandgreedybest-firstsearch,by whichitsolvetheproblemefficiently. A* search algorithm finds the
shortest path through the search spaceusing the heuristic function. This search algorithm expands less
search tree andprovides optimal result faster. A* algorithm is similar to UCS except that it
usesg(n)+h(n)insteadofg(n).
InA*searchalgorithm,weusesearchheuristicaswellasthecosttoreachthenode.Hence we can
combine both costs as following, and this sum is called as a fitnessnumber.

AlgorithmofA*search:
Step1: PlacethestartingnodeintheOPENlist.
Step2:CheckiftheOPENlistisemptyornot,ifthelistisemptythenreturnfailureand stops.
Step 3:Selectthe node from the OPEN list which has the smallestvalue ofevaluation function
(g+h), if node n is goal node then return success and stop,otherwise
Step 4: Expand node n and generate all of its successors, and put n into the closedlist. For each
successor n', check whether n' is already in the OPEN or CLOSEDlist,ifnotthen
computeevaluationfunction forn'andplaceintoOpenlist.
Step5:Elseifnoden'isalreadyinOPENandCLOSED,thenitshouldbeattachedtothe backpointer
which reflects the lowestg(n') value.
Step6: Returnto Step 2

Advantages:

 A* search algorithmis thebest algorithmthanothersearch algorithms.

 A*search algorithmisoptimal andcomplete.
13
 This algorithmcansolveverycomplexproblems.

Disadvantages:

 Itdoesnotalwaysproducetheshortestpathasitmostlybasedonheuristicsand approximation.
 A* searchalgorithmhassomecomplexityissues.
 ThemaindrawbackofA*ismemoryrequirementasitkeepsallgeneratednodesin the
memory,so itisnot practicalfor variouslarge-scaleproblems.

Example:

In this example, we will traverse the given graph using the A* algorithm. Theheuristic value of
all states is given in the below table so we will calculate the
f(n)ofeachstateusingtheformulaf(n)=g(n)+h(n),whereg(n)isthecosttoreachanynodefromstartstate.
Here wewilluseOPENand CLOSEDlist.

Solution:

Initialization:{(S,5)}

Iteration1:{(S-->A,4), (S-->G, 10)}

Iteration2: {(S-->A-->C, 4),(S-->A-->B,7),(S-->G, 10)}

14
Iteration3:{(S-->A-->C--->G,6),(S-->A-->C--->D,11),(S-->A-->B,7),(S--
>G,10)}
Iteration4willgivethefinalresult,asS--->A--->C--->Gitprovidestheoptimalpathwith cost 6.

Pointstoremember:

 A*algorithmreturnsthepathwhichoccurredfirst,anditdoesnotsearchforallremaining paths.
 TheefficiencyofA*algorithmdependsonthe qualityofheuristic.
 A* algorithmexpands all nodes whichsatisfythe conditionf(n)

Complete:A* algorithmiscomplete aslong as:

 Branchingfactorisfinite.
 Cost ateveryactionisfixed.
Optimal:A*searchalgorithmisoptimalifitfollowsbelowtwoconditions:
Admissible: the first condition requires for optimality is that h(n) should be anadmissible
heuristic for A* tree search. An admissible heuristic is optimistic innature.
Consistency: Secondrequiredcondition is consistencyforonlyA* graph-search.
Iftheheuristicfunctionisadmissible,thenA*treesearchwillalwaysfindtheleastcostpath.
TimeComplexity:ThetimecomplexityofA*searchalgorithmdependsonheuristicfunction,andthen
umberofnodesexpandedisexponentialtothedepthofsolution d.So thetimecomplexityis
O(b^d),whereb is thebranching factor.
SpaceComplexity:The spacecomplexityof A*searchalgorithmisO(b^d)

HillClimbing Algorithm

 Hillclimbingalgorithm isalocalsearchalgorithm whichcontinuouslymoves in the direction

of increasing elevation/value to find the peak of
themountainorbestsolutiontotheproblem.Itterminateswhenitreachesapeakvaluewhereno
neighborhas ahighervalue.
 Hill climbing algorithm is a technique which is used for optimizing
themathematicalproblems.OneofthewidelydiscussedexamplesofHillclimbing algorithm is
Traveling-salesman Problem in which we need tominimize the distancetraveledbythe
salesman.
 It is also called greedy local search as it only looks to its good immediateneighborstate
and not beyond that.
 A node of hill climbing algorithm has two components which are state andvalue.
 Hill Climbingis mostlyusedwhen agood heuristic is available.
 In this algorithm, we don't need to maintain and handle the search tree orgraphasit
onlykeeps a singlecurrent state.

FeaturesofHillClimbing:

15
FollowingaresomemainfeaturesofHillClimbingAlgorithm:

 Generate and Test variant: Hill Climbing is the variant of Generate andTest method.
The Generate and Test method produce feedback whichhelps todecide
whichdirectionto move inthesearchspace.
 Greedy approach: Hill-climbing algorithm search moves in the directionwhich
optimizes thecost.
 No backtracking: It does not backtrack the search space, as it does notremember the
previousstates.

State-spaceDiagramforHillClimbing:

The state-space landscape is a graphical representation of the hill-climbingalgorithm

which is showing a graph between various states of algorithm
andObjectivefunction/Cost.
On Y-axis we have taken the function which can be an objective function orcost
function, and state-space on the x-axis. If the function on Y-axis is
costthen,thegoalofsearchistofindtheglobalminimumand localminimum.Ifthe function of
Y-axis is Objective function, then the goal of the search is tofindtheglobal maximumand
local maximum.

Differentregionsinthe state spacelandscape:

LocalMaximum:Localmaximumisastatewhichisbetterthanitsneighborstates,butthereis
alsoanother state whichis higher than it.
GlobalMaximum:Globalmaximumis thebestpossiblestateofstatespacelandscape.Ithas
thehighest valueof objective function.
Currentstate:Itisastateinalandscapediagramwhereanagentiscurrentlypresent.
Flatlocalmaximum:Itisaflatspaceinthelandscapewherealltheneighborstatesofcurrent
stateshavethesamevalue.
Shoulder:Itis aplateau region which hasan uphill edge.

TypesofHillClimbingAlgorithm:
16
1. SimplehillClimbing:
2. Steepest-Ascenthill-climbing:
3. Stochastichill Climbing:
1. SimpleHill Climbing:
Simplehillclimbingisthesimplestwaytoimplementahillclimbingalgorithm. It only
evaluates the neighbor node state at a time and selects thefirst one which optimizes
current cost and set it as a current state. It
onlychecksit'sonesuccessorstate,andifitfindsbetterthanthecurrentstate,thenmove elsebe in
thesamestate. This algorithmhas thefollowingfeatures:

 Lesstime consuming
 Lessoptimalsolutionandthesolutionisnot guaranteed

AlgorithmforSimpleHillClimbing:

Step 1: Evaluate the initial state, if it is goal state then return success and Stop.Step 2: Loop
Until a solution is found or there is no new operator left to apply.Step3: Select and applyan
operatorto thecurrentstate.
Step 4:Checknewstate:

i. Ifitisgoalstate,thenreturnsuccessandquit.
ii. Elseifitisbetterthanthecurrentstatethenassignnewstateasacurrentstate.
iii. Else if not better than the current state, then return to step2.Step 5:
Exit.

2. Steepest-Ascenthill climbing:
Thesteepest-Ascentalgorithmisavariationofsimplehillclimbingalgorithm.Thisalgorithm examines
all the neighboring nodes of the current state and selects oneneighbor node which is closest to
the goal state. This algorithm consumes moretimeas it searches for multipleneighbors.

AlgorithmforSteepest-Ascenthill climbing:

Step 1: Evaluate the initial state, if it is goal state then return success and stop, elsemakecurrent
state asinitial state.
Step2: Loopuntilasolutionisfoundorthecurrent statedoesnot change.

a. LetSUCCbeastatesuchthatanysuccessorofthecurrentstatewillbebetterthan it.
b. Foreachoperatorthatapplies to the currentstate:
i. Applythenewoperatorandgenerateanewstate.
ii. Evaluatethe newstate.
iii. Ifitisgoalstate,thenreturnitandquit,elsecompareittotheSUCC.
iv. IfitisbetterthanSUCC,thensetnewstateasSUCC.
v. IftheSUCCisbetterthanthecurrentstate,thensetcurrentstatetoSUCC.
17
Step 5: Exit.

3. Stochastichillclimbing:
Stochastic hill climbing does not examine for all its neighbor before moving.Rather, this search
algorithm selects one neighbor node at random and decideswhetherto chooseitas a
currentstateorexamine anotherstate.

ProblemsinHillClimbingAlgorithm:

1. Local Maximum: A local maximum is a peak state in the landscape which isbetter than each
of its neighboring states, but there is another state also presentwhichis
higherthanthelocalmaximum.
Solution: Backtracking technique can be a solution of the local maximum in statespace
landscape. Create a list of the promising path so that the algorithm canbacktrackthesearch
spaceand exploreother paths as well.

2. Plateau: A plateau is the flat area of the search space in which all the neighborstates of the
current state contains the same value, because of this algorithm doesnot find any best direction
to move. A hill-climbing search might be lost in theplateau area.
Solution: The solution for the plateau is to take big steps or very little steps
whilesearching,tosolvetheproblem.Randomlyselectastatewhichisfarawayfromthecurrentstate so
it ispossiblethat thealgorithmcouldfind non-plateauregion.

18
3. Ridges: A ridge is a special form of the local maximum. It has an area which
ishigher than its surrounding areas, but itself has a slope, and cannot be reached in
asinglemove.
Solution:Withtheuseofbidirectionalsearch,orbymovingindifferentdirections,wecan
improvethisproblem.

Simulated Annealing:

A hill-climbing algorithm which never makes amove towards a lower

valueguaranteed to be incomplete because it can get stuck on a local maximum. And
ifalgorithmappliesarandomwalk,bymovingasuccessor,thenitmaycompletebutnotefficie
nt.SimulatedAnnealingisanalgorithmwhichyieldsbothefficiencyandcompleteness.
In mechanical term Annealing is a process of hardening a metal or glass to a
hightemperature then cooling gradually, so this allows the metal to reach a low-
energycrystalline state. The same process is used in simulated annealing in which
thealgorithm picks a random move, instead of picking the best move. If the
randommoveimprovesthestate,thenitfollowsthesamepath.Otherwise,thealgorithm
follows the path which has a probability of less than 1 or it moves downhill
andchoosesanotherpath.

Applications of Hill Climbing Algorithm

The hill climbing technique has seen wide-spread usage in artificial intelligence and optimization
respectively. It methodically solves those problems via coupled research activities by
systematically testing options and picking out the most appropriate one. Some of the application
are as follows:

Some of the application are as follows:

1. Machine Learning:

Fine tuning of machine learning models frequently is doing the hyper parameter optimization that
provides the model with guidance on how it learns and behaves. Another exercise which serves the
same purpose is hill training. Gradual adjustment of hyperparameters and their evaluation according
to the respectively reached the essence of the hill climbing method.

2. Robotics:

19
In robotics, hill climbing technique turns out to be useful for an artificial agent roaming through a
physical environment where its path is adjusted before arriving at the destination.

3. Network Design:

The tool may be employed for improvement of network forms, processes, and topologies in the
telecommunications industry and computer networks. This approach erases the redundancy thus the
efficiency of the networks are increased by studying and adjusting their configurations. It facilitates
better cooperation, efficiency, and the reliability of diverse communication system.

4. Game playing:

Altough the hill climbing can be optimal in game playing AI by developing the strategies which
helps to get the maximum scores.

5. Natural language processing:

The software assists in adjusting the algorithms to enable the software to be efficient at dealing with
the tasks at hand such as summarizing text, translating languages and recognizing speech. These
abilities owing to it as a significant tool for many applications

AO* ALGORITHM
The AO* method divides any given difficult problem into a smaller group of problems that
are then resolved using the AND-OR graph concept. AND OR graphs are specialized graphs
that are used in problems that can be divided into smaller problems. The AND side of the
graph represents a set of tasks that must be completed to achieve the main goal, while the OR
side of the graph represents different methods for accomplishing the same main goal.

The start state and the target state are already known in the knowledge-based search strategy
known as the AO* algorithm, and the best path is identified by heuristics. The informed
search technique considerably reduces the algorithm’s time complexity. The AO* algorithm is
far more effective in searching AND-OR trees than the A* algorithm.

Working of AO* algorithm:

The evaluation function in AO* looks like this:

f(n) = g(n) + h(n)
f(n) = Actual cost + Estimated cost

here,

f(n) = The actual cost of traversal.

g(n) = the cost from the initial node to the current node.
h(n) = estimated cost from the current node to the goal state.

20
Example:

AO* Algorithm – Question tree

Here in the above example below the Node which is given is the heuristic value i.e h(n). Edge
length is considered as 1.
Step 1

AO* Algorithm (Step-1)

With help of f(n) = g(n) + h(n) evaluation function,

Start from node A,
f(A⇢B) = g(B) + h(B)
=1 + 5 ……here g(n)=1 is taken by default for path cost
=6

f(A⇢C+D) = g(c) + h(c) + g(d) + h(d)

=1+2+1+4 ……here we have added C & D because they are in AND

21
=8
So, by calculation A⇢B path is chosen which is the minimum path, i.e f(A⇢B)
Step 2

AO* Algorithm (Step-2)

According to the answer of step 1, explore node B

Here the value of E & F are calculated as follows,

f(B⇢E) = g(e) + h(e)

f(B⇢E) = 1 + 7
=8

f(B⇢f) = g(f) + h(f)

f(B⇢f) = 1 + 9
= 10
So, by above calculation B⇢E path is chosen which is minimum path, i.e f(B⇢E)
because B's heuristic value is different from its actual value The heuristic is
updated and the minimum cost path is selected. The minimum value in our situation is 8.
Therefore, the heuristic for A must be updated due to the change in B's heuristic.
So we need to calculate it again.

f(A⇢B) = g(B) + updated h(B)

=1+8
=9
We have Updated all values in the above tree.

22
Step 3

AO* Algorithm (Step-3) -Geeksforgeeks

By comparing f(A⇢B)& f(A⇢C+D)

f(A⇢C+D) is shown to be smaller. i.e 8 < 9
Now explore f(A⇢C+D)
So, the current node is C

f(C⇢G) = g(g) + h(g)

f(C⇢G) = 1 + 3
=4

f(C⇢H+I) = g(h) + h(h) + g(i) + h(i)

f(C⇢H+I) = 1 + 0 + 1 + 0 ……here we have added H & I because they are in AND
=2

f(C⇢H+I) is selected as the path with the lowest cost and the heuristic is also left unchanged
because it matches the actual cost. Paths H & I are solved because the heuristic for those paths
is 0,
but Path A⇢D needs to be calculated because it has an AND.

f(D⇢J) = g(j) + h(j)

f(D⇢J) = 1 + 0
=1
the heuristic of node D needs to be updated to 1.

f(A⇢C+D) = g(c) + h(c) + g(d) + h(d)

=1+2+1+1
=5

as we can see that path f(A⇢C+D) is get solved and this tree has become a solved tree now.
In simple words, the main flow of this algorithm is that we have to find firstlylevel 1st
heuristic
value and then level 2nd and after that update the values with going upward means towards
the root node.
In the above tree diagram, we have updated all the values.

23
Difference between the A* Algorithm and AO* algorithm
 A* algorithm and AO* algorithm both works on the best first search.
 They are both informed search and works on given heuristics values.
 A* always gives the optimal solution but AO* doesn’t guarantee to give the optimal
solution.
 Once AO* got a solution doesn’t explore all possible paths but A* explores all paths.
 When compared to the A* algorithm, the AO* algorithm uses less memory.
 opposite to the A* algorithm, the AO* algorithm cannot go into an endless loop.

PROBLEM REDUCTION
Problem reduction search is a basic problem-solving technique of AI. It involves reducing a problem to a
set of easier sub-problems whose solutions, if found, can be combined to form a solution to the hard
problem. When a problem can be divided into a set of sub problems, where each sub problem can be
solved separately and a combination of these will be a solution.

Problem reduction is the process of simplifying a complex problem into a set of simpler sub-
problems that can be solved individually. This allows AI systems to apply more efficient and
effective solution strategies.

When a problem can be divided into a set of sub problems, where each sub problem can be
solved separately and a combination of these will be a solution, AND-OR graphs or AND - OR
trees are used for representing the solution. The decomposition of the problem or problem
reduction generates AND arcs.

Problem Reduction Process

1. Decomposition: The original problem is broken down into smaller subproblems, each
represented by nodes in the graph. The AND arcs connect these subproblems, indicating
that all must be solved to reach the overall solution.
2. Search Algorithm: To find solutions within an AND-OR graph, algorithms similar to
best-first search are employed. These algorithms must account for both AND and OR
relationships, ensuring that all necessary subgoals are addressed while exploring
alternative paths when possible.
3. Cost Propagation: As solutions to subproblems are found, the costs are propagated back
up the graph. This process updates the values of parent nodes based on the minimum costs
of their children, helping to identify the most efficient path to the overall solution.

Other techniques include abstraction, heuristic methods, and constraint satisfaction. By breaking
down problems, AI systems can optimize computational resources, reduce processing time, increase
accuracy, and enhance overall efficiency

24
The AND-OR (AO*) graphs are used for representing the solution. The decomposition of the problem or
problem reduction generates AND arcs. One AND arc may point to any number of successor nodes. All
these must be solved so that the arc will rise to many arcs, indicating several possible solutions. Hence the
graph is known as AND - OR instead of AND. Figure shows an AND - OR graph:

AND-OR GRAPH

The above graph represents the search space for solving the problem P, using the goal reduction methods:
(i) P if Q and R, (ii) P if S, (iii) Q if T, (iv) Q if U

Note: explain A* algorithm with an example

Adversarial Search
Adversarial search is a search, where we examine the problem which arises when we try to
plan ahead of the world and other agents are planning against us.

o The environment with more than one agent is termed as multi-agent environment, in
which each agent is an opponent of other agent and playing against each other. Each
agent needs to consider the action of other agent and effect of that action on their
performance.
o So, Searches in which two or more players with conflicting goals are trying to
explore the same search space for the solution, are called adversarial searches, often
known as Games.
o Games are modeled as a Search problem and heuristic evaluation function, and these are
the two main factors which help to model and solve games in AI.

25
Types of Games in AI:

Deterministic Chance Moves

Perfect information Chess, Checkers, go, Othello Backgammon, monopoly

Bridge, poker, scrabble,

Imperfect information Battleships, blind, tic-tac-toe
nuclear war

o Perfect information: A game with the perfect information is that in which agents can look into
the complete board. Agents have all the information about the game, and they can see each other
moves also. Examples are Chess, Checkers, Go, etc.
o Imperfect information: If in a game agents do not have all information about the game and not
aware with what's going on, such type of games are called the game with imperfect information,
such as tic-tac-toe, Battleship, blind, Bridge, etc.
o Deterministic games: Deterministic games are those games which follow a strict pattern and set
of rules for the games, and there is no randomness associated with them. Examples are chess,
Checkers, Go, tic-tac-toe, etc.
o Non-deterministic games: Non-deterministic are those games which have various unpredictable
events and has a factor of chance or luck. This factor of chance or luck is introduced by either
dice or cards. These are random, and each action response is not fixed. Such games are also called
as stochastic games.
Example: Backgammon, Monopoly, Poker, etc.

Note: In this topic, we will discuss deterministic games, fully observable environment, zero-sum, and
where each agent acts alternatively.

Zero-Sum Game
o Zero-sum games are adversarial search which involves pure competition.
o In Zero-sum game each agent's gain or loss of utility is exactly balanced by the losses or gains of
utility of another agent.
o One player of the game try to maximize one single value, while other player tries to minimize it.
o Each move by one player in the game is called as ply.
o Chess and tic-tac-toe are examples of a Zero-sum game.

Zero-sum game: Embedded thinking

The Zero-sum game involved embedded thinking in which one agent or player is trying to figure out:

o What to do.
o How to decide the move
o Needs to think about his opponent as well
o The opponent also thinks what to do
Each of the players is trying to find out the response of his opponent to their actions. This requires
embedded thinking or backward reasoning to solve the game problems in AI.

26
Formalization of the problem:
A game can be defined as a type of search in AI which can be formalized of the following
elements:

o Initial state: It specifies how the game is set up at the start.

o Player(s): It specifies which player has moved in the state space.
o Action(s): It returns the set of legal moves in state space.
o Result(s, a): It is the transition model, which specifies the result of moves in the state space.
o Terminal-Test(s): Terminal test is true if the game is over, else it is false at any case. The state
where the game ends is called terminal states.
o Utility(s, p): A utility function gives the final numeric value for a game that ends in terminal
states s for player p. It is also called payoff function. For Chess, the outcomes are a win, loss, or
draw and its payoff values are +1, 0, ½. And for tic-tac-toe, utility values are +1, -1, and 0.

Game tree:
A game tree is a tree where nodes of the tree are the game states and Edges of the tree are the moves
by players. Game tree involves initial state, actions function, and result Function.

Example: Tic-Tac-Toe game tree:

The following figure is showing part of the game-tree for tic-tac-toe game. Following are some key
points of the game:

o There are two players MAX and MIN.

o Players have an alternate turn and start with MAX.
o MAX maximizes the result of the game tree
o MIN minimizes the result.

27
Example Explanation:

o From the initial state, MAX has 9 possible moves as he starts first. MAX place x and
MIN place o, and both player plays alternatively until we reach a leaf node where one
player has three in a row or all squares are filled.
o Both players will compute each node, minimax, the minimax value which is the best
achievable utility against an optimal adversary.
o Suppose both the players are well aware of the tic-tac-toe and playing the best play. Each
player is doing his best to prevent another one from winning. MIN is acting against Max
in the game.
o So in the game tree, we have a layer of Max, a layer of MIN, and each layer is called
as Ply. Max place x, then MIN puts o to prevent Max from winning, and this game
continues until the terminal node.
o In this either MIN wins, MAX wins, or it's a draw. This game-tree is the whole search
space of possibilities that MIN and MAX are playing tic-tac-toe and taking turns
alternately.
Hence adversarial Search for the minimax procedure works as follows:

o It aims to find the optimal strategy for MAX to win the game.
o It follows the approach of Depth-first search.
o In the game tree, optimal leaf node could appear at any depth of the tree.
o Propagate the minimax values up to the tree until the terminal node discovered.
In a given game tree, the optimal strategy can be determined from the minimax value of each node,
which can be written as MINIMAX(n). MAX prefer to move to a state of maximum value and MIN
prefer to move to a state of minimum value then:

Important Features of Adversarial Search

An important field in artificial intelligence is adversarial search. This deals with decision-making
when faced with hostile situations. Here are some key aspects of adversarial search:

o PerfectorImperfectInformation
In games, there are two main types of information players have access to - perfect and imperfect.
In games with perfect information, all players fully know the current state of the game. However,
in games with imperfect information, some details are kept hidden from the players
o AdversarialSearchAlgorithms
In competitive games such as chess, a contender might use a method referred to as the minimax
strategy or the alpha-beta pruning to determine the best move. Such algorithms estimate feasible
results of each move and give hints that indicate the correct platform for the player.
o ThumbRule
The tree can be quite large and in some cases, this may mean that the full search of the tree may

28
not be achievable. In these cases, the algorithm utilizes heuristics, i.e., shortcuts that allow it to
proceed faster through the game tree, avoiding the need to evaluate every possible move. These
short rules provide an estimate of the best move, possible without actually exploring the complete
game tree.

Min max algorithm

o Mini-max algorithm is a recursive or backtracking algorithm which is used in decision-

making and game theory. It provides an optimal move for the player assuming that
opponent is also playing optimally.
o Mini-Max algorithm uses recursion to search through the game-tree.
o Min-Max algorithm is mostly used for game playing in AI. Such as Chess, Checkers, tic-
tac-toe, go, and various tow-players game. This Algorithm computes the minimax
decision for the current state.
o In this algorithm two players play the game, one is called MAX and other is called MIN.
o Both the players fight it as the opponent player gets the minimum benefit while they get
the maximum benefit.
o Both Players of the game are opponent of each other, where MAX will select the
maximized value and MIN will select the minimized value.
o The minimax algorithm performs a depth-first search algorithm for the exploration of the
complete game tree.
o The minimax algorithm proceeds all the way down to the terminal node of the tree, then
backtrack the tree as the recursion.

Pseudo-code for MinMax Algorithm:

1. function minimax(node, depth, maximizingPlayer) is

2. if depth ==0 or node is a terminal node then
3. return static evaluation of node
4.
5. if MaximizingPlayer then // for Maximizer Player
6. maxEva= -infinity
7. for each child of node do
8. eva= minimax(child, depth-1, false)
9. maxEva= max(maxEva,eva) //gives Maximum of the values
10. return maxEva
11.
12. else // for Minimizer player
13. minEva= +infinity
14. for each child of node do
15. eva= minimax(child, depth-1, true)
16. minEva= min(minEva, eva) //gives minimum of the values
17. return minEva
Initial call:

Minimax(node, 3, true)

29
Working of Min-Max Algorithm:
o The working of the minimax algorithm can be easily described using an example. Below
we have taken an example of game-tree which is representing the two-player game.
o In this example, there are two players one is called Maximizer and other is called
Minimizer.
o Maximizer will try to get the Maximum possible score, and Minimizer will try to get the
minimum possible score.
o This algorithm applies DFS, so in this game-tree, we have to go all the way through the
leaves to reach the terminal nodes.
o At the terminal node, the terminal values are given so we will compare those value and
backtrack the tree until the initial state occurs. Following are the main steps involved in
solving the two-player game tree:

Step-1: In the first step, the algorithm generates the entire game-tree and apply the utility function to
get the utility values for the terminal states. In the below tree diagram, let's take A is the initial state
of the tree. Suppose maximizer takes first turn which has worst-case initial value =- infinity, and
minimizer will take next turn which has worst-case initial value = +infinity.

Step 2: Now, first we find the utilities value for the Maximizer, its initial value is -∞, so we will
compare each value in terminal state with initial value of Maximizer and determines the higher nodes
values. It will find the maximum among the all.

o For node D max(-1,- -∞) => max(-1,4)= 4

o For Node E max(2, -∞) => max(2, 6)= 6
o For Node F max(-3, -∞) => max(-3,-5) = -3
o For node G max(0, -∞) = max(0, 7) = 7

30
Step 3: In the next step, it's a turn for minimizer, so it will compare all nodes value with +∞, and will
find the 3rd layer node values.

o For node B= min(4,6) = 4

o For node C= min (-3, 7) = -3

31
Step 4: Now it's a turn for Maximizer, and it will again choose the maximum of all nodes value and
find the maximum value for the root node. In this game tree, there are only 4 layers, hence we reach
immediately to the root node, but in real games, there will be more than 4 layers.

o For node A max(4, -3)= 4

That was the complete workflow of the minimax two player game.

Properties of Mini-Max algorithm:

o Complete- Min-Max algorithm is Complete. It will definitely find a solution (if exist), in
the finite search tree.
o Optimal- Min-Max algorithm is optimal if both opponents are playing optimally.
o Time complexity- As it performs DFS for the game-tree, so the time complexity of Min-
Max algorithm is O(bm), where b is branching factor of the game-tree, and m is the
maximum depth of the tree.
o Space Complexity- Space complexity of Mini-max algorithm is also similar to DFS
which is O(bm).

Limitation of the minimax Algorithm:

The main drawback of the minimax algorithm is that it gets really slow for complex games such as
Chess, go, etc. This type of games has a huge branching factor, and the player has lots of choices to
decide. This limitation of the minimax algorithm can be improved from alpha-beta pruning which
we have discussed in the next topic.

32
OPTIMAL DECISIONS IN MULTIPLAYER GAMES:

The optimal solution becomes a contingent strategy when specifies MAX(the player on our
side)’s move in the initial state, then Max move to the states resulting for every possible
response by MIN. Then MAX’s moves in the states resulting from every possible response by
MIN to those moves, and so on.

In a normal search problem, the optimal solution would be a sequence of actions leading to a
goal state-a terminal state that is a win. In adversarial search, MIN has something to say about it.
MAX therefore must find a contingent strategy, which specifies MAX's move in the initial state,
then MAX's moves in the states resulting from every possible response by

MIN, then MAX's moves in the states resulting from every possible response by MIN to those
moves, and so on. This is exactly analogous to the AND-OR search algorithm (Figure 4.1 1) with
MAX playing the role of OR and MIN equivalent to AND. Roughly speaking, an optimal
strategy leads to outcomes at least as good as any other strategy when one is playing an infallible
opponent. We begin by showing how to find this optimal strategy.

Even a simple game like tic-tac-toe is too complex for us to draw the entire game tree on one
page, so we will switch to the trivial game in Figure 5.2. The possible moves for MAX at the
root node are labeled a1, a2, and a3. The possible replies to a1 for MIN are b1, l>2, bs, and so
on. This particular game ends after one move each by MAX and MIN. (In game parlance, we say
that this tree is one move deep, consisting of two half-moves, each of which is called a ply.) The
utilities of the terminal states in this game range from 2 to 14.

Given a game tree, the optimal strategy can he cleterrninecl from the minimax value of each
node, which we write as MINIMAX(n). The minimax value of a node is the utility (for MAX) of
being in the corresponding state, assuming that both players play optimally from there to the end
of the game. Obviously, the minimax value of a terminal state is just its utility. Furthermore,
given a choice, MAX prefers to move to a state of maximum value, whereas MIN prefers a state
of minimwn value. So we have the following:

33
Let us apply these definitions to the game tree in Figure 5.2. The terminal nodes on the bottom
level get their utility values from the game's UTILITY function. The first MIN node, labeled B,
has three successor states with values 3, 12, and 8, so its minimax value is 3. Similarly, the other
two MIN nodes have minimax value 2. The root node is a MAX node; its successor states have
minimax values 3, 2, and 2; so it has a minimax value of 3. We can also identify the minimax
decision at the root: action a1 is the optimal choice for MAX because it leads to the state with the
highest minimax value.

This definition of optimal play for MAX assumes that MIN also plays optimally-it maximizes
the worst-case outcome for MAX. What if Mil\ does not play optimally? Then it is easy to show
(Exercise 5.7) that MAX will do even better. Other strategies against suboptimal opponents may
do better than the minimax strategy, but these strategies necessarily do worse against optimal
opponents.

Game playing

Game Playing is an important domain of artificial intelligence. Games don’t require much
knowledge; the only knowledge we need to provide is the rules, legal moves and the conditions
of winning or losing the game. Both players try to win the game. So, both of them try to make
the best move possible at each turn. Searching techniques like BFS(Breadth First Search) are
not accurate for this as the branching factor is very high, so searching will take a lot of time.
So, we need another search procedures that improve –
Generate procedure so that only good moves are generated.
 Test procedure so that the best move can be explored first.
Game playing is a popular application of artificial intelligence that involves the development
of computer programs to play games, such as chess, checkers, or Go. The goal of game playing
in artificial intelligence is to develop algorithms that can learn how to play games and make
decisions that will lead to winning outcomes.
1. One of the earliest examples of successful game playing AI is the chess program Deep
Blue, developed by IBM, which defeated the world champion Garry Kasparov in 1997.
Since then, AI has been applied to a wide range of games, including two-player games,
multiplayer games, and video games.
There are two main approaches to game playing in AI, rule-based systems and machine
learning-based systems.

1. Rule-based systems use a set of fixed rules to play the game.

2. Machine learning-based systems use algorithms to learn from experience and make
decisions based on that experience.

34
In recent years, machine learning-based systems have become increasingly popular, as they are
able to learn from experience and improve over time, making them well-suited for complex
games such as Go. For example, AlphaGo, developed by DeepMind, was the first machine
learning-based system to defeat a world champion in the game of Go.
Game playing in AI is an active area of research and has many practical applications, including
game development, education, and military training. By simulating game playing scenarios, AI
algorithms can be used to develop more effective decision-making systems for real-world
applications.
The most common search technique in game playing is Minimax search procedure. It is
depth-first depth-limited search procedure. It is used for games like chess and tic-tac-toe.

Minimax algorithm uses two functions –

MOVEGEN : It generates all the possible moves that can be generated from the current
position.

STATICEVALUATION : It returns a value depending upon the goodness from the viewpoint
of two-player

This algorithm is a two player game, so we call the first player as PLAYER1 and second player
as PLAYER2. The value of each node is backed-up from its children. For PLAYER1 the
backed-up value is the maximum value of its children and for PLAYER2 the backed-up value
is the minimum value of its children. It provides most promising move to PLAYER1, assuming
that the PLAYER2 has make the best move. It is a recursive algorithm, as same procedure
occurs at each level.

Figure 1: Before backing-up of values

35
Figure 2: After backing-up of values We assume that PLAYER1 will start the game.

4 levels are generated. The value to nodes H, I, J, K, L, M, N, O is provided by

STATICEVALUATION function. Level 3 is maximizing level, so all nodes of level
3 will take maximum values of their children. Level 2 is minimizing level, so all its
nodes will take minimum values of their children. This process continues. The value
of A is 23. That means A should choose C move to win.

Advantages of Game Playing in Artificial Intelligence

 Enhanced Strategic Thinking: Game-playing algorithms empower AI to strategize and

make optimal choices, improving decision-making in various scenarios.
 Adaptive Learning: Machine learning-driven approaches enable AI to learn and refine
strategies, adapting over time for better performance.
 Real-world Relevance: Strategies developed in games find applications in diverse fields,
enhancing decision-making in practical situations.
 Efficient Decision-making: Algorithms like Alpha-Beta Pruning optimize computation,
enabling AI to efficiently explore complex game scenarios.
 Benchmarking AI Progress: AI's success in games serves as a marker of advancement,
showcasing the growth of AI's strategic capabilities.

Disadvantages of Game Playing in Artificial Intelligence

 Computational Complexity: Game-playing algorithms can be computationally

intensive, limiting their real-time application in complex scenarios.

36
 Limited Generalization: Strategies developed for specific games might not readily
apply to broader real-world decision-making contexts.
 Lack of Creativity: AI's decisions are based on algorithms and past experiences, lacking
the creativity and intuition that humans possess.
 Complexity of Game Rules: Adapting game-playing algorithms to diverse games with
intricate rules can be challenging and time-consuming.
 Overfitting: In machine learning-based approaches, there's a risk of overfitting to limited
training data, leading to suboptimal decisions in novel situations.

Problem in game playing

Lack of Control

The integration of AI systems and machine learning can result in unpredictable outcomes. These
systems learn and adapt in real-time based on player behavior and other game world factors.

This makes it a challenge for developers to predict and control every aspect of the game. This
lack of control can sometimes detract from the intended gaming experience, with the AI
behaving in ways that weren’t originally intended by the creators.

Lack of Creativity

Procedural generation and generative AI tools are now frequently used for content creation in
games. These AI tools can create huge amounts of game content quickly, which may seem like a
good thing for gaming companies.

However, while procedural generation can provide endless terrains and scenarios, it might lack
the depth, nuance, and engaging gaming narratives that a human designer could offer. There’s a
risk that relying too heavily on AI for content creation can result in repetitive and less engaging
gaming experiences.

Plus, if every game design company is using the same tools, there won’t be as much variety in
video games.

Technical Issues

Aspects of game development that heavily rely on AI can introduce a host of technical problems.

For instance, while AI tools can facilitate aspects like real-time adjustments, they also demand
more from the game engine in terms of computational power. Bugs and unforeseen interactions
within advanced AI can lead to breakdowns in gameplay or even crash the entire game. Ensuring
smooth integration of AI into the gaming experience requires rigorous testing and refinement.

37
ALPHA-BETA PRUNING:
o Alpha-beta pruning is a modified version of the minimax algorithm. It is an optimization
technique for the minimax algorithm.
o As we have seen in the minimax search algorithm that the number of game states it has to
examine are exponential in depth of the tree. Since we cannot eliminate the exponent, but
we can cut it to half. Hence there is a technique by which without checking each node of
the game tree we can compute the correct minimax decision, and this technique is
called pruning. This involves two threshold parameter Alpha and beta for future
expansion, so it is called alpha-beta pruning. It is also called as Alpha-Beta Algorithm.
o Alpha-beta pruning can be applied at any depth of a tree, and sometimes it not only prune
the tree leaves but also entire sub-tree.
o The two-parameter can be defined as:
o Alpha: The best (highest-value) choice we have found so far at any point along
the path of Maximizer. The initial value of alpha is -∞.
o Beta: The best (lowest-value) choice we have found so far at any point along the
path of Minimizer. The initial value of beta is +∞.
o The Alpha-beta pruning to a standard minimax algorithm returns the same move as the
standard algorithm does, but it removes all the nodes which are not really affecting the
final decision but making algorithm slow. Hence by pruning these nodes, it makes the
algorithm fast.

Condition for Alpha-beta pruning:

The main condition which required for alpha-beta pruning is:

1. α>=β

Key points about alpha-beta pruning:

o The Max player will only update the value of alpha.
o The Min player will only update the value of beta.
o While backtracking the tree, the node values will be passed to upper nodes instead of
values of alpha and beta.
o We will only pass the alpha, beta values to the child nodes.

Pseudo-code for Alpha-beta Pruning:

1. function minimax(node, depth, alpha, beta, maximizingPlayer) is
2. if depth ==0 or node is a terminal node then
3. return static evaluation of node
4.
5. if MaximizingPlayer then // for Maximizer Player
6. maxEva= -infinity
7. for each child of node do
8. eva= minimax(child, depth-1, alpha, beta, False)

38
9. maxEva= max(maxEva, eva)
10. alpha= max(alpha, maxEva)
11. if beta<=alpha
12. break
13. return maxEva
14.
15. else // for Minimizer player
16. minEva= +infinity
17. for each child of node do
18. eva= minimax(child, depth-1, alpha, beta, true)
19. minEva= min(minEva, eva)
20. beta= min(beta, eva)
21. if beta<=alpha
22. break
23. return minEva

Working of Alpha-Beta Pruning:

Let's take an example of two-player search tree to understand the working of Alpha-beta pruning

Step 1: At the first step the, Max player will start first move from node A where α= -∞ and β= +∞,
these value of alpha and beta passed down to node B where again α= -∞ and β= +∞, and Node B
passes the same value to its child D.

Step 2: At Node D, the value of α will be calculated as its turn for Max. The value of α is compared
with firstly 2 and then 3, and the max (2, 3) = 3 will be the value of α at node D and node value will
also 3.

Step 3: Now algorithm backtrack to node B, where the value of β will change as this is a turn of Min,
Now β= +∞, will compare with the available subsequent nodes value, i.e. min (∞, 3) = 3, hence at
node B now α= -∞, and β= 3.

39
In the next step, algorithm traverse the next successor of Node B which is node E, and the values of
α= -∞, and β= 3 will also be passed.

Step 4: At node E, Max will take its turn, and the value of alpha will change. The current value of
alpha will be compared with 5, so max (-∞, 5) = 5, hence at node E α= 5 and β= 3, where α>=β, so
the right successor of E will be pruned, and algorithm will not traverse it, and the value at node E
will be 5.

Step 5: At next step, algorithm again backtrack the tree, from node B to node A. At node A, the
value of alpha will be changed the maximum available value is 3 as max (-∞, 3)= 3, and β= +∞, these
two values now passes to right successor of A which is Node C.

At node C, α=3 and β= +∞, and the same values will be passed on to node F.

40
Step 6: At node F, again the value of α will be compared with left child which is 0, and max(3,0)= 3,
and then compared with right child which is 1, and max(3,1)= 3 still α remains 3, but the node value
of F will become 1.

Step 7: Node F returns the node value 1 to node C, at C α= 3 and β= +∞, here the value of beta will
be changed, it will compare with 1 so min (∞, 1) = 1. Now at C, α=3 and β= 1, and again it satisfies
the condition α>=β, so the next child of C which is G will be pruned, and the algorithm will not
compute the entire sub-tree G.

Step 8: C now returns the value of 1 to A here the best value for A is max (3, 1) = 3. Following is the
final game tree which is the showing the nodes which are computed and nodes which has never
computed. Hence the optimal value for the maximizer is 3 for this example.

41
Move Ordering in Alpha-Beta pruning:
The effectiveness of alpha-beta pruning is highly dependent on the order in which each node is
examined. Move order is an important aspect of alpha-beta pruning.

It can be of two types:

o Worst ordering: In some cases, alpha-beta pruning algorithm does not prune any of the
leaves of the tree, and works exactly as minimax algorithm. In this case, it also consumes
more time because of alpha-beta factors, such a move of pruning is called worst ordering.
In this case, the best move occurs on the right side of the tree. The time complexity for
such an order is O(bm).
o Ideal ordering: The ideal ordering for alpha-beta pruning occurs when lots of pruning
happens in the tree, and best moves occur at the left side of the tree. We apply DFS hence
it first search left of the tree and go deep twice as minimax algorithm in the same amount
of time. Complexity in ideal ordering is O(bm/2).

Rules to find good ordering:

Following are some rules to find good ordering in alpha-beta pruning:

o Occur the best move from the shallowest node.

o Order the nodes in the tree such that the best nodes are checked first.
o Use domain knowledge while finding the best move. Ex: for Chess, try order: captures
first, then threats, then forward moves, backward moves.
o We can bookkeep the states, as there is a possibility that states may repeat.

EVALUATION FUNCTIONS
As seen in the MIN MAX algorithm, each leaf node had a value associated with it. We had
stored this value in an array. But in the real world when we are creating a program to play Tic-
Tac-Toe, Chess, Backgammon, etc. we need to implement a function that calculates the value
of the board depending on the placement of pieces on the board. This function is often known

42
as Evaluation Function. It is sometimes also called a Heuristic Function.
The evaluation function is unique for every type of game. In this post, the evaluation function
for the game Tic-Tac-Toe is discussed. The basic idea behind the evaluation function is to give
a high value for a board if the maximizer turn or a low value for the board if
the minimizer turn.
For this scenario let us consider X as the maximizer and O as the minimizer.
Let us build our evaluation function :
 If X wins on the board we give it a positive value of +10.

 If O wins on the board we give it a negative value of -10.

 If no one has won or the game results in a draw then we give a value of +0.

We could have chosen any positive/negative. For the sake of simplicity, we chose 10 and
shall use lowercase ‘x’ and lowercase ‘o’ to represent the players and an underscore ‘_’ to
represent a blank space on the board.
If we represent our board as a 3×3 2D character matrix, like char board[3][3]; then we have
to check each row, each column, and the diagonals to check if either of the players has
gotten 3 in a row.

Time Complexity: O(max(row,col))

Auxiliary Space: O(1)
The idea of this article is to understand how to write a simple evaluation function for the game
Tic-Tac-Toe. In the next article we shall see how to combine this evaluation function with the
minimax function

43
ASSIGNMENT-2

SHORT ANSWER QUESTIONS

1. write a short note on searching for solutions

2. Briefly describe about Depth first search.
3. write a short note on Breadth first search.
4. Briefly describe about Hill climbing.
5. write a short note on problem reduction.
6. Briefly describe about problem in game playing.

LONG ANSWER QUESTIONS

1. Explain about uniformed search strategies in detail.

2. Explain in depth about search with partial information (Heuristic search).
3. Explain in depth about A*, AO* algorithms.
4. Explain about game playing, adversial search in detail.
5. Explain in depth about mini-max algorithm.
6. Explain about optimal decisions in multiplayer games in detail.
7. Explain in depth about Alpha-Beta pruning.
8. Explain about Evaluation functions in detail.

44