人工智能项目

PAGE

10

AICourseProjectDocument:ArtificialIntelligence-BasedConnect4PlayerUsingPython

Doneby:AbdalazizSawwanMay.05.2021

Supervisedby:Dr.PeiWang

Contents

Introduction 3

TheoreticalAnalysis 4

RelatedWork 5

TheGeneralEmployedAITechniques 5

TheMinimaxAlgorithm 5

TheAlpha-BetaPruningAlgorithm 8

TheUtility-FunctionHeuristicEvaluator 10

TheImplementation 13

TheBasicPanelandItsUser-FriendlyInterface 13

TheImplementationoftheAIAgentandSomeOtherPartsof

theCode 15

TheEfficiencyoftheAIModel 16

Conclusion,PersonalComments,andFinalThoughts 18

References 18

Introduction

ConnectFourisaboardgamethatisplayedbyexactlytwoplayers,playersinitareassignedtodifferentcolorsandthentaketurnsdroppingcoloreddiscsintothesuspendedgrid.Thegame’sgridhassevencolumnsandsixrows.Thepiecesfallstraightdown,occupyingthelowestavailablespace.Figure1illustratesthegamepanel.

Figure1:Anillustrationofthegamepanel(Sourcein[1].)

Themaingoalofthegameistobethefirstplayertohaveeitherhorizontal,vertical,ordiagonallineoffoursame-coloreddiscs.ItiswellknownthatConnectFourisasolvedgame,i.e.thereisaspecificknownstrategybywhichthefirstplayercanalwayswinbyplayingthecorrectplays.Hence,inthisproject,wetrytoplay“semi-perfectly”againsttheAIandobservetheresults.

Furthermore,unlikemostofthecardgames,ConnectFourdoesprovidefullinformation,wherewhenaplayeratatimeplays,allthetwoplayersgetalltheinformationregardingmovesthathavedeterministicallyalreadytakenplaceandregardingallmovesthatcantakeplaceforthenextstep,inagivengamestate.ThismakesimplementinganAIplayerofthegamemorefeasibleforthepurposeofthisproject.

Theprojectincludesfirst,implementingthegameenvironmentitselfinasuitableanduser-friendlyway,andsecond,animplantationofanAIplayerwhowecanconfigureitsparametersandhardness.Finally,ageneralevaluationoftheAIispresented.

TheoreticalAnalysis

Startingfromthestandardgame,wewillhaveapanelof6×7=42locations,eachlocationhasthreepossiblestatesthatcanhave;beingempty,havingthediscofthefirstplayer,orhavingthediscofthesecondplayer.Thatwoulddirectlygivearoughupper-boundof342≈1.1×1020possiblegamesituationsthatthesearchspaceofthegamemayhave.

However,wecancomputeamoreaccurateandtightupperboundofthepossiblesituationsbyevaluatingthesequenceofpossiblegamescorrespondingtoaspecificnumberofdiscsplayedsofar,andthen,justsumminguptheelementsofthissequenceofnumbers.

Thissequenceofpossiblesituationsafteranumberofturnswillstartfromzerosituationsafterzeroturns,thensevensituationsafteroneturn(thefirstplayerhassevenpossiblepositionstoplacetheirdiscon),then7×7=49positionsafterthesecondturn.

Afterthesecondturn,itbecomesalittlebittrickier,calculatingthenumberofpossiblesituationsafterthreeturnsisnottrivial;thenumberofpossible

situations at that point will be

7×7×1+7×6×

5+7×6×2=238

2

situations.Whichisderivedafterconsideringthatinsomescenarios,differentordersofplacingthediscsofthefirstplayermayproducethesamesituationofthegame.Here,weconsiderallthecases.

Thewholesequenceofpossiblesituationsafteraspecificnumberofturns,andstartingfromzeroisgivenbythefollowingsequence:1,7,49,238,1120,4263,16422,54859,184275,…[2].

Aftercalculatingthenumberofsituationsafterconsideringall42possibleturnsaswellastheaeroturn,wewillendupwithatotalnumberofsituationsthatisaround4.5×1012situations.

Forausualboardgame,anorderoftrillionsofpossiblestatesinthesearchspaceisrelativelyintoolarge(likethesearchspaceinChessorGoboardgames),anditisnottoolowthatasimplebrute-forcealgorithmthatexhaustsallthesituationsisfeasiblealonetodothat.ThisprovesthatourchoicetoconsiderthisgamespecificallywasagoodchoicebecauseimplementinganAI

agentthatdoesnottriviallyexhaustsallthepossiblescenarioswouldbeusefulinordertoplayagainstinthisgame.

RelatedWork

Tommyetal.[3]havedemonstratedthatasuitableoptimalAIalgorithmisstillunknownfortheConnectFourgame,theyappliedtwodifferentAIalgorithms;onethatmainlyutilizesthealpha-betapruningalgorithm,andoneutilizestheMTD(f)Algorithm(Memory-enhancedTestDriverAlgorithm).

Theyconsiderintheirresearchtheoptimality,whichisthewinningpercentageingeneral,thespeed,whichisrelatedtotheexecutiontime,andfinallythenumberofleafnodes.TheirresultsstatethattheirAImodelswininlessthan50%ofgameswithareasonableexecutiontime.

Sarhanetal.[4]havepresentedadesignthatconvertsthestandardConnectFourgameintoareal-timegamebyincorporatingtimerestrains.Theyhavedesignedtheirartificialintelligencemodelbasedoninfluencemapping.Intheirwork,awaterfall-basedAIsoftwarehasbeendevelopedforthegame.TheirmainresultwastosuccessfullydesigntheirsoftwareusingC++programminglanguage.

Finally,Galli[5],whoisaprominentonlineinstructivevideosmakeraboutdifferenttopicsincomputersciencehasdiscussedanimplementationofanAImodelfortheConnectFourproblemandtheimplementationofthegameitself.Inourprojecthere,weinsomeinstances,usesimilartechniquesthatareusedinhislectures.Thisisbecauseoftheirrelatively-highefficiency.

TheGeneralEmployedAITechniques

Inthissection,wedemonstrateabriefsummaryofthetheoryinofthemaintechniquesusedinourAImodelforthisproject.

TheMinimaxAlgorithm

WeimplementanAIthatmainlyemploystheminimaxalgorithmthatwehavelearnedintheclass.Thealgorithmissimplyimplementedbymakingtheplayerstrytooptimizesomeutilityfunctionthattheyhave.

Oneplayerwilltrytomaximizetheirutilityfunction,whichwewillcallthemaximizingplayer.Andtheotherplayerwilltrytominimizetheirutilityfunction,whichwewillcalltheminimizingplayer.

Wecanchoosetheutilityfunctionsforeachplayertobethecomplementoftheother,sothat,wewouldhaveazero-sumgamethatiseasierandmorefeasibletobeimplementedusingminimaxalgorithm.Figure2showsthealgorithmfromagame-theoreticperspective.

Figure2:Gametheoreticperspectiveoftheminimaxobjectivefunction.(Source[6].)

Fortheexactwaythealgorithmworks,itisbettertoillustrateusinganexample;considerthesimpleexampleinFigure3.

Figure3:Asimpleexamplefortheminimaxalgorithm(Source[7].)

Here,weconsiderasimplegamewithasimplecasewherethereareeightpossiblefinalsituationsofthegame,whereeachoneisassignedtoautilityfunctionthatthefirstplayer(thewhiteplayer)triedtomaximize,andthesecondplayer(theblackplayertriedtominimize.)

Thealgorithmevaluateseachleafnodeusingaheuristicevaluationfunctionthatwecalltheutilityfunction,obtainingthevaluesshown.Themoveswherethemaximizingplayerhasadvantageareassignedwithpositivenumbers,whilethemovesthatleadtoasituationwheretheminimizingplayerhasadvantageareassignedwithnegativenumbers.Asmuchthemagnitudesofthenumbersbecomelarger,asmuchtheadvantageprevailstowardsoneside.ApseudocodeofthealgorithmisprovidedinFigure4.

Figure4:Pseudocodefortheminimaxalgorithm(Source[7].)

InourConnectFourcase,thesearchtreegrowsexponentiallywithabaseofnearlyseven,thismakesitverycomputationallyexpensivetomakeouralgorithmexplorethetreeuntilitreachesthelastleafnodes.Hence,thenewideainsectionIV.IIisintroduced.

TheAlpha-BetaPruningAlgorithm

Asclearfromourpreviousanalysisoftheminimaxalgorithm,itwouldbeverycomputationallyexpensivetosearchthroughthewholedepthofthetreebecauseoftheexponentially-increasingnumberofleafs.Henceaveryfeasiblewaytoreducethesearchspaceisbytrimmingapartofthetreeofthepossiblesituationsofthegame.

Alpha–BetaPruningcanbeconsideredasageneralsearchalgorithmwhichhasanobjectiveofminimizingthenumberofexplorednodesthathaveutility-functionvaluescalculatedbythemainheuristicfunctionevaluatorthatisemployedintheminimaxalgorithm.

Alpha-BetaPruningalgorithmisanadversarialsearchalgorithmthatisusuallyemployedtoimplementanagentplayingtwo-playergame,whichmakesitaverygreatfitforthepurposeofimplementingandAIfortheConnectFourboardgame.

Theideabehindthealgorithmisthatitterminatedtheevaluationoftheutilityfunctionvaluesofthenodeswhenatleastonepossibilitygetsfoundthatprovesthattheplayininquiryisnotbetterthanaplaythathasalreadybeenpreviouslyexamined.Suchplaysdonotneedtohavetheirutilityfunctionvaluescalculatedfurther.

WhenappliedtheAlpha-BetaPruningalgorithmonastandardminimaxsearchtree,itreturnsaresultofthesamemoveastheminimaxwouldreturnwithoutapplyingthealgorithm,butanewtrimmedtreewillbeconsideredthathassomebranches,whichareimpossibletopossiblyaffectthefinaldecisionofthealgorithm,cutout.Hence,amoretractableproblemwillbeconsideredratherthanthemaincomputationally-expensiveoriginalone.Figure5depictsanexampleofanapplicationfortheAlpha-BetaPruningalgorithm.

Figure5:Asimpleexampleforthealpha-betapruningalgorithm(Source[7].)

InFigure5,anexamplewhereitisnotimportanttocalculatetheutilityfunctionofthreepossiblesituationsoutofeightbecause,afterwehaveevaluatedtheotherfivealready,webecamesurethatwhatevervaluesthose

leafsmayhave,thatwillnotaffectthefinalresultofthemainminimaxalgorithminanyway.

Wecaneasilyobservethat,whenlookingattheleftsubtree,whateverthevalueofthefourthleafisassigned,theweightnodeaboveitwillnoteverhaveavaluelessthanfive.Thismeanssurelythattheblacknodeaboveitwillinheritthevaluefromtheleftchild,whichhasavalueofthree,insteadofinheritingitfromthechildontheright,whichwillnothaveavaluelessthanthree,letalonefive.Thesameexactprincipleisappliedontherightsubtreethatgetsmorenodestrimmedatonceaftertheinformationofthefirstfiveleafshavealreadybeendiscovered.

Figure6showsthepseudocodeofthestandardalpha-betapruningalgorithmappliedtotheminimaxalgorithm.

Figure6:PseudocodefortheAlpha-BetaPruningalgorithm(Source[7].)

TheUtility-FunctionHeuristicEvaluator

Determiningtheutilityfunction,orthefunction’svalueevaluator,isthehardestpartofthesolutionforthegamebecauseofitsheuristicnature.This

majorhindrancecouldhavebeenavoidedifwecanefficientlyreachtheendnodes(i.e.,theleafs).Inthiscase,wewouldjustassigntheendnodestoeither

+∞or−∞dependingonwhowinsonthoseendleafs.

However,inourcasehere,wehavetohavesomekindofheuristicevaluationofwhoseadvantagesomestateofthegameis,andinwhatdegreeroughlyitisadvantageous(ordisadvantageous).Hence,constructingtheheuristicutility-functionhassomedegreeofarbitrariness.

IntheimplementationofourAI,Istartedfirstlyconsideringthenumberofdiscsofeachcolorwithinaspecificdomain(a4×4windowinthiscasehere)thatmayenduptoformawinningsituation,whetherbylyingdownhorizontally,vertically,ordiagonally.

Furthermore,averygreatadditiontothisheuristicfunctionthatIhavedonewasmadebydistinguishingthemiddlecolumnandgivingitmoreadvantageoverothercolumns.Thisadditionhasanotherbenefittoo,whichisbreakingtheinitialsymmetrythatwehaveinthestartofthegame.Thatisit,whenevertheAIstartswiththefirstturn,itchoosesthemiddlecolumnalways,anditgivesthemiddlecolumnmoreadvantageoverothercolumns.

Now,considerFigure7next:

Figure7:Theprimitiveheuristicutilityfunctiontoevaluatethescoreofaboard.

Thisismymainchosenwaytocalculatetheutilityfunction.Asclearfromthecode,whenthecountofthenumberoftheplayer’sdiscswithinacertaingivendomainofspacestobeconsidered(ourcertaindomainhereisthe4×4gridaroundtheaddeddisc.)

Ouraffectingpartsandtheirdegreesarechosenasfollowing:

Youget+99999pointsofutilitywheneveryourdiscinyourhandcompletesacountofexactlyfourdiscsofyourswithintheconsidereddomain,whichis4×4gridinthiscase(i.e.,afterperformingawinningsituation.)

Youget+5pointsofutilitywheneveryourdiscinyourhandcompletesacountofexactlythreediscsofyoursandoneemptyspacewithintheconsidereddomain,whichis4×4gridinthiscase.

Youget+2pointsofutilitywheneveryourdiscinyourhandcompletesacountofexactlytwodiscsofyoursandtwoemptyspaceswithintheconsidereddomain,whichis4×4gridinthiscase.

Youget−999pointsofutilitywheneveryourdiscinyourhandleavesbehinditacountofexactlythreediscsofyouropponent’sandoneemptyspaceswithintheconsidereddomain,whichis4×4gridinthiscase.

Thefactorinarbitrarinessinourchoicesisapparentinthechoiceoftheexactvaluesandintheexactscenarios.However,theexperimentalresultsshowninsectionVIverifythattheyareacceptabletosomeextent.

Furthermore,wedidnothavetoconsidermoreinvolvedcasesandassignvaluestothem,likeforexampleconsidering5×5gridsofdomainwithmorecasessothattheheuristicfunctionbecomesmoresophisticated.

Ourchoiceto+99999pointsofutilityisobvioustobehappeningincasethatthemoveisawinningmove,andthechoiceof−999pointsofutilityistooobvioustobehappeningincasethatthemoveisalosingmove(i.e.,theopponentcanwininasinglemoveafterit.)Inthesametime,itisimportanttomaketheAIpreferplayingawinningmoveoveravoidingalosingmove.Thisiswhywechose|99999|>|999|ofutilitypointsinthetwocases.

Now,consideringFigure8:

Figure8:Thesecondpieceofcoderegardingtheutilityfunction.

Here,thepracticalimplementationoftheconsidereddomainconsideringallthepossibleorientationsofthediscs;thehorizontal,vertical,andthetwodiagonals.Andaveryimportantpartistheonethatgivesmoresignificanceofreservingthemiddlecolumn(Iassumedthatthenumberofcolumnshereisodd.)

TheImplementation

Inthissection,wediscussbrieflythehighlevelofsomepartsofourimplementationofthecode,Ididwritethecodeheavilycommented,andImadethenamesofthevariablesrepresentativetowhattheymean.Someideasfromthecodewereinspiredorappliedfrom[5–9].

TheBasicPanelandItsUser-FriendlyInterface

Startingwithaverybriefdescriptionoftheuser-friendlyinterfacetobuildthepanelitself,westart,bysimplyanddirectlyapplyingthestraightforwardinstructionsinthedocumentationofthepygamelibrary[10].Figure9showsapartfromthatimplementation.

Figure9:Apieceofcodefortheinitializationofthepanelandthegame.

ThispartismainlyaboutdefiningthesimpleRGBarraysofeachcolortorepresentitlaterintheuser-friendlyinterface.

Furthermore,asDr.Wanghassuggested,Imademycodeflexibletoacceptmoregeneralcasesofchoosingwhatevernumberofrowsandcolumns.Figure10showstheuser-interfaceaftersettingtheNumber_of_rowsvariableto4,andtheNumber_of_columnsvariableto5.

Figure10:AgeneralpanelthatcanbeproducedbysettingtheNumber_of_rowsandNumber_of_columnsvariables.

Itisworthmentioninghere,thattheAIworksveryperfectlyindifferentsettingsofthenumberofcolumnsandrows,becausethenumberofcolumns

androwsthataresetintheinitializationdesignatedvariablesaredirectlylinkedintheimplementationoftheAIitself.Inadditiontothat,itisworthtobehighlightedthatthegameatthefirstplacewasjustacommandlinegamethatjustprintsthematrixoftheoccupationoftheslotsofthepanelaftereachstepratherthanshowingourfinalcoloredpanel.

TheImplementationoftheAIAgentandSomeOtherPartsoftheCode

AbriefclarificationoftheimplementationoftheAIplayer.Figure11showsthemainpartoftheAIalgorithmwhichconstitutesthemainbodyoftheAI.

Figure11:ThemainfunctionoftheAIagent.

Asclear,thefunctionisrecursive,andwastakenfromthepseudocodesimplementedinFigure4andFigure6.Theadjustableparametersarethedepth,

whichisthevariabled.Thevariablesalphaandbeta,asstatedinthestandardpseudocode,are+∞and−∞.

Asobviousinthefunction,eachinvokingofitreducesthedepthbyone(asobviousbecausethealgorithmgoesuplevelbylevelasdepictedinFigure3.)Furthermore,wheninvokingthefunctionitselfeachtime,italternatesbetweentwosubfunctionswithinit,oneforthemaximizingplayer,whichisflaggedbyatruevalueofthemaximizingPlayervariable,andonefortheminimizingplayer,whichisflaggedbyafalsevalueofthemaximizingPlayervariable.

AnothersmallpieceofcodethatIwouldliketostatehereisthewayIchosetoalternatebetweentheturnsofthetwoplayers.Figure12showsthepartofcodethatalternatedtheTtvariablebetween0and1aftereachtimethelineinthefigureisinvoked.

Figure12:HowtheTtvariablealternatesbetweenthetwovaluesof0and1.

Thelastsmallpartofthecodetobehighlightedhereisfromthepygamelibrary,whichholdsthepygamewindowfor2secondsafterthegameendstoavoidthesuddendiminishofthewindowrightafterthelastmove.Figure13showsthispartofthecode.

Figure13:Thepieceofcodethatisresponsibleonholdingthepygamewindowfor2000millisecondsafterthegameends.

TheEfficiencyoftheAIModel

ThissectiongivesaverybrieffeedbackoftheefficiencyofourAImodelconsideringmanycriteria:

TheAIwithanydepthassigneddefeatsarandomplayerwhochoosestheirnextcolumnrandomlyalways.

TheAIwithouttheAlpha-BetaPruningneedsunreasonabletimetoplaywhenassignedtodepthmorethan4.

TheAIwiththeAlpha-BetaPruningneedsunreasonabletimetoplaywhenassignedtodepthmorethan6.

TheAIwithdepthvalueof5wasneverdefeatedbyrationalplayers.

TheAIwithdepthvalueof3wasdefeatedinroughlyaroundonegameoutoftenplayedagainstrationalplayers.

AnAIwithhigherdepthalwaysdefeatstheAIwithlowerdepth.

TheAIwhostartsfirstalwayswinsagainstthesameAI-modeledagentwiththesamedepth.

TheAIwithdepthvalueof2wasdefeatedinroughlyaroundtwotimesoutoftengamesplayedagainstrationalplayers.

Figure14showstheendofasamplegameplayedagainstanAIwithadepthvalueoffour.Thescreenshotwascapturedwithinthetwosecondsfreezingafteritfinis