Artificial Intelligence for Games, Second Edition

1 ARTIFICIALINTELLIGENCEFOR GAMESS econd EditionIAN MILLINGTONandJOHN FUNGEAMSTERDAM BOSTON HEIDELBERG LONDONNEW YORK OXFORD PARIS SAN DIEGOSAN FRANCISCO SINGAPORE SYDNEY TOKYOM organ Kaufmann Publishers is an imprint of ElsevierMorgan Kaufmann Publishers is an imprint of Corporate Drive, Suite 400, Burlington, MA 01803, USAThis book is printed on acid-free 2009 by Elsevier Inc. All rights used by companies to distinguish their products are often claimed as trademarks or registered trademarks. In allinstances in which Morgan Kaufmann Publishers is aware of a claim, the product names appear in initial capital or all capitalletters.

2 All trademarks that appear or are otherwise referred to in this work belong to their respective owners. Neither MorganKaufmann Publishers nor the authors and other contributors of this work have any relationship or affiliation with suchtrademark owners nor do such trademark owners confirm, endorse or approve the contents of this work. Readers, however,should contact the appropriate companies for more information regarding trademarks and any related part of this publication may be reproduced, stored in a retrieval system, or transmitted in any form or by anymeans electronic, mechanical, photocopying, scanning, or otherwise without prior written permission of the may be sought directly from Elsevier s Science & Technology Rights Department in Oxford, UK: phone: (+44) 1865843830, fax: (+44) 1865 853333, E-mail.

3 You may also complete your request online via the Elsevierhomepage ( ), by selecting Support & Contact then Copyright and Permission and then ObtainingPermissions. Library of Congress Cataloging-in-Publication DataMillington, Intelligence for games / Ian Millington, John Funge. 2nd 978-0-12-374731-0 (hardcover : alk. paper)1. Computer games Programming. 2. Computer animation. 3. Artificial Funge, John David, 1968- II. dc222009016733 British Library Cataloguing-in-Publication DataA catalogue record for this book is available from the British : 978-0-12-374731-0 For information on all Morgan Kaufmann publicationsvisit our Website by: diacriTech, IndiaPrinted in the United States of America0910111213 54321 For Conor Xiaoyuan the AuthorsIan Millingtonis a partner of Icosagon Ltd.

4 ( ), a consulting company devel-oping next-generation AI technologies for entertainment, modeling, and simulation. Previouslyhe founded Mindlathe Ltd., the largest specialist AI middleware company in computer Games, working on a huge range of game genres and technologies. He has a long background in AI,including PhD research in complexity theory and natural computing. He has published academicand professional papers and articles on topics ranging from paleontology to Funge( ) recently joined Netflix to start and lead the new Game Platformsgroup. Previously,John co-founded AiLive and spent nearly ten years helping to create a successfulcompany that is now well known for its pioneering machine learning technology for games.

5 AiLiveco-created theWii MotionPlus hardware and has established its LiveMove products as the industrystandard for automatic motion recognition. At AiLive John also worked extensively on LiveAI, areal-time behavior capture product that is being used by the former lead game designer of GuitarHero and Rock Band to create a new genre of game. John is also an Assistant Adjunct Professorat the University of California, Santa Cruz (UCSC) where he teaches a Game AI course that heproposed, designed and developed. John has a PhD from the University of Toronto and an MScfrom the University of Oxford.

6 He holds several patents, is the author of numerous technicalpapers, and wrote two previous books on Game the AuthorsivAcknowledgmentsxixPrefacexxiAbo ut the WebsitexxiiiPart IAI and Is AI? Academic Game of Game Decision Agent-Based In the , Data Structures, the of the Book18 Chapter2 Game Complexity When Simple Things Look When Complex Things Look The Perception Changes of Kind of AI in and Processor Memory PC Console AI Structure of an AI Toolchain Putting It All Together34 Part Basics of Movement Two-Dimensional Movement On the Steering Variable Seek and Velocity Delegated Pursue and Looking Where You re Path Collision Obstacle and Wall Steering Blending and Weighted Cooperative

7 Steering Aiming and Projectile The Firing Projectiles with Iterative Jump Landing Hole Fixed Scalable Emergent Two-Level Formation Extending to More than Two Slot Roles and Better Slot Dynamic Slots and Tactical Output Capability-Sensitive Common Actuation in the Third Rotation in Three Converting Steering Behaviors to Three Align to Look Where You re Faking Rotation Pathfinding Weighted Directed Weighted The The Data Structures and Performance of * The The Data Structures and Implementation Algorithm Node Array A* Choosing a Tile Dirichlet Points of Navigation Non-Translational Cost Path on A* The Hierarchical Pathfinding Pathfinding on the Hierarchical Hierarchical Pathfinding on Strange Effects of Hierarchies on Instanced Ideas in Open Goal Dynamic Other Kinds of Information Low Memory Interruptible Pooling Time The The Implementation Movement Footfalls287 Exercises288xContentsChapter5 Decision of

8 Decision The The On the Knowledge Implementation Performance of Decision Balancing the Beyond the Random Decision The The Data Structures and On the Implementation Hard-Coded Hierarchical State Combining Decision Trees and State Implementing Behavior Concurrency and Adding Data to Behavior Reusing Limitations of Behavior A Introduction to Fuzzy Fuzzy Logic Decision Fuzzy State Markov Markov State Goal-Oriented Simple Overall Overall Utility GOAP with IDA* Smelly The The Data Structures and Implementation Rule Where The The Data Structures and Other Things Are Blackboard Language Choosing a A Language Rolling Your Scripting Languages and Other Types of The Data Structures and Implementation Putting It All Together490 Chapter6 Tactical and Strategic Tactical Using Tactical Generating the Tactical Properties of a Automatically Generating the The Condensation Representing the Game Simple Influence Terrain

9 Learning with Tactical A Structure for Tactical Map Convolution Cellular The Cost Tactic Weights and Concern Modifying the Pathfinding Tactical Graphs for Using Tactical Multi-Tier Emergent Scripting Group Military Online or Offline Intra-Behavior Inter-Behavior A The Zoo of Learning The Balance of The Parameter Hill Extensions to Basic Hill Left or Raw String Window Application in Structure of Decision What Should You Learn? Four Bayes Implementation Tree ID3 with Continuous Incremental Decision Tree The The Data Structures and Implementation Tailoring Weaknesses and Realistic Other Ideas in Reinforcement Neural The The Data Structures and Implementation Other Approaches658 Exercises662 Chapter8 Board Types of The Game The Static Evaluation The Minimaxing AB The AB Search Tables and Hashing Game What to Store in the Hash Table Replacement A Complete Transposition

10 Transposition Table Using Opponent s Thinking Test Implementing The MTD Books and Other Set Implementing an Opening Learning for Opening Set Play Iterative Variable Depth Strategy Impossible Tree Real-Time AI in a Turn-Based Game708 Exercises708 Part IIIS upporting Technologies711 Chapter9 Execution The Interruptible Load-Balancing Hierarchical Priority of Graphics Level of AI Scheduling Behavioral Group In Summary743 Exercises744 Chapter10 World Knowledge Determining What Approach to Event Inter-Agent Implementation Abstract Faking What Do We Know?