Evolving Build Orders in Starcraft
1 like580 views
As did board games like Chess in the past, real-time strategy games are becoming popular test applications for real-time AI research. In this paper we approach the real-time planning problem by considering build-order optimization in real-time strategy games. This problem class can be formulated as a resource accumulation and allocation problem where an agent has to decide which objects to produce at what time in order to meet one of several goals: either maximizing the number of produced objects in a given time period or producing a certain number of objects as fast as possible. We propose a system using genetic programming which optimizes build orders in the commercial real time strategy game Starcraft息.
Evolving Build Orders in Starcraft
- 1. Evolving Build Orders In Starcraft Matthieu Macret
- 2. Matthieu Macret Msc student Starcraft Science 鍖ction real-time strategy game (RTS) (1998) 11 million copies sold worldwide E-sport in Korea with professional players 2
- 3. Matthieu Macret Msc student Starcraft basis Gather resources (crystal and gas) Building your base Building your army Manage your army Destroy the enemy 3
- 4. Matthieu Macret Msc student Build order (BO) Sequence of actions in the game: Build a command center Build a SCV Build a barrack Build a marine ... 4
- 5. Matthieu Macret Msc student Build order (BO) Equivalent to opening strategies in chess (ex: English Opening, Sicilian Defence, Ruy Lopez...) Determine your gameplay style for the rest of the game. Context: Early stage of the game when there is no interaction with the enemy. (5-10 鍖rst min) 5
- 6. Matthieu Macret Msc student Chess / Starcraft Complexity 6 Chess Starcraft (Terran) Number of different pieces Maximum number of pieces Size of the environment 6 33 16 200 8 x 8 128 x 128
- 7. Matthieu Macret Msc student Complexity Each unit/building has: requirements (other buildings, units...), cost (resources, supply, time) 7
- 8. Matthieu Macret Msc student Related work 束 A 鍖rst Look at Build Order Optimization in Real-Time Strategy Games 損, Buro (2006) 束 Build Order Optimization for Real-Time Strategy Game 損,Wei and Sun (2007) 束 Using Automated Replay Annotation for Case-Based Planning in Games損,Weber (2010) 束 Automatically generating game tactics via evolutionary learning 損, Ponsen (2006) 8
- 9. Matthieu Macret Msc student Optimizing build orders Using genetic programming. Intelligent way to search the space of the BO Using game mechanics. Do an objective evaluation of the BO. Time, resources optimization but also other criteria. Ex: 10 marines at t=2min, maximizing defense and upgradeWeapon1 completed 9
- 10. Matthieu Macret Msc student Genetic programming Open Beagle Framework C++ (faster than JAVA...) Everything is customizable Support for distributed computing environments 10
- 11. Matthieu Macret Msc student Build Order representation 11 A1 A2 A3 T
- 12. Matthieu Macret Msc student Genetic programming principle 12 Population of BO - Generation n Population of BO - Generation n+1 mutationselection subtitutioncrossover
- 13. Matthieu Macret Msc student Evaluation 13 Individual Evaluator Genotype Primitive Primitive Primitive Build Order Converter Fitness score Build order Genotype Optimization criteria
- 14. Matthieu Macret Msc student Evaluator 14 Evaluator Starcraft Simulator Fitness function Game State Units Buildings Statistics Upgrades Resources
- 15. Matthieu Macret Msc student Starcraft Simulator 15 Build Order Simulator - C++ , CLIPS Initial game state Build Order Game state in function of time
- 16. Matthieu Macret Msc student CLIPS C Language Integrated Production System Rule engine Similar to language LISP Developed to be easily embeddable in any program 16
- 17. Matthieu Macret Msc student Facts at initialization 17 f-1 (time 0) f-2 (resources crystal 50) f-3 (resources gas 0) f-4 (supply 4) f-5 (supplyMax 10) f-8 (waiting commandCenter 0) f-9 (available commandCenter 1) f-56 (available SCV 1) f-57 (waiting SCV 0) f-92 (upgrade infantryWeapons1 0)
- 18. Matthieu Macret Msc student Rule 2 rules by unit, building or upgrade: one rule to put the order in queue. one rule to execute the order. 1 rule to update the time. 18
- 19. Matthieu Macret Msc student Rule system Some 鍖gures about the system: 135 initialization facts 139 rules 19
- 20. Matthieu Macret Msc student 20 Initialize the rule system Add build order to the fact list Update time Run the rule system Until t=tmax Game State File
- 21. Matthieu Macret Msc student Game state 鍖le 21
- 22. Matthieu Macret Msc student Fitness function 22 Game State File Fitness function Fitness score
- 23. Matthieu Macret Msc student Examples: Fitness function 23 Goal: Have 10 SCV at t=30s Number of SCV at t=30_________________ 10
- 24. Matthieu Macret Msc student Fitness function examples Maximizing resources Have at least 10 marines Have a barrack at t=44s Minimizing number of orders 24 resources at tmax Nbr of marines at tmax_________ 10 Nbr of barracks at t=44 Nbr of orders at tmax 1 ________________ XXX Goal:
- 25. Matthieu Macret Msc student Experiment Goal: Have 10 SCV at t=300s 25
- 26. Matthieu Macret Msc student Actions in Starcraft Build Supply Depot Build SCV Build Marines Build Barracks 26
- 27. Matthieu Macret Msc student Genetic programming parameters Population size = 200 Number of generation = 50 Max size of a BO = 25 27
- 28. Matthieu Macret Msc student Fitness function 28 Goal: Have 10 SCV at t=300s Number of SCV at t=300 _________________ 10
- 30. Matthieu Macret Msc student Best individual buildSCV buildSupplyDepot buildSCV buildSupplyDepot buildSCV buildSCV buildSCV buildSCV buildSCV... (until 22 X buildSCV) 30
- 31. Matthieu Macret Msc student Observations The system learnt that it is necessary to build a supply depot to overcome the limit of eight units. The system learnt that building a barrack or a marine is useless. The goal is achieved ! 31
- 32. Matthieu Macret Msc student Conclusion Using genetic programming: Intelligent way to search the space Learning effect Easy to set the optimization criteria BUT: no real-time (long to evolve) only interesting for the early stages of the game 32
- 33. Matthieu Macret Msc student Future work Experimenting with the whole rule system and a more complex 鍖tness functions. Developing an user interface to set the optimization criteria. Exploring computer creativity in real time strategy game. 33