Behavioral mathematics for game AI

BEHAVIORAL MATHEMATICS

FOR GAME AI

DAVE MARK

Charles River Media

A part of Course Technology, Cengage Learning

Australia, Brazil, Japan, Korea, Mexico, Singapore, Spain, United Kingdom, United States

© 2009 Course Technology, a part of Cengage Learning.

ALL RIGHTS RESERVED. No part of this work covered by

the copyright herein may be reproduced, transmitted,

stored, or used in any form or by any means graphic,

electronic, or mechanical, including but not limited to

photocopying, recording, scanning, digitizing, taping, Web

distribution, information networks, or information storage

and retrieval systems, except as permitted under Section

107 or 108 of the 1976 United States Copyright Act, without

the prior written permission of the publisher.

All trademarks are the property of their respective owners.

Library of Congress Control Number: 2008940614

ISBN-13: 978-1-58450-684-3

ISBN-10: 1-58450-684-9

Course Technology, a part of Cengage Learning

20 Channel Center Street

Boston, MA 02210

USA

Cengage Learning is a leading provider of customized

learning solutions with office locations around the globe,

including Singapore, the United Kingdom, Australia,

Mexico, Brazil, and Japan. Locate your local office at:

international.cengage.com/region.

Cengage Learning products are represented in Canada

by Nelson Education, Ltd.

For your lifelong learning solutions, visit courseptr.com.

Visit our corporate Web site at cengage.com.

Behavioral Mathematics for Game AI

Dave Mark

Publisher and General Manager,

Course Technology PTR: Stacy L. Hiquet

Associate Director of Marketing: Sarah Panella

Content Project Manager: Jessica McNavich

Marketing Manager: Jordan Casey

Acquisitions Editor: Heather Hurley

Project Editor: Karen A. Gill

Technical Reviewer: Kevin Dill

Editorial Services Coordinator: Jen Blaney

Copy Editor: Ruth Saavedra

Interior Layout: Shawn Morningstar

Cover Creator: Dave Mark

Cover Designer: Mike Tanamachi

Indexer: Broccoli Information Management

Proofreader: Mike Beady

For product information and technology

assistance, contact us at

Cengage Learning Customer and Sales Support,

1-800-354-9706.

For permission to use material from this text

or product, submit all requests online at

cengage.com/permissions.

Further permissions questions can be e-mailed to

[email protected].

Printed in the United States of America

1 2 3 4 5 6 7 11 10 09

eISBN-10: 1-58450-693-8

I

first got into computers in the early 1980s. By the late 1980s, my very nontech￾nical grandfather, Gilbert Todd, advised me to “grab onto them computers and

stick with ’em… that’s where the future is.” I did just that, but more out of my

own inexorable need to be involved in technology than from his encouragement.

After a brief spin in the music business, I got back into computers in the mid￾1990s by doing all manner of IT consulting.

In 2002, my wife Laurie and I had just started dipping into the game business

by forming Intrinsic Algorithm. On May 20 of that year, my dad drove me to the

airport to head off to what was my first Electronics Entertainment Expo (E3) con￾ference. My 88-year-old grandfather wanted to come along for the ride. As an ex￾pilot, he enjoyed watching the planes. He knew that I was going out to Los Angeles

to some sort of computer game–related conference, although he probably believed

that it was a little more of a heady event than what the then-ubiquitous loud music,

spectacular lights, and “booth babes” would have suggested to him.

As I got out of the car in front of the terminal and retrieved my luggage from

the trunk, my grandfather gave me the best handshake his aging body could gener￾ate and told me, “You head out there and tell ’em how it’s done.”

I didn’t have the heart to argue with my grandfather and say that I wasn’t going

to E3 to tell anyone anything, but rather to soak up as much of the state of the in￾dustry as I could. I simply thanked him for the encouragement and told him that I

would do my best to “set ’em straight.”

Those words were the last thing my grandfather said to me. On May 25, 2002,

the Saturday after the show and the night before I was due to fly back, he had a heart

attack and died.

My grandfather’s final words to me—which none of us knew at the time would

be so—have rattled around in my brain for the past six years. Just like the trip that

I left for on that day, I have spent more time listening and learning than telling any￾one how anything is done. However, as I started writing this book, my grandfather’s

A Little History

and a Lot of Dedication

iii

words came back to me once again. I couldn’t help but think that, perhaps, his

advice was more timeless than the handful of days that I spent wandering through

the expansive LA Convention Center. Maybe his encouragement was issued without

an expiration date. Or maybe I should just assume that it is still in effect.

Regardless, here I am six years later writing a book on game AI. So, PawPa, I

may be a bit late, but I’m ready to head out there and tell ’em how it’s done. Thank

you.

In the meantime, there are others who have been helping me along the way

who deserve some thanks:

To my parents, who bought me my first Apple IIc back in 1984—although

they were a bit less enthusiastic when I used it to play games. See? I told you I could

make something out of that!

To my best friend in my teen years, Gregg Bieser, who did more than simply

play games with me on our respective Apples. It was with Gregg that I made my first

awkward—even abortive—efforts to make my own games.

To my AP Computer sidekicks and friends, Phil, Bob, Scott, and Rick, whose

love of strategy board games and RPGs (fueled by the strangely never-diminishing

supply of caffeine at Phil’s house) helped crystallize in me what I wanted my own

games to look and play like some day.

To my younger brothers, Jared and Kevin, who, at elementary school ages in

the 1980s, were my guinea pigs as AD&D players. In retrospect, being a Dungeon

Master at 15 years old was the first time I turned mathematics into behaviors.

To the late Eric Dybsand, who, at the 2003 GDC, told me I knew what I was

talking about—even when I didn’t think I did. Respawn soon, my friend! In the

meantime, I hope you can get this book delivered to wherever you are. It seems like

you were right. Oh, do me a favor and loan a copy to PawPa while you are at it. He

won’t understand a word of it, but it will make him proud.

To Steve Woodcock, not only for being there from the beginning, but for stick￾ing around during the hard part, and then telling me it was time to get back on the

horse after I had fallen off.

To Alex Champandard for both giving me plenty of good advice and handing

me the “megaphone and soapbox” that a weekly column can turn into.

To Steve Rabin for his supply of wisdom regarding “AI Wisdom” and trusting

me to help hold the reins to something bigger than both of us.

To Heather Hurley and Karen Gill at Charles River Media for helping me make

the jump from 13 pages to 500.

iv Dedications

To my tech editor, Kevin Dill, for reading every word and number—and

reminding me about the geometry of triangles.

To my in-laws, Larry and Lenora Reynolds, who loaned Laurie and me some

bootstraps they had lying around—and were patient with us when we wore them

out.

To my son Steven, who constantly reminds me that games can bridge generations

—and teaches me that my thumbs are too slow.

To my daughter, Kathy, who constantly reminds me that games can be about

more than shooting stuff—and teaches me how to observe people in ways that

continue to amaze me.

To my son Aaron, who constantly reminds me of what I was like when I was his

age—which kinda scares both of us.

To my stepdaughter Beth, who constantly reminds me that it can be fun to

completely beat the snot out of an opponent.

And, finally, thanks must go out to my wife and business partner, Laurie.

Starting Intrinsic Algorithm was my dream. Her dream was helping me achieve

mine. During the conversation at a restaurant in late 2001 that launched us into the

game business, she gave me the best bit of advice I’ve ever had. When I asked her,

“But what if I can’t do it? What if I fail?” she simply shrugged and said, “Well, then

we’ll know.”

Thanks, dear. You don’t know what that meant to me, then and now. This

book is dedicated to your dedication.

Thank you all,

Dave Mark

Dedications v

vi

Dave Mark is the president and lead designer of Intrinsic Algorithm, LLC, an

independent game development studio and AI consulting company in Omaha,

Nebraska. He has been programming since 1984 when he was in high school where,

much to the dismay of his teacher, he wrote his first text adventure on the school’s

DEC PDP-1144.

After a brief detour in the music business as a composer/arranger, keyboard

player, and recording engineer during the early 1990s, Dave re-entered the technol￾ogy arena in 1995. In 2002, he came to the startling realization that the corporate IT

consulting and development world is a little short on creativity and fun. As a result,

Dave left to start Intrinsic Algorithm LLC with his wife, Laurie.

He is a contributor to the AI Game Programming Wisdom series of books, a

regular columnist at AIGameDev.com, and a founding member of the AI Game

Programmers Guild.

Dave continues to attend the University of Life. He does not plan to graduate

anytime soon.

About the Author

vii

As I have read different books on a variety of subjects over the years, I have

found a variety of styles to be effective for communicating ideas. In addition

to simply reading the text of a book on a technical subject, I have often

appreciated the extra effort that went into creating examples of the concept. I enjoy

diagrams and graphs so that I can simply have a place to anchor my thoughts as

I ponder the issue. Where appropriate, I like seeing the formulas used, already

normalized into a form that can be dropped into code. And, of course, I find actual

code snippets very helpful when the problem is one of programming.

Some of these elements have been more helpful than others. Some of them

have been used to the point of overkill such that it was next to impossible to extract

meaningful content from the clutter. On the other hand, I have often felt that I have

been left wanting a diagram, a table, or a bit of code so that I could put things into

perspective.

To that end, as I set out to write this book, I made myself a promise to attempt

to find the balance that would be the most helpful to you, the reader. Throughout

this work, I attempt to cover four different approaches: theory, math, examples,

and code.

Much of the discussion in this book will be about the theory behind the con￾cepts. This will be where I lay out the concept of a point as groundwork. While this

might seem to be the part of the book that is the least directly relevant to game pro￾gramming, it is also where much of the important material is. Everything spills out

of these ideas. Rather than bland recitation, I try to make the theory accessible

through example and anecdote.

If necessary, the theory sections will show the relevant mathematics of the

concepts. Please note that, unlike some other books, my goal is not to overwhelm

you with esoteric proofs of how I got to where I did, but to give you as a developer

an end product that you can find useful in production.

Author’s Preface

IN THE GAME

Very often throughout the book, I will lay out hypothetical game-like situations

that show how to use a theoretical concept. While these examples may be game

genre–specific, the concepts themselves can usually be applied universally. You will

be able to quickly identify these sections by the icon at the left that will appear at the

beginning of each in-game example. Note that there’s a listing of all the In the Games

following the table of contents.

PUTTING IT IN CODE

Where appropriate, I will offer up examples of how tools are used in programming

situations. Sometimes these functions will be ones that you can use in your own

projects. In these cases, you can find the code on the book’s Web site at

http://www.courseptr.com/downloads.

For clarity’s sake, I list some of the naming conventions that I use in my pro￾jects and, therefore, in this book.

Type and struct names are in all caps: MY_TYPE.

Struct names are preceded by a lowercase “s”: sMY_STRUCT.

Variables and functions are in initial caps: MyFunction( MyVariable ).

Member variables of a class are generally preceded with a lowercase “m”:

mMyMemberVariable.

List and vector names are preceded by a lowercase “l” and “v,” respectively. I

combine these when necessary, such as in a member of a class that is also a vector.

In this case, the name is preceded by “mv,” such as in mvMyMemberVector.

Given that discussions of differences in programming style are often likened to

religious wars, I hope my naming conventions do not cause you to view me as a

heretic or to lob this book onto a blazing pyre of sacrilegious tomes with evil code￾naming conventions.

Oh yeah, open and close braces for functions belong in the same column, but

open braces for if and while statements belong at the end of the if or while line.

I want to follow the column from the end brace to the command that started it all.

If you think differently, then you… you… you’re just wrong! So there!

viii Author’s Preface

OK… sorry. That was uncalled for. I truly hope that my quirks don’t annoy you

or make this book harder to understand. I’m just old. I learned some of these habits

in 1984. Blame my high school computer teacher.

*sigh*

Throughout all of the sections, we will encounter terms that are worth noting.

To help you locate and remember these items, they will be bolded and marked with

the important lingo arrow in the margin.

Sometimes, I will add a cautionary note or an aside of some sort. This will be

set apart with the stylized, yet familiar comment brackets you see here.

In addition to seeing in-game examples, you will encounter numerous exam￾ples from “life”—mine as well as those around me. Since, as AI programmers, we

are often in the business of re-creating lifelike situations and behaviors, I find this

approach fitting. Also, I hope that you forgive me for a sense of humor. It is my at￾tempt to keep you from falling into the mind-numbing stupor that technical books

have been known to induce. In a manner of speaking, I’m doing it for your own

good. Don’t just learn—enjoy!

Author’s Preface ix

This page intentionally left blank

Part I Introduction 1

1 Why Behavioral Mathematics? 3

Games and Choices 4

Going Beyond Looks 10

2 Observing the World 15

Identifying Factors 16

Finding Hidden Factors 22

Quantifying Observations 24

Needing More Than Observations 28

3 Converting Behaviors to Algorithms 29

Using Numbers to Select 30

Using Numbers to Define 33

Using Algorithms to Construct Numbers 37

Part II Decision Theory 43

4 Defining Decision Theory 45

Normative Decision Theory 45

Descriptive Decision Theory 48

The Best of Both Worlds 51

5 Game Theory 55

Starting Simple 56

Matching Pennies 57

Prisoner’s Dilemma 61

Contents

xi

Asymmetric Games 69

Cutting the Cake 70

Ultimatum Game 72

Dictator Game 75

Trust Game 76

6 Rational vs. Irrational Behavior 79

Perfect Rationality 80

The Pirate Game 80

Superrationality 85

Guess Two-Thirds of the Average Game 87

Bounded Rationality 96

Misusing Irrelevant Information 97

Ignoring Relevant Information 100

Rational Ignorance 105

The Cost of Information 105

The Cost of Calculation 107

Combining It All 109

7 The Concept of Utility 111

Decisions under Risk 112

Pascal’s Wager 113

No Pain, No Gain 115

Utility of Money 121

Value vs. Utility 121

Utility vs. Risk 123

Utility of Time 140

Production over Time 141

Distance over Time 145

Changes in Utility over Time 150

Our Utility of Utility 165

xii Contents

8 Marginal Utility 167

Value vs. Utility vs. Marginal Utility 168

Changes in Marginal Utility 169

Decreasing Marginal Utility 170

Increasing Marginal Utility 177

Marginal Risk vs. Marginal Reward 181

Defining Thresholds 187

Multiple Utility Thresholds 188

The Utility of Marginal Utility 194

9 Relative Utility 195

Hedonic Calculus 196

Multi-Attribute Utility Theory 198

Inconsistencies 205

Problems with Perception 206

Problems with Categorization 207

Problems with Understanding 207

Apparent Contradictions 210

Giffen Goods 210

Moral Dilemmas 219

The Relative Benefit of Relative Utilities 225

Part III Mathematical Modeling 227

10 Mathematical Functions 229

Simple Linear Functions 229

Quadratic Functions 231

Shifting the Quadratic 231

Tilting the Parabola 233

Reshaping the Parabola 234

Sigmoid Functions 236

The Logistic Function 236

The Logit Function 239

Ad Hoc Functions 240

Contents xiii

11 Probability Distributions 241

Identifying Population Features 242

Segmenting the Population 244

Analyzing a Single Segment 247

Uniform Distributions 248

Normal (Gaussian) Distributions 250

Properties of Normal Distributions 250

Generating Normal Distributions 254

Triangular Distributions 269

Simplified Normal Distributions 269

Parametric Building 270

Uneven Distributions 272

Parabolic Distributions 274

Poisson Distributions 276

Distributing the Distributions 279

12 Response Curves 285

Constructing Response Curves 286

Building Buckets 289

Retrieving a Result 294

Converting Functions to Response Curves 296

Simple 1-to-1 Mappings 296

Advanced 1-to-1 Mappings 297

Converting Distributions to Response Curves 303

Data Structure 304

Entering Data 304

Selecting a Result 308

Adjusting Data 311

Search Optimization 314

Hand-Crafted Response Curves 316

Dynamic Response Curves 317

xiv Contents