AI algorithms with alpha beta stratagy 1

very good ppt

1. 1RCS702/Unit-2
Subject Name:-Artificial Intelligence
Subject Code:-RCS702
Unit No.:-2
Lecture No.:-6
Topic Name :-Alpha-Beta Algorithm
Er. Hiresh Kumar Gupta
Department of CSE

2. Content
1.Alpha-Beta Pruning
2.Condition for alpha-beta pruning
3.Pseudo-code for Alpha-beta Pruning
4.Working of Alpha-Beta Pruning
5.Example
6.Important Questions
RCS702/Unit-2 2

3. Alpha-Beta Pruning
•Alpha-betapruningisamodifiedversionoftheminimaxalgorithm.It
isanoptimizationtechniquefortheminimaxalgorithm.
•Aswehaveseenintheminimaxsearchalgorithmthatthenumberof
gamestatesithastoexamineareexponentialindepthofthetree.Since
wecannoteliminatetheexponent,butwecancutittohalf.Hencethere
isatechniquebywhichwithoutcheckingeachnodeofthegametree
wecancomputethecorrectminimaxdecision,andthistechniqueis
calledpruning.ThisinvolvestwothresholdparameterAlphaandbeta
forfutureexpansion,soitiscalledalpha-betapruning.Itisalso
calledasAlpha-BetaAlgorithm.
•Alpha-betapruningcanbeappliedatanydepthofatree,and
sometimesitnotonlyprunethetreeleavesbutalsoentiresub-tree.
3RCS702/Unit-2

4. •Thetwo-parametercanbedefinedas:
–Alpha:Thebest(highest-value)choicewehavefoundsofarat
anypointalongthepathofMaximizer.Theinitialvalueofalpha
is-∞.
–Beta:Thebest(lowest-value)choicewehavefoundsofaratany
pointalongthepathofMinimizer.Theinitialvalueofbeta
is+∞.
•TheAlpha-betapruningtoastandardminimaxalgorithm
returnsthesamemoveasthestandardalgorithmdoes,butit
removesallthenodeswhicharenotreallyaffectingthe
finaldecisionbutmakingalgorithmslow.Hencebypruning
thesenodes,itmakesthealgorithmfast.
4RCS702/Unit-2

5. Condition for Alpha-beta pruning
•Themainconditionwhichrequiredforalpha-betapruning
is:
α>=β
•TheMaxplayerwillonlyupdatethevalueofalpha.
•TheMinplayerwillonlyupdatethevalueofbeta.
•Whilebacktrackingthetree,thenodevalueswillbepassed
touppernodesinsteadofvaluesofalphaandbeta.
•Wewillonlypassthealpha,betavaluestothechildnodes.
5RCS702/Unit-2

6. Pseudo-code for Alpha-beta Pruning
functionminimax(node,depth,alpha,beta,maximizingPlayer)is
ifdepth==0ornodeisaterminalnodethen
returnstaticevaluationofnode
ifMaximizingPlayerthen//forMaximizerPlayer
maxEva=-infinity
foreachchildofnodedo
eva=minimax(child,depth-1,alpha,beta,False)
maxEva=max(maxEva,eva)
alpha=max(alpha,maxEva)
ifbeta<=alpha
6RCS702/Unit-2

7. break
returnmaxEva
else //forMinimizerplayer
minEva=+infinity
foreachchildofnodedo
eva=minimax(child,depth-1,alpha,beta,true)
minEva=min(minEva,eva)
beta=min(beta,eva)
ifbeta<=alpha
break
returnminEva
7RCS702/Unit-2

8. Working of Alpha-Beta Pruning
Let'stakeanexampleoftwo-playersearchtreeto
understandtheworkingofAlpha-betapruning:
•Step1:Atthefirststepthe,Maxplayerwillstart
firstmovefromnodeAwhereα=-∞andβ=+∞,
thesevalueofalphaandbetapasseddowntonode
Bwhereagainα=-∞andβ=+∞,andNodeB
passesthesamevaluetoitschildD.
8RCS702/Unit-2

9. 9RCS702/Unit-2

10. •Step2:AtNodeD,thevalueofαwillbe
calculatedasitsturnforMax.Thevalueofαis
comparedwithfirstly2andthen3,andthemax
(2,3)=3willbethevalueofαatnodeDand
nodevaluewillalso3.
•Step3:NowalgorithmbacktracktonodeB,
wherethevalueofβwillchangeasthisisaturn
ofMin,Nowβ=+∞,willcomparewiththe
availablesubsequentnodesvalue,i.e.min(∞,3)
=3,henceatnodeBnowα=-∞,andβ=3.
10RCS702/Unit-2

11. 11RCS702/Unit-2

12. •Inthenextstep,algorithmtraversethenextsuccessor
ofNodeBwhichisnodeE,andthevaluesofα=-∞,
andβ=3willalsobepassed.
•Step4:AtnodeE,Maxwilltakeitsturn,andthevalue
ofalphawillchange.Thecurrentvalueofalphawillbe
comparedwith5,somax(-∞,5)=5,henceatnodeE
α=5andβ=3,whereα>=β,sotherightsuccessorofE
willbepruned,andalgorithmwillnottraverseit,and
thevalueatnodeEwillbe5.
12RCS702/Unit-2

13. 13RCS702/Unit-2

14. •Step5:Atnextstep,algorithmagainbacktrackthetree,
fromnodeBtonodeA.AtnodeA,thevalueofalphawill
bechangedthemaximumavailablevalueis3asmax(-∞,
3)=3,andβ=+∞,thesetwovaluesnowpassestoright
successorofAwhichisNodeC.
•AtnodeC,α=3andβ=+∞,andthesamevalueswillbe
passedontonodeF.
•Step6:AtnodeF,againthevalueofαwillbecompared
withleftchildwhichis0,andmax(3,0)=3,andthen
comparedwithrightchildwhichis1,andmax(3,1)=3still
αremains3,butthenodevalueofFwillbecome1.
14RCS702/Unit-2

15. 15RCS702/Unit-2

16. •Step7:NodeFreturnsthenodevalue1to
nodeC,atCα=3andβ=+∞,herethevalueof
betawillbechanged,itwillcomparewith1so
min(∞,1)=1.NowatC,α=3andβ=1,and
againitsatisfiestheconditionα>=β,sothe
nextchildofCwhichisGwillbepruned,and
thealgorithmwillnotcomputetheentiresub-
treeG.
16RCS702/Unit-2

17. 17RCS702/Unit-2

18. •Step8:Cnowreturnsthevalueof1toAhere
thebestvalueforAismax(3,1)=3.
Followingisthefinalgametreewhichisthe
showingthenodeswhicharecomputedand
nodeswhichhasnevercomputed.Hencethe
optimalvalueforthemaximizeris3forthis
example.
18RCS702/Unit-2

19. 19RCS702/Unit-2

20. Move Ordering in Alpha-Beta pruning
Theeffectivenessofalpha-betapruningishighlydependenton
theorderinwhicheachnodeisexamined.Moveorderisan
importantaspectofalpha-betapruning.Itcanbeoftwotypes:
•Worstordering:Insomecases,alpha-betapruningalgorithm
doesnotpruneanyoftheleavesofthetree,andworksexactly
asminimaxalgorithm.Inthiscase,italsoconsumesmoretime
becauseofalpha-betafactors,suchamoveofpruningiscalled
worstordering.Inthiscase,thebestmoveoccursontheright
sideofthetree.Thetimecomplexityforsuchanorderis
O(b
m
).
20RCS702/Unit-2

21. •Idealordering:Theidealorderingforalpha-
betapruningoccurswhenlotsofpruning
happensinthetree,andbestmovesoccurat
theleftsideofthetree.WeapplyDFShenceit
firstsearchleftofthetreeandgodeeptwiceas
minimaxalgorithminthesameamountof
time.ComplexityinidealorderingisO(b
m/2
).
21RCS702/Unit-2

22. Example
RCS702/Unit-2 22

23. Important Questions
Solved following question by alpha-beta pruning
method-
1. 2.
RCS702/Unit-2 23

24. 3.
RCS702/Unit-2 24

25. References
Text Book:
Stuart Russell, Peter Norvig, “Artificial Intelligence –A Modern Approach”,
Pearson Education
Reference Book:
Elaine Rich and Kevin Knight, “Artificial Intelligence”, McGraw-Hill
Other:
https://www.javatpoint.com/ai-alpha-beta-pruning
https://www.mygreatlearning.com/blog/alpha-beta-pruning-in-ai/
https://www.geeksforgeeks.org/minimax-algorithm-in-game-theory-set-4-alpha-beta-pruning/
25RCS702/Unit-2

26. Thank You
26RCS702/Unit-2