Jacek Man´dziuk Knowledge-Free and Learning-Based Methods in Intelligent Game Playing 123 Prof.JacekMan´dziuk FacultyofMathematicsand InformationScience WarsawUniversityofTechnology PlacPolitechniki1 00-661Warsaw Poland E-mail:[email protected] ISBN 978-3-642-11677-3 e-ISBN 978-3-642-11678-0 DOI 10.1007/978-3-642-11678-0 Studiesin Computational Intelligence ISSN1860-949X Library of Congress Control Number:2009943991 (cid:2)c 2010 Springer-VerlagBerlin Heidelberg Foreword by David B. Fogel At a time when biologicallyinspiredmachine intelligence tools arebecoming crucial to the development of game-playing strategies, Jacek Man´dziuk has written a book that focuses on exactly these tools. His book Knowledge-free and Learning-based Methods in Intelligent Game Playing concentrates on games requiring mental ability “mind games” as Man´dziuk describes them. His extensivesurvey ofthe literature is aimedmainly onthose methods that offerthepotentialtohaveacomputerteachitselfhowtoplayagamestarting withverylittle (orno)knowledgeofthegame,ortolearnhowtoimproveits play basedonfeedback about the quality ofits performance.His perspective isoneofafuturist,lookingaheadtograndchallengesandthe computational intelligence methods that may be used to meet those challenges. To date, the greatest achievements in game play in most standard “mind games” have come from knowledge-intensive methods, not knowledge-free methods. They have come from programming human knowledge into the software, rather than having the software learn for itself. This is true, for example, for Othello, checkers,and chess. But this is going to have to change because the games that now really challengeusaresufficientlycomplicatedthattraditionalknowledge-intensive methods will not yield satisfactory results. Computing power alone is un- likely to be the basis for addressing Go, and even if that computational power does become sufficient, we could easily imagine Go on a 190×190 board instead of the 19×19 traditional game, which our modern computers alreadyfindvexing.Inthatcase,MonteCarlotreesearchestothe endofthe game,endgamedatabases,andopeningbooksbasedonhumangrandmaster knowledge would no longer be very helpful to the computers. When compared to Go, the games than we humans play in the real world areoffargreatercomplexity.Forexample,wecouldlooktoreal-timestrategy video games that have thousands of “agents” acting simultaneously, but we could just as well consider, say, the games of economics that are played be- tween nations. Determining which countries should receive favorable trading status and which should have tariffs placed on their goods is a game.Its not played on a board or a table or a computer, but it is game nonetheless, and the consequencesofwinning orlosingareusuallyfargreaterthanis foundin acontestbetween,say,twocheckersplayers.Iwonderifanyonetrulybelieves that the usual devices of traditional artificial intelligence will ever be very successful in addressing such games. Certainly, I do not believe they will be. An alternativeis to focus onhow humans adaptto different challenges,or moregenerallyhowanyintelligentsystemsdothis.Intelligencethenbecomes a matter of adapting behavior to meet goals across a range of environments, andwecanobserveexamplesnotonlyourselves,butalsoinsocieties(suchas ants) and in evolving organisms. Neural networks, evolutionary algorithms, and reinforcement learning take center stage, and here Man´dziuk highlights their application to games including backgammon, checkers, and Othello, with additionalremarkstowardpoker,bridge,chess,Go,andother gamesof strategy. His perspective is that the key to making major advancements in intelligent game playing comes from capturing our human abilities such as creativity, selective focus, and generalization.His conviction is compelling. Thisisabookthatisbothbroadanddetailed,comprehensiveandspecific, anditoffersavisiontowardthechallengesthatawaitus.Withtheexpanding interest in game playing Man´dziuk offers a timely book that will serve the growing games community for years to come. I hope you find it a source of continual inspiration. David B. Fogel Lincoln Vale CA LP Natural Selection, Inc. San Diego, California, USA Foreword by Simon M. Lucas Sincetheseminalworkofthefoundingfathersofcomputerscienceandinfor- mation theory, people such as Alan Turing and Claude Shannon, there has been a rich history of researchapplied to games,and without doubt this has contributedgreatlytothedevelopmentofartificialintelligenceasadiscipline. The focus of this book is on Mind Games, games of skill such as Chess, Go, and Bridge which predate computers. There have been two approaches to designingagentscapableofahighstandardofplayinsuchgames:handpro- gramming, and machine learning. Both methods have had their high-profile successes,with Deep Blue (Chess)being anexemplar ofexpert hand-tuning, and TD-Gammon (Backgammon), Logistello (Othello) and Blondie (Check- ers) being exponents of the machine-learning approaches (though each of these differed in the nature of the learning). As the book argues, there is much more to this field than simply designing agents that are capable of a highstandardofplay.Thewayinwhichitisachievedisofgreatimportance. Hand programmedagents tend to be specific to a particular game. Learning agents on the other hand offer the potential of a more general ability, and the ability to learn is central to most meaningful definitions of intelligence. Games offer an excellent application domain and a demanding test-bed for AI and CI techniques. This bookoffersaunique perspectiveonthesubject,embracingbothcon- ventionalAIapproachestogame-playingaswellastheopen-endedchallenges that games pose for computational intelligence. It gives a detailed account of the main events in the development of the field, and includes the most important algorithms in game-tree search, temporal difference learning, and in evolutionary game learning, and describes in detail how these have been appliedtoarangeofdifferentmindgames.Thefocusonmindgamesenables a deep coverage of the most important researchin this area. The book is organised into four parts. The first part covers the founda- tions including the main game-tree searchalgorithms and then discusses the state of the art in the most important mind games. Part two describes the main computational intelligence methods that have been applied to learn gamestrategy,anddescribesselectedTDandneuro-evolutionaryapproaches to specific games including Backgammon, checkers, and Othello. Part three then goes into greater detail on how to get the best out of these methods, including the choice of function approximation architecture, the selection of game-features, and tuning the algorithms for best performance. It also dis- cusses the main approaches to move ordering, and to opponent modelling. Part four describes some of the grand challenges in game playing, organised into chapters on intuition, creativity and knowledge discovery, and general game playing. This is a wellbalancedbook that celebratesthe greatachievementsofthe field while pointing out that many basic questions have yet to be answered. Atalltimes the authorshowsanimpressiveknowledgeofthe subjectandan ability to communicate this clearly.The book makes fascinating reading and should be of great interest to researchers involved in all kinds of computa- tionalintelligence andAI, and willhelp attractmorepeople to study games. For PhD students starting out in the area it should be regarded as essen- tial, and would also be useful as recommended reading for taught courses in computational intelligence and games. Professor Simon M. Lucas University of Essex, UK Editor-in-Chief IEEE Transactions on Computational Intelligence and AI in Games Preface Humans and machines are very different in their approaches to game play- ing. Humans use intuition, perception mechanisms, selective search, creativ- ity, abstraction, heuristic abilities and other cognitive skills to compensate their (comparably) slow information processing speed, relatively low mem- ory capacity, and limited search abilities. Machines, on the other hand, are extremely fast and infallible in calculations, capable of effective brute-force- type search, use “unlimited” memory resources, but at the same time are poor at using reasoning-based approaches and abstraction-based methods. The above major discrepancies in the human and machine problem solving methods underlined the development of traditional machine game playing as being focused mainly on engineering advances rather than cognitive or psychological developments. In other words, as described by Winkler and Fu¨rnkranz [347, 348] with respect to chess, human and machine axes of game playingdevelopmentareperpendicular,but the mostinteresting,most promising,andprobablyalsomostdifficult researcharealieson the junction between human-compatible knowledge and machine compatible processing. I undoubtedly share this point of view and strongly believe that the future of machine game playing lies in implementation of human-type abilities (ab- straction,intuition,creativity,selectiveattention,andother)whilestilltaking advantage of intrinsic machine skills. Thebookisfocusedonthedevelopmentsandprospectivechallengingprob- lemsintheareaofmindgameplaying(i.e.playinggames that require mental skills) using Computational Intelligence (CI) methods, mainly neural net- works, genetic/evolutionary programming and reinforcement learning. The majority of discussed game playing ideas were selected based on their functional similarity to human game playing. These similarities in- clude:learningfromscratch,autonomousexperience-basedimprovementand example-basedlearning. The above features determine the major distinction betweenCIandtraditionalAImethodsrelyingmostlyonusingeffectivegame tree search algorithms, carefully tuned hand-crafted evaluation functions or hardware-basedbrute-force methods. On the other hand, it should be noted that the aim of this book is by no means to underestimate the achievementsoftraditionalAI methods in game playing domain. On the contrary,the accomplishments of AI approachesare undisputableandspeakforthemselves.Thegoalisrathertoexpressmybelief that other alternative ways of developing mind game playing machines are possible and urgently needed. DuetorapiddevelopmentoftheAI/CIapplicationsinmindgameplaying, discussingorevenmentioningallrelevantpublicationsinthisareaiscertainly beyond the scope of the book. Hence, the choice of references and presented methodshadtobe restrictedtoarepresentativesubset,selectedsubjectively based on my professional knowledge and experience. The book starts with the Introduction followed by 14 chapters grouped into4parts.Theintroductorychapterprovidesabriefoverviewofthebook’s subject, further elaborating on the reasons behind its origin and discussing its content in more detail. The first part of the book entitled AI tools and state-of-the-artaccomplishments inmindgames coversabriefoverviewofthe field, discusses basic AI methods and concepts used in mind game research and presents some seminal examples of AI game playing systems. Part II - CI methods in mind games. Towards human-like playing starts withanoverviewofmajorsubdisciplines withinCI,namelyneuralnetworks, evolutionary methods, and reinforcement learning, in the context of game playing developments. The other chapter in Part II emphasizes the selected accomplishments of Computational Intelligence in the field. The third part - An overview of challenges and open problems presents, chapter-by-chapter, five aspects of mind game playing, which I consider challenging for CI methods. These areas are related to evaluation function learning,efficientgamerepresentations,effectivetrainingschemes,search-free playing and modeling the opponent. The topics are presented in the context ofachievementsmadetodate,openproblems,andpossiblefuturedirections. The final part of the book, entitled Grand challenges, is devoted to the most challenging problems in the field, namely: implementation of intuitive playing,creativityandmulti-gameplaying.Allthree above-mentionedissues are typical for human approaches to mind games and at the same time ex- tremely hardto implement in game playing machines - partly due to not yet fully uncovered mechanisms of perception, representation and processing of game information in the human brain. The last chapter highlights the main conclusions of the book and summarizes prospective challenges. Insummary,Ibelievethattheneedforfurtherdevelopmentofhuman-like, knowledge-free methods in mind games is unquestionable, and the ultimate goal that can be put forward is building a truly autonomous, human-like multi-game playing agent. In order to achieve this goal several challenging problems have to be addressed and solved on the way. Presentation of these challengingissuesisthe essenceofthis book.I hopethe bookwillbe helpful, especially for young scientists entering the field, by summarizing the state- of-the-art accomplishments and rising new research perspectives. IwouldliketothankProf.JanuszKacprzykfortheinspirationforwriting this book and Prof. Wl(cid:4)odzis(cid:4)law Duch for fruitful discussions concerning the scopeofthebookandrelatedsubjects.I’mverygratefultoProf.DavidFogel and Prof. Simon Lucas for writing forewords and for encouraging comments regardingthebook’sscopeandcontent.Iwouldalsoliketothankmyformer and current PhD students: Cezary Dendek, Krzysztof Mossakowski, Daniel Osman and Karol Wale¸dzik, as well as other co-authors of my papers dis- cussed in this book for a satisfying and productive cooperation. I wish to thank KarolWale¸dzik for his valuable comments andsuggestionsconcerning the initial version of the book. Last but not least I’m grateful to my family for supporting me in this undertaking. Warsaw, September 2009 Jacek Man´dziuk Contents 1 Introduction............................................. 1 Part I: AI Tools and State-of-the-Art Accomplishments in Mind Games 2 Foundations of AI and CI in Games. Claude Shannon’s Postulates ............................................... 11 3 Basic AI Methods and Tools............................. 15 3.1 Definitions and Notation .............................. 15 3.2 Game Tree Searching ................................. 16 3.2.1 Minimax Algorithm ........................... 17 3.2.2 Alpha-Beta Search ............................ 18 3.2.3 Heuristic Enhancements ....................... 20 3.2.4 SCOUT and Negascout (PVS).................. 27 3.2.5 MTD(f) and MTD-bi ......................... 29 3.3 Rollout Simulations and Selective Sampling.............. 31 3.3.1 UCT Algorithm .............................. 36 4 State of the Art ......................................... 41 4.1 ..., Deep Blue, Fritz, Hydra, Rybka, ... .................. 41 4.2 Chinook – A Perfectly Playing Checkers Machine......... 43 4.3 Logistello – The Othello World Champion............... 44 4.4 Maven and Quackle – The Top Level Machine Scrabble Players ............................................. 45 4.5 Poker and Bridge – Slightly behind Humans ............. 47 4.6 Go – The Grand Challenge ............................ 49