What is Starcraft?
AIIDE 2010 competition (AAAI)
Our approach
Code & Results

Bayesian programming applied to StarcraftA summer project experiment:
or why we can’t come to the beachGabriel Synnaeve
University of Grenoble / E-Motion @ INRIA

December 1, 2010

1/38

What is Starcraft?
AIIDE 2010 competition (AAAI)
Our approach
Code & Results

12

34What is Starcraft?
“Best” RTS in the world
Starcraft 101
An interesting problem
AIIDE 2010 competition (AAAI)
4 Tournaments
Tournament 1
Tournament 4
Our approach
Bayesian programmingHigh level model
Units as Bayesian robots
Code & ResultsInterfacing with Starcraft
Implementation
Results at AIIDE 2010
2/38

What is Starcraft?
AIIDE 2010 competition (AAAI)
Our approach
Code & Results“Best” RTS in the world
Starcraft 101
An interesting problem

Starcraft: Broodwar
Starcraft (January 1998) + Broodwar (exp., November 1998)

3/38

What is Starcraft?
AIIDE 2010 competition (AAAI)
Our approach
Code & Results“Best” RTS in the world
Starcraft 101
An interesting problem

RT what?
Real Time Strategy game

4/38

What is Starcraft?
AIIDE 2010 competition (AAAI)
Our approach
Code & Results“Best” RTS in the world
Starcraft 101
An interesting problem

Pro gaming and competitions
eSports, sponsorship, tournaments’ dotations, salaries (Korea)

5/38

What is Starcraft?
AIIDE 2010 competition (AAAI)
Our approach
Code & Results“Best” RTS in the world
Starcraft 101
An interesting problem

Starcraft in numbers
11 years of competitive play
200 to 300 actions per minute amongst pro gamers
10 millions licenses sold (4.5 in South Korea)$60000 average pro gamer salary (average SouthKorean: $16000)
1/4 TV channels are displaying Starcraft games in Korea
160 BPM: reached rates of pro gamers hearts
3 millions licenses sold for Starcraft II in 1 month (1million in 24 hours, released July 27, 2010)
4.9 millions South Koreas still playing SC:Broodwar(August 2010)

6/38

What is Starcraft?
AIIDE 2010 competition (AAAI)
Our approach
Code & Results“Best” RTS in the world
Starcraft 101
An interesting problem

Micro/Macro

7/38

What is Starcraft?
AIIDE 2010 competition (AAAI)
Our approach
Code & Results“Best” RTS in the world
Starcraft 101
An interesting problem

Macro - Economy and Strategy
4 resources:
Minerals: basic resource, needed for every production
Gas: advanced resource, needed for “high tech”
building/units/research/upgrades
Food cap: needed to increase it to produce units
Time: everything takes time to build→ Develop tech tree
→ Develop production capacity→ Produce units→ Enhance units

8/38

What is Starcraft?
AIIDE 2010 competition (AAAI)
Our approach
Code & Results“Best” RTS in the world
Starcraft 101
An interesting problem

9/38

What is Starcraft?
AIIDE 2010 competition (AAAI)
Our approach
Code & Results“Best” RTS in the world
Starcraft 101
An interesting problem

Micro - Tactics and Unit Management
Micro-management is using your units as close as possible tothe maximum outcome you can have with them.
Basically, units have:
Hit points

Basics:Size

Focus fire weak units / highdamage units

Speed

Retreat wounded units

Can fly (or not)Cast spells

Energy points

Placement (short time tactics)

Spells10/38

What is Starcraft?
AIIDE 2010 competition (AAAI)
Our approach
Code & Results“Best” RTS in the world
Starcraft 101
An interesting problem

Toy problem?
Multiplayer video games AI:
Simulated: no sensors problems
Multiplayer: real humans
Closed and rich worlds⇒ Good in-between real world / simulation.

11/38

What is Starcraft?
AIIDE 2010 competition (AAAI)
Our approach
Code & Results“Best” RTS in the world
Starcraft 101
An interesting problem

Starcraft specifically
Chess / Go / Rock-paper-scissors
Real-time (1/24th second per micro-turn)
Machine learning ready (replays)
AI competitions

12/38

What is Starcraft?
AIIDE 2010 competition (AAAI)
Our approach
Code & Results

4 Tournaments
Tournament 1
Tournament 4

Open tournament
Expressive Intelligence Studio at University of Santa Cruz(UCSC)
Ben Weber announced the tournament in November 2009at AIIDE
Free participation
Open to all
Began work on it in March 2010 as a pet projectDue for the 15th of September (2010)13/38

What is Starcraft?
AIIDE 2010 competition (AAAI)
Our approach
Code & Results

4 Tournaments
Tournament 1
Tournament 4

Micro-based tournaments

Micro-management: flat map;

Small-scale combat: cliffs

14/38

What is Starcraft?
AIIDE 2010 competition (AAAI)
Our approach
Code & Results

4 Tournaments
Tournament 1
Tournament 4

Normal games

Tech-limited: small map, only zealots/goons;
Full game: real (competitions, progaming) maps

15/38

What is Starcraft?
AIIDE 2010 competition (AAAI)
Our approach
Code & Results

4 Tournaments
Tournament 1
Tournament 4

Challenges in micro-management
Fight well, move well, think fast:
Select targets
Don’t stuck units (very hard!)
Predict (close) future
Be efficient (200x200, 1/24th of a second)

16/38

What is Starcraft?
AIIDE 2010 competition (AAAI)
Our approach
Code & Results

4 Tournaments
Tournament 1
Tournament 4

Challenges in full games
Chess in real-time:
Do not bug/freeze/slow down
Predict oponents strategies and tactics
Be able to counter/handle any strategy
Know when to attack and when not
Micro-manage well in different environments
A lot of other tasks
Do not bug/freeze/slow down
Do not bug/freeze/slow down
...

17/38

What is Starcraft?
AIIDE 2010 competition (AAAI)
Our approach
Code & Results

Bayesian programmingHigh level model
Units as Bayesian robots

Bayesianism

18/38

What is Starcraft?
AIIDE 2010 competition (AAAI)
Our approach
Code & Results

Bayesian programmingHigh level model
Units as Bayesian robots

Transmute incompleteness into uncertainty

high level

low level

Incompleteness=⇒Uncertainty

Many low level moves
achieving the samehigh level goal

Considering the units as
individual Bayesianrobots

Fog of war (limitedsight)

Seen units (viewedunits filter)

Partial knowledge ofopponent’s force (sizeand composition)

Probabilistic inference,machine learning fromreplays

19/38

What is Starcraft?
AIIDE 2010 competition (AAAI)
Our approach
Code & Results

Bayesian programmingHigh level model
Units as Bayesian robots

Machine learnings
from replays(parameters ofpredictive models)
reinforcement(exploration ofparameters spacefor the Bayesianrobots)
online (adapt toparticularopponent)

20/38

What is Starcraft?
AIIDE 2010 competition (AAAI)
Our approach
Code & Results

Bayesian programmingHigh level model
Units as Bayesian robots

low levelhigh level

Problems to tackle

Our bot

Oponent's

Strategy

Strategy (Tech tree,army composition)~3 minTactics

Tactics (Armypositions)~30 sec

Micro-management

Micro-management~1 secdirect knowledge

21/38

What is Starcraft?
AIIDE 2010 competition (AAAI)
Our approach
Code & Results

Bayesian programmingHigh level model
Units as Bayesian robots

Model overview
ELostsReporter

DataThatWe
Collect

EUnitsEstimator
ViewedETechEstimator

EUnitsEstimator"PositionsFilter"
EProdEstimator

UnitsTypes
UnitsTypes UnitsNumbers

TechUnitsNumbers

StrategyManager

UnitsTypes

GameSense

UnitsWanted

Tech/Prod

EcoManagerUnitsPositions

UnitsNumbers

EMinM

EGazM

#Buildings

TacticManager

Defend/Attack

Where (how)WarManager
ForceEstimator
GameSense
UnitsGroup(Linear) Optimization(Library)

UnitsGroup

CanHarass?

UnitsGroup

BayesianUnit BayesianUnit BayesianUnit
BayesianUnit BayesianUnit BayesianUnit

Mass
CanCounter?
Tech

BayesianUnit BayesianUnit BayesianUnit

22/38

What is Starcraft?
AIIDE 2010 competition (AAAI)
Our approach
Code & Results

Bayesian programmingHigh level model
Units as Bayesian robots

The Bayesian unit (1)The workers are not controlled as (Bayesian) sensory motor
systems as their tasks are extremelly simple.
Modal unit, can be simplified as:
Scout
Move (small / large group)
In position
Fight:- Attack- Fight-move- Flee} When not attacking

23/38

What is Starcraft?
AIIDE 2010 competition (AAAI)
Our approach
Code & Results

Bayesian programmingHigh level model
Units as Bayesian robots

The Bayesian unit (2)Mode dependant influences,as:“statically” occupied
tiles“dynamically” occupied
tiles
heightdamage map (+gradient)
pathfinder
...

24/38

What is Starcraft?
AIIDE 2010 competition (AAAI)
Our approach
Code & Results

Bayesian programmingHigh level model
Units as Bayesian robots

The Bayesian unit, Fight-move example (1)Variables:
Diri∈{possible directions} ∈ {T , F}, n = #{possible directions}
Obji ∈ {T , F},
Dami ∈ {no, low, med, high},
Repi ∈ {no, low, high},Hi ∈ {0 . . . 3},
Occi ∈ {no, terrain, building}
Decomposition:
P(Dir1:n , Obj1:n , Dam1:n Rep1:n , H1:n , Occ1:n )= Πni=1 P(Obji |Diri ).P(Dami |Diri ).P(Repi |Diri ).P(Hi |Diri ).P(Occi |Diri )25/38

What is Starcraft?
AIIDE 2010 competition (AAAI)
Our approach
Code & Results

Bayesian programmingHigh level model
Units as Bayesian robots

The Bayesian unit, Fight-move example (2)Parameters:
They are hand-specified for the moment but should belearned through task-specific maps and maximization.
Questions:
The pathfinder gives us Obj1:n , the damage map Dam1:n , thedistance to and size of other units Rep1:n , etc.
P(Dir1:n |Obj1:n , Dam1 : n, Rep1:n , H1:n , Occ1:n )26/38

What is Starcraft?
AIIDE 2010 competition (AAAI)
Our approach
Code & Results

Bayesian programmingHigh level model
Units as Bayesian robots

Bayesian flocking (simplified)
Variables:
Diri
ObjiRepi
Parameters:
P(Repi |Diri ) are learned with maze-like maps and on theobjective to minimize the time-to-completion.
Obji is not well-defined: We have to divise its value by thenumber of units flocking together.

27/38

What is Starcraft?
AIIDE 2010 competition (AAAI)
Our approach
Code & Results

Bayesian programmingHigh level model
Units as Bayesian robots

Bayesian repulsion (flocking applied to “in position”)(2 youtube videos
http://www.youtube.com/snippyhollow#p/a/u/1/sMyF_PlDqFo
http://www.youtube.com/snippyhollow#p/a/u/2/mvv9kUntLHU )Like flocking but with different parameters (and an additional
attractor: the position).

28/38

What is Starcraft?
AIIDE 2010 competition (AAAI)
Our approach
Code & Results

Interfacing with Starcraft
Implementation
Results at AIIDE 2010

BWAPI
BroodWar API#include <BWAPI. h>. onFrame ( ){units = Broodwar−>getAllUnits ( ) ;f o r ( set<Unit * >:: const_iterator i t = units . begin ( ) ;i t != units . end ( ) ; ++i t ){i f ( ( * i t )−>isWorker ( ) )continue ;i f ( ( * i t )−>getType ( ) == UnitType : : Protoss_Zealot )( * i t )−>attackMove ( enemyPosition ) ;else( * i t )−>attackUnit (enemyUnit) ;}
}

29/38

What is Starcraft?
AIIDE 2010 competition (AAAI)
Our approach
Code & Results

Interfacing with Starcraft
Implementation
Results at AIIDE 2010

What has been implemented?
ELostsReporter

DataThatWe
Collect

EUnitsEstimator
ViewedETechEstimator

EUnitsEstimator"PositionsFilter"
EProdEstimatorUnitsTypes
UnitsTypes UnitsNumbers

TechUnitsNumbers

StrategyManager

UnitsTypes

UnitsPositions

UnitsNumbers

GameSense

EMinM

EGazM

TacticManager#Buildings

Borrowed
Implemented

UnitsWanted

Tech/Prod

EcoManager

Defend/Attack

Where (how)Partially implemented

WarManager
ForceEstimator
GameSense
UnitsGroup(Linear) Optimization(Library)

UnitsGroup

CanHarass?

UnitsGroup

BayesianUnit BayesianUnit BayesianUnit
BayesianUnit BayesianUnit BayesianUnit

Mass
CanCounter?
Tech

BayesianUnit BayesianUnit BayesianUnit

30/38

What is Starcraft?
AIIDE 2010 competition (AAAI)
Our approach
Code & Results

Interfacing with Starcraft
ImplementationResults at AIIDE 2010

Interesting snags

Hidden walkable
pixelsStuck units
Dealing with lag

31/38

What is Starcraft?
AIIDE 2010 competition (AAAI)
Our approach
Code & Results

Interfacing with Starcraft
Implementation
Results at AIIDE 2010

To-do code work
Currently:
Key tests (no “unit” test)
Synchronous (1/24th second) + threads (pathfinding,storms coverage, planning)

To-do:
Automate tests (94 test maps)
Switch to an event-driven paradigm/framework (19498
true lines of C++)
Add tests
Implement remaining/new models
Integrate learnings

32/38

What is Starcraft?
AIIDE 2010 competition (AAAI)
Our approach
Code & Results

Interfacing with Starcraft
Implementation
Results at AIIDE 2010

Tournament 1
7 participants
Took part, got left out /FreSC (Epita team) won

Played against FreSC: draw! (0-3,3-0, 6-8)

33/38

What is Starcraft?
AIIDE 2010 competition (AAAI)
Our approach
Code & Results

Interfacing with Starcraft
Implementation
Results at AIIDE 2010

Tournaments 2 & 3
Tournament 2:
2 participants
Didn’t took part
FreSC won
Tournament 3:
8 participants
Didn’t took part
Mimicbot won

34/38

What is Starcraft?
AIIDE 2010 competition (AAAI)Our approach
Code & Results

Interfacing with Starcraft
Implementation
Results at AIIDE 2010

Tournament 4
17 participants
Took part, really ,, 0-3, 3-0, 1-3 passed one round only(“top 8”).
Eliminated because of a (lame) strategy not handledcorrectly (bug)Overmind (UC Berkeley team) won
Team Overmind:
13 members (Ph.D students)
1 member took part in WCG 2001
http://overmind.cs.berkeley.edu/35/38

What is Starcraft?
AIIDE 2010 competition (AAAI)
Our approach
Code & Results

Interfacing with Starcraft
Implementation
Results at AIIDE 2010

Half-satisfying resultsNot all have been implemented /What have been implemented performed well ,... after tweaks & hacks /We keep on working on Starcraft ,36/38

What is Starcraft?
AIIDE 2010 competition (AAAI)
Our approach
Code & Results

Interfacing with Starcraft
Implementation
Results at AIIDE 2010

Bibliography
A Data Mining Approach to Strategy Prediction (2009) [Weber B.
& Mateas M.]
Bayesian Programming and Hierarchical Learning in Robotics(2000) [Diard J. & Lebeltel O.]
It knows what you’re going to do (2001) [Laird J.E.]
Bayesian Robot Programming (2004) [Lebeltel O. & al.]Teaching Bayesian Behaviours to Video Game Characters(2004) [Le Hy R. & al.]Probability Theory: The Logic of Science (2003) [Jaynes E.T.]

37/38

What is Starcraft?
AIIDE 2010 competition (AAAI)
Our approach
Code & Results

Interfacing with Starcraft
Implementation
Results at AIIDE 2010Thanks

Thank you for your attention.

38/38