Millington Ian - Artificial Intelligence for Games

Artificial Intelligence for Games, Second Edition

Ian Millington

John Funge

CRC Press

Taylor & Francis Group

6000 Broken Sound Parkway NW, Suite 300

Boca Raton, FL 33487-2742

2015 by Taylor & Francis Group

CRC Press is an imprint of Taylor & Francis Group, an Informa business

No claim to original U.S. Government works

Version Date: 20160329

International Standard Book Number-13: 978-1-4987-8581-5 (EPUB)

This book contains information obtained from authentic and highly regarded sources. Reasonable efforts have been made to publish reliable data and information, but the author and publisher cannot assume responsibility for the validity of all materials or the consequences of their use. The authors and publishers have attempted to trace the copyright holders of all material reproduced in this publication and apologize to copyright holders if permission to publish in this form has not been obtained. If any copyright material has not been acknowledged please write and let us know so we may rectify in any future reprint.

Except as permitted under U.S. Copyright Law, no part of this book may be reprinted, reproduced, transmitted, or utilized in any form by any electronic, mechanical, or other means, now known or hereafter invented, including photocopying, microfilming, and recording, or in any information storage or retrieval system, without written permission from the publishers.

For permission to photocopy or use material electronically from this work, please access www.copyright.com or contact the Copyright Clearance Center, Inc. (CCC), 222 Rosewood Drive, Danvers, MA 01923, 978-750-8400. CCC is a not-for-profit organization that provides licenses and registration for a variety of users. For organizations that have been granted a photocopy license by the CCC, a separate system of payment has been arranged.

Trademark Notice: Product or corporate names may be trademarks or registered trademarks, and are used only for identification and explanation without intent to infringe.

Visit the Taylor & Francis Web site at http://www.taylorandfrancis.com

and the CRC Press Web site at www.crcpress.com

CRC Press is a premier publisher of scientific, technology and medical content, reaching around the globe to publish the pioneering achievements of science that provide researchers, professionals, and students with the resources they need to make further advances. CRC Press is a member of Taylor & Francis Group, an informa business.

For more authoritative books in your field and for in-depth information about CRC Press books, visit www.crcpress.com

• Join our email list to receive exclusive, unadvertised discounts and alerts when new books publish in your field
• Visit Featured Authors to learn about your favorite author with detailed bios, news about their work, and discussions of their research
• Read the latest book reviews from industry experts, influencers, and thought leaders about STM (Science, Technology and Medicine) reference and textbooks

The tables in this ebook have been modified to enhance the reader experience. On compatible devices, the enhancement should keep the header rows visible as you scroll through a table.

Please report any issues with this ebook or any desired enhancements to the .

www.crcpress.com

For Conor I.M.

For Xiaoyuan J.F.

Ian Millington is a partner of Icosagon Ltd. ( www.icosagon.com ), a consulting company developing next-generation AI technologies for entertainment, modeling, and simulation. Previously he 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 academic and professional papers and articles on topics ranging from paleontology to hypertext.

John Funge ( www.jfunge.com ) recently joined Netflix to start and lead the new Game Platforms group. Previously, John co-founded AiLive and spent nearly ten years helping to create a successful company that is now well known for its pioneering machine learning technology for games. AiLive co-created the Wii MotionPlus hardware and has established its LiveMove products as the industry standard for automatic motion recognition. At AiLive John also worked extensively on LiveAI, a real-time behavior capture product that is being used by the former lead game designer of Guitar Hero and Rock Band to create a new genre of game. John is also an Assistant Adjunct Professor at the University of California, Santa Cruz (UCSC) where he teaches a Game AI course that he proposed, designed and developed. John has a PhD from the University of Toronto and an MSc from the University of Oxford. He holds several patents, is the author of numerous technical papers, and wrote two previous books on Game AI.

Although our names are on the cover, this book contains relatively little that originated with us, but on the other hand it contains relatively few references. When the first edition of this book was written Game AI wasnt as hot as it is today: it had no textbooks, no canonical body of papers, and few well-established citations for the origins of its wisdom.

Game AI is a field where techniques, gotchas, traps, and inspirations are shared more often on the job than in landmark papers. We have drawn the knowledge in this book from a whole web of developers, stretching out from here to all corners of the gaming world. Although they undoubtedly deserve it, were at a loss how better to acknowledge the contribution of these unacknowledged innovators.

There are people with whom we have worked closely who have had a more direct influence on our AI journey. For Ian that includes his PhD supervisor Prof. Aaron Sloman and the team of core AI programmers he worked with at Mindlathe: Marcin Chady, who is credited several times for inventions in this book; Stuart Reynolds; Will Stones; and Ed Davis. For John the list includes his colleagues and former colleagues at AiLive: Brian Cabral, Wolff (Daniel) Dobson, Nigel Duffy, Rob Kay, Yoichiro Kawano, Andy Kempling, Michael McNally, Ron Musick, Rob Powers, Stuart Reynolds (again), Xiaoyuan Tu, Dana Wilkinson, Ian Wright, and Wei Yen.

Writing a book is a mammoth task that includes writing text, producing code, creating illustrations, acting on reviews, and checking proofs. We would therefore especially like to acknowledge the hard work and incisive comments of the review team: Toby Allen, Jessica D. Bayliss, Marcin Chady (again), David Eberly, John Laird, and Brian Peltonen. We have missed one name from the list: the late, and sorely missed, Eric Dybsand, who also worked on the reviewing of this book, and were proud to acknowledge that the benefit we gained from his comments are yet another part of his extensive legacy to the field.

We are particularly grateful for the patience of the editorial team led by Tim Cox at Morgan Kauffman, aided and abetted by Paul Gottehrer and Jessie Evans, with additional wisdom and series guidance from Dave Eberly.

Late nights and long days arent a hardship when you love what you do. So without doubt the people who have suffered the worst of the writing process are our families. Ian thanks his wife Mel for the encouragement to start this and the support to see it through. John also thanks his wife Xiaoyuan and dedicates his portion of the book to her for all her kind and loving support over the years.