I. Mini-Max Algorithm 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:
I. Mini-Max Algorithm in AI
Jagdamba Education Society's
SND College of Engineering & Research Centre
Department of Computer Engineering
SUBJECT: Artificial Intelligence & Robotics
Lecture No-15
Prof.Dhakane Vikas N

2. Mini-Max Algorithm in AI
Mini-maxalgorithmisarecursiveor
backtrackingalgorithmwhichisusedin
decision-makingandgametheory.
Itprovidesanoptimalmovefortheplayer
assumingthatopponentisalsoplaying
optimally.
Mini-Maxalgorithmusesrecursiontosearch
throughthegame-tree.
Min-Maxalgorithmismostlyusedforgame
playinginAI.SuchasChess,Checkers,tic-tac-
toe,go,andvarioustow-playersgame.This
Algorithmcomputestheminimaxdecisionfor
thecurrentstate.

3. Mini-Max Algorithm in AI
Inthisalgorithmtwoplayersplaythegame,one
iscalledMAXandotheriscalledMIN.
Boththeplayersfightitastheopponentplayer
BothPlayersofthegameareopponentofeach
other,whereMAXwillselectthemaximizedvalue
andMINwillselecttheminimizedvalue.
Theminimaxalgorithmperformsadepth-first
searchalgorithmfortheexplorationofthe
completegametree.
Theminimaxalgorithmproceedsalltheway
downtotheterminalnodeofthetree,then
backtrackthetreeastherecursion.

4. Working of Min-Max Algorithm:
Theworkingoftheminimaxalgorithmcanbeeasily
describedusinganexample.Belowwehavetakenan
exampleofgame-treewhichisrepresentingthetwo-
playergame.
Inthisexample,therearetwoplayersoneiscalled
MaximizerandotheriscalledMinimizer.
MaximizerwilltrytogettheMaximumpossible
score,andMinimizerwilltrytogettheminimum
possiblescore.

5. Working of Min-Max Algorithm:
ThisalgorithmappliesDFS,sointhisgame-tree,we
havetogoallthewaythroughtheleavestoreach
theterminalnodes.
Attheterminalnode,theterminalvaluesaregiven
sowewillcomparethosevalueandbacktrackthe
treeuntiltheinitialstateoccurs.
Followingarethemainstepsinvolvedinsolvingthe
two-playergametree:

6. Working of Min-Max Algorithm:
Followingarethemainsteps
involvedinsolvingthetwo-player
gametree:
Step-1:Inthefirststep,the
algorithmgeneratestheentire
game-treeandapplytheutility
functiontogettheutilityvalues
fortheterminalstates.
Inthebelowtreediagram,let's
takeAistheinitialstateofthe
tree.
Supposemaximizertakesfirst
turnwhichhasworst-caseinitial
value=-infinity,andminimizer
willtakenextturnwhichhas
worst-caseinitialvalue=
+infinity.

7. Working of Min-Max Algorithm:
Step2:Now,firstwefindtheutilitiesvaluefor
theMaximizer,itsinitialvalueis-∞,sowewill
compareeachvalueinterminalstatewithinitial
valueofMaximizeranddeterminesthehigher
nodesvalues.
Itwillfindthemaximumamongtheall.
FornodeD max(-1,--∞)=>max(-1,4)=4
ForNodeE max(2,-∞)=>max(2,6)=6
ForNodeF max(-3,-∞)=>max(-3,-5)=-3
FornodeG max(0,-∞)=max(0,7)=7

8. Working of Min-Max Algorithm:
Step3:Inthenextstep,it'saturn
forminimizer,soitwillcompare
allnodesvaluewith+∞,andwill
findthe3rdlayernodevalues.
FornodeB=min(4,6)=4
FornodeC=min(-3,7)=-3

9. Working of Min-Max Algorithm:
Step4:
Nowit'saturnforMaximizer,andit
willagainchoosethemaximumofall
nodesvalueandfindthemaximum
valuefortherootnode.
Inthisgametree,thereareonly4
layers,hencewereachimmediately
totherootnode,butinrealgames,
therewillbemorethan4layers.
FornodeAmax(4,-3)=4

10. Properties of Mini-Max algorithm
Complete-Min-MaxalgorithmisComplete.Itwilldefinitelyfinda
solution(ifexist),inthefinitesearchtree.
Optimal-Min-Maxalgorithmisoptimalifbothopponentsareplaying
optimally.
Timecomplexity-AsitperformsDFSforthegame-tree,sothetime
complexityofMin-MaxalgorithmisO(bm),wherebisbranchingfactor
ofthegame-tree,andmisthemaximumdepthofthetree.
SpaceComplexity-SpacecomplexityofMini-maxalgorithmisalso
similartoDFSwhichisO(bm).

11. Limitation of the minimax Algorithm
Themaindrawbackoftheminimaxalgorithmisthatitgetsreallyslow
forcomplexgamessuchasChess,go,etc.Thistypeofgameshasahuge
branchingfactor,andtheplayerhaslotsofchoicestodecide.
Thislimitationoftheminimaxalgorithmcanbeimprovedfromalpha-
betapruningwhichwehavediscussedinthenexttopic.

12. Alpha-Beta Pruning in ai
Alpha-betapruningisamodifiedversionoftheminimaxalgorithm.Itis
anoptimizationtechniquefortheminimaxalgorithm.
Aswehaveseenintheminimaxsearchalgorithmthatthenumberof
gamestatesithastoexamineareexponentialindepthofthetree.Since
wecannoteliminatetheexponent,butwecancutittohalf.
Hencethereisatechniquebywhichwithoutcheckingeachnodeofthe
gametreewecancomputethecorrectminimaxdecision,andthis
techniqueiscalledpruning.
ThisinvolvestwothresholdparameterAlphaandbetaforfuture
expansion,soitiscalledalpha-betapruning.ItisalsocalledasAlpha-Beta
Algorithm.
Alpha-betapruningcanbeappliedatanydepthofatree,andsometimesit
notonlyprunethetreeleavesbutalsoentiresub-tree.

13. Alpha-Beta Pruning in ai
Thetwo-parametercanbedefinedas:
Alpha:Thebest(highest-value)choicewehavefoundsofaratanypoint
alongthepathofMaximizer.Theinitialvalueofalphais-∞.
Beta:Thebest(lowest-value)choicewehavefoundsofaratanypoint
alongthepathofMinimizer.Theinitialvalueofbetais+∞.
TheAlpha-betapruningtoastandardminimaxalgorithmreturnsthe
samemoveasthestandardalgorithmdoes,butitremovesallthenodes
whicharenotreallyaffectingthefinaldecisionbutmakingalgorithm
slow.
Hencebypruningthesenodes,itmakesthealgorithmfast.

14. Alpha-Beta Pruning in ai
ConditionforAlpha-betapruning:
Themainconditionwhichrequiredforalpha-betapruningis:
α>=β
Keypointsaboutalpha-betapruning:
TheMaxplayerwillonlyupdatethevalueofalpha.
TheMinplayerwillonlyupdatethevalueofbeta.
Whilebacktrackingthetree,thenodevalueswillbepassedtouppernodes
insteadofvaluesofalphaandbeta.
Wewillonlypassthealpha,betavaluestothechildnodes.

15. Working of Alpha -Beta Pruning:
Working ofAlpha-Beta
Pruning:
Let'stakeanexampleoftwo-player
searchtreetounderstandthe
workingofAlpha-betapruning
Step1:
Atthefirststepthe,Maxplayer
willstartfirstmovefromnodeA
whereα=-∞andβ=+∞,these
valueofalphaandbetapassed
downtonodeBwhereagainα=-∞
andβ=+∞,andNodeBpassesthe
samevaluetoitschildD.

16. Working of Alpha -Beta Pruning:
Step2:
AtNodeD,thevalueofαwillbecalculated
asitsturnforMax.
Thevalueofαiscomparedwithfirstly2
andthen3,andthemax(2,3)=3willbe
thevalueofαatnodeDandnodevaluewill
also3.
Step3:
NowalgorithmbacktracktonodeB,where
thevalueofβwillchangeasthisisaturn
ofMin,Nowβ=+∞,willcomparewiththe
availablesubsequentnodesvalue,i.e.min
(∞,3)=3,henceatnodeBnowα=-∞,and
β=3.
Inthenextstep,algorithmtraversethe
nextsuccessorofNodeBwhichisnodeE,
andthevaluesofα=-∞,andβ=3willalso
bepassed.

17. Working of Alpha -Beta Pruning:
Step4:
AtnodeE,Maxwilltakeitsturn,
andthevalueofalphawillchange.
Thecurrentvalueofalphawillbe
comparedwith5,somax(-∞,5)=
5,henceatnodeEα=5andβ=3,
whereα>=β,sotheright
successorofEwillbepruned,and
algorithmwillnottraverseit,and
thevalueatnodeEwillbe5.

18. Working of Alpha -Beta Pruning:
Step5:
Atnextstep,algorithmagain
backtrackthetree,fromnodeBto
nodeA.
AtnodeA,thevalueofalphawill
bechangedthemaximum
availablevalueis3asmax(-∞,
3)=3,andβ=+∞,thesetwo
valuesnowpassestoright
successorofAwhichisNodeC.
AtnodeC,α=3andβ=+∞,andthe
samevalueswillbepassedontonode
F.

19. Working of Alpha -Beta Pruning:
Step6:
AtnodeF,againthevalueofα
willbecomparedwithleftchild
whichis0,andmax(3,0)=3,and
thencomparedwithrightchild
whichis1,andmax(3,1)=3stillα
remains3,butthenodevalueofF
willbecome1.

20. Working of Alpha -Beta Pruning:
Step7:
NodeFreturnsthenodevalue1to
nodeC,atCα=3andβ=+∞,here
thevalueofbetawillbechanged,
itwillcomparewith1somin(∞,
1)=1.
NowatC,α=3andβ=1,andagain
itsatisfiestheconditionα>=β,so
thenextchildofCwhichisGwill
bepruned,andthealgorithmwill
notcomputetheentiresub-treeG.

21. Working of Alpha -Beta Pruning:
Step8:
Step8:Cnowreturnsthevalueof
1toAherethebestvalueforAis
max(3,1)=3.
Followingisthefinalgametree
whichistheshowingthenodes
whicharecomputedandnodes
whichhasnevercomputed.
Hencetheoptimalvalueforthe
maximizeris3forthisexample.