Analyseren van een complex strategiespel door
multi-agent potentiaalvelden
Ralph Temperville
Promotor: prof. dr. Guy De Tré
Begeleider: Joachim Nielandt
Masterproef ingediend tot het behalen van de academische graad van
Master of Science in de ingenieurswetenschappen: computerwetenschappen
Vakgroep Telecommunicatie en Informatieverwerking
Voorzitter: prof. dr. ir. Herwig Bruneel
Faculteit Ingenieurswetenschappen en Architectuur
Academiejaar 2013-2014
iii
Voorwoord
Sinds mijn jonge jaren was ik zoals velen gefascineerd door artifici¨ele intelligentie en, meer
bepaald dan door het gedrag van computergestuurde tegenstanders in video spellen. Ik
was dan ook getuige van de razendsnelle evolutie binnen de game-AI. Eerdere computergestuurde tegenstanders gebruikten cheats om een hogere moeilijkheidsgraad na te bootsen
omdat hun beslissingspatronen nog niet op punt stonden. Dit is de dag van vandaag al
sterk verbeterd maar tegen ervaren spelers kunnen computers nog steeds geen RTS spel
winnen.
Naast games hebben ontwikkelingen in de AI ook altijd sterk mijn aandacht getrokken.
Zo geloof ik ook sterk in de toekomstige zelfrijdende auto’s waar Google bijvoorbeeld aan
werkt. Alsook de pakketbezorgingsdienst van Amazon die onderzoekt hoe drones kunnen
helpen bij het verdelen van pakjes. Deze radicale vernieuwingen laten blijken dat de AI
nog maar in zijn kinderschoenen staat en enorm veel potentieel heeft.
Mijn interesse in het onderwerp was een mooi vertrekpunt maar zorgde er uiteraard niet
op zichzelf voor dat de eindmeet gehaald wordt. Ik durf dan ook toe te geven dat mijn
masterproef een zware beproeving was die er niet zonder slag of stoot tot stand gekomen
is. Het is met vlag en wimpel het meest lijvige werk dat ik voltooid heb en hier ben ik dan
ook trots op.
Eerst en vooral wil ik mijn begeleider Joachim bedanken die steeds open stond voor een
gesprek over de koers en vooruitgang van de masterproef en die ook steeds bereid was
om de scriptie na te lezen en te voorzien van constructieve feedback. Hiernaast wil ik
ook mijn promotor prof. Guy De Tr´e, bedanken en mijn collegastudenten die tijdens de
tussentijdse presentatie eveneens behulpzame feedback verschaft hebben. Ook Dimitry, die
samen met mij hetzelfde onderwerp heeft gekozen, bleek een grote hulp te zijn. Onze thesis
was meermaals het onderwerp van interessante en verhelderende gesprekken over bepaalde
beslissingen die genomen moesten worden of over problemen die we ondervonden.
Op het thuisfront wil ik ook graag mijn ouders bedanken die me altijd gesteund hebben
en steeds openstonden om mijn scriptie met een kritisch oog na te kijken. Mijn vriendin
gaf me niet enkel dit semester maar gedurende mijn volledige schoolcarri`ere de moed om
door te bijten tijdens de moeilijke periodes, waarvoor ik haar enorm dankbaar ben.
Tot slot wil ik nog al mijn vrienden bedanken om mij de nodige steun te geven in dit drukke
laatste jaar. Zonder hen was mijn studietijd nooit geweest zoals ik ze heb mogen ervaren
en ik ben ze dan ook stuk voor stuk dankbaar voor de toffe tijden in Gent. Bedankt!
Ralph Temperville, juni 2014
v
Toelating tot bruikleen
“De auteur geeft de toelating deze scriptie voor consultatie beschikbaar te stellen en delen
van de scriptie te kopi¨eren voor persoonlijk gebruik.
Elk ander gebruik valt onder de beperkingen van het auteursrecht, in het bijzonder met
betrekking tot de verplichting de bron uitdrukkelijk te vermelden bij het aanhalen van
resultaten uit deze scriptie.”
Ralph Temperville, juni 2014
Analysing a complex strategy game using
multi-agent potential fields
Ralph Temperville
Supervisor(s): Guy De Tr´e, Joachim Nielandt
Abstract—In this article we create a dynamic and adaptive framework to
aggregate temporal multi-agent potential fields using expression trees. We
test this model by applying it to several scenarios with different constraints
within Starcraft Brood War.
Keywords—Potential field, aggregation techniques, Starcraft Brood War
I. I NTRODUCTION
EVELOPMENT in artificial intelligence has been increasing at a steady pace during the last few decades. Game
AIs specifically have seen great improvement over the past few
decades. For example, the real time strategy game Starcraft
serves as a tool in a lot of research about game AIs because of its
inherent complexity and depth. In fact, there even exist competitions for these AIs to compete against each other to determine
which author has created the best model.
A recent breakthrough with regards to game AI is the use of
artificial potential field techniques to easily make decisions in
complex scenarios as proposed by [1]. These fields can help
AIs to improve pathing decisions in environments with multiple
active agents to which they have to react to. Other uses of these
APFs include tracking the suitability for certain actions on the
playfield.
In this article we propose a framework to enable complex aggregations between multiple potential fields. This framework
consists of a multitude of building blocks such as operators and
basic potential fields. To test the framework and show its power,
we apply the framework to three use-cases, set within the game
where we analyse each scenario through a specific aggregation
of potential fields.
D
II. C ONSTRUCTING THE FRAMEWORK
A. Expression tree
The foundation of the framework is built around the idea of
the expression tree first presented in [2]. This data structure allows for a modular design where basic potential fields are leaf
nodes and operators are non-leaf nodes. The number of children
of a given node is equal to the arity of the operator this node
represents. Some advantages of using this model are reusability,
modularity and adaptability. Firstly all structures created can
be reused (even multiple times) by making a node point to the
root of this structure. Secondly, the model is modular because
all operator logic is comprised into its own tree node. This also
means it is straightforward to define additional custom operators. Lastly, the model is adaptable because the operators can
be chained together in infinite ways to exhibit the behaviour required.
B. Basic potential fields
The leaf nodes of the expression tree consist of basic potential
fields. These fields are centered around a position on the map
and they can also adopt several shapes. The three types of fields
we define are constant (this field has the same charge at any
given point near the source), linear (the charge decays in a linear
fashion the further we move away from the source) and gaussian
(the field is bell curve shaped and asymptotically decays to zero
the further we move away from the source).
Note that the linear field has a decay rate parameter and the
gaussian field has a σ parameter which can both be tweaked
according to the specific needs of the scenario. All fields are
also initialized with certain charge strength.
C. Operators
The main strength of the framework lies in the multitude of
ways one can aggregate several fields to one purposeful field for
analysis. Several operators on potential fields are needed, operators that can be used to perform these aggregations are listed
below. The operators are split up by arity.
C.1 Unary operators
The unary operators are operators with only one child node.
This category consists of three notable operators:
• The negation operator which maps a potential field to its negative equivalent.
• The cutoff operator which inserts a boundary on the diameter
of a potential field.
• The threshold operator which reduces all charges below a
certain threshold value to zero.
C.2 Binary operators
The decay operator is the only binary operator we define.
This operator has two child nodes and computes the piecewise
multiplication of the two potential fields. This field is mainly
used to weaken or strengthen a potential field with a certain factor. To do this, we pick a constant field with the desired decay
rate as the second child node.
C.3 n-ary operators
The bulk of the operators are n-ary operators, which can have
a varying number of child nodes. We define four n-ary operators:
• The maximum operator creates a potential field with the
charge at any given position equal to the maximum value of the
charges of the children at that position.
• The minimum operator is similar to the maximum operator.
• The sum operator creates a field with a charge equal to the
sum of the children node charges at the given position.
• The average operator is similar to the sum operator, but the
charges get divided by the number of child nodes after adding
up their charges.
C.4 The memory construction
In addition to the operators as defined before, there are two
extra operators which are discussed separately because of their
synergy. To create a field which retains some temporal information, we need to add a way to store these intermediate results
between different snapshots over time. To do this, we create the
memory construction which consists of a memory leaf node and
a memory operator.
The memory leaf node is a node which retrieves its charge
from a two-dimensional array at the position where it is evaluated. The memory operator on the other hand is a unary operator
which saves all evaluations of its child node at the position it is
evaluated and passes the evaluation value upwards in the expression tree.
The combination of these two nodes gives us an easy way
to store and use temporal information. The model in Figure 1,
for example, builds a potential field where the movement of an
entity is stored.
charge). As an aggregation operator between all these fields, we
choose the summing operator. Since the resulting potential field
can have charges which exceed 1 we add a minimum operator
with a constant leaf node with charge 1. This enforces a ceiling
of 1 on the summation of the basic potential fields.
Now we add a memory construction to store the temporal information of the field. We create a memory leaf node and precede it by a decay operator. This means that the temporal information slowly decays to zero and leaves a trail. We combine
this decay operator and the minimum operator by means of the
maximum operator. Finally, we precede this node by a memory
operator to store the resulting field.
A.2 Implementation
The described model was implemented in Starcraft using a
scenario which shows the advantage of this field. The scenario
consists of two groups of marines that patrol a certain area to
protect their base. In Figure 2, the potential field is shown that
is the result of applying our model to this scenario.
Result
Memory operator
2D Tabel
Fig. 2. The spatio-temporal potential field of enemy unit movement
Maximum operator
Memory leaf node
Lineair potential
field
Fig. 1. An application of the memory construction
III. U SE CASES
The operation of this framework is demonstrated by three use
cases. These use cases have different goals in order to show the
framework’s adaptability to changing requirements. In each of
which we visualise and discuss the resulting aggregated potential field. Note that the visualisation uses a colour coding from
green to red where green is the highest possible potential and
green is the lowest possible potential.
A. Use case 1: Distribution of the enemy army in the spatiotemporal domain
In this use case, we build a potential field which captures the
movement and the concentration of the enemy units.
A.1 Construction of the tree
For this use case, we start by defining all enemy units as basic
linear potential fields with a charge of 1 (the highest possible
On this heat map we can clearly see the path on which the
marines patrol. The intensity of the field signifies the gravity
point of the army. The highest concentration of army units is
located around the red spots on the map.
This overlay can be used by the player to determine the patterns in the enemy’s movement and to attack from an advantageous position.
B. Use case 2: Determining the optimal scouting regions
B.1 Construction of the tree
There are a few factors to distinguish important places to
scout on. Firstly, we start by creating a constant potential field
with a medium strength which covers the whole map.
Next, we give our own units constant potential fields with a
width equal to the viewing distance. Afterwards we add a memory mechanism which slowly decays temporal information because areas recently scouted become more interesting the longer
they remain hidden.
Since important scouting locations often include areas with
resources because enemies can expand there, we will give the
resources a small, but strong linear potential field to indicate
this.
Lastly, we want to give areas in close proximity of spotted enemies higher importance to scout, in the assumption that these
units are frequently nearby an enemy base. To do this, we also
give the enemy units linear potential fields with a memory construct to retain this temporal information.
(in the bottom right-hand corner) is negated by the enemy army
force, which is the green area.
B.2 Implementation
Figure 3 depicts a potential field created by the model we just
designed. In this model, the green areas are the visible, or recently scouted areas, which have the lowest priority to scout.
The red spots are areas in the close proximity to resources and
as such places where the enemy could have a base. These have
a high priority to be scouted.
Players can use the overlay and the heat map to quickly analyse the optimal areas to scout, taking into account the temporal
movement of its units.
Fig. 4. The potential field for finding the optimal expansion area
IV. C ONCLUSION
The use cases show that the framework is strongly adaptive and that we can build a multitude of temporal multi-agentaggregated potential fields with it. These fields can subsequently
help AI computer players, or human players for that matter,
analyse and make otherwise complex, in-game decisions.
Fig. 3. The potential field for finding high priority scouting areas
C. Use case 3: Determining the optimal areas for expansion
For our last use case, we want to construct a potential field
to determine the feasibility for expansion. here are three main
influences this field should take into consideration. The first one
is that it should be close to allied forces and bases to protect it.
Secondly it should be far away from enemy army movement and
finally the expansion area should of course be in close proximity
to resources which is a paramount factor.
C.1 Construction of the tree
Allied units are given a potential field with a low charge and
a low decay rate. This creates a wide field around the allied
forces. Additionally, a memory construction is added to facilitate temporal information of the movement of our allied forces.
The enemy units will receive a field similar to that of the allied
units, except that here, we will negate the field to give these
fields a negative charge.
For the resources field, we use a high charge and a high decay rate to create small and highly attractive areas around the
resources.
To finalize our field we sum the three last components together with a constant field having a medium charge. We do
this so hill and depressions in the constant field are created by
friendly and enemy units (and resources) respectively.
C.2 Implementation
In the implementation in Figure 4 we see this model applied
to Starcraft. In the top left-hand corner we can distinguish the
allied army represented by the orange influence areas. The red
spots are formed by the resource patches. On this map, there are
4 resource patches available, three are clearly visible while one
V. F UTURE WORK
While the upside of this framework in the context of RTS
games has been amply illustrated, further research could still
be conducted into the significance of this framework for other
fields that use aggregated potential fields, such as robotics. Another point of improvement is research into the parallelization
and of this framework to allow it to scale to several thousand
nodes in a complicated expression tree. Studies such as [3] and
[4] into parallelization of expression trees together with potential field specific parallelization could then be merged.
R EFERENCES
[1] J. Hagelb¨ack and S. J. Johansson. A multiagent potential field-based bot for
real-time strategy games. Int. J. Comput. Games Technol., 2009:4:1–4:10,
January 2009.
[2] R. F. Cohen and R. Tamassia. Dynamic expression trees and their applications. In Proceedings of the Second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’91, pages 52–61, Philadelphia, PA, USA, 1991.
Society for Industrial and Applied Mathematics.
[3] R. Cole and U. Vishkin. Vlsi algorithms and architectures. chapter Optimal
Parallel Algorithms for Expression Tree Evaluation and List Ranking, pages
91–99. Springer-Verlag, London, UK, UK, 1988.
[4] R. Cole and U. Vishkin. The accelerated centroid decomposition technique
for optimal parallel tree evaluation in logarithmic time. Algorithmica, 3(14):329–346, 1988.
x
TOELATING TOT BRUIKLEEN
INHOUDSOPGAVE
xi
Inhoudsopgave
Voorwoord
iii
Toelating tot bruikleen
Extended abstract
Inhoudsopgave
Gebruikte afkortingen
1 Inleiding
v
vii
x
xv
1
1.1
Wat is een RTS spel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1
1.2
Geschiedenis van het RTS spel . . . . . . . . . . . . . . . . . . . . . . . . .
2
1.3
Artifici¨ele intelligentie in spellen . . . . . . . . . . . . . . . . . . . . . . . .
3
1.4
Doel van de thesis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5
1.5
Structuur en omvang . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6
2 Literatuurstudie
2.1
2.2
9
Potentiaalvelden . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
9
2.1.1
Oorsprong . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
9
2.1.2
Artifici¨ele potentiaalvelden . . . . . . . . . . . . . . . . . . . . . . .
10
2.1.3
Voordelen en nadelen . . . . . . . . . . . . . . . . . . . . . . . . . .
12
Expressiebomen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
13
2.2.1
13
Werking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
xii
INHOUDSOPGAVE
2.2.2
Voordelen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
14
3 Tools
17
3.1
Starcraft . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
17
3.1.1
Macromanagement . . . . . . . . . . . . . . . . . . . . . . . . . . .
19
3.1.2
Micromanagement . . . . . . . . . . . . . . . . . . . . . . . . . . .
20
3.1.3
Fog of war . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
21
BWAPI . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
21
3.2
4 Framework
25
4.1
Keuze van de implementatie taal . . . . . . . . . . . . . . . . . . . . . . .
25
4.2
Expressieboom . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
26
4.2.1
Expressieknoop . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
27
4.2.2
Positieknoop . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
28
4.2.3
Operatorknopen . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
29
4.2.4
Compositie van operatoren . . . . . . . . . . . . . . . . . . . . . . .
40
4.2.5
Caching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
41
5 Use cases
5.1
5.2
5.3
43
Use case 1: Distributie van vijandig leger in spatio-temporeel domein . . .
44
5.1.1
Constructie van het model . . . . . . . . . . . . . . . . . . . . . . .
44
5.1.2
Toepassing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
45
Use case 2: Optimale scouting regio’s bepalen . . . . . . . . . . . . . . . .
46
5.2.1
Constructie van het model . . . . . . . . . . . . . . . . . . . . . . .
48
5.2.2
Toepassing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
49
Use case 3: Optimale expansieplaats bepalen . . . . . . . . . . . . . . . . .
49
5.3.1
Constructie van het model . . . . . . . . . . . . . . . . . . . . . . .
51
5.3.2
Toepassing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
52
6 Conclusie
55
INHOUDSOPGAVE
xiii
7 Toekomstig werk
57
Appendices
Bijlage A
58
Bijlage B
60
Bijlage C
62
Bibliografie
65
Lijst van figuren
67
Lijst van tabellen
69
xiv
INHOUDSOPGAVE
xv
Gebruikte afkortingen
2D
Twee-dimensionaal
AI
Artifici¨ele intelligentie
API
Application Programming Interface
BWAPI
Brood War Application Programming Interface
DFT
Depth First Traversal
FOW
Fog Of War
FPS
Frames Per Second
LSP
Logically Aggregated Geographic Suitability Maps
OOP
Objectgeori¨enteerd programmeren
PF
Potential Field
RBG
Rood-Blauw-Groen spectrum
RTS
Real Time Strategy
xvi
GEBRUIKTE AFKORTINGEN
1
Hoofdstuk 1
Inleiding
Artifici¨ele intelligentie is een gegeven dat mensen al decennia intrigeert. Velen denken
meteen aan computersystemen die menselijk kunnen denken en hostile takeovers beramen
zoals Skynet uit de terminator franchise. Dit is echter verre van het soort onderzoek dat
vandaag de dag gedaan wordt inzake AI. Veel vaker wordt het leren uit fouten en het gebruik
van feedback loops van computers bedoeld. Onderzoek naar AI stijgt de laatste decennia
aan een exponentieel tempo wat leidt tot vele ontwikkelingen waar mensen rechtstreeks mee
in contact komen. Denk maar aan de aankondiging van Amazon die pakjes wil laten leveren
door zelfstandig navigerende drones. Of Google die volop bezig is met het optimaliseren
van zelfrijdende auto’s. Het is dan ook vrij waarschijnlijk dat de wereld er binnen enkele
decennia volledig anders zal uit zien door de evoluties op vlak van AI.
1.1
Wat is een RTS spel
Real time strategy of kortweg RTS is een genre van computerspellen. Real time wil zeggen dat er niet gewerkt wordt met een beurtensysteem zoals bijvoorbeeld schaken of verschillende typische kaartspellen, e.g., manillen, wiezen ... Elke speler kan dus constant
commando’s geven en hoeft niet te wachten op de andere speler. De strategy component
2
HOOFDSTUK 1. INLEIDING
betekent in deze context dat de speler eenheden en gebouwen bezit die hij elk kan beheren (micromanagement) met vaak als ultieme doel de troepen van de tegenstander uit te
schakelen. Hiernaast moet een speler ook typisch grondstoffen verzamelen waarmee hij op
zijn beurt meer eenheden en gebouwen kan bouwen (macromanagement).
1.2
Geschiedenis van het RTS spel
De oorsprong van de RTS vinden we bij het spel Broderbund’s The Ancient Art of War
dat gepubliceerd werd in 1984. De speler moest hier een keuze maken uit troepen die
door middel van een blad-steen-schaar systeem tegen elkaar vochten. Hier was echter nog
geen sprake van het managen van een economie, wat door velen beschouwd wordt als een
essenti¨ele component van RTS spellen. De echte grondlegger van het genre zoals we het
vandaag kennen is Dune II, gemaakt door Westwood Studio’s, uitgekomen in 1992.
Na deze initi¨ele titel volgden de RTS spellen elkaar in hoog tempo op. Ensemble studios
introduceerde Age of Empires in 1997 met computergestuurde tegenstanders met ongekende
intelligentie en het isometrisch perspectief wat vandaag de dag de standaard is binnen RTS
games. Warcraft: Orcs & Humans (1993) door Blizzard, dat ondertussen uitgegroeid is
tot een enorme franchise met oa. Warcraft3, World of Warcraft, Hearthstone ..., lag aan
de basis van het Warcraft verhaal en liet de speler toe een RTS te spelen binnen een ruime
fantasiewereld. En tot slot de titaan van de RTS spellen: Starcraft, uitgebracht door
Blizzard in 2000, waarvan maar liefts 11 miljoen kopies van verkocht zijn en wat hierdoor
de titel van 13e meest verkochte spel mag dragen.
Meer recentere RTS spellen zijn onder andere de Command & Conquer reeks van Westwood, dat zich zoals Starcraft in een futuristische setting bevindt. Age of Mythology
(2002) gooit het dan weer over een andere boeg door titanen en goden te introduceren die
elk bepaalde voordelen met zich meebrengen om het RTS genre een twist te geven. De
laatste jaren bestaan de meest besproken RTS spellen hoofdzakelijk uit nieuwe edities van
¨ INTELLIGENTIE IN SPELLEN
1.3. ARTIFICIELE
3
de hierboven besproken gevestigde RTS reeksen. Zo is vorig jaar nog de nieuwe expansie
voor Starcraft 2 uitgekomen, getiteld “Heart of the Swarm”, waar deze keer het Zerg ras
in de spotlights gezet wordt.
Het mag na deze uiteenzetting van het RTS genre dus duidelijk zijn dat RTS een succesvol
recept is dat de tand des tijds goed doorstaan heeft. Starcraft (I en II) spelers in ZuidKorea worden vandaag de dag behandeld als popsterren en topatleten, en deze trend zet
zich door in Westerse landen. Deze spelers trainen soms meer dan 8 uur per dag om hun
techniek en strategie te perfectioneren. Er bestaan ook televisiezenders in Zuid-Korea die
24/7 Starcraft wedstrijden uitzenden zoals we hier sportkanalen hebben. Het hoeft dus
geen verduidelijking dat Starcraft een enorm complexe en competitieve RTS is.
1.3
Artifici¨
ele intelligentie in spellen
In artifici¨ele intelligentie is de doelstelling het formaliseren en mechaniseren van het gedrag
en de redeneringspatronen van het menselijk brein. Aangezien het brein immens complex is
en we zeker nog niet op het punt gekomen zijn waar we kunnen beweren dat we de werking
ervan begrijpen moeten we dus een benadering of simplificatie doen. Verder zullen we kort
de evolutie van artifici¨ele intelligentie bespreken, en daarnaast de toepassingen binnen de
spelwereld.
In 1951 ontwierp Dietrich Prinz een schaakprogramma voor de computer Ferranti Mark I.
Het ging hier over een exhaustief brute force algoritme dat door de breedte van de spelboom
slechts gebruikt kon worden om het einde van het spel te spelen (en dus niet van begin
tot eind). Gelijkaardig werd in 1997 door IBM de alom bekende spelcomputer Deep Blue
voorgesteld die er voor het eerst in slaagde de grootmeester en voormalig wereldkampioen
schaken Garry Kasparov te verslaan. De techniek die hier gebruikt werd is vooral gebaseerd
op heuristieken met een sterke objectief functie (die het voordeel of nadeel van de staat
4
HOOFDSTUK 1. INLEIDING
(a) Dune II (1992)
(b) Warcraft: Orcs & Humans (1993)
(c) Age of Empires I (1997)
(d) Starcraft I (2000)
(e) Command & Conquer 4: Tiberian Twilight
(f) Starcraft II: Heart of the Swarm (2013)
(2010)
Figuur 1.1: De evolutie van de RTS
1.4. DOEL VAN DE THESIS
5
van het bord kwantificeren). Hiernaast maakt Deep Blue ook gebruik van alfa-beta snoeien
waardoor niet de volledige zoekruimte moet doorlopen worden.
Terwijl het een enorme prestatie was door Deep Blue om Garry Kasparov te verslaan wordt
er door puristen vaak de vraag gesteld in hoeverre dit programma intelligent is. De brute
force aanpak die Deep Blue gebruikt houdt in dat het programma niet nadenkt over de
staat van het bord. Het is hoe dan ook niet evident om duidelijk te defini¨eren wanneer een
programma als intelligent mag beschouwd worden. We zullen in deze thesis verder geen
tijd besteden aan dit eerder filosofisch getint vraagstuk.
1.4
Doel van de thesis
In deze thesis onderzoeken we hoe het gebruik van temporele potentiaalvelden kan helpen
bij het analyseren van speltoestanden in Starcraft. Potentiaalvelden laten toe complexe
situaties eenvoudig te evalueren door hun spatiale aard. Door verschillende operatoren te
defini¨eren en het temporele aspect toe te voegen kunnen we ook vaststellingen doen over
een bepaalde periode en zijn we niet beperkt tot momentopnames. Hiermee willen we een
dynamisch framework bouwen dat het mogelijk maakt om enkele diverse situaties duidelijk
te analyseren door een gepaste aggregatie van potentiaalvelden.
Door het framework op verschillende use cases toe te passen tonen we aan dat dit framework aanpasbaar is en voor zeer diverse doeleinden gebruikt kan worden. Deze use cases
omvatten drie verschillende problemen binnen Starcraft Brood War die we proberen op te
lossen door gebruik van potentiaalvelden (zie Hoofdstuk 5). Om het framework dynamisch
te maken defini¨eren we een groot aantal operatoren tussen potentiaalvelden en bouwen
we een structureel sterk model. Door deze dynamische aard kan het framework makkelijk
overweg met de voortdurend veranderende spelwereld van Starcraft. Dit betekent ook dat
het framework de adaptiviteit bezit nodig voor de verschillende types problemen dat het
tracht op te lossen.
6
HOOFDSTUK 1. INLEIDING
We houden ook rekening met uitbreidbaarheid met het oog op toepassingen met andere
noden, door het mogelijk te maken gemakkelijk extra operatoren te defini¨eren, en door de
performantie te verbeteren door onder andere caching toe te laten.
De analyses op Starcraft door gebruik van het framework zullen we maken aan de hand
van een in-game overlay die intu¨etief aangeeft waar de objectief functie van de specifieke
use case het hoogst is. Dit laat ook spelers en spelcommentators toe deze verschillende
overlays te gebruiken om zelf analyses te maken.
Het dient ook opgemerkt te worden dat het toepassingsgebied van dit framework groter
is dan louter computerspellen en dat er vele nuttige verderzettingen bestaan in andere
domeinen.
1.5
Structuur en omvang
De vooropgestelde omvang en structuur van de thesis verloopt als volgt. In Hoofdstuk 2 bespreken we eerst bestaande literatuur in verband met expressiebomen en potentiaalvelden
om een duidelijk beeld te scheppen in de bestaande technieken en om de lezer vertrouwd
te maken met een aantal benodigde theoretische concepten. Hierna worden in Hoofdstuk 3
de gebruikte tools en frameworks uit de doeken gedaan waarop het framework gebouwd is.
Vervolgens bespreken we het ontwikkelde framework uit in Hoofdstuk 4 dat het mogelijk
maakt om potentiaalvelden te aggregeren op een modulaire en dynamische manier. Dit
framework definieert ook enkele basisoperatoren die gemakkelijk kunnen samengevoegd
worden om complexe aggregaties uit te voeren. Tot slot passen we het ontwikkelde framework ook toe op drie verschillende use cases toe en analyseren we de resultaten in Hoofdstuk
5. Hiertoe passen we de parameters van het framework aan voor elke use case en gebruiken
we dit op de complexe spelsituaties.
Onderdelen die buiten de scope van deze thesis vallen zijn onder andere het parallelliseren
1.5. STRUCTUUR EN OMVANG
7
van het algoritme, alsook het automatisch optimaliseren van de parameters van het framework door bijvoorbeeld een heuristiek. Ook zullen we ons op vlak van de operatoren
beperken tot een subset die voldoende complex is om de verschillende use cases uit te
werken.
8
HOOFDSTUK 1. INLEIDING
9
Hoofdstuk 2
Literatuurstudie
In dit hoofdstuk bespreken we de theoretische kernconcepten die in deze thesis gebruikt
worden en kaderen we deze in de huidige literatuur. Enerzijds potentiaalvelden in Sectie
2.1 en anderzijds expressiebomen in Sectie 2.2 die we uiteindelijk samen gebruiken om het
framework op te stellen.
2.1
2.1.1
Potentiaalvelden
Oorsprong
Een eerste luik van de literatuurstudie gaat over potententiaalvelden, een centraal concept
in deze thesis. Het idee van potentiaalvelden komt voort uit de notie van electromagnetische
potentiaal in de fysica. Als een object een elektrische lading bevat wordt er rond dit object
een elektrisch veld opgespannen door dit object. Dit veld oefent op zijn beurt een kracht
uit op alle andere geladen objecten. Deze kracht is afhankelijk van enerzijds de euclidische
afstand tussen de twee objecten en anderzijds de grootte van de lading van het beschouwde
object. De relatie tussen deze twee eigenschappen wordt beschreven door de wet van
Coulomb, gegeven in Vergelijking 2.1. Hier zijn Q1 en Q2 de respectievelijke ladingen
10
HOOFDSTUK 2. LITERATUURSTUDIE
van de twee objecten, r de afstand tussen de twee objecten in meter en de elektrische
veldconstante. De eigenschappen van statische elektrische ladingen wordt bestudeerd in
de elektrostatica.
F =
Q1 Q2
4πR2
(2.1)
Het is belangrijk om te weten dat de ladingen van objecten zowel negatief als positief
kunnen zijn. Ladingen met een gelijk teken stoten elkaar af terwijl ladingen met een verschillend teken elkaar aantrekken. Dit verklaart bijvoorbeeld waarom bepaalde magneten
elkaar afstoten en andere elkaar aantrekken.
2.1.2
Artifici¨
ele potentiaalvelden
Artifici¨ele potentiaalvelden (APF’s) zijn de abstractie van het hierboven beschreven natuurkundig fenomeen binnen de computerwetenschappen. Hier beweegt een entiteit zich
door een omgeving met statische en dynamische (negatief geladen) obstakels die hij probeert te ontwijken. Tegelijkertijd probeert de entiteit zich naar een doel (positief geladen)
te navigeren. Op het grid waar de entiteit zich bevindt heeft elke tegel een resulterende
positieve of negatieve kracht die resulteert uit de aggregatie van alle velden van de andere
objecten. De entiteit kan dus op een gretige wijze het veld met de meest attractieve waarde
zoeken in de 8 tegels rondom de tegel waarop hij zich bevindt en naar die tegel bewegen. In
Figuur 2.1 wordt een voorbeeld getoond van een artificieel potentiaalveld met een obstakel
(bruine bol) en een doel waar de entiteit zich naartoe beweegt (groene bol). De pijlen
geven de differentiaal aan van de potentiaal (van lage potentiaal naar hoge potentiaal).
Dit is ook het pad dat gevolgd zal worden door eenheden om het doel te bereiken.
Om de benodigde computationele rekenkracht te verminderen kunnen we uiteraard de granulariteit van de cellen verlagen. Dit betekent dat pixels gegroepeerd worden en afgebeeld
worden op ´e´en cel waardoor al deze pixels dezelfde lading hebben. We cre¨eren dus in feite
een injectieve afbeelding van meerdere pixels naar ´e´en waarde.
2.1. POTENTIAALVELDEN
11
Figuur 2.1: Een voorbeeld van een artificieel potentiaalveld
De eerste toepassingen van APF’s bevonden zich vooral in het veld van de robotica waar
deze techniek gebruikt werd voor pad planning van robots zoals besproken in artikel [2].
Het grootste deel van het academisch werk rond deze techniek situeert zich dan ook in
deze tak. Hierna werd ook het nut ingezien van deze techiek in andere domeinen zoals
mobiele sensor netwerken [1] waar een optimale dekking gezocht wordt door het gebruik
van afstotende potentiaalvelden.
Het is pas sinds 2008 dat er voor het eerst onderzoek gepubliceerd werd in verband met het
gebruik van APF’s in AI van computerspellen. Het werk [7] door Johan Hagelb¨ack, een
authoriteit op vlak van AI binnen computerspellen, sprak voor het eerst over de implementatie van APF’s binnen games voor navigatie van eenheden binnen een sterk dynamische
wereld. Na het afstellen van de parameters van de potentiaalvelden bleek deze aanpak een
groot voordeel te bieden tegenover de traditionelere pathfinding algoritmes.
Enkele andere toepassingen van potentiaalvelden binnen Starcraft zijn onder andere het
verbeteren van de kiting mogelijkheden van AI’s. Deze specifieke techniek wordt verder
12
HOOFDSTUK 2. LITERATUURSTUDIE
besproken in de sectie 3.1.2. In [8] wordt onderzoek gedaan naar deze techniek door middel
van potentiaalvelden.
2.1.3
Voordelen en nadelen
APF’s laten toe om een zeer gecompliceerde situaties eenvoudig te modelleren en te evalueren. Ze kunnen gemakkelijk overweg met een grote hoeveelheid entiteiten. Potentiaalvelden
kunnen ook automatisch makkelijk overweg met ingewikkelde pathfinding problemen met
meerdere constraints door hun topologische aard. Hierop wordt traditioneel vaak het A*
algoritme toegepast [3]. Evaluatie van de potentiaal op een specifiek punt schaalt ook
lineair met het aantal te beschouwen entiteiten. Uit recente papers in verband met game
AI en potentiaalvelden kunnen we afleiden dat deze techniek leidt tot superieure AI’s die
beter presteren dan systemen die er geen gebruik van maken.
Een welgekend probleem van APF’s is de problematiek met lokale maxima. Tijdens het
bewegen naar het globaal maximum kan het voorkomen dat een entiteit vast komt te zitten
in een lokale top waar alle omringende tegels een kleinere aantrekkende potentiaal bezitten.
Dit probleem heeft is echter inherent aan APF’s en wordt door zijn complexiteit niet verder
behandeld in deze thesis.
Een ander welgekend probleem bij het gebruik van potentiaalvelden ligt in het afstellen
van de parameters van de potentiaalvelden. In een poging om dit probleem aan te pakken
werd er in [4] een oplossing gezocht door gebruik te maken van een genetisch algoritme.
Dit is een heuristiek die probeert zo goed mogelijke parameters te bepalen, zoals het geval
is bij elke heuristiek, niet gegarandeerd het globale optimum vindt. Hierna werd er ook
in [5] verder gewerkt met deze techniek om micro management (besproken in Sectie 3.1.2)
door AI’s te verbeteren.
2.2. EXPRESSIEBOMEN
2.2
2.2.1
13
Expressiebomen
Werking
Een tweede groot luik omvat het concept van expressiebomen. Expressiebomen bestaan
reeds een langere tijd en worden in tal van domeinen gebruikt. Een expressieboom is een
datastructuur die eerst en vooral voldoet aan de eigenschappen van een normale boom:
de datastructuur is hierarchisch en bevat een wortelknoop die de ouder is van alle andere
knopen in de boom. De knopen zonder kinderen worden ook bladknopen genoemd. Elke
niet-bladknoop bevat een of meerdere verwijzingen naar zijn kinderen. Naast deze eigenschappen wordt er bij een expressieboom een verschil gemaakt tussen operatorknopen en
waardeknopen.
2.2.1.1
Operatieknopen
Operatieknopen beschrijven een bepaalde operatie op hun kinderknopen. Bij de evaluatie
van deze knoop worden eerst alle kinderen ge¨evalueerd. Hierna wordt de specifieke operatie
toegepast op de evaluatiewaarden en wordt het resultaat teruggegeven naar boven in de
boom (richting de wortel).
2.2.1.2
Waardeknopen
Waardeknopen zijn de bladknopen van de expressieboom. Ze hebben dus geen kinderen en
zijn gemakkelijk op zichzelf evalueerbaar. De waarde van deze knoop kan zowel afhangen
van een variabele als constant bepaald zijn tijdens de initialisatie.
14
2.2.1.3
HOOFDSTUK 2. LITERATUURSTUDIE
Evaluatie
De evaluatie van een expressieboom verloopt door depth first traversal (DFT), zoals te zien
in Figuur 2.2. Dit wordt vaak gedaan door op een recursieve manier de evaluatiemethode
van de knopen op te roepen, beginnende bij de wortel.
a
b
d
c
e
f
g
h
i
j
Figuur 2.2: Depth first traversal
2.2.2
Voordelen
Dit type voorstelling heeft enkele grote voordelen. Eerst en vooral is de structuur zeer
begrijpbaar voor mensen en is constructie en uitwerking intu¨ıtief. De voorrangsregels van
de operatoren zitten ook expliciet vervat in de boom en er is dus geen nood aan haakjes
of mogelijkheid tot ambigu¨ıteit.
Vervolgens leent de expressieboom zich ook tot het toevoegen van modulaire functionaliteit.
Er kunnen eenvoudig operatoren toegevoegd worden zolang ze voldoen aan de geleverde
interface. Alle functionaliteit van een operator zit vervat in een eigen klasse wat de coupling
vermindert en de cohesion verhoogt alsook het DRY (don’t repeat yourself) principe oplegt.
2.2. EXPRESSIEBOMEN
15
De voordelen van deze software engineering principes werden beschreven in [11].
Een derde voordeel is de mogelijkheid om de expressieboom te evalueren op een parallele
manier met meerdere threads die elk een deel van de boom verwerken. Dit zorgt voor een
aanzienlijke snelheidswinst op multicore systemen. Deze techniek wordt besproken in [12]
en [13]. Zo kan de expressieboom ge¨evalueerd worden in logaritmische tijd (O(log(n))) in
plaats van lineaire tijd (O(n)).
Als laatste kunnen we ook gemakkelijk caching toevoegen aan de boom door in bepaalde
nodes reeds berekende waarden bij te houden om later te herbruiken. Dit process heet
memoization en kan eveneens een grote performantiewinst betekenen. Deze techniek werd
voor het eerst besproken in [14] en passen we zelf ook toe in ons framework in Sectie 4.2.5.
16
HOOFDSTUK 2. LITERATUURSTUDIE
17
Hoofdstuk 3
Tools
3.1
Starcraft
Zoals reeds duidelijk gemaakt in de inleiding worden de in deze thesis ontworpen technieken toegepast op het RTS spel Starcraft “Brood War”. Een belangrijke eigenschap van
dit spel is de real time component. Hierdoor is het noodzakelijk dat de ontworpen technieken performant genoeg zijn om alle informatie enkele tientallen malen per seconde te
herberekenen afhankelijk van de frames per seconde (FPS).
De reden waarom we het oudere Starcraft “Brood War” gebruiken en niet de recente editie
Starcraft II: “Wings of Liberty” is hoofdzakelijk omdat het oudere framework een API
heeft, BWAPI genaamd. De nieuwe versie van Starcraft laat dit veel moeilijker toe en
aanpassingen aan het spel worden ook wettelijk verboden door Blizzard. Hierdoor werd
beslist om geen interface voor het nieuwe versie te ontwikkelen door de makers van BWAPI.
Deze oudere versie van Starcraft laat ons eveneens toe meerdere instanties parallel te laten
lopen door de exponenti¨ele stijging van de processorkracht in de laatste 14 jaar. BWAPI
wordt verder besproken in Sectie 3.2.
Starcraft speelt zich af in een futuristisch tijdperk waar spelers de keuze hebben uit drie
18
HOOFDSTUK 3. TOOLS
fundamenteel verschillende rassen met elk hun eigen sterktes en zwaktes. De Terran is het
menselijke ras dat beschikt over futuristische menselijke eenheden zoals soldaten, tanks,
buggies ... Het tweede ras is de Protoss, dit zijn hoogtechnologische aliens met duurdere
maar iets sterkere eenheden die over schilden beschikken. Het laatste ras is de Zerg,
bestaande uit insectoiden met dierlijke instincten. Hun eenheden zijn relatief zwak maar
kosten ook het minste. De tactiek van de Zerg is vaak het overrompelen van de vijand met
enorme hoeveelheden eenheden. In Tabel 3.1 ziet u een vergelijking van de drie rassen.
Terran
Protoss
Zerg
Kracht
Gemiddeld Hoog
Laag
Kost
Gemiddeld Hoog
Laag
Productie snelheid
Laag
Gemiddeld Hoog
Tabel 3.1: Vergelijking van de rassen in Starcraft
Een ander belangrijk punt is de opsplitsing tussen macro- en micromanagement. Beide
aspecten van het spel zijn noodzakelijk om de tegenstander te verslaan. Ze zijn complementair van aard en versterken elkaar vaak.
Een voorbeeld van een typische situatie binnen Starcraft “Brood War” wordt weegegeven
op Figuur 3.1.
3.1. STARCRAFT
19
Figuur 3.1: Een voorbeeld van Starcraft: Brood War.
3.1.1
Macromanagement
Macromanagement omvat alle activiteiten en beslissingen op langere termijn. Deze langetermijnbeslissingen omvatten enerzijds economische beslissingen zoals wanneer en waar
een expansie gebouwd moet worden. Economische groei is in Starcraft namelijk de voornaamste motor om een groot leger uit te bouwen. Anderzijds is ook de compositie van
het leger belangrijk, zodat dit een zo goed mogelijk antwoord op de compositie van het
vijandig leger biedt. Elke eenheid heeft namelijk bepaalde zwaktes die kunnen uitgebuit
worden door andere eenheden (banelings zijn bijvoorbeeld over het algemeen zeer sterk
tegen soldaten maar zeer slecht tegen bepanserde eenheden).
Om correcte macro beslissingen te kunnen maken gaan spelers enerzijds vaak voort op
20
HOOFDSTUK 3. TOOLS
het eigen gevoel dat gevormd werd door vele ervaringen. Anderzijds bouwen ze ook vaak
op conventionele tactieken die uit studie zijn voortgekomen. Er zijn geen gouden regels
die zorgen voor perfecte macro beslissingen door de zee van mogelijke situaties die zich
kunnen voortdoen. Dit zorgt er eveneens voor dat er vele matches nodig zijn om het
nodige fingerspitzengef¨
uhl te kweken om correcte macro beslissingen te nemen.
3.1.2
Micromanagement
Micromanagement gaat over alle kortetermijnbeslissingen die een voordeel kunnen betekenen tegenover de tegenstander. Meestal is deze component zeer aandachts-intensief en
behoeft deze een hoge concentratie. Een voorbeeld is het individueel besturen van de
eenheden om er zo mogelijk effici¨enter gebruik van te maken. Eenheden met een slechte
gezondheid kunnen bijvoorbeeld teruggetrokken worden waardoor de toegebrachte schade
aan deze eenheid beperkt blijft.
Een ander voorbeeld van micromanagement is de kiting techniek. Deze techniek bestaat er
uit eenheden met een grote aanvalsafstand individueel te controleren en afwisselend aan te
vallen en weg te manoeuvreren van de vijand. Hierdoor blijven de eigen eenheden buiten
schot terwijl ze tegelijkertijd toch kunnen aanvallen. Een voorbeeld hiervan is het vechten
van soldaten (lange aanvalsafstand) tegen “banelings” (zeer korte aanvalsafstand) waar
soldaten vaak enkel kunnen winnen door het kiten van de banelings en de soldaten ruim
te verspreiden over het speelveld.
Op economisch vlak kan micromanagement ook een groot voordeel betekenen door bijvoorbeeld de timing van de bouwvolgorde van de verschillende eenheden en gebouwen
te perfectioneren. Professionele spelers kunnen deze volgordes tot op de seconde perfect
uitvoeren wat vaak een grote invloed heeft op het later verloop van het spel.
Om deze micromanagement technieken parallel en succesvol toe te passen op een omvangrijk leger zijn echter een zeer groot aantal acties per minuut nodig wat ook meteen de reden
3.2. BWAPI
21
is dat de toepassingen van deze technieken vaak de uitstekende spelers van de topspelers
onderscheidt. Ze zorgen ook voor dat Starcraft geen artifici¨ele grens heeft op het gebied
van moeilijkheid waardoor spelers zich eindeloos kunnen verbeteren en ontplooien wat voor
een hoge competitiviteit zorgt.
3.1.3
Fog of war
Een ander belangrijk concept in Starcraft is de Fog of war (FOW). De FOW is aanwezig
op alle gebieden waar de speler geen eenheden of gebouwen heeft. Dit houdt in dat deze
speler daar geen vijandelijke eenheden of gebouwen kan zien. Dit spelmechanisme maakt
het opzettelijk moeilijk voor de spelers om een globale visie op de map, en de vooruitgang
en expansie van de vijand te houden. Ook is het belangrijk op te merken dat Starcraft
verhoogde gebieden bevat waar eenheden die beneden staan geen zicht op hebben tot ze zich
naar hetzelfde niveau begeven. Hierdoor kan een speler een tactisch voordeel opbouwen
door zijn eenheden hogerop te plaatsen aan belangrijke chokepoints (smalle doorgangen).
Door de FOW is het uitermate belangrijk om te scouten. Scouting is het verzamelen van
informatie over de activiteiten van de vijand door ´e´en of meerdere eenheden rond de map
te sturen en de FOW weg te werken rond de vijand. Scouting is een essenti¨ele techniek in
Starcraft die het toelaat vroegtijdig te anticiperen op de beslissingen van de vijand.
3.2
BWAPI
Aangezien Starcraft strikt “closed source” 1 is is het onmogelijk om broncode toe te voegen
of aan te passen. Om het toch mogelijk te maken te communiceren met het spel door middel
van code is de “Brood War Application Programming Interface” (BWAPI) ontwikkeld.
Dit framework, volledig ontwikkeld in C++, laat toe om alle informatie te bevragen die
1
Closed source of Propri¨etaire software is software waarvan de broncode niet openbaar gemaakt wordt.
22
HOOFDSTUK 3. TOOLS
een gebruiker kan raadplegen binnen het spel vanuit een geschreven programma. Ook
kunnen er gemakkelijk commando’s gegeven worden aan eenheden, gebouwen, menus ...
Een voorbeeld van de mogelijkheden van BWAPI wordt getoond in figuur 3.2
Figuur 3.2: Een voorbeeld van BWAPI in actie. Door
visuele toevoegingen zoals gekleurde vormen en tekst
kan BWAPI op een intu¨ıtieve manier informatie overbrengen.
Naast de activiteiten die de speler zelf ook kan uitvoeren is het mogelijk om het spelverloop
te versnellen, het opstarten van spellen te automatiseren en het programma te debuggen.
Al deze features samen geven een mooi framework om verschillende AI technieken op toe
te passen. Het mag dan ook geen verrassing zijn dat Starcraft samen met BWAPI een van
de meest gebruikte tools is bij het onderzoek naar AI binnen strategiespellen. Meer dan
60 verschillende academische papers hebben BWAPI gebruikt als implementatieplatform.
Elk jaar vinden er een aantal competities plaats tussen verschillende AI’s die gebruik
maken van BWAPI [6]. Enkele belangrijke competities zijn AIIDE, CIG (Universiteit van
Dortmund) en SSCAI (Universiteit van Comenius) waar AI’s volledige spellen moeten
3.2. BWAPI
23
uitspelen tegen elkaar. Het is vooral een test om de verschillende cutting-edge technieken
naast elkaar in actie te zien waardoor het onderzoek naar betere AI technieken constant
op de spits gedreven wordt.
24
HOOFDSTUK 3. TOOLS
25
Hoofdstuk 4
Framework
In deze thesis is het naast het analyseren van complexe situaties in een spelomgeving
ook de bedoeling om een modulair en flexibel framework te ontwerpen dat toelaat om op
eenvoudige wijze complexe geaggregeerde PF’s op te stellen. Dit framework moet het ook
eenvoudig toelaten om velden op temporeel vlak te aggregeren. Dit is namelijk essentieel
om complexe analyses te maken in een RTS spel.
In dit hoofdstuk bespreken we de opbouw en structuur van het framework en lichten
we ook toe waarom we bepaalde keuzes gemaakt hebben bij het ontwerp ervan. Hierna
beschrijven we verschillende operatoren die het framework kracht geven in Sectie 4.2.3. Tot
slot bespreken we ook enkele optimalisaties om de performantie te verhogen zoals caching
in Sectie 4.2.5.
4.1
Keuze van de implementatie taal
Het framework is ontworpen in C++ wat enkele voordelen met zich meebrengt:
Snelheid
Een van de grootste redenen waarom C++ een zodanig dominante programmeertaal
26
HOOFDSTUK 4. FRAMEWORK
is, is de snelheid gecombineerd met een hoog abstractieniveau dat OOP mogelijk
maakt. Aangezien we realtime analyses willen doen over een grote 2D spelwereld is
C++ de evidente keuze om haperingen te voorkomen.
Compatibiliteit met BWAPI
Zoals hierboven besproken maken we voor de interactie met de spelwereld gebruik
van BWAPI. Aangezien deze interface ook volledig in C++ geschreven is kunnen we
zo optimaal gebruik maken van de functionaliteit binnen BWAPI.
OOP
Het gebruik van object-geori¨enteerd programmeren zal enorm handig blijken voor de
structuur van het framework. Hoofdzakelijk door polymorfisme kan veel onnodige
complexiteit vermeden worden.
4.2
Expressieboom
Een eerste concept dat we gebruiken is de expressieboom. Een expressieboom is een datastructuur die een eenvoudige evaluatie van een complexe expressie mogelijk maakt. De
bladeren van de expressieboom bestaan vaak uit variabelen of constanten die op zichzelf
makkelijk te evalueren zijn. De knopen in de boom die geen bladknoop zijn bevatten expressies (eenvoudige code) gebaseerd op de waarden van de kinderknopen. Deze knopen
kunnen we zien als aggregatoren van de kinderknopen, ze reduceren de evaluaties van elk
van de kinderknopen tot ´e´en evaluatiewaarde. Zo kunnen we Vergelijking 4.1 voorstellen
met een overeenkomstige expressieboom zoals te zien in Figuur 4.1.
√
2x + y
10
(4.1)
In onze complexere expressieboom, waar we in plaats van met constante waarden of variabelen met potentiaalvelden werken, hebben we een klassediagram zoals te zien in Appendix
A. We zullen nu elk van de knopen overlopen om een duidelijk inzicht in de werking ervan
te verschaffen.
4.2. EXPRESSIEBOOM
27
Resultaat
/
10
+
*
√
x
2
y
Figuur 4.1: De expressie in boomvoorstelling.
4.2.1
Expressieknoop
Deze abstracte klasse is de ouder van elke knoop. Alle kinderknopen dienen de evaluatiemethode te implementeren die de potentiaal op een co¨ordinaat teruggeeft. Door deze
interface waaraan elke knoop moet voldoen kunnen we gebruik maken van polymorfe methoden. Polymorfisme kan beschreven worden als het voorzien van ´e´en interface voor
verschillende types. Een polymorfisch type zoals de expressieknoop is een type wiens operaties kunnen toegepast worden op waarden van andere types (de subklasses van dit type).
Naast het bieden van een vaste interface voor knopen zorgt deze klasse ook voor caching
van reeds berekende potentialen met als gevolg performantiewinst. In Sectie 4.2.5 wordt
hier verder over uitgewijd.
De evaluatie methode vastgelegd door de expressieknoop is fundamenteel in het ontwerp
van ons framework. Deze methode neemt twee argumenten, de x en de y co¨ordinaat, die
28
HOOFDSTUK 4. FRAMEWORK
de positie bepalen in de 2D spelomgeving waar we het opgestelde veld willen evalueren.
De evaluatiemethode geeft steeds een decimaal getal terug: de lading van het veld op de
opgegeven positie. Dit is eveneens de enige informatie die andere objecten nodig hebben
over de knopen. Ze worden als het ware afgesloten van de logica binnenin de knoop en
hoeven zelfs niet te weten over welke type knoop het gaat (polymorfisme).
Een volgende opsplitsing die we zullen maken is die tussen operatorknopen en positieknopen.
4.2.2
Positieknoop
Deze klasse omvat alle knopen die eveneens ook bladeren van de boom zijn. Deze knopen
hebben dus geen bladeren en zijn op zichzelf gemakkelijk evalueerbaar. Deze waarde kan
ook een attribuut van een object zijn waardoor we de evaluatie van de boom kunnen
aanpassen door buiten de boom het object te wijzigen. Een verdere opsplitsing bestaat
tussen de constante knoop en de ladingsknoop.
4.2.2.1
Constante knoop
Een eerste type bladknoop is de voorstelling van een constante waarde. Deze bevat een
floating point waarde en geeft eenvoudigweg deze waarde terug bij de evaluatie. Het nut
van deze knopen ligt vooral in het toepassen van binaire operaties waarbij ´e´en van de
twee waarden vastligt. Denk aan het verzwakken van een veld met een bepaalde constante
factor. Of het instellen van een plafond bij het toepassen van de n-aire operator minimum.
4.2.2.2
Ladingsknoop
Een minder triviale knoop is de Ladingsknoop die de lading van een enkele eenheid voorstelt. Een Ladingsknoop bevat hierom een Unit instantie die in BWAPI een enkele eenheid
voorstelt. Deze instantie bevat onder andere de huidige positie van de eenheid. Naast de
4.2. EXPRESSIEBOOM
29
Unit instantie kan ook het type veld gekozen worden die de eenheid opspant. We voorzien
drie verschillende types velden:
ˆ Constant: Dit veld heeft dezelfde waarde in alle punten.
ˆ Linear: Dit veld verzwakt op een lineare manier afhankelijk van de euclidische af-
stand van de eenheid tot het punt waarop gemeten wordt en de gekozen decay waarde.
evaluate(x, y) = charge − charge · decay · euclidianDistance
(4.2)
ˆ Gaussiaans: Hier wordt een gaussiaans veld opgespannen wat ervoor zorgt dat de
lading op geen enkel punt nul is maar dat de lading asymptotisch naar nul gaat als
de afstand tot het centrum groter wordt. Voor de parameter µ (mean) nemen we
nul aangezien de potentiaal het hoogst moet zijn als de afstand tot het centrum nul
is. De parameter σ (standaardafwijking) kunnen we variabel kiezen naargelang de
breedte van de basis die we wensen.
2
1
2
Gaussian(x) = √ e−(x−µ) /2σ
σ 2π
4.2.3
(4.3)
Operatorknopen
Naast vaste waarden willen we uiteraard ook operaties toepassen op de hiernet gedefinieerde potentiaalvelden. In deze sectie bespreken we een ruim aantal ge¨ımplementeerde
operatorknopen die samen gebruikt worden met de reeds besproken waardeknopen. We
splitsen de operatoren op in drie fundamentele types: de unaire operatoren die ´e´en kind
bezitten, de binaire operatoren die twee kinderen bezitten en ten slotte de n-aire operatoren die een variabel aantal argumenten nemen. Het aantal argumenten is hier steeds gelijk
aan het aantal kinderen waar de desbetreffende knoop over beschikt.
Merk op dat we bij enkele traditioneel binaire operatoren verkiezen deze te implementeren
als een n-aire operatorknoop. Dit doen we enkel bij operatoren die zowel associatief als
30
HOOFDSTUK 4. FRAMEWORK
commutatief zijn om het gebruiksgemak te verhogen wanneer we met een groot aantal
argumenten werken (anders is een lange aaneenschakeling van de binaire variant nodig).
Een voorbeeld hiervan is de som operator.
4.2.3.1
Unaire Operatoren
Negatie
Een eerste operator is de negatieoperator die een potentiaalveld als argument neemt en een
veld terug geeft dat in elk punt een waarde bevat die gelijk is in absolute waarde, maar
waarvan het teken anders is.
negatex,y : R → R
x 7→ −x
(4.4)
(4.5)
Het nut van deze operator ligt bij het opstellen van repulsieve velden. Zo moeten we het
type veld (positief of negatief) niet inbakken in de bladknopen die dan enkel de vorm en
sterkte van het veld moeten vastleggen. Dit verhoogt de modulariteit en herbruikbaarheid
van de bladknopen en de andere operatoren. In Figuur 4.2 wordt de operator toegepast
op een lineair potentiaalveld. Rechts ziet u het originele veld en links de negatie van dit
veld door het toevoegen van een negatie operator.
4.2. EXPRESSIEBOOM
31
Figuur 4.2: Een voorbeeld van de negatie operator met links een negatief veld en rechts
een positief veld.
Begrenzing (cutoff )
Soms is het nuttig een operator te bezitten die de invloed van een potentiaalveld begrenst
tot een bepaalde afstand van de bron. Dit is net het doel van de begrenzingsoperator.
Door bijvoorbeeld het constante veld besproken in Sectie 4.2.2.1 vooraf te laten gaan door
deze operator kunnen we een cirkelvormig veld opstellen dat in alle punten binnen de cirkel
dezelfde lading heeft. Zonder deze operator zou het constante veld zich over de volledige
2D-ruimte uitstrekken.
cutoffx,y : R → R

 x : d((x, y), (x , y )) =< z
0
0
x 7→
 0 : d((x, y), (x , y )) > z
0
0
(4.6)
(4.7)
In de definitie van deze operator (Vergelijking 4.7) hebben we twee extra parameters,
namelijk (x0 , y0 ) en z. De eerste is de co¨ordinaat van de bron van de lading die nodig is om
32
HOOFDSTUK 4. FRAMEWORK
de euclidische afstand te kunnen berekenen. De tweede parameter die wordt meegegeven
bij de initialisatie van de begrenzingsoperator is de afstand tot waar het veld begrensd
moet worden. De lading op alle posities die verder dan z van de bron van de lading liggen
zal dus 0 zijn.
(a) Geen begrenzing
(b) Begrenzing van 150
(c) Begrenzing van 100
Figuur 4.3: Illustratie van de begrenzingsoperator toegepast op hetzelfde veld
In Figuur 4.3 wordt het gebruik van de begrenzingsoperator ge¨ıllustreerd op een constant
veld met lading 1 (maximale lading).
Merk ook op dat deze operator enkel een positieknoop als kindknoop kan bezitten aangezien
de positie van de bron van het veld gekend moet zijn om deze nuttig te kunnen toepassen.
Drempel (threshold)
Naast een begrenzing op basis van de euclidische afstand zoals besproken in de vorige sectie
is het soms ook nodig om een veld te beperken op basis van de grootte van de lading. De
operator die dit voorziet zullen we de drempeloperator noemen. Bij het aanmaken van
deze operatorknoop dienen we een drempelwaarde op te geven. Een specifieke use case
van deze operator is het scenario waar we met ´e´en of meerdere geaggregeerde gaussiaanse
potentiaalvelden werken. Zoals we eerder gezien hebben, naderen deze velden asymptotisch
naar 0 en hebben we dus veel posities waar de lading zeer klein is en geen significante
4.2. EXPRESSIEBOOM
33
betekenis meer heeft.
thresholdx,y : R → R

 x : x >= z
x 7→
 0:x<z
(4.8)
(4.9)
In deze stuksgewijze functie gedefinieerd in Vergelijking 4.11 worden alle ladingen kleiner
dan een bepaalde z - vastgelegd bij initialisatie - gereduceerd naar 0.
(a) Geen drempel
(b) Drempel van 0.5
Figuur 4.4: Illustratie van de drempeloperator toegepast op hetzelfde veld
Een voorbeeld van de drempeloperator ziet u in Figuur 4.4 waar we deze operator toevoegen
aan een lineair potentiaalveld. In het eerste geval is er geen operator aanwezig, in het
tweede geval gebruiken we een drempeloperator met een drempelwaarde 0.5. Let vooral
op het abrupte einde van het veld bij het gebruik van de drempeloperator.
34
4.2.3.2
HOOFDSTUK 4. FRAMEWORK
Binaire Operatoren
Verzwakking (decay)
De verzwakkingsoperator is de eerste binaire operator en laat het toe een veld te verzwakken
door dit te vermenigvuldigen met een ander potentiaalveld (eventueel een constant veld).
decayx,y : R × R → R
x, y 7→ x.y
(4.10)
(4.11)
Een belangrijke operator om temporele potentiaalvelden op te stellen is de verzwakkingsoperator. Om de temporaliteit visueel voor te stellen is het soms nodig bepaalde potentiaalvelden te doen afzwakken, afhankelijk van de verlopen tijd sinds het vastleggen van
deze potentiaalvelden. Een specifieke toepassing hiervan, en alsook een use case die later
besproken wordt, is het bepalen van bewegingspatronen.
4.2.3.3
n-aire operatoren
Het grootste deel van de operatorknopen zijn n-aire operatoren die een variabel aantal
expressieknoop-argumenten kunnen aannemen.
Minimum
Deze operator evalueert alle kindknopen op de opgevraagde positie en geeft het minimum
van alle evaluaties terug. Deze operator is enorm handig als we bijvoorbeeld een bovengrens willen opleggen aan ons potentiaalveld. Dit bereiken we door een minimumoperator
te gebruiken met twee kinderen. Enerzijds het veld waar we een bovengrens aan willen
opleggen en anderzijds een constante knoop (besproken in Sectie 4.2.2.1) ge¨ınitialiseerd
met de waarde die we als bovengrens willen gebruiken.
4.2. EXPRESSIEBOOM
35
minimumx,y :R∗ → R
(4.12)
x1 , . . . , xn 7→ min(x1 , . . . , xn )
(4.13)
In Figuur 4.5 zien we de minimumoperator toegepast op een lineair potentaalveld met een
maximum van 1 en een constante knoop ge¨ınitialiseerd met de waarde 0.7. Let in (b) en
(d) vooral op het gecre¨eerde plateau met een waarde 0.7.
Maximum
Deze operator is volledig analoog aan de minimumoperator maar we nemen hier het maximum van de evaluaties van de kinderen. Deze operator is onder meer handig om benedengrenzen op te leggen aan bepaalde velden.
maximumx,y :R∗ → R
(4.14)
x1 , . . . , xn 7→ max(x1 , . . . , xn )
(4.15)
Som (sum)
De som operator is een vrij voor de hand liggende operator. De evaluatie van deze operator
is gelijk aan de som van de evaluaties van alle kinderen. Deze operator wordt verder vaak
gebruikt om meerdere potentiaalvelden te aggregeren tot ´e´en potentiaalveld.
Merk op dat we hiermee positieve en negatieve potentiaalvelden elkaar kunnen laten uitmiddelen.
sumx,y :R∗ → R
x1 , . . . , xn 7→
(4.16)
n
X
i=0
xi
(4.17)
36
HOOFDSTUK 4. FRAMEWORK
(a) Geen bovengrens
(b) Bovengrens van 0.7
(c) Geen bovengrens met waarden
(d) Bovengrens van 0.7 met waarden
Figuur 4.5: Illustratie van de minimumoperator als bovengrens
4.2. EXPRESSIEBOOM
37
Gemiddelde (average)
De gemiddelde operator laat toe om potentiaalvelden minder grillig te maken door deze
operator te te passen op de velden samen met een constant veld. Hierdoor trekken we de
potentiaalwaarden van het resulterende veld dichter bij de waarde van dit constant veld.
Een andere handige toepassing is het herschalen van een aggregatie van verschillende potentiaalvelden. Wanneer we n velden hebben met elk een bepaalde maximale waarde k
kunnen we er zeker van zijn dat het resulterend potentiaalveld na het toepassen van de
gemiddelde operator ook een waarde zal geven die hoogstens k is. Dit resultaat is dan
afhankelijk van de relatieve grootte van de som van de verschillende potentiaalvelden. Dit
is enorm handig indien we de waarden van een potentiaalveld willen visualiseren door een
welbepaald interval te mappen op het RGB spectrum (0-255).
averagex,y :R∗ → R
(4.18)
n
1X
xi
x1 , . . . , x n →
7
n i=0
4.2.3.4
(4.19)
Geheugenknoop (memory)
Wanneer we de zo net gedefinieerde operatoren overlopen kunnen we vaststellen dat de
bouwblokken het momenteel niet toelaten om veranderingen in de tijd vast te leggen (het
temporeel aspect dat we willen bekomen). We kunnen momenteel enkel bij elke evaluatie
een momentopname nemen die zich aanpast aan de positie van de eenheden. Om nuttige
analyses te kunnen opstellen hebben we nood aan deze temporele informatie, meer specifiek
de veranderingen van het potentiaalveld in de tijd, wat mogelijk gemaakt wordt door de
geheugenknoop.
De geheugenknoop bestaat fundamenteel uit twee delen: de geheugenoperator en de geheugenbladknoop.
38
HOOFDSTUK 4. FRAMEWORK
Deze knopen worden apart van de andere operatoren besproken om de synergie te benadrukken.
Resultaat
Geheugen operator
2D Tabel
Maximum operator
Verzwakkings operator
Ladingsknoop
Figuur 4.6: De structuur van een voorbeeld van de geheugenknoop
Geheugenbladknoop
De geheugenbladknoop bevindt zich zoals te verwachten onderaan in de expressieboom en
heeft dus geen kindknopen. Deze knoop bevat een referentie naar een 2D tabel waarin
waarden worden opgeslagen. Bij het evalueren van deze knoop op een bepaalde positie
wordt de waarde uit de tabel op de overeenkomstige plaats eenvoudigweg teruggegeven.
Geheugenoperator
De geheugenoperator is een tweede essentieel deel van de geheugenknoop. Dit is een unaire
operator (neemt ´e´en expressieknoop als argument) die dezelfde evaluatiewaarde terug geeft
4.2. EXPRESSIEBOOM
39
als zijn kindknoop. Deze operator verandert dus functioneel niks aan de berekening binnen
de expressieboom. De operatorknoop bevat ook een referentie naar dezelfde 2D tabel
waar de geheugenbladknoop naar verwijst. Wanneer de evaluatiemethode van deze knoop
opgeroepen wordt, wordt de evaluatiewaarde van de kindknoop berekend en wordt de
waarde in de 2D tabel op de desbetreffende positie aangepast met de nieuwe waarde.
Voorbeeld
Met de twee besproken onderdelen kunnen we nu een constructie bouwen die over een
geheugen beschikt. We zullen nu een voorbeeld opstellen waar we het spoor van ´e´en
bepaalde eenheid willen vastleggen in de tijd.
Eerst en vooral zullen we van deze eenheid een lineair potentiaalveld maken door het
gebruik van een ladingsknoop (zie Sectie 4.2.2.2). Een tweede bladknoop is de geheugenbladknoop die de aggregatie van de vorige toestanden zal bijhouden na elke evaluatie. Als
aggregatieoperator tussen de aggregatie van het verleden en de huidige toestand kiezen we
de maximumoperator. Deze heeft dus twee kindknopen, namelijk de ladingsknoop en de
geheugenbladknoop. Tot slot plaatsen we een geheugenoperator voor de maximumoperator om het geheugen aan te passen na de evaluatie. De volledige constructie kan u zien in
Figuur 4.6.
Het voorbeeld wordt toegepast in Starcraft in de Figuur 4.7, waar het pad dat de eenheid
gevolgd heeft duidelijk zichtbaar wordt door het potentiaalveld.
40
HOOFDSTUK 4. FRAMEWORK
Figuur 4.7: De memoryknoop in Starcraft toegepast
4.2.4
Compositie van operatoren
In de vorige sectie hebben we enkele belangrijke operatoren besproken die we kunnen zien
als de bouwblokken van ons framework. Een groot voordeel van de modulariteit van deze
bouwblokken is dat we nieuwe operatoren kunnen ontwerpen bestaande uit een compositie
van verschillende bestaande operatoren.
Net zoals in de wiskunde de compositie van twee functies f ◦ g tot een nieuwe functie
leidt, leidt de compositie van meerdere operatorknopen tot een nieuwe operator die we
gemakkelijk verder als een bouwblok kunnen gebruiken. Het aantal argumenten van deze
nieuwe operator is gelijk aan de som van het aantal argumenten van de bladknopen (indien
deze een operatorknoop zijn).
4.2. EXPRESSIEBOOM
41
Operator knoop
Resultaat
Positie knoop
Maximum operator
Constante knoop
0
Minimum operator
Constante knoop
1
Argument
Figuur 4.8: Een voorbeeld van een operator compositie die de potentiaal
begrenst binnen het [0,1] interval.
In Figuur 4.8 zien we een compositie van een maximumoperator en een minimumoperator tot een nieuwe operator die ´e´en argument neemt en vervolgens alle evaluatiewaarden
transformeert naar een evaluatiewaarde binnen het interval [0, 1].
4.2.5
Caching
Aangezien de analyses in real-time gebeuren en het aantal bevragingen aan de expressieboom lineair schaalt met de grootte van de map is het belangrijk om enkele technieken
toe te passen die de performantie verbeteren. Caching is een techniek die bestaat uit het
tijdelijk opbergen van gegevens om een snellere access-time te faciliteren. Hierbij dient de
cache ook transparant te zijn in gebruik.
42
HOOFDSTUK 4. FRAMEWORK
Memoization is een speciale vorm van caching die gebruikt wordt om functies te optimaliseren. Hier worden reeds berekende outputs samen met hun argumenten opgeslagen bij
het uitvoeren van de functie. Indien de functie een tweede maal opgeroepen wordt met
dezelfde argumenten wordt de waarde uit de cache terug gegeven en dienen er geen extra
berekeningen gemaakt te worden.
De expressieknoop voorziet een overkoepelende methode die memoization toelaat voor de
evaluatiemethode, en dit voor elke knoop apart. Tijdens de initialisatie van een knoop
kunnen we al dan niet kiezen of deze memoization moet voorzien. Aangezien we hier wel
met dynamische bladknopen zitten die constant van positie veranderen zal de evaluatiemethode met dezelfde argumenten echter niet altijd hetzelfde resultaat geven. Hierom laten
we toe een deelboom al dan niet geforceerd te evalueren wat betekent dat hij de cache zal
verversen. We kunnen deze memoization nu gebruiken om elke x frames een cache refresh
te doen en de benodigde rekenkracht sterk te verminderen.
43
Hoofdstuk 5
Use cases
Nu we de structuur en de werking van het framework uitvoerig besproken hebben in Hoofdstuk 4 en de bijhorende operatoren uit de doeken gedaan hebben stellen we dit framework
op de proef door enkele uiteenlopende use cases. Door diverse use cases te kiezen willen we
ook aantonen dat het framework flexibel genoeg is om toegepast worden in verschillende
velden, zoals reeds vermeld in de inleiding.
We zullen in totaal voor vier use cases een expressieboom opstellen die de gewenste functionaliteit implementeert aan de hand van (temporele) aggregatie van potentiaalvelden.
Aangezien we een visuele analysetool bouwen voor menselijk gebruik is de kwantificatie
van de correctheid van het model niet eenvoudig. De “correctheid” is hier een vrij subjectief gegeven dat vaak afhangt van persoonlijke voorkeur. Hierom zullen we na het bouwen
van de expressieboom deze toepassen op gespeelde spellen en kritische spelsituaties analyseren met de gecre¨eerde overlay.
Naast de expressieboom dienen ook de parameters van de aparte knopen afgesteld worden.
Er zijn drie soorten parameters die een grote invloed hebben op het resulterende veld:
ˆ De grootte van de lading van de basis potentiaalvelden of de sterkte van de velden.
ˆ De decay rate parameter van de basis potentiaalvelden die aangeven hoe ver het veld
44
HOOFDSTUK 5. USE CASES
uitspreid.
ˆ De decay rate parameter bij de verzwakkingsoperator samen gebruikt met de ge-
heugenoperator. Hierdoor kunnen we instellen hoe lang temporele informatie moet
behouden worden.
In de use cases zullen we gebruik maken van “heatmaps” om de potentiaalvelden visueel
voor te stellen. Deze heatmaps hebben een kleurcode waarbij groen een lage potentiaal en
rood een hoge potentiaal aanduidt.
5.1
Use case 1: Distributie van vijandig leger in spatiotemporeel domein
De eerste use case bestaat uit het analyseren van de distributie van de vijandige troepen
over de tijd. Deze analyse helpt spelers om bepaalde bewegingspatronen van het vijandige
leger te herkennen en het gravitatiepunt van het leger te kunnen bepalen.
5.1.1
Constructie van het model
We zullen beginnen bij de basis van de expressieboom, namelijk de bladeren. De individuele
vijandelijke eenheden zullen we voorstellen als lineaire potentiaalvelden waarbij sterkere
eenheden een sterker potentiaalveld opspannen.
Bij de aggregatie tussen de velden van de verschillende eenheden willen we dat meerdere
eenheden in elkaars nabijheid samen in een sterker veld resulteren. Hiervoor gebruiken we
de somoperator tussen de verschillende vijandige eenheden. De som van vele eenheden kan
echter wel leiden tot zeer hoge potentialen. We kiezen er dan ook voor de potentiaal te
begrenzen op 1 door gebruik te maken van de minimumoperator waardoor we de waarde
van de potentiaal gemakkelijk kunnen afbeelden op een RGB-waarde..
5.1. USE CASE 1: DISTRIBUTIE VAN VIJANDIG LEGER IN SPATIO-TEMPOREEL
DOMEIN
45
Nu we de spatiale informatie van de vijandelijke eenheden kunnen vastleggen rest ons
enkel nog het toevoegen van de temporele component. Hiervoor gebruiken we de geheugenoperator en bladknoop samen zoals besproken in Sectie 4.2.3.4 om een geheugen op
te bouwen. Het geheugen zullen we eerst verzwakken met een factor 0.99 m.b.v. de verzwakkingsoperator. De aggregatie van het resultaat hiervan en de huidige spatiale staat
zullen we doen door de maximum operator. Tot slot plaatsen we een geheugenoperator
voor deze maximumoperator zodat we het nieuwe berekende veld steeds kunnen opslaan
in het geheugen.
In Figuur 5.1 wordt het opgebouwde model in boomstructuur getoond.
Geheugen operator
Maximum operator
Verzwakkings operator
Geheugen bladknoop
Minimum operator
Contante knoop
1
Ladings knoop
Eenheid 1
Sommatie operator
...
Ladings knoop
Eenheid n
Figuur 5.1: Het model voor use case 1
5.1.2
Toepassing
Eerst en vooral dient opgemerkt te worden dat de visualisaties in deze use case met een
schaal van groen naar rood werken. Hierbij is groen de laagst mogelijke potentiaal en rood
de hoogst mogelijke potentiaal.
46
HOOFDSTUK 5. USE CASES
Het voornamelijkste doel dat we wensen te bereiken met het model opgesteld in de vorige
sectie is het herkennen van bepaalde patronen in de bewegingen van de vijandelijke troepen.
Dit model genereert als het ware een heatmap van de militaire eenheden waarbij oudere
posities vervagen met de tijd.
In het eerste opgestelde scenario zijn er twee aparte groepjes vijandige soldaten die elk
patrouilleren langs een pad voor de ingang van hun basis. In Figuur 5.2 worden er drie
voorstellingen gegeven van hetzelfde ogenblik.
Op de figuren van de toepassing van het model op dit scenario kunnen we duidelijk de
pattrouille route onderscheiden die de vijandelijke troepen volgen. Hierdoor kunnen we
bijvoorbeeld beslissen om langs de zijingang aan te vallen waar er zich geen verdediging
bevindt.
Een ander voordeel van dit veld is dat we in een oogopslag kunnen zien waar het zwaartepunt van het leger zich bevindt. Hierdoor kunnen we vanuit een optimale hoek aanvallen
en dus een tactisch voordeel opbouwen.
5.2
Use case 2: Optimale scouting regio’s bepalen
Zoals besproken in Sectie 3.1.3 is scouting een noodzaak om correcte beslissingen te kunnen
maken. Om hierbij te helpen zullen we een potentiaalveld opstellen dat aangeeft welke
gebieden dienen gescout te worden.
Enkele belangrijke eigenschappen van gebieden waar gescout moet worden zijn eerst en
vooral plaatsen die recent niet gescout is en waar er zich dus reeds gedurende een ruime
tijd een FOW bevindt. Hiernaast zijn plaatsen in de nabijheid van vijandelijke eenheden
interessant om te scouten aangezien dit een aanwijzing kan zijn dat er zich een basis bevindt
in de buurt. Tot slot zijn het handvol mogelijke startposities (in de buurt van mineralen)
5.2. USE CASE 2: OPTIMALE SCOUTING REGIO’S BEPALEN
(a) De potentiaalveld overlay bij een groepje soldaten
(b) Het speelveld
(c) Het opgestelde potentiaalveld
Figuur 5.2: Use case 1 met het opgestelde model
47
48
HOOFDSTUK 5. USE CASES
ook zeer nuttig om te scouten aangezien de vijand zich hier kan bevinden.
5.2.1
Constructie van het model
Eerst bepalen we de bladknopen van de expressieboom. Zoals hiervoor besproken dienen
we met verschillende factoren rekening te houden die we elk als bladknoop aan de expressieboom zullen moeten toevoegen. Eerst en vooral maken we een positief constant veld
over het gehele speelveld om alle posities initieel interessant te maken om te scouten.
De eigen eenheden en gebouwen geven we elk een constant potentiaalveld met een diameter
gelijk aan de afstand tot waar de eenheid kan zien. Hierna aggregeren we de eigen eenheden
met de maximumoperator en vervolgens voegen we de geheugen constructie toe, samen met
een verzwakkingsoperator zoals in use case 1. Voor de geheugenoperator plaatsen we een
negatieoperator aangezien reeds gescoute gebieden minder interessant zijn om opnieuw te
scouten.
De vijandige eenheden geven we lineaire potentiaalvelden aangezien we in de buurt van
deze eenheden willen scouten. Ook voor deze eenheden stellen we een geheugenconstructie
op zoals in use case 1 zodat we het temporele aspect kunnen vastleggen.
De plaatsen waar spelers kunnen uitbreiden zijn eveneens ook de plaatsen waar er zich
grondstoffen zoals mineralen bevinden. Om deze in kaart te brengen aan de hand van
potentiaalvelden zullen we de mineralen lineaire potentiaalvelden geven en als aggregatieoperator de sommatie gebruiken waardoor het punt met de grootste potentiaal eveneens
de plaats is die zich het dichtst bij de mineralen bevindt.
Om al deze componenten samen te voegen zullen we de sommatieoperator toepassen wat
zal leiden tot een globaal beeld van de meest voordelige plaatsen om te scouten.
In Appendix B wordt het model visueel voorgesteld. Hier is (a) het constante veld, (b) de
5.3. USE CASE 3: OPTIMALE EXPANSIEPLAATS BEPALEN
49
eigen eenheden, (c) de vijandelijke eenheden en (d) de mineralen.
5.2.2
Toepassing
Om het voordeel van deze use case in de verf te zetten voegen we enkele mineraal velden
toe aan het scenario uit use case 1. Een groepje mineralen aan de linkerkant en een groepje
onderaan het speelveld.
In het resultaat in Figuur 5.3 zien we het potentiaalveld nadat een eenheid een groepje
mineralen gescout heeft. De groene vlek op de heatmap geven gebieden aan waar er
eenheden aanwezig zijn of recent gescout is (zie het overeenkomstig patroon op de kaart).
De twee rode vlekken geven gebieden aan die nuttig zijn om te scouten aangezien deze
mineralen bevatten en waar een vijand dus een basis kan hebben. Wanneer een eenheid
een mineraalveld scout zoals in (a) te zien is, wordt deze rode vlek weggewerkt. In subfiguur
(c) wordt het potentiaalveld getoond nadat de eenheid enkele minuten stilstaat. Dit geeft
aan dat dit gebied recent niet gescout is geweest en een kandidaat is om opnieuw bezocht
te worden.
De strategie die spelers met deze overlay moeten volgen voor een maximum aan informatie
te verkrijgen is proberen zoveel mogelijk gebied groen te maken. En meer bepaald om de
rode vlekken weg te werken. Dit veld biedt kortom een intu¨ıtieve manier om om te gaan
met de problemen die de fog of war met zich meebrengt.
5.3
Use case 3: Optimale expansieplaats bepalen
Een derde en laatste use case voor het framework is het bepalen wat de meest opportune
plaats is om een nieuwe expansie te bouwen. Aangezien macroeconomie een belangrijke
motor voor de opbouw van het leger, is het nodig tijdig een expansie te bouwen om meer
grondstoffen te verzamelen en de tegenstander op lange termijn te verslaan door economische dominantie.
50
HOOFDSTUK 5. USE CASES
(a) De potentiaalveld overlay bij een groepje soldaten
(b) Het opgestelde potentiaalveld
(c) Het opgestelde potentiaalveld na afkoeling
(d) Het speelveld
Figuur 5.3: Use case 2 met het opgestelde model
5.3. USE CASE 3: OPTIMALE EXPANSIEPLAATS BEPALEN
51
Belangrijke eigenschappen voor een goede expansieplek is vooreerst de aanwezigheid van
grondstoffen zoals mineralen en gas. Zonder deze aanwezigheid heeft expansie geen nut,
deze eigenschap is dus een nodig criterium voor expansie. Hiernaast willen we nog twee
extra wenselijke eigenschappen toevoegen. Eerst en vooral hebben we het liefst dat de
expansie dicht bij de huidige basis en bij het leger ligt zodat deze beschermd kan worden.
Ten tweede bouwen we ook het liefst een expansie die zo ver mogelijk verwijderd ligt van
de eenheden van de tegenstander zodat deze expansie zo lang mogelijk onopgemerkt blijft.
5.3.1
Constructie van het model
Zoals altijd hanteren we ook bij deze use case een bottom-up strategie om de expressieboom
op te bouwen en beginnen we dus bij de bladknopen. Hier hebben we drie grote componenten: eerst en vooral de grondstoffen die we een sterk afnemende lineair potentiaalveld
geven aangezien dit een belangijke constraint is. Hiernaast zijn er de eigen eenheden die
we een zwak afnemende potentiaal geven zodat we het voordeel van nabije eenheden kunnen kwantificeren. En ten slotte zijn er de vijandelijke eenheden, die net zoals de eigen
eenheden, een zwakke lineaire potentiaal hebben, maar waarvoor we een negatieoperator
plaatsten zodat deze een omgekeerd effect heeft.
Bij de eigen en vijandelijke eenheden gebruiken we een geheugenconstructie om temporele
informatie te behouden. Dit betekent dat we ook plaatsen waar vijandelijke troepen recent
geweest zijn als minder aantrekkelijk zien. Uiteindelijk aggregeren we de drie componenten
door de sommatieoperator wat resultulteert in een potentiaalveld dat de optimale plek om
een expansie te bouwen de grootste potentiaal geeft.
In Appendix C wordt het opgestelde model voor deze use case getoond met (a) het constante veld, (b) de eigen eenheden, (c) de vijandelijke eenheden en (d) de mineralen.
52
5.3.2
HOOFDSTUK 5. USE CASES
Toepassing
Aangezien we met een constant basisveld werken zal in dit scenario de kleurcode iets anders
liggen. Hier is rood een optimale plaats om uit te breiden terwijl groen een zeer slechte
positie is om een expansie te vestigen. De gele kleur wijst op een gemiddelde suitability
(die dus weinig be¨ınvloed is).
In Figuur 5.4 wordt het resultaat getoond van de toepassing van het opgestelde model
op dit scenario. Enkele dingen die meteen duidelijk worden uit de heatmap is dat van
de vier groepjes mineraalvelden de twee bovenste het meest geschikt zijn voor expansie.
De grote gele vlek bovenaan wordt opgespannen door de eigen soldaten en geven dus een
positieve impuls voor expansie. Elk van de groepjes mineraalvelden spant ook een kleiner
maar sterker veld op, wat tot 4 lokale maxima leidt. Tot slot kunnen we ook onderaan de
heatmap zien dat het negatief geladen veld van de vijandelijke eenheden deels opgehoffen
wordt door de mineralen.
Door in dit model het globale maximum te zoeken waar er zich nog geen eigen basis
bevindt, vinden we meteen de meest optimale plaats om een expansie te vestigen. Het
visuele karakter van de overlay maakt het ook intuitief om snel conclusies te trekken.
5.3. USE CASE 3: OPTIMALE EXPANSIEPLAATS BEPALEN
(a) De potentiaalveld overlay bij een groepje soldaten
(b) Het speelveld
(c) Het opgestelde potentiaalveld
Figuur 5.4: Use case 3 met het opgestelde model
53
54
HOOFDSTUK 5. USE CASES
55
Hoofdstuk 6
Conclusie
In deze thesis heb ik aangetoond dat het door gebruik van expressiebomen samen met
potentiaalvelden mogelijk is om een adaptief en modulair framework te bouwen dat complexe aggregaties van potentiaalvelden mogelijk maakt. Deze aanpak laat het makkelijk
toe om extra operatoren te defini¨eren naast de set van operatoren die ik reeds besproken
heb. Hiernaast kunnen de parameters van de potentiaalvelden ook gewijzigd worden met
als doel het opstellen van verschillende types potentiaalvelden. Een belangrijke component
van het framework is de geheugenknoop die het temporele aspect incorporeert, wat een
must was om complexe analyses te maken in Starcraft.
Ten slotte heb ik het ontworpen framework ook toegepast op drie fundamenteel verschillende use cases in Starcraft waaruit blijkt dat het framework inderdaad adaptief en in
veel verschillende contexten toegepast kan worden. Deze implementatie in BWAPI liet
ook toe om visualisaties toe te voegen die spelers kunnen helpen om intu¨ıtief en real-time
beslissingen te maken op basis van de gegenereerde potentiaalvelden.
Een grote moeilijkheid ligt echter nog in het vastleggen van de parameters van de potentiaalvelden en aggregatoren. Dit moet momenteel nog empirisch gebeuren en het neemt
daardoor veel tijd in beslag om een correct veld op te bouwen. In de use cases hadden
meerbepaald drie parameters vaak een doorslaggevende impact tot een correct veld. Eerst
56
HOOFDSTUK 6. CONCLUSIE
en vooral de grootte van de ladingen van de aparte eenheden en meerbepaald het relatief
schalen van deze groottes. Vervolgens heeft ook de afzwakkingsratio van de potentiaalvelden veel invloed, deze bepaalt hoe ver het potentiaalveld invloed uitoefent. Tot slot is bij
het gebruik van de geheugenknoop de afzwakkingsparameter van zeer groot belang. Deze
parameter bepaalt hoe lang vooraf vastgelegde potentiaalvelden in het geheugen blijven en
dus hoe snel het model vervaagt.
57
Hoofdstuk 7
Toekomstig werk
Deze thesis opent vele nieuwe onderzoekspaden waarbij verder gewerkt wordt met het
ontworpen framework. De mogelijke toepassingen zijn ook niet beperkt tot louter RTS
spellen en kunnen in vele scenario’s toegepast worden waar potentiaalvelden nuttig zijn.
Denk bijvoorbeeld aan robotica of het opstellen van geografische modellen.
Een eerste mogelijke uitbreiding is het toevoegen van een nieuwe set operatoren. Een specifiek voorbeeld zijn logische operatoren of een mapping op verschillende functies. Deze techniek zou het toelaten om net zoals bij de LSP methode bepaalde vormen van gewenstheid
van bepaalde potentiaalvelden aan te geven na mapping op elementaire criteriumfuncties.
Een tweede mogelijke uitbreiding op dit framework is het toepassen van een genetische
heuristiek om een structuur op te bouwen aan de hand van het framework, gegeven enkele
basis potentiaalvelden en het gewilde resulterende potentiaalveld. Hierdoor kan het vaak
omslachtige proces van het opstellen van een expressieboom zoals we gedaan hebben in de
drie use cases geautomatiseerd worden.
Tot slot kan er ook onderzocht worden hoe we een slimmere cache kunnen bouwen voor
dit framework die rekening houdt met de spatiale verplaatsingen zodat er herberekeningen
uitgespaard worden wat uiteindelijk tot een betere performantie leidt.
58
BIJLAGE A.
59
Bijlage A
60
BIJLAGE B.
Geheugenbladknoop
Constante
cknoop
ccccc1
Maximumcoperator
Minimumcoperator
...
Constantecknoop
cccccn
(b)
Maxcoperator
Negatiecoperator
Geheugencoperator
Verzwakkingscoperator
Constantecknoop
1
Constantecknoop
(a)
Ladingscknoop
ccccc1
Geheugenbladknoop
Ladingscknoop
ccccc1
Maximumcoperator
Geheugencoperator
Verzwakkingscoperator
Constantecknoop
1
Sommatiecoperator
...
...
Ladingscknoop
cccccn
(c)
Ladingscknoop
cccccn
(d)
61
Bijlage B
62
BIJLAGE C.
Geheugenbladknoop
...
(b)
Ladingscknoop
cccccn
Sommatiecoperator
Ladingscknoop
ccccc1
Maximumcoperator
Geheugencoperator
Verzwakkingscoperator
Constantecknoop
(a)
Sommatiecoperator
Geheugenbladknoop
Verzwakkingscoperator
Ladingscknoop
ccccc1
Maximumcoperator
Geheugencoperator
Negatiecoperator
Ladingscknoop
ccccc1
...
...
Ladingscknoop
cccccn
(c)
Ladingscknoop
cccccn
Sommatiecoperator
(d)
63
Bijlage C
BIBLIOGRAFIE
65
Bibliografie
[1] A. Howard, M. J. Mataric, and G. S. Sukhatme. Mobile sensor network deployment
using potential fields: A distributed, scalable solution to the Area Coverage Problem.
In Distributed Autonomous Robotic Systems, 2002, 2002.
[2] C.W. Warren. Global path planning using artificial potential fields. In Robotics and
Automation, 1989. Proceedings., 1989 IEEE International Conference on, pages 316–
321 vol.1, May 1989.
[3] P.E. Hart, N.J. Nilsson, and B. Raphael. A formal basis for the heuristic determination
of minimum cost paths. Systems Science and Cybernetics, IEEE Transactions on,
4(2):100–107, July 1968.
[4] TW Sanberg. Evolutionary multi-agent potential field based ai approach for ssc scenarios in rts games. Master’s thesis, University of Copenhagen.
[5] E. A. Rathe and J. B. Svendsen. Micromanagement in starcraft using potential fields
tuned with a multi- objective genetic algorithm, 2012.
[6] S. Ontanon, G. Synnaeve, A. Uriarte, F. Richoux, D. Churchill, and M. Preuss. A survey of real-time strategy game ai research and competition in starcraft. Computational
Intelligence and AI in Games, IEEE Transactions on, 5(4):293–311, Dec 2013.
[7] J. Hagelb¨ack and S. J. Johansson. A multiagent potential field-based bot for real-time
strategy games. Int. J. Comput. Games Technol., 2009:4:1–4:10, January 2009.
66
BIBLIOGRAFIE
[8] A. Uriarte and S. Onta˜
no´n. Kiting in rts games using influence maps, 2012.
[9] R. F. Cohen and R. Tamassia. Dynamic expression trees and their applications. In
Proceedings of the Second Annual ACM-SIAM Symposium on Discrete Algorithms,
SODA ’91, pages 52–61, Philadelphia, PA, USA, 1991. Society for Industrial and
Applied Mathematics.
[10] B. Stroustrup. The C++ Programming Language. Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA, 3rd edition, 2000.
[11] Johann Eder, Gerti Kappel, and Michael Schrefl. Coupling and cohesion in objectoriented systems, 1992.
[12] R. Cole and U. Vishkin. Vlsi algorithms and architectures. chapter Optimal Parallel
Algorithms for Expression Tree Evaluation and List Ranking, pages 91–99. SpringerVerlag, London, UK, UK, 1988.
[13] R. Cole and U. Vishkin. The accelerated centroid decomposition technique for optimal
parallel tree evaluation in logarithmic time. Algorithmica, 3(1-4):329–346, 1988.
[14] D. Michie. ”Memo”Functions and Machine Learning. Nature, 218(5136):19–22, April
1968.
[15] D. Versteele. Multi-agent potential field aggregation by behavior trees. Master’s thesis,
University of Ghent.
LIJST VAN FIGUREN
67
Lijst van figuren
1.1
De evolutie van de RTS . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4
2.1
Een voorbeeld van een artificieel potentiaalveld . . . . . . . . . . . . . . .
11
2.2
Depth first traversal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
14
3.1
Een voorbeeld van Starcraft: Brood War. . . . . . . . . . . . . . . . . . . .
19
3.2
Een voorbeeld van BWAPI in actie. Door visuele toevoegingen zoals gekleurde vormen en tekst kan BWAPI op een intu¨ıtieve manier informatie
overbrengen. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
22
4.1
De expressie in boomvoorstelling. . . . . . . . . . . . . . . . . . . . . . . .
27
4.2
Een voorbeeld van de negatie operator met links een negatief veld en rechts
een positief veld. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
31
4.3
Illustratie van de begrenzingsoperator toegepast op hetzelfde veld . . . . .
32
4.4
Illustratie van de drempeloperator toegepast op hetzelfde veld . . . . . . .
33
4.5
Illustratie van de minimumoperator als bovengrens . . . . . . . . . . . . .
36
4.6
De structuur van een voorbeeld van de geheugenknoop . . . . . . . . . . .
38
4.7
De memoryknoop in Starcraft toegepast . . . . . . . . . . . . . . . . . . .
40
68
LIJST VAN FIGUREN
4.8
Een voorbeeld van een operator compositie die de potentiaal begrenst binnen
het [0,1] interval. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
41
5.1
Het model voor use case 1 . . . . . . . . . . . . . . . . . . . . . . . . . . .
45
5.2
Use case 1 met het opgestelde model . . . . . . . . . . . . . . . . . . . . .
47
5.3
Use case 2 met het opgestelde model . . . . . . . . . . . . . . . . . . . . .
50
5.4
Use case 3 met het opgestelde model . . . . . . . . . . . . . . . . . . . . .
53
LIJST VAN TABELLEN
69
Lijst van tabellen
3.1
Vergelijking van de rassen in Starcraft . . . . . . . . . . . . . . . . . . . .
18

Een monorail in combinatie met bochte - Lyftman LR

Nieuw: Se-n-Se richting PPT

Procestechniek BBL-opleidingen

QS Mechanisch operator B

9 Formalisme van de QM: observabelen en eigenfuncties

Uniformisering eenheden en herstandaardisatie GGT

Begeleidingsformulier

pdf formaat

Download vacature