Matthew Goldfarb 馬修·戈德法布

PAGE

1

PAGE

4

MatthewGoldfarb

IntroductiontoArtificialIntelligence

FinalProject

12/7/04

GamingAlgorithms

Search-basedandlearning-basedalgorithmsaretwocommonformsofalgorithmsusedincomputergaming.Inordertocomparetheefficiencyofbothalgorithms,Iconstructedtwoseparategames,eachusingoneofthealgorithms.Aftercodingandsuccessfullyrunningeachgameitbecameapparentthatboththesearch-basedandlearning-basedalgorithmshadpositiveandnegativetraitswithrespectto“AI”gaming.Tobetterillustratetheprocessofcodingbothalgorithmsitisnecessarytounderstandhowthesealgorithmshavebeenuseditisnecessarytodefineboth,explainthepositiveandnegativetraitsofbothalgorithms,aswellaswhetherornoteitheristrulyArtificialIntelligence.

Understandingeitheralgorithmbeginswithasimpledefinition.Search-basedalgorithmsarethosethatallowthecomputerto“think”withasetofgivenknowledgeinresponseto“unknowninput”.Anexampleof“unknowninput”ingamingiswhenaplayertakesaturn,thecomputerthenreactstothis“unknown”eventbasedonitsgivenknowledge.Thisgivenknowledgeissimplythesetofinformationthathasbeenpredeterminedbytheauthorofthecodeusedinthegame.

Learning-basedalgorithms,however,donotgivethecomputeranypre-determinedknowledge.Thecomputer“l(fā)earns”howtoplayandwinagamethroughinteractionwithaplayer.Simply,thecomputer“l(fā)earns”howtowinagamethroughgainedknowledge.Thedifferencebetweenthesealgorithmsisthepresenceofknowledge.Asearch-basedalgorithmallowsthecomputertohaveknowledge,whilealearning-basedalgorithmgainsknowledgethroughgameplay.

Althoughbothalgorithmsmayworkwellintheory,afterconstructingtwoseparategamesusingeitheralgorithm,itbecameclearthatthesearch-basedalgorithmperformsbetteringameplay,inotherwordsitwinsmoreoftenthanthelearning-based.However,thelearning-basedalgorithmismore“intelligent”,sinceithastheabilitytolearn.Itisapparentthatbothalgorithmshavetheirpositiveandnegativetraits.

Iusedtheboardgamescrabbletotestthesearch-basedalgorithm.Thegameisplayedbyconnectingasinglewordtolettersalreadyplacedontheplayingboard,keepinginmindthemanycombinationsofwordspossible,thebestcombinationresultinginahigherscore.Thelettersavailabletoeachplayerarelimitedtothoserandomlychosenfromacollectionofonehundredletters,eachlettercarryingadifferentpointvalue,theselettersarehiddenfromotherplayersmakingthegamemorecomplex.Thegameiswonbychoosingthebestwordcombinations,usingtheletterswiththehighestpointvalue,resultinginthegreatestscore.Thegameisextremelycomplicatedandnoteasilywon.

Iusedasearch-basedalgorithmbecauseIfeltitwasnecessaryforthecomputertohaveadatabaseofwordsinordertoproperlyplaythegame.Itwouldbeunworkableforacomputerto“l(fā)earn”anywordseitherthanthosegivenbytheauthorofthecodebecauseevenifthecomputerwereto“l(fā)earn”knewwordsthroughgameplay,theveryfirstmovewouldbeimpossiblewithoutapriorknowledgeofatleastoneword.

Afterconstructingandrunningthesearch-basedalgorithminscrabbleitbecameapparentthatthepositivetraitsofthisalgorithm,positivebeingthemost“AI-like”traits,wereitsabilitytoreacttoan“unknown”eventwiththebestwordscore,givenitspriorknowledge.ArtificialIntelligencerequiresthatacomputerbeableto“think”

throughaproblemandreactwith“intelligence”.Howeversuch“intelligence”doesnotalwaysresultinthebestpossiblemove.Thegameiscodedtogainthehighestscoreeachturn,howeverthegameofscrabblemayrequireaplayerto“thinkahead”andblocktheotherplayer’smoveorsetitselfupforabettermovethenextturn.Myalgorithmcannot“planahead”becauseitiscodedtoproducethehighestscoreeachturn.Atruly“human-like”algorithmwouldbeableto“planahead”whichisahumanability.

Thegametic-tac-toewasusedtoexhibitalearning-basedalgorithm.Unlikethescrabblegamethisalgorithmallowedthecomputeronlythemostbasicrulesofthegamewithnopriorknowledgeofbettermoves.Tic-tac-toeisplayedbyplacingeitherx’soro’sononesquareoutofathreebythreematrix.Thegameiswonbyconnectingthreex’soro’sinarow,eitherdiagonally,vertically,orhorizontally.Althoughthegameissimple,therearehowevercertainmoveswhichwillalwaysresultinatieorwin.Myalgorithmbeginswithanumberofrandomselectionsofsquares,resultingineitheraties,winorloss.Thecomputerrecordstheseresultswhichresultsinthecomputer”learning”gamestrategyforfuturegameplay.Thiscanbeviewedas“intelligent”sincetheprocessof“l(fā)earning”resultsinbettergameplay,howeveranegativetraitistheinconsistencyof“l(fā)earning”anduseofrecorded“knowledge”.

Boththesearch-basedandlearning-basedalgorithmshave“AI-like”qualities,howeverbothdohavedrawbacks.Itismyopinion,afterconstructingandrunningbothalgorithms,thatbothareformsofArtificialIntelligence.InordertocreateabetterArtificialIntelligenceitmightbebettertocombinebothalgorithms,allowingthecomputertoboth“l(fā)earn”andutilizeexistingknow