book

Artificial Intelligence for Games, 2nd Edition

by Ian Millington, John Funge

August 2009

Intermediate to advanced

872 pages

24h 44m

English

CRC Press

Read now

Unlock full access

Preliminaries
Dedication
About the Authors
Acknowledgments
Changes to the second edition
Preface
About the Website
Part I AI and Games
Chapter 1 Introduction
1.1 What Is AI?1.1.1 Academic AIThe Early DaysThe Symbolic EraThe Modern EraEngineering1.1.2 Game AI1.2 Model of Game AI1.2.1 Movement1.2.2 Decision Making1.2.3 Strategy1.2.4 Infrastructure1.2.5 Agent-Based AI1.2.6 In the Book1.3 Algorithms, Data Structures, and Representations1.3.1 AlgorithmsPerformance CharacteristicsPseudo-Code1.3.2 Representations1.4 On the Website1.4.1 Programs1.4.2 LibrariesOptimizationsRendering and MathsUpdating the Code1.5 Layout of the BookFigure 1.1
Chapter 2 Game AI
2.1 The Complexity Fallacy2.1.1 When Simple Things Look Good2.1.2 When Complex Things Look Bad2.1.3 The Perception Window2.1.4 Changes of Behavior2.2 The Kind of AI in Games2.2.1 Hacks2.2.2 HeuristicsCommon HeuristicsMost ConstrainedDo the Most Difficult Thing FirstTry the Most Promising Thing First2.2.3 Algorithms2.3 Speed and Memory2.3.1 Processor IssuesSIMDMulti-Core Processing and Hyper-ThreadingVirtual Functions/Indirection2.3.2 Memory ConcernsCache2.3.3 PC Constraints2.3.4 Console ConstraintsWorking with Rendering HardwareHandheld Consoles2.4 The AI Engine2.4.1 Structure of an AI Engine2.4.2 Toolchain Concerns2.4.3 Putting It All TogetherFigure 2.1Figure 2.2
Part II Techniques

Chapter 3 Movement
3.1 The Basics of Movement Algorithms3.1.1 Two-Dimensional MovementCharacters as Points3.1.2 Statics½ DimensionsMath3.1.3 KinematicsIndependent FacingUpdating Position and OrientationVariable Frame RatesForces and Actuation3.2 Kinematic Movement Algorithms3.2.1 SeekData Structures and InterfacesPerformanceFleeArriving3.2.2 WanderingPseudo-CodeData StructuresImplementation Notes3.2.3 On the Website3.3 Steering Behaviors3.3.1 Steering Basics3.3.2 Variable Matching3.3.3 Seek and FleePseudo-CodeData Structures and InterfacesPerformanceFleeOn the Website3.3.4 ArrivePseudo-CodePerformanceImplementation NotesLeave3.3.5 AlignPseudo-CodeImplementation NotesPerformanceThe Opposite3.3.6 Velocity MatchingPseudo-CodePerformance3.3.7 Delegated Behaviors3.3.8 Pursue and EvadePseudo-CodeImplementation NotesPerformanceEvadeOvershooting3.3.9 FacePseudo-Code3.3.10 Looking Where You’re GoingPseudo-CodeImplementation NotesPerformance3.3.11 WanderPseudo-CodeData Structures and InterfacesPerformance3.3.12 Path FollowingPseudo-CodeData Structures and InterfacesPath TypesKeeping Track of the ParameterPerformance3.3.13 SeparationPseudo-CodeImplementation NotesPerformanceAttractionIndependence3.3.14 Collision AvoidancePseudo-CodePerformance3.3.15 Obstacle and Wall AvoidancePseudo-CodeData Structures and InterfacesPerformanceCollision Detection ProblemsThe Corner Trap3.3.16 Summary3.4 Combining Steering Behaviors3.4.1 Blending and Arbitration3.4.2 Weighted BlendingThe AlgorithmPseudo-CodeData StructuresPerformanceFlocking and SwarmingOn the WebsiteProblemsStable EquilibriaConstrained EnvironmentsNearsightedness3.4.3 PrioritiesThe AlgorithmPseudo-CodeData Structures and InterfacesImplementation NotesOn the WebsitePerformanceEquilibria FallbackWeaknessesVariable Priorities3.4.4 Cooperative Arbitration3.4.5 Steering PipelineAlgorithmTargetersDecomposersConstraintsThe ActuatorPseudo-CodeData Structures and InterfacesTargeterDecomposerConstraintActuatorDeadlockGoalPathsPerformanceOn the WebsiteExample ComponentsTargeterDecomposerConstraintConclusion3.5 Predicting Physics3.5.1 Aiming and Shooting3.5.2 Projectile TrajectoryPredicting a Landing Spot3.5.3 The Firing Solution3.5.4 Projectiles with DragRotating and Lift3.5.5 Iterative TargetingThe ProblemThe AlgorithmPseudo-CodeData Structures and InterfacesPerformanceIterative Targeting without Motion EquationsOther Uses of PredictionFigure 3.1Figure 3.2Figure 3.3Figure 3.4Figure 3.5Figure 3.6Figure 3.7Figure 3.8Figure 3.9Figure 3.10Figure 3.11Figure 3.12Figure 3.13Figure 3.14Figure 3.15Figure 3.16Figure 3.17Figure 3.18Figure 3.19Figure 3.20Figure 3.21Figure 3.22Figure 3.23Figure 3.24Figure 3.25Figure 3.26Figure 3.27Figure 3.28Figure 3.29Figure 3.30Figure 3.31Figure 3.32Figure 3.33Figure 3.34Figure 3.35Figure 3.36Figure 3.37Figure 3.38Figure 3.39Figure 3.40Figure 3.41Figure 3.42Figure 3.43Figure 3.44Figure 3.45Figure 3.46Figure 3.47Figure 3.48
3.6 Jumping
3.6.1 Jump PointsAchieving the JumpWeaknesses3.6.2 Landing PadsThe Trajectory CalculationPseudo-CodeData Structures and InterfacesImplementation NotesPerformanceJump Links3.6.3 Hole Fillers3.7 Coordinated Movement3.7.1 Fixed Formations3.7.2 Scalable Formations3.7.3 Emergent Formations3.7.4 Two-Level Formation SteeringRemoving the LeaderModerating the Formation MovementDrift3.7.5 ImplementationData Structures and InterfacesImplementation CaveatsPerformanceSample Formation Pattern3.7.6 Extending to More than Two Levels3.7.7 Slot Roles and Better AssignmentHard and Soft Roles3.7.8 Slot AssignmentGeneralized Slot CostsImplementationData Structures and InterfacesPerformance3.7.9 Dynamic Slots and Plays3.7.10 Tactical MovementTactical Motion and Anchor Point Moderation3.8 Motor Control3.8.1 Output Filtering3.8.2 Capability-Sensitive SteeringCoping with Combined Steering Behaviors3.8.3 Common Actuation PropertiesHuman CharactersCars and MotorbikesTracked Vehicles (Tanks)3.9 Movement in the Third Dimension3.9.1 Rotation in Three Dimensions3.9.2 Converting Steering Behaviors to Three DimensionsLinear Steering Behaviors in Three DimensionsAngular Steering Behaviors in Three Dimensions3.9.3 Align3.9.4 Align to Vector3.9.5 Face3.9.6 Look Where You’re Going3.9.7 Wander3.9.8 Faking Rotation AxesThe AlgorithmPseudo-CodeData Structures and InterfacesImplementation NotesPerformanceExercisesFigure 3.49Figure 3.50Figure 3.51Figure 3.52Figure 3.53Figure 3.54Figure 3.55Figure 3.56Figure 3.57Figure 3.58Figure 3.59Figure 3.60Figure 3.61Figure 3.62Figure 3.63Figure 3.64Figure 3.65Figure 3.66Figure 3.67Figure 3.68Figure 3.69Figure 3.70Figure 3.71Figure 3.72Figure 3.73
Chapter 4 Pathfinding
4.1 The Pathfinding Graph4.1.1 Graphs4.1.2 Weighted GraphsRepresentative Points in a RegionThe Non-Negative Constraint4.1.3 Directed Weighted Graphs4.1.4 Terminology4.1.5 Representation4.2 Dijkstra4.2.1 The Problem4.2.2 The AlgorithmProcessing the Current NodeThe Node ListsCalculating Cost-So-Far for Open and Closed NodesTerminating the AlgorithmRetrieving the Path4.2.3 Pseudo-CodeOther Functions4.2.4 Data Structures and InterfacesSimple ListPathfinding ListGraph4.2.5 Performance of Dijkstra4.2.6 Weaknesses4.3 A*4.3.1 The Problem4.3.2 The AlgorithmProcessing the Current NodeThe Node ListsCalculating Cost-So-Far for Open and Closed NodesTerminating the AlgorithmRetrieving the Path4.3.3 Pseudo-CodeChanges from Dijkstra4.3.4 Data Structures and InterfacesPathfinding ListPriority QueuesPriority HeapsBucketed Priority QueuesImplementationsHeuristic FunctionA Heuristic for Any GoalHeuristic Speed4.3.5 Implementation Notes4.3.6 Algorithm Performance4.3.7 Node Array A*Keeping a Node ArrayChecking if a Node Is in Open or ClosedThe Closed List Is IrrelevantThe Open List ImplementationA Variation for Large Graphs4.3.8 Choosing a HeuristicUnderestimating HeuristicsOverestimating HeuristicsEuclidean DistanceCluster HeuristicFill Patterns in A*Quality of HeuristicsDijkstra Is A*4.4 World RepresentationsQuantization and LocalizationGenerationValidity4.4.1 Tile GraphsDivision SchemeQuantization and LocalizationGenerationValidityUsefulness4.4.2 Dirichlet DomainsDivision SchemeQuantization and LocalizationValidityUsefulness4.4.3 Points of VisibilityDivision SchemeQuantization, Localization, and ValidityUsefulness4.4.4 Navigation MeshesDivision SchemeQuantization and LocalizationValidityUsefulnessEdges as Nodes4.4.5 Non-Translational Problems4.4.6 Cost Functions4.4.7 Path SmoothingThe AlgorithmPseudo-CodeData Structures and InterfacesPerformance4.5 Improving on A*4.6 Hierarchical Pathfinding4.6.1 The Hierarchical Pathfinding GraphNodesConnectionsConnection CostsMinimum DistanceMaximin DistanceAverage Minimum DistanceSummary of the Heuristics4.6.2 Pathfinding on the Hierarchical GraphAlgorithmPseudo-CodeData Structures and InterfacesPerformance4.6.3 Hierarchical Pathfinding on Exclusions4.6.4 Strange Effects of Hierarchies on Pathfinding4.6.5 Instanced GeometryAlgorithmInstance GraphWorld GraphPseudo-CodeData Structures and InterfacesImplementation NotesPerformanceWeaknessesSetting Node Offsets4.7 Other Ideas in Pathfinding4.7.1 Open Goal Pathfinding4.7.2 Dynamic Pathfinding4.7.3 Other Kinds of Information Reuse4.7.4 Low Memory AlgorithmsIDA*—Iterative Deepening A*SMA*—Simplified Memory-Bounded A*4.7.5 Interruptible Pathfinding4.7.6 Pooling Planners4.8 Continuous Time Pathfinding4.8.1 The Problem4.8.2 The AlgorithmNodes as StatesThe Size of the GraphHow the Graph Is CreatedWhich Pathfinder4.8.3 Implementation Notes4.8.4 Performance4.8.5 Weaknesses4.9 Movement Planning4.9.1 Animations4.9.2 Movement PlanningThe Planning GraphPlanningInfinite GraphsImplementation Issues4.9.3 Example4.9.4 FootfallsExercisesFigure 4.1Figure 4.2Figure 4.3Figure 4.4Figure 4.5Figure 4.6Figure 4.7Figure 4.8Figure 4.9Figure 4.10Figure 4.11Figure 4.12Figure 4.13Figure 4.14Figure 4.15Figure 4.16Figure 4.17Figure 4.18Figure 4.19Figure 4.20Figure 4.21Figure 4.22Figure 4.23Figure 4.24Figure 4.25Figure 4.26Figure 4.27Figure 4.28Figure 4.29Figure 4.30Figure 4.31Figure 4.32Figure 4.33Figure 4.34Figure 4.35Figure 4.36Figure 4.37Figure 4.38Figure 4.39Figure 4.40Figure 4.41Figure 4.42Figure 4.43Figure 4.44Figure 4.45Figure 4.46Figure 4.47Figure 4.48Figure 4.49Figure 4.50Figure 4.51Figure 4.52Figure 4.53Figure 4.54Figure 4.55
Chapter 5 Decision Making
5.1 Overview of Decision Making5.2 Decision Trees5.2.1 The Problem5.2.2 The AlgorithmDecisionsCombinations of DecisionsDecision ComplexityBranching5.2.3 Pseudo-CodeMultiple Branches5.2.4 On the Website5.2.5 Knowledge Representation5.2.6 Implementation Nodes5.2.7 Performance of Decision Trees5.2.8 Balancing the Tree5.2.9 Beyond the Tree5.2.10 Random Decision TreesPseudo-CodeTiming OutOn the WebsiteUsing Random Decision Trees5.3 State MachinesA Basic State MachineFinite State MachinesThe Game FSM5.3.1 The Problem5.3.2 The Algorithm5.3.3 Pseudo-Code5.3.4 Data Structures and InterfacesTransition ImplementationWeaknesses5.3.5 On the Website5.3.6 Performance5.3.7 Implementation Notes5.3.8 Hard-Coded FSMPseudo-CodePerformanceWeaknesses5.3.9 Hierarchical State MachinesThe ProblemThe AlgorithmExamplesPseudo-CodeImplementation NotesPerformanceOn the Website5.3.10 Combining Decision Trees and State MachinesPseudo-Code5.4 Behavior TreesTypes of TaskA Simple ExampleBehavior Trees and Reactive Planning5.4.1 Implementing Behavior Trees5.4.2 Pseudo-CodePerformanceImplementation NotesNon-Deterministic Composite Tasks5.4.3 DecoratorsGuarding Resources with Decorators5.4.4 Concurrency and TimingWaitingThe Parallel TaskPolicies for ParallelUsing ParallelThe Parallel Task for Condition CheckingIntra-Task Behavior5.4.5 Adding Data to Behavior Trees5.4.6 Reusing TreesInstantiating TreesReusing Whole TreesReusing Sub-trees5.4.7 Limitations of Behavior Trees5.5 Fuzzy Logic5.5.1 A Warning5.5.2 Introduction to Fuzzy LogicFuzzy SetsMembership of Multiple SetsFuzzificationNumeric FuzzificationFuzzification of Other Data TypesDefuzzificationUsing the Highest MembershipBlending Based on MembershipCenter of GravityChoosing a Defuzzification ApproachDefuzzification to a Boolean ValueDefuzzification to an Enumerated ValueCombining FactsFuzzy Rules5.5.3 Fuzzy Logic Decision MakingThe ProblemThe AlgorithmRule StructurePseudo-CodeData Structures and InterfacesImplementation NotesPerformanceWeaknessesCombs Method5.5.4 Fuzzy State MachinesThe ProblemThe AlgorithmPseudo-CodeData Structures and InterfacesImplementation NotesPerformanceMultiple Degrees of TransitionOn the WebsiteFigure 5.1Figure 5.2Figure 5.3Figure 5.4Figure 5.5Figure 5.6Figure 5.7Figure 5.8Figure 5.9Figure 5.10Figure 5.11Figure 5.12Figure 5.13Figure 5.14Figure 5.15Figure 5.16Figure 5.17Figure 5.18Figure 5.19Figure 5.20Figure 5.21Figure 5.22Figure 5.23Figure 5.24Figure 5.25Figure 5.26Figure 5.27Figure 5.28Figure 5.29Figure 5.30Figure 5.31Figure 5.32Figure 5.33Figure 5.34Figure 5.35Figure 5.36Figure 5.37Figure 5.38Figure 5.39Figure 5.40Figure 5.41Figure 5.42Figure 5.43Figure 5.44
5.6 Markov Systems
5.6.1 Markov ProcessesConservative Markov ProcessesIterated ProcessesMarkov Processes in Math and Science5.6.2 Markov State MachineThe AlgorithmDefault TransitionsActionsPseudo-CodeData Structures and InterfacesOn the Website5.7 Goal-Oriented Behavior5.7.1 Goal-Oriented BehaviorGoalsActions5.7.2 Simple SelectionPseudo-CodeData Structures and InterfacesPerformanceWeaknesses5.7.3 Overall UtilityPseudo-CodeData Structures and InterfacesPerformance5.7.4 TimingUtility Involving TimePseudo-CodeData Structures and InterfacesPerformanceCalculating the Goal Change over TimeThe Need for Planning5.7.5 Overall Utility GOAPThe AlgorithmPseudo-CodeData Structures and InterfacesImplementation NotesPerformanceWeaknesses5.7.6 GOAP with IDA*IDA*The HeuristicThe AlgorithmPseudo-CodeData Structures and InterfacesImplementation NotesPerformance5.7.7 Smelly GOBCompound ActionsAction-Based SignalsCharacter-Specific Signals5.8 Rule-Based Systems5.8.1 The ProblemDatabase MatchingCondition–Action RulesDatabase Rewriting RulesForward and Backward ChainingFormat of Data in the DatabaseNotation of Wild Cards5.8.2 The Algorithm5.8.3 Pseudo-Code5.8.4 Data Structures and InterfacesThe DatabaseRulesIF-ClausesItem MatchingDatum MatchingData Group MatchingSummary5.8.5 Implementation Notes5.8.6 Rule ArbitrationFirst ApplicableLeast Recently UsedRandom RuleMost Specific ConditionsDynamic Priority Arbitration5.8.7 UnificationPerformance5.8.8 ReteThe AlgorithmMatching the DatabaseAn ExampleRemoving a FactAdding a FactManaging the UpdateAn Update ExampleOn the WebsitePerformance5.8.9 ExtensionsManaging Large Rule SetsJustification in Expert Systems5.8.10 Where Next5.9 Blackboard Architectures5.9.1 The Problem5.9.2 The AlgorithmExtracting an Action5.9.3 Pseudo-Code5.9.4 Data Structures and InterfacesThe Blackboard Language5.9.5 Performance5.9.6 Other Things Are Blackboard SystemsRule-Based SystemsFinite State Machines5.10 Scripting5.10.1 Language FacilitiesSpeedCompilation and InterpretationExtensibility and IntegrationRe-Entrancy5.10.2 Embedding5.10.3 Choosing a LanguageAdvantagesDisadvantagesOpen-Source Languages5.10.4 A Language SelectionLuaScheme and VariationsPythonOther OptionsTclJavaJavaScriptRuby5.10.5 Rolling Your OwnThe Stages of Language ProcessingTokenizingParsingCompilingInterpretingJust-in-Time CompilingTools: A Quick Look at Lex and Yacc5.10.6 Scripting Languages and Other AI5.11 Action Execution5.11.1 Types of ActionA Single ActionInterrupting ActionsCompound ActionsScripted ActionsAn Aside on Scripts5.11.2 The Algorithm5.11.3 Pseudo-Code5.11.4 Data Structures and Interfaces5.11.5 Implementation NotesDebugging5.11.6 Performance5.11.7 Putting It All TogetherOn the WebsiteFigure 5.45Figure 5.46Figure 5.47Figure 5.48Figure 5.49Figure 5.50Figure 5.51Figure 5.52Figure 5.53Figure 5.54Figure 5.55Figure 5.56Figure 5.57
Chapter 6 Tactical and Strategic AI
6.1 Waypoint Tactics6.1.1 Tactical LocationsA Set of LocationsPrimitive and Compound TacticsWaypoint Graphs and Topological AnalysisContinuous TacticsContext SensitivityPutting It Together6.1.2 Using Tactical LocationsSimple Tactical MovementUsing Tactical Information Like Any Other DataTactical Information in Fuzzy Logic Decision MakingGenerating Nearby WaypointsTactical Pathfinding6.1.3 Generating the Tactical Properties of a WaypointCover PointsVisibility PointsShadow PointsCompound TacticsGenerating Tactical Properties and Tactical Analysis6.1.4 Automatically Generating the WaypointsWatching Human PlayersCondensing a Waypoint Grid6.1.5 The Condensation AlgorithmPseudo-CodeData Structures and InterfacesThe Trade-Off6.2 Tactical Analyses6.2.1 Representing the Game Level6.2.2 Simple Influence MapsSimple InfluenceCalculating the InfluenceLimited Radius of EffectConvolution FiltersMap FloodingApplicationsDealing with Unknowns6.2.3 Terrain AnalysisTerrain DifficultyVisibility Map6.2.4 Learning with Tactical Analyses6.2.5 A Structure for Tactical AnalysesMulti-Layer AnalysesWhen to Combine ThingsBuilding a Tactical Analysis Server6.2.6 Map FloodingThe AlgorithmPseudo-CodeData Structures and InterfacesPerformance6.2.7 Convolution FiltersThe AlgorithmBoundariesPseudo-CodeData Structures and InterfacesImplementation NotesPerformanceFiltersGaussian BlurSeparable FiltersThe Sharpening Filter6.2.8 Cellular AutomataCellular Automata RulesRunning a Cellular AutomatonThe Complexity of Cellular AutomataApplications and RulesArea of SecurityBuilding a City6.3 Tactical Pathfinding6.3.1 The Cost Function6.3.2 Tactic Weights and Concern Blending6.3.3 Modifying the Pathfinding Heuristic6.3.4 Tactical Graphs for Pathfinding6.3.5 Using Tactical Waypoints6.4 Coordinated Action6.4.1 Multi-Tier AIGroup DecisionsGroup MovementGroup PathfindingIncluding the PlayerExplicit Player OrdersStructuring Multi-Tier AI6.4.2 Emergent CooperationScalabilityPredictability6.4.3 Scripting Group ActionsPseudo-CodeData Structures and InterfacesImplementation NotesPerformanceCreating Scripts6.4.4 Military TacticsCase Study: A Fire Team Takes a HouseExercisesFigure 6.1Figure 6.2Figure 6.3Figure 6.4Figure 6.5Figure 6.6Figure 6.7Figure 6.8Figure 6.9Figure 6.10Figure 6.11Figure 6.12Figure 6.13Figure 6.14Figure 6.15Figure 6.16Figure 6.17Figure 6.18Figure 6.19Figure 6.20Figure 6.21Figure 6.22Figure 6.23Figure 6.24Figure 6.25Figure 6.26Figure 6.27Figure 6.28Figure 6.29Figure 6.30
Chapter 7 Learning
7.1 Learning Basics7.1.1 Online or Offline Learning7.1.2 Intra-Behavior Learning7.1.3 Inter-Behavior Learning7.1.4 A Warning7.1.5 Over-Learning7.1.6 The Zoo of Learning Algorithms7.1.7 The Balance of Effort7.2 Parameter Modification7.2.1 The Parameter LandscapeEnergy and Fitness Values7.2.2 Hill ClimbingPseudo-CodeData Structures and InterfacesImplementation NotesPerformance7.2.3 Extensions to Basic Hill ClimbingMomentumAdaptive ResolutionMultiple TrialsFinding the Global Optimum7.2.4 AnnealingDirect MethodPseudo-CodeImplementation NotesPerformanceBoltzmann ProbabilitiesPseudo-CodePerformanceOptimizations7.3 Action Prediction7.3.1 Left or Right7.3.2 Raw Probability7.3.3 String Matching7.3.4 N-GramsN-Grams in Computer SciencePseudo-CodeData Structures and InterfacesImplementation NotesPerformance7.3.5 Window SizeMemory ConcernsSequence Length7.3.6 Hierarchical N-GramsPseudo-CodeData Structures and ImplementationPerformanceConfidence7.3.7 Application in Combat7.4 Decision Learning7.4.1 Structure of Decision LearningWeak or Strong Supervision7.4.2 What Should You Learn?7.4.3 Four Techniques7.5 Naive Bayes ClassifiersPseudo-Code7.5.1 Implementation Notes7.6 Decision Tree Learning7.6.1 ID3AlgorithmEntropy and Information GainMore than Two ActionsNon-Binary Discrete AttributesPseudo-CodeSplit by AttributeEntropyEntropy of SetsData Structures and InterfacesStarting the AlgorithmPerformance7.6.2 ID3 with Continuous AttributesSingle SplitsPseudo-CodeData Structures and InterfacesPerformanceOn the WebsiteMultiple Categories7.6.3 Incremental Decision Tree LearningThe AlgorithmWalk ThroughProblems with ID4Heuristic Algorithms7.7 Reinforcement Learning7.7.1 The Problem7.7.2 The AlgorithmQ-Learning’s Representation of the World Doing LearningHow It WorksExploration StrategyConvergence and EndingOn the Website7.7.3 Pseudo-Code7.7.4 Data Structures and Interfaces7.7.5 Implementation Notes7.7.6 Performance7.7.7 Tailoring ParametersAlpha: The Learning RateGamma: The Discount RateRho: Randomness for ExplorationNu: The Length of WalkChoosing Rewards7.7.8 Weaknesses and Realistic ApplicationsLimits of the AlgorithmApplicationsCase Study: Choosing Tactical Defense LocationsOn the Website7.7.9 Other Ideas in Reinforcement LearningTDOff-Policy and On-Policy AlgorithmsTD in Board Game AINeural Networks for StorageActor–Critic7.8 Artificial Neural NetworksNeural Network Zoology7.8.1 OverviewArchitectureFeedforward and RecurrenceNeuron AlgorithmLearning Rule7.8.2 The ProblemWhat about Decision Tree Learning?7.8.3 The AlgorithmInitial Setup and FrameworkFeedforwardBackpropagationThe Error TermThe Gain7.8.4 Pseudo-Code7.8.5 Data Structures and Interfaces7.8.6 Implementation CaveatsOn the Website7.8.7 Performance7.8.8 Other ApproachesRadial Basis FunctionWeakly Supervised LearningHebbian LearningExercisesFigure 7.1Figure 7.2Figure 7.3Figure 7.4Figure 7.5Figure 7.6Figure 7.7Figure 7.8Figure 7.9Figure 7.10Figure 7.11Figure 7.12Figure 7.13Figure 7.14Figure 7.15Figure 7.16Figure 7.17Figure 7.18Figure 7.19Figure 7.20Figure 7.21Figure 7.22Figure 7.23Figure 7.24Figure 7.25
Chapter 8 Board Games
8.1 Game Theory8.1.1 Types of GamesNumber of PlayersPlies, Moves, and TurnsThe Goal of the GameInformationApplying Algorithms8.1.2 The Game TreeBranching Factor and DepthTransposition8.2 Minimaxing8.2.1 The Static Evaluation FunctionRange of the FunctionCombining Scoring FunctionsSimple Move Choice8.2.2 Minimaxing8.2.3 The Minimaxing AlgorithmPseudo-CodeData Structures and InterfacesMore than Two PlayersPerformance8.2.4 NegamaxingNegamax and the Static Evaluation FunctionPseudo-CodeData Structures and InterfacesPerformanceImplementation Notes8.2.5 AB PruningAlpha PruningBeta PruningAB NegamaxPseudo-CodeData Structures and InterfacesPerformance8.2.6 The AB Search WindowMove OrderAspiration Search8.2.7 NegascoutPseudo-CodeData Structures and InterfacesPerformanceMove Ordering and NegascoutPrincipal Variation Search8.3 Transposition Tables and Memory8.3.1 Hashing Game StatesZobrist KeysHash ImplementationIncremental Zobrist HashingThe Game Class, Revisited8.3.2 What to Store in the Table8.3.3 Hash Table Implementation8.3.4 Replacement Strategies8.3.5 A Complete Transposition TablePerformanceImplementation Notes8.3.6 Transposition Table IssuesPath DependencyInstability8.3.7 Using Opponent’s Thinking Time8.4 Memory-Enhanced Test Algorithms8.4.1 Implementing TestPseudo-CodeTransposition Table8.4.2 The MTD AlgorithmMTD VariationsMemory Size8.4.3 Pseudo-CodePerformance8.5 Opening Books and Other Set Plays8.5.1 Implementing an Opening BookOpening Book in the Evaluation Function8.5.2 Learning for Opening Books8.5.3 Set Play BooksEnding Database8.6 Further Optimizations8.6.1 Iterative DeepeningMTD ImplementationHistory Heuristic8.6.2 Variable Depth ApproachesExtensionsQuiescence Pruning8.7 Turn-Based Strategy Games8.7.1 Impossible Tree SizeDivide and ConquerHeuristics8.7.2 Real-Time AI in a Turn-Based GameExercisesFigure 8.1Figure 8.2Figure 8.3Figure 8.4Figure 8.5Figure 8.6Figure 8.7Figure 8.8Figure 8.9Figure 8.10Figure 8.11Figure 8.12
Part III Supporting Technologies
Chapter 9 Execution Management
9.1 Scheduling9.1.1 The SchedulerFrequenciesPhasePseudo-CodeImplementation NotesPerformanceDirect AccessPseudo-CodeData Structures and InterfacesPerformancePhase QualityAutomatic PhasingWright’s MethodAnalytic MethodSingle Task Spikes9.1.2 Interruptible ProcessesThreadsSoftware ThreadsMicro-ThreadsHyper-Threads and Multiple CoresQuality of Service9.1.3 Load-Balancing SchedulerPseudo-CodeData StructuresPerformance9.1.4 Hierarchical SchedulingData Structures and InterfacesBehavior Selection9.1.5 Priority SchedulingPseudo-CodePerformanceOther PoliciesPriority Problems9.2 Anytime Algorithms9.3 Level of Detail9.3.1 Graphics Level of Detail9.3.2 AI LODImportance Values9.3.3 Scheduling LODFrequency SchedulersPriority SchedulersCombined Scheduling9.3.4 Behavioral LODEntry and Exit ProcessingBehavior CompressionHysteresisChoose Any Available BehaviorChoose the First Available Behavior in the ListSelect the Most Central BehaviorSelect the Available Behavior with the Smallest RangeFallback BehaviorsPseudo-CodeData Structures and InterfacesImplementation NotesPerformance9.3.5 Group LODProbability Distributions9.3.6 In SummaryExercisesFigure 9.1Figure 9.2Figure 9.3Figure 9.4Figure 9.5Figure 9.6Figure 9.7Figure 9.8Figure 9.9Figure 9.10
Chapter 10 World Interfacing
10.1 Communication10.2 Getting Knowledge Efficiently10.2.1 PollingPolling Stations10.2.2 EventsEvent Managers10.2.3 Determining What Approach to Use10.3 Event Managers10.3.1 ImplementationPseudo-CodeData Structures and InterfacesPerformanceImplementation Notes10.3.2 Event CastingBroadcastingNarrowcastingCompromising10.3.3 Inter-Agent Communication10.4 Polling Stations10.4.1 Pseudo-Code10.4.2 Performance10.4.3 Implementation Notes10.4.4 Abstract Polling10.5 Sense Management10.5.1 Faking It10.5.2 What Do We Know?Polling and Notification Revisited10.5.3 Sensory ModalitiesSightSpeedSight ConeLine of SightDistanceBrightnessDifferentiationHearingTouchSmellFantasy Modalities10.5.4 Region Sense ManagerThe AlgorithmPseudo-CodeData Structures and InterfacesPerformanceCamouflage and ShadowsWeaknesses10.5.5 Finite Element Model Sense ManagerFinite Element ModelsThe Sense GraphSightThe AlgorithmSightsSoundSmellCalculating Intensity from Node to NodeIterative AlgorithmDispatchingOn the WebsiteImplementation NotesWeaknessesContent CreationExercisesFigure 10.1Figure 10.2Figure 10.3Figure 10.4Figure 10.5Figure 10.6Figure 10.7Figure 10.8Figure 10.9Figure 10.10
Chapter 11 Tools and Content Creation
11.0.1 Toolchains Limit AI11.0.2 Where AI Knowledge Comes from11.1 Knowledge for Pathfinding and Waypoint Tactics11.1.1 Manually Creating Region DataTile GraphsDirichlet DomainsNavigation MeshesBounded Regions11.1.2 Automatic Graph Creation11.1.3 Geometric AnalysisCalculating CostsCalculating ConnectionsPoint-Based RepresentationsArbitrary Bounding RegionsLimitations of Visibility ApproachesMesh RepresentationsCalculating Nodes11.1.4 Data MiningCalculating NodesCalculating ConnectionsCharacter MovementLimitationsOther Representations11.2 Knowledge for Movement11.2.1 ObstaclesWallsObstacle Representation11.2.2 High-Level Staging11.3 Knowledge for Decision Making11.3.1 Object Types11.3.2 Concrete Actions11.4 The Toolchain11.4.1 Data-Driven Editors11.4.2 AI Design ToolsScripting ToolsState Machine Designers11.4.3 Remote Debugging11.4.4 Plug-InsExercisesFigure 11.1Figure 11.2Figure 11.3Figure 11.4Figure 11.5
Part IV Designing Game AI
Chapter 12 Designing Game AI
12.1 The Design12.1.1 Example12.1.2 Evaluating the BehaviorsExample12.1.3 Selecting TechniquesExample12.1.4 The Scope of One Game12.2 Shooters12.2.1 Movement and Firing12.2.2 Decision Making12.2.3 Perception12.2.4 Pathfinding and Tactical AI12.2.5 Shooter-Like GamesPlatform and Adventure GamesMMOGs12.3 Driving12.3.1 Movement12.3.2 Pathfinding and Tactical AI12.3.3 Driving-Like Games12.4 Real-Time Strategy12.4.1 Pathfinding12.4.2 Group Movement12.4.3 Tactical and Strategic AI12.4.4 Decision Making12.5 Sports12.5.1 Physics Prediction12.5.2 Playbooks and Content Creation12.6 Turn-Based Strategy Games12.6.1 Timing12.6.2 Helping the PlayerFigure 12.1Figure 12.2Figure 12.3Figure 12.4Figure 12.5Figure 12.6Figure 12.7
Chapter 13 AI-Based Game Genres
13.1 Teaching Characters13.1.1 Representing Actions13.1.2 Representing the World13.1.3 Learning MechanismNeural Network ArchitectureObservational LearningMind-Reading for Observational LearningFeedback Learning13.1.4 Predictable Mental Models and Pathological StatesInstinctsThe Brain Death of a Character13.2 Flocking and Herding Games13.2.1 Making the Creatures13.2.2 Tuning Steering for Interactivity13.2.3 Steering Behavior Stability13.2.4 Ecosystem DesignSize of the Food ChainBehavior ComplexitySensory LimitsMovement RangePutting It All TogetherFigure 13.1Figure 13.2Figure 13.3
References
A.1 Books, Periodicals, and PapersA.2 Games

Content preview from Artificial Intelligence for Games, 2nd Edition

Chapter 8

Board Games

The earliest application of AI to computer games was as opponents in simulated versions of common board games. In the West, Chess is the archetypal board game, and the last 40 years have seen a dramatic increase in the capabilities of Chess-playing computers.

In the same time frame, other games such as Tic-Tac-Toe, Connect Four, Reversi (Othello), and Go have been studied, and AI of various qualities has been created.

The AI techniques needed to make a computer play board games are very different than the others in this book. For the real-time games that dominate the charts, this kind of AI only has limited applicability. ...

Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.

Read now

Unlock full access

More than 5,000 organizations count on O’Reilly

O’Reilly covers everything we've got, with content to help us build a world-class technology community, upgrade the capabilities and competencies of our teams, and improve overall team performance as well as their engagement.

Julian F.

Head of Cybersecurity

I wanted to learn C and C++, but it didn't click for me until I picked up an O'Reilly book. When I went on the O’Reilly platform, I was astonished to find all the books there, plus live events and sandboxes so you could play around with the technology.

Addison B.

Field Engineer

I’ve been on the O’Reilly platform for more than eight years. I use a couple of learning platforms, but I'm on O'Reilly more than anybody else. When you're there, you start learning. I'm never disappointed.

Amir M.

Data Platform Tech Lead

I'm always learning. So when I got on to O'Reilly, I was like a kid in a candy store. There are playlists. There are answers. There's on-demand training. It's worth its weight in gold, in terms of what it allows me to do.

Mark W.

Embedded Software Engineer

Paradigms of Artificial Intelligence Programming

Publisher Resources

ISBN: 9780123747310

Cloud Computing

Data Engineering

Data Science

AI & ML

Programming Languages

Software Architecture

IT/Ops

Security

Design

Business

Soft Skills

Artificial Intelligence for Games, 2nd Edition

by Ian Millington, John Funge

Board Games

Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.