Automated GenerationTactics for Strategy Games Machine Learning in

Automated GenerationTactics for Strategy Games Machine Learning in

Automated GenerationTactics for Strategy Games Machine Learning in Computer Games Original: Marc Ponsen Update: H. Munoz-Avila Game AI: The Last Frontier Progress in graphics and sound has slowed in recent years Now, more than ever, good game play is at the forefront and AI is one of the most critical components (Rabin 2004). Interactive computer games provide a rich environment for incremental research on humanlevel AI Populating games with realistic, humanlevel characters will lead to fun, challenging games with great game play (Laird 2000). 2 Previous class: Large Decision Space Variables Civilization-wide variables Civilization-wide variables o oN: Number of civilizations encountered N: Number of civilizations encountered o o D: Number of diplomatic states (that you can have with an opponent)

D: Number of diplomatic states (that you can have with an opponent) o o G: Number of government types available to you G: Number of government types available to you o o R: Number of research advances that can be pursued R: Number of research advances that can be pursued o o I: Number of partitions of income into entertainment, money, & research I: Number of partitions of income into entertainment, money, & research U: #Units U: #Units o o L: Number of locations a unit can move to in a turn L: Number of locations a unit can move to in a turn C: #Cities C: #Cities o o Z: Number of citizens per city Z: Number of citizens per city o o S: Citizen status (i.e., laborer, entertainer, doctor) S: Citizen status (i.e., laborer, entertainer, doctor) o o B: Number of choices for city production B: Number of choices for city production Decision complexity per turn (for a typical game state) N U

Z C O(D O(DNGRI*L GRI*LU*(S *(SZB) B)C)) ; ;this thisignores ignoresboth bothother othervariables variablesand anddomain domainknowledge knowledge ooThis becomes large with the number of units and cities This becomes large with the number of units and cities oo Example: N=3; D=5; G=3; R=4; I=10; U=25; L=4; C=8; Z=10; S=3; B=10 Example: N=3; D=5; G=3; R=4; I=10; U=25; L=4; C=8; Z=10; S=3; B=10 oo Size of decision space (i.e., possible next states): 2.5*106565(in one turn!) Size of decision space (i.e., possible next states): 2.5*10 (in one turn!) oo Comparison: Decision space of chess per turn is well below 140 (e.g., 20 at first move) Comparison: Decision space of chess per turn is well below 140 (e.g., 20 at first move) (David W. Aha, NRL)

So what can AI do? Some tasks are solved: pathfinding Other tasks can be solved well with standard techniques: FSM Tackle tasks of the problem that can be hard to solve otherwise Example: Automated Generation of tactics Which AI techniques? Requirements: must be General; Independent of details Must work on any map Must work on any opponent Must work with different kinds teammates 5 Example Task: Strategic Decision Making with Planning (Alternative 1) UT task: Domination

Strategy: secure most locations 1. Declarative language for expressing conditions Solution to 1: call external function UT action: move Bot1 to (implemented with location B FSMs) Solution to 2: use 2. Dealing with Java Bots to represent contingencies whileactions (FSMs) Bots are executing Planning requires less engineering actions requirements than FSMs but can still require lots of human effort Alternative 2: Heuristic evaluation Divide the map into areas (determining the actual

partition can be done with FSMs) For each area assign a heuristic value Send bots to region with highest heuristic value Alternative 2: Heuristic evaluation GOOD (0.9 score) F(area) = w1*friendlyDeaths(zone) + w2*ownership(zone)+ BAD (0.2 score) OK (e.g., 0.6 score) Heuristic evaluation has proved very useful (game trees, planning, A*,) Alternative 3: Learning The process of learning in games generally implies the adaptation of behavior for opponent players in order to

improve performance Self-correction Creativity Automatically fixing exploits Responding intelligently to new situations Scalability Better entertainment for strong players Better entertainment for weak players 9 Offline vs. Online Learning

Online during gameplay Adapt to player tactics Avoid repetition of mistakes Requirements: computationally cheap, effective, robust, fast learning (Spronck 2004) Offline - before the game is released Devise new tactics Discover exploits 10 Some Machine Learning Techniques 11 Alternative 3.1: Learning Decision Assumes you have many Tree of Tactics game traces (visualized as a table)

Decision Tree induction If owning locations 1 and 2, and 3 then defend locations 1, 2, and 3 Assumes game designer has identified classes or categories of desired behaviors (e.g., defend locations) Induces a tree that indicates under which conditions a particular behavior is desirable Alternative 3.2: Reinforcement Learning STATES ACTIONS good action bad action

Best action identified so far For state EFE (Enemy controls 2 DOM points) OK But that DOM game is kind of simple Bots can be be at any location Maps are 70*70 (M*M) Capture occurs only after 5 ticks of getting to a dom location (D) B Bots have health points [0..10] Horde Bonus : For each teammate within 4 squares: add 3 to damage dealt For each teammate within 8 squares: add 2 to damage dealt For each teammate within 12 squares: add 1 to damage dealt spawn point (S) is owned by the team controlling its nearest domination

point Number of states O(M2 * 6 * D * 11 * B * S) AI uses abstracted the states to O(D* B) RL application: Dynamic Scripting for Wargus Dynamic Scripting (DS) is an online learning technique inspired by RL Original implementation of DS (Spronck 2004) in the Computer RolePlaying Game NeverWinter Nights 15 Dynamic Scripting team controlled by computer Rulebase A generate script Script A scripted

control Rulebase B Script B scripted control human control A Combat weight updates generate script team controlled by human player B human

control 16 Dynamic Scripting and Requirements Computationally Cheap - Script generation and weight updates once per encounter Effective - Rules are manually designed Robust - Reward/penalty system Fast Learning Experiments showed that DS is able to adapt fast to an unchanging tactic 17 Wargus: A Real-Time Strategy Game d n a e t a t s e g

r a l : ! x e e c l a p Com ecision sp n o i t a d iz l i v i C s )

a e M g r O a D l s n a a (Not larger th but 18 Dynamic Scripting in Wargus Different rulebases for different game states State transition on constructing a building that allows new units or new research AiNeed(AiBarracks) AiResearch(AiUpgradeArmor1) AiNeed(AiWorker)

AiForce(1, {AiSoldier, 9}) AiWaitForce(1) AiAttackWithForce(1) 19 Domain Knowledge in Wargus Abstraction of the state space Abstraction: States in Wargus are manually predefined and represent game phases that inform the AI on the possible tactics during a game The possible tactics during a game mainly depend on available units and technology The availability of units and technology depends on the buildings the player possesses Therefore, the utility of tactics depends on the available buildings 20 Domain Knowledge in Wargus Abstraction of the decision space

A library of tactics for each state Tactics are action sequences consisting of 1 or more game actions (e.g., building, combat, research etc.) State 1 Knowledge base State n Knowledge base Construct City Center Construct Keep Train 4 workers Train 30 workers Defend with 1 Soldier Construct Blacksmith

Defend with 1 Knight Attack with 10 Knights Research better Weapons Attack with 2 Soldiers - Research magic spell Defend with 2 Mages State 20 Knowledge base Construct Castle Train 30 workers Attack with 10 Knights Research magic spell Defend with 2 Mages Construct Guard tower 21 Domain Knowledge in Wargus y l

t n e ci i f f e ) n i 4 0 w 0 2 o t . l s a t n e r a

n e e l s g n o n i P t ( p ! i s r t c n S e c n Decision abstraction i

o p m Dyna t static op s n i a ag ex l p m co State abstraction 22 Rules in Rulebases 12 Build rules 9 Research rules 4 Economy rules 25 Combat rules AiNeed(AiBarracks)

AiResearch(AiUpgradeArmor1) AiNeed(AiWorker) AiForce(1, {AiSoldier, 9}) AiWaitForce(1) AiAttackWithForce(1) 23 Tactics Two `balanced tactics Small Balanced Land Attack (SBLA) Large Balanced Land Attack (LBLA) Two `rush tactics Soldier Rush (SR) Knight Rush (KR) 24 Dynamic Scripting Test

Dynamic player (using dynamic scripting) plays 100 consecutive games against static player Randomisation Turning Point (RTP): First game that dynamic player outperforms static player with 90% probability according to a randomisation test (Cohen, 1995) 25 Dynamic Scripting RTP Results Tactic Tests Low High Avg. Med. >100 Won SBLA

31 18 99 50 39 0 59.3 LBLA 21 19 79 49 47

0 60.2 SR 10 10 1.2 KR 10 10 2.3 Dynamic Scripting is WORKS! unable Ittoadapts adapt to efficiently the against SBLA

optimized tactics andSR LBLA and KR 26 Wargus Demo 27 Solution 3.3: Evolutionary Computation Dynamic Scripting was unable to cope with some tougher static opponents (Ponsen et al. 2004) Can we increase the efficiency of Dynamic Scripting (i.e., speed up learning and win more games) by improving the domain knowledge? Our proposed solution: revision of tactic library with Now we evolutionary computation:

Semi-Automatic domain knowledge revision Automatic domain knowledge revision are talking! 28 Semi-Automatic Improvement of Domain-Knowledge nveedd g o i r s ep dim y l l y aall brraarryy Dynamic Scripting u n u

a li b m mantaaccttiicc li Generate Script t Knowledge Base Adaptive Game AI Performance Evaluation Compete against static scripts Training script 1 Training script 2 . Training script n Counter Strategy 1 Counter Strategy 2 . Counter Strategy n

Knowledge Base Revision Evolutionary Algorithm Manually Extract Tactics from Evolved Counter Strategies Evolve Domain Knowledge 29 Evaluation Semi-Automatic Approach Benefits Evolved tactics can be used to improve domain knowledge used by adaptive AI (Ponsen et al. 2004) Dynamic scripting converged to solution (i.e., learns to win) two times faster against medium-skilled opponents Overall 40% more games are won Limitations

Time consuming Domain knowledge not optimal (due to human factor) Strong tactics not recognized in evolved scripts Inferior tactics added to knowledge base 30 Automatic Knowledge Acquisition for Dynamic Scripting (AKADS) auto ted a r e gen y l l a c ra r y mati c lib i

t c a tKnowledge Base Adaptive Game AI Training script 1 Training script 2 . Training script n Dynamic Scripting Generate Script Counter Strategy 1 Counter Strategy 2 . Counter Strategy n Knowledge Base Revision Evolutionary Algorithm Automatically Extract Tactics from

Evolved Counter Strategies Evolve Domain Knowledge 31 Evolutionary Computation Idea: Biological analogy on how populations of species evolve over generations Step 1: start with a population (each member is a candidate solution) Step 2: Create the next generation by considering evolutionary operations on the population from the previous generation (e.g., mutation) and a fitness function (only the more fit get to contribute to the next generation) Continue the process until a certain condition is reached Evolving Domain Knowledge Input: training scripts Manually designed scripts Dynamic or evolutionary scripts

Output: chromosomes representing candidate solutions (i.e., winning counter-strategies) 33 Chromosome Chromosome Start Start State 1 State 2 State State marker Gene Gene ID Parameter 1 Parameter 2

S 1 C1 2 State number x 5 Gene 1.1 State 1 def B Full game State m End Gene x.1 4

Gene 1.2 Gene x.2 script Gene x.n command Parameter p S 3 E 8 Gene 3.1 R 15

Gene 3.2 State 3 B 3 Gene 3.3 S 4 Automatically Extracting Tactics Use states to distinguish tactics in chromosome! All genes grouped in a specific state constitutes a tactic that will be inserted into the corresponding knowledge base Genetic Operators State Crossover

Gene Replace Mutation Gene Biased Mutation Randomization Evaluation of Automatic Approach Benefits Less time consuming compared to other approaches (knowledge base automatically generated) Qualitatively better domain knowledge compared to semi-automatic improved knowledge base: Overall 15% more games are won Converged to solution (i.e., learns to win) two times faster against medium-skilled opponents Dynamic Scripting learned to cope with strong opponents Limitations Danger of knowledge base over fitting Conclusion

Game AI has used only a fraction of the AI techniques We talked today about strategy games but principles such as state abstraction, learning, heuristic evaluation can be applied to many game genres: racing games, sport games, FPS We have seen a few examples of fielded applications in games The potential is there References Ponsen, M. and Spronck, P. (2004). Improving Adaptive Game AI with Evolutionary Learning. Computer Games: Artificial Intelligence, Design and Education (CGAIDE 2004). pp. 389-396. University of

Wolverhampton. Spronck, P., Sprinkhuizen-Kuyper, I. and Postma. E. 2004. Online Adaptation of Game Opponent AI with Dynamic Scripting. International Journal of Intelligent Games and Simulation, Vol. 3, No. 1, University of Wolverhampton and EUROSIS, pp. 4553. Ponsen, M., Munoz-Avila, H., Spronk, P., Aha, D. (2007) Knowledge Acquisition for Adaptive Game AI. To appear in: Science of Computer Programming. Special Issue on Computer Games. Elsevier. Ponsen, M., Munoz-Avila, H., Spronk, P., Aha, D. (2006) Automatically generating game tactics with evolutionary learning. To appear in: AI Magazine. AAAI Press. Ponsen, M., Munoz-Avila, H., Spronck, P., and Aha, D. Automatically Acquiring Domain Knowledge For Adaptive Game AI Using Evolutionary Learning . Proceedings of the Seventeenth Innovative Applications of Artificial Intelligence Conference (IAAI05-05). AAAI Press.

Recently Viewed Presentations

  • Mexican Independence from Spain - WFISD

    Mexican Independence from Spain - WFISD

    Mexico's Independence. 80,000 people joined the fight, but the army was soon defeated by the Spanish. Hidalgo was captured and executed in 1811. Mexicans continued to fight for independence over the next decade. 1821: Mexico gained independence from Spain. Mexico...
  • Chapter 1 Introduction to Business Analytics

    Chapter 1 Introduction to Business Analytics

    Shows the impact that variation in a model input has on some output while holding all other inputs constant. ... Newsvendor problem. One-way data table. ... Chapter 1 Introduction to Business Analytics
  • License Management Use CasesFrankfurt releaseSamuli Kuusela ...

    License Management Use CasesFrankfurt releaseSamuli Kuusela ...

    Presented already once in: Use Case SC, Modeling SC, Use Case Realization mtg. Development of the Use Cases will continue in the Use Case SC. Agreed to present in Architecture SC. Agreed to align with the on-going license mgmt model...
  • Reconstructing Software Architectures CSSE 477 (SAD Two*) Software

    Reconstructing Software Architectures CSSE 477 (SAD Two*) Software

    Reconstructing Software Architectures CSSE 477 (SAD Two*) Software Architecture Week 4, Day 4, including Ch 10 in Bass's book How's Project 3 going?
  • Presentation Title - safety.networkrail.co.uk

    Presentation Title - safety.networkrail.co.uk

    Fatigue Improvement Programme - World Sleep Day. At Network Rail, we recognise the importance of sleep. Sleep is also very closely linked with Fatigue. Network Rail has a national Fatigue Improvement Programme, looking at managing fatigue risk of our entire...
  • 06.01 Classification Project Classifying Birds The 6.01 lesson

    06.01 Classification Project Classifying Birds The 6.01 lesson

    Here's a reminder of how a cladogram can look: Blue Jay Robin Cardinal Canary Pelican Cladogram #1 Describe the physical traits your birds had in common with one another in your taxonomy chart. Break down your descriptions by taxa (kingdom,...
  • Eco-Column Data Tables & Instructions for Weekly Observations

    Eco-Column Data Tables & Instructions for Weekly Observations

    Dry the watch glasses. Wednesday. If you did not complete Day/Week 1 observations, finish those first. Once Day/Week 1 observations are complete, scroll to the next slide for your vocabulary assignment. ... no sign of earthworm added watertoday, 1 earthworm...
  • Rotation Schedule - bcsc.k12.in.us

    Rotation Schedule - bcsc.k12.in.us

    Open to page 86 in your Treasures book. Taking turns with your group members, read aloud Meet Rosina with your group. The last page is 106. When you have finished the story, work together complete the comprehension activities with your...