Поделиться через

RTS Battle simulation with IronPython

  • Статья

I used Python to simulate Age of Empires archer battles.  I wanted to be able to answer questions like:

  1. If 12 archers attack 10 archers, what will the margin of victory be?
  2. If two armies of the same size attack each other, how do different strategies affect the outcome?

This also led to some practical strategies and some quiz questions about why certain behaviors occur.

Python is good for both quickly modeling systems like this and easily running the queries. Code snippets need to be able to:

  1. Concisely represent the query. If we can ask the question in 1 sentence of English, we don't want 6 pages of code to write the same query.
  2. Allow operations like averaging across multiple runs.
  3. Scale to arbitrary complexity, and potentially include arbitrarily complex algorithms ( Turing machine calculations).

These queries would be painful to express in C# 1.0 (although certainly improved with C# 3.0 and Linq). Many interesting queries can be written in literally a single line of Python code. 

I wrote all these snippets using IronPython, a Python implemention on .NET.

 

This is a relatively large entry because I wanted to deliver an end-to-end view in a single entry. It's broken into the following parts:

  1. The rules.
  2. The Python code for emulating them.
  3. Concise queries and pretty charts.

 

The Rules

The rules for the simulation:

The rules (as I observe in AOE, Dune 2, and other RTS games) that I'm simulating here are:

  1. Each unit has a health meter. (In my case, I arbitrarily chose 50 HP.)
  2. A unit is alive if health > 0.
  3. Time is broken into discrete turns. (In RTS, these turns operate on a timer, so if you snooze, you lose. )
  4. At each turn, each live unit can attack any enemy unit.  (Imagine the units are short-ranged like archers.)  This results in the target unit's HP decreasing by the attack value (in this case, 1 HP per attack).
  5. All units issue their attacks simultaneously. So 2 units may kill each other at the same time. (This avoids bias in the order units issue attacks).

So if 2 units are attacking each other, they'd both start out with 50 HP, and each turn, they'd both attack the other one and decrease 1 HP. After 50 turns, they'd both kill each other.

Complexity from Simplicity

This is a pretty simple set of rules. Specifically:

  1. The rules are deterministic. There is no dice-rolling. (Contrast to the battle system in Civilization or Risk.)
  2. All units are identical. Units don't have a location, so they don't need to maneuver into positions or worry about neighbors.
  3. A unit's attack power doesn't decrease with damage, so a 1% HP and 100% HP have the same offensive capability. 
  4. If 10 units all attack the same foe in a given turn, and the first one kills him, then the other 9 units are attacking a corpse for that turn and thus wasting their ammo.

A more complex simulation could of course change any of these to try to get a more accurate simulation.  In fact, when I first started the simulation, I figured that I'd soon be adding more complexity. However, just applying simple rules on large scales can quickly lead to complex behavior. (see Emergent Properties for more on this) See the graphs below for some examples.

 

Policy: who do you attack?

A policy issue that arises out of rule #3 is "what enemy unit does each individual unit attack?" For example, say we have a 3 on 3 battle (A,B,C vs. X,Y,Z). Does each unit just attack a random opponent on the other side? Does an entire army gang up on the weakest opponent to try to take him out? Does an army coordinate to avoid wasted ammunition?

 

The Python Code

Modeling:

This is a pretty simple set of rules to model with Python. I model the unit with a class cleverly named Unit, which just encapsulates health and attack policy. A single turn of attacks is executed by the Attack1 function.

Here's the essential code. Note that it's under 50 lines, and that's even including some asserts and comments:

 

 #---------------------------------
# Inidividual unit.
class Unit:
  def __init__(self, fpAttackPolicy=PickWeakest):
    self.healthStart = self.health=50
    self.fpAttackPolicy = fpAttackPolicy
  def __str__(self):
    return "health: %d/%d" % (self.health, self.healthStart)
  def ApplyDamage(self, d):
    self.health -= d
    if (self.health < 0): self.health = 0
  # Return true iff is alive.
  def IsAlive(self): 
    return (self.health > 0)
  # Pick a target in the opposing army.
  def PickTarget(self, army):
    guy = self.fpAttackPolicy(army)
    assert(guy.IsAlive())
    return guy

#---------------------------------
# Given 2 arrays of armies, do a single round of attacks. 
# Return True if both armies are still alive. 
def Attack1(a1, a2):
  # 1) calculate targets
  # each alive unit can attack another unit.
  t1 = [x.PickTarget(a2) for x in a1 if x.IsAlive()]
  t2 = [x.PickTarget(a1) for x in a2 if x.IsAlive()]
  assert(len(t1) > 0)
  assert(len(t2) > 0)  
  # 2) apply targets.  
  # Apply all attacks at once, to avoid giving bias to order of attack. 
  # This allows 2 units to kill each other. 
  for x in (t1 + t2):
    x.ApplyDamage(1)
  # 3) check if armies are still alive
  if (NumAlive(a1) == 0): return False
  if (NumAlive(a2) == 0): return False  
  return True

# count how many in army are still alive.
def NumAlive(army):
  c = 0
  for x in army:
    if x.IsAlive(): c+= 1
  return c

 

 

Additional layers

You can layer simple utility functions on top of the essentials. For example, a Make() function creates an army (an array of Unit instances) for a given size that has the attack-weakest policy. MakeR is similar for an attack-random policy. A VictoryMargin() function quantifies how much army #1 defeated army #2 by. The Battle() function takes 2 armies and fights until 1 is destroyed and then returns some statistics about the battle.

 # Make an army
def Make(size, fpAttackPolicy=PickWeakest):
  return [Unit(fpAttackPolicy) for i in range(size)]

 # shorthand for Making army with 'random attack' policy
def MakeR(size):
  return Make(size, PickRandom)


 # return victory margin between 2 armies.
#  = (winner current health / winner starting health) * 100
#   negative for a1, positive for a2
#   0 if both are dead
def VictoryMargin(a1, a2):
    s1 = Stat(a1)
    s2 = Stat(a2)
    if s1.alive:
        assert(not s2.alive)
        return - s1.health * 100 / s1.healthStart
    elif s2.alive:
        assert(not s1.alive)
        return s2.health * 100 / s2.healthStart
    else:
        return 0 # both dead

# Fight the 2 armies until 1 is defeated, printing status at each turn.
# Return a rich summary object.
def Battle(a1, a2):
  turn = 0
  done = False
  print '-----------'
  while(True): 
    # print status
    print '%2d)' % (turn),
    for x in a1:
      print '%2d' % (x.health),
    print '|',
    for x in a2:
      print '%2d' % (x.health),
    print # end of line
    if (done): break
    turn+= 1
    done = not Attack1(a1, a2)
  print '-----------'
  v = VictoryMargin(a1, a2)
  print "done. Margin=%d%% (of victor's original health)" % (v)
  # Create a summary container for results.
  class Res:
    def __init__(self):
      self.turns = turn
      self.victory = v
      self.size1=len(a1) # starting size of each army
      self.size2=len(a2)  
      self.end1 = NumAlive(a1) # ending size of each army
      self.end2 = NumAlive(a2) 
  return Res()

  

 

 

 

Concise Queries and Pretty Charts

This section shows some simple queries and executions.

1) Simple 2 on 1 battle:

The following runs a battle of 2 units vs. 1 unit, showing the results after each turn.

   Battle(Make(2), Make(1))

Here's the output. Each row is a turn. The 4 columns are: turn #, Unit #1 of Team #1, Unit #2 of Team #1, and Unit #1 of Team #2.

 ----------- 0) 50 50 | 50 1) 49 50 | 48 2) 48 50 | 46 3) 47 50 | 44 4) 46 50 | 42 5) 45 50 | 40 6) 44 50 | 38 7) 43 50 | 36 8) 42 50 | 34 9) 41 50 | 3210) 40 50 | 3011) 39 50 | 2812) 38 50 | 2613) 37 50 | 2414) 36 50 | 2215) 35 50 | 2016) 34 50 | 1817) 33 50 | 1618) 32 50 | 1419) 31 50 | 1220) 30 50 | 1021) 29 50 |  822) 28 50 |  623) 27 50 |  424) 26 50 |  225) 25 50 |  0-----------done. Margin=-75% (of victor's original health)

All units here are using the "attack weakest opponent" policy. Not surprisingly, the side with 2 clobbers the side with just 1.  The bigger army has a 2:1 size advantage, but retains 75% of its original health, and 100% of its units stay alive.

 

2) If 2 armies of the same size randomly attack each other, is the outcome random?

Intuitively, you'd expect 2 equally-sized armies that randomly attack each other to be a toss-up. After all, there's too much symmetry to have a bias in winner.

We can verify this. This snippet runs a battle for nTimes and returns a vector of the victory margin from each battle. Recall victory margin is between -100 (if army1 has a perfect victory) and +100 (if army2 has a  perfect victory). 0 means a tie (i.e., both armies are killed).

 def NVictory_Random(size=5, nTimes=10):
  return frun(nTimes, lambda: Battle(MakeR(size), MakeR(size)).victory)

 

So you can run something like:
   l = NVictory_Random(5, 100)

to get a list of 100 trials of 5-on-5, and then see how close that is to a tie. A quick sanity check shows avg(l) gave an average of -.42, which is pretty close to zero.
However, to be more formal, you can run queries like:
   len([x for x in l if abs(x) <= 7])*100/len(l)
Which returned 95 for me, meaning that 95% of the results were within 7% of a tie (0).

Or, just run the standard deviation for the data set l against an expected target value of 0:
   math.sqrt(sum([x*x for x in l])/len(l))
Which gave me 4.35 on my data.

That's pretty much a tie, as we expected.

 

3) How many turns does a battle take as a function of army size?

If 2 armies of same size battle, do larger battles take longer?

Here are 2 queries to show turns vs. army size (for 1 <= i <= nMax) for 2 different attack policies (attack the weakest opponent, attack a random opponent).

 def NTurns_Weakest(nMax):
  return [Battle(Make(i),Make(i)).turns for i in range(1,nMax+1)]


 def NTurns_Random(nMax, nTimes=5):
  return [  favg(nTimes, lambda : Battle(MakeR(i),MakeR(i)).turns) for i in range(1,nMax+1)]

For the attack-random case, we run an average across 5 times.

The graph of the results is:

image

 

Some interesting observations here:

  1. For random attacks, the army size doesn't influence battle duration beyond noise. 20-on-20 takes about as long as 1-on-1.
  2. For attack-weakest, the battle takes longer with larger armies.  (Quiz #1: Why?)

 

4) How much better is attack-weakest vs. attack-random?

We can simulate a single round of N-on-N via: Battle(MakeR(n), Make(N)). Note that this is MakeR (for attack-random) vs. Make (for attack-weakest).

This query runs the battle across a range of sizes, and then gets a projection including victory margin and number of turns.

 def RvsW2(nMax = 4):
  # get raw data
  b = [Battle(MakeR(i),Make(i)) for i in range(1,nMax+1)]
  # run projection to get interesting fields:
  w=map(lambda i: (i.size2, i.end2, i.turns, i.victory), b)
  return w

 

Here are the results we get:

image

If we take number of turns instead:

image

 

Observations:

  1. Notice that Victory Margin is always positive, indicating that attack-weakest policy always wins over attack-random.
  2. It turns out the graphs are surprisingly deterministic, even though there's randomness from the attack-random policy. Running multiple times appears to gives the same curve. (Quiz #2: Why?)
  3. Notice that as battle duration (# of turns) goes up, victory margin goes down (and vice-versa).  My theory is that the longer the battle lasts, the more time the losing side (attack-random) has to inflict damage on the winning side, thus pulling down the victory margin.

 

Practical tidbit #1: When you're playing a RTS, it's more efficient to manually have your units target a single enemy then to let the AI employ an essentially attack-random policy.

 

5) How does size advantage affect victory margin?

We can see that an N-on-N battle is a tie. But how big do extra units help?

Here's a snippet to show a battle between armies of (size) vs. (size+x), for a range on x.

 

 def NMargin_Extra(nMaxDelta = 5, size=10):
  return [Battle(Make(size), Make(size+i)).victory for i in range(nMaxDelta)]

 

Here's the graph of the results, where the base size is 10. This shows the victory margin in the range on 10-on-10 vs 10-on-30.

image

As we'd expect:

  1. When the armies are the same size (size-advantage=0), it's a tie (victory margin=0).
  2. The large the size advantage, the bigger the victory margin approaching the maximum of +100.
  3. The difference between double (10-on-20) and triple (10-on-30) is insignificant. 

Practical tidbit #2:  When attacking an enemy army, a 2-1 advantage should clobber. Waiting to build up for a 3-1 advantage may be overkill.

 

sim3.py

Comments

  • Anonymous
    January 02, 2008
    I am happy to find someone that likes both C# and Python and blogs about it! I love both for their own reasons! If you can show or point people to integrating VS 2008 with python or IPython it would be a real help!

  • Anonymous
    January 02, 2008
    The last graph looks like you'd expect it to look taking Lanchester's Square Law into consideration. (The overall strength of an army is the square of its size.) I wonder if the numbers would change noticably if you apply the standard RTS AI logic more precisely, that is once a unit choose its random target, it sticks on that target for all future turns until its no longer available.  I doubt it would have statistical influence when the armies are of equal size, but it might affect the shape of the victory margin curve against armies of differing sizes.

  • Anonymous
    January 02, 2008
    As Timothy Fries mentioned, Lanchester's Laws and several other theorems from game theory are rather useful. http://en.wikipedia.org/wiki/Lanchester%27s_laws There's another, similiar set of formulas for more similiar situations, but I can't remember the name right now.

  • Anonymous
    January 04, 2008
    Movado - If you like Python + C#, then you'd be interested in IronPython: an implementation of Python written in C# for .NET.  Check out more at: http://www.codeplex.com/IronPython There are some efforts integrating Python + VS. Check out: http://www.codeplex.com/IronPythonStudio

  • Anonymous
    January 04, 2008
    Timothy / Trauma - That's funny, I didn't know about Lanchestor's laws specifically before I wrote this. When I read them, it sounds like he uses similar rules to the ones I outlined above.   I'll have to try out that policy. It should be pretty easy to prototype with python. Stay tuned...

  • Anonymous
    January 10, 2008
    I have been wanting to learn python for quite a while, and your blog post inspired me to finally go forward. I downloaded and installed IronPythonStudio and can run simple python programs but it has a problem with your code above? I think you are missing Code for the PickWeakest subclass? I am willing to play with the code and try to figure it out but if you can save me the headache, I am more likly to continue with python. Thanks for your help!

  • Anonymous
    January 10, 2008
    John - I'm thrilled you found this interesting. The snippets above were just the interesting parts of the code, but not all the code. Sorry about the confusion. I attached the full py file as sim3.py. It should be viewable as: http://blogs.msdn.com/jmstall/attachment/6957037.ashx It includes all the basics, plus a ton of comments and additional queries.