science of board games

I have been doing some recent thinking about battles in games, which led me to write a little code to satisfy my curiosity.

Specifically, I am going to talk about battles in Twilight Imperium 3rd Edition, although what I am discussing would apply to many games whose battles are resolved by dice throws (like Risk).

The goal I had in mind is to calculate the odds of me winning a battle. Simple enough, right? Well, not quite. There's actually quite a few ways of trying to do it, and there's even been research papers on this topic published within the last few years.

The first way you can do it is to "set up" the fleets in a program, and then simulate a number of battles, and count up how many you win. This actually isn't too bad of a way: it has the advantage of always taking a fairly constant amount of time. However, it is occasionally prone to bias and inaccuracy.

I implemented it anyways so that I could verify my program that does it correctly.

The correct way is to enumerate all possibilities and scenarios, and see how many times you win. The big problem with this is the sheer number of them: it's exponential work to calculate the odds (around O(2ⁿ), where n is the size of the bigger fleet). This can be lessened to a certain extent with certain techniques, like dynamic programming, but it's still an ugly problem.

Luckily, in Twilight Imperium, most battles aren't too ridiculously large: typically only a dozen or so ships on each side.

First, a few results to pique your interest: how many fighters does it take to match the might of the mighty war sun? This is important, since war suns cost a bajillion dollars to fun and build, and fighters are often practically free.

The following table shows the results of X fighters defeating a single war sun. The fighters are assumed to be standard fighters (hit on 9 or 0), and no cards (obviously).

Num. Fighters	Prob. of beating a war sun
1	0.00026%
2	0.43%
3	5.36%
4	20.20%
5	34.96%
6	55.28%
7	73.54%
8	84.31%
9	92.18%

Looks like the answer is about 6 fighters are equal in the might to one war sun.

(It's worth noting that a war sun would not likely be fighting alone much: usually it has its own fleet of fighters to act as little shields, for example, to prevent it from taking damage.)

Alright, time for the code for all of you code monkeys out here. I do all of my board game coding in Ruby.

The first thing we need is a class to represent ships. I created a fairly basic class:

class Ship
  attr_accessor :hp
  attr_accessor :attack
  attr_accessor :attack_times
 
  def initialize(hp, attack, attack_times = 1)
    @hp, @attack, @attack_times = hp, attack, attack_times
  end
 
  def prob
    (11 - @attack) / 10.0
  end
 
  def <=>(y)
    if @hp > y.hp
      1
    elsif @hp < y.hp
      -1
    else
      @attack * @attack_times <=> y.attack * y.attack_times
    end
  end
 
  def dup
    Ship.new(@hp, @attack, @attack_times)
  end
end

This allows a set of ships to be sortable, and provides a few hand operations, like copying them and calculating its probability of hitting something.

The fleets are created, for example:

myships = [Ship.new(1, 9)] # fighter
yourships = [Ship.new(2, 3, 3)] # war sun
 

Two operations are needed, first off: calculation of how big the fleet is (in terms of hit points), also a sum function (not sure why this isn't built into Ruby already), and then the ability to remove some amount of hits from a fleet in an intelligent manner. This is primarily dependent on the above sorting code:

def fleet_size(fleet)
  fleet.inject(0) {|sum, ship| sum + ship.hp}
end
 
# add up each element
def sum(x)
  x.inject { |sum, y| sum + y }
end
 
def remove_hp(ships, hits)
  h = hits
  nships = ships.dup.sort
  while (h -= 1) >= 0
    return [] if nships.length == 0
    if nships[0].hp == 1
      nships.delete_at(0)
    else
      new_ship = nships.delete_at(0).dup
      new_ship.hp -= 1
      nships += [new_ship]
      nships.sort!
    end
  end
  nships
end

First, we'll do the cheating method of just simulating some number of dice rolls and counting our wins. That code is performed like so

def calc_hits(fleet)
  hits = 0
  fleet.each do |ship|
    0.upto(ship.attack_times - 1) do
      hits += 1 if rand < ship.prob
    end
  end
  hits
end
 
def fight(mine, yours)
  myhits = calc_hits(mine)
  yourhits = calc_hits(yours)
 
  new_mine = remove_hp(mine, yourhits)
  new_yours = remove_hp(yours, myhits)
  [new_mine, new_yours]
end
 
def sampling(mine, yours)
  wins = 0
  total = 1024 * [mine.length, yours.length].max
  0.upto(total - 1) do |i|
    m = mine.dup
    y = yours.dup
    while m.length > 0 and y.length > 0
      m, y = fight(m, y)
    end
    wins += 1 if m.length > 0
  end
  (wins + 0.0) / total
end
 

Not a lot of comments there, because it's fairly self-explanatory and I don't care about it much.

The fun stuff comes with the probability theory method.

One important piece is a way to iterate through all of the different combinations of dice rolls. Rather than do actual dice rolls (this would give us 10ⁿ possibilities instead of 2ⁿ!), we will enumerate the number of hits possible for each ship (most can get 0 or 1, but some can do more, like war suns). This code iterates through those:

# this is odd
# sort of like counting a normal number
# except different entries will be in different bases <img src='http://www.scienceofboardgames.com/wp-includes/images/smilies/icon_smile.gif' alt=':)' class='wp-smiley' /> 
# base = number of attacks allowed by the ship
def next_hit(iter, fleet)
  niter = iter.dup
 
  # if flipping a #ATTACKS to 0, then keep going
  # otherwise, increment the last entry and return
  0.upto(fleet.length - 1) do |i|
    if niter[i] < fleet[i].attack_times
      niter[i] += 1
      return niter
    else
      niter[i] = 0
    end
  end
  niter
end

This means that [1, 0] (1 hit for the first ship, 0 for the second) would get incremented to be [0, 1], and then [1, 1] and so forth.

We're doing probabilities here, so we need a factorial and choose function:

def factorial(n)
  if n == 0 or n == 1
    1
  else
    n * factorial(n - 1)
  end
end
 
def choose(n, k)
  factorial(n) / (factorial(k) * factorial(n - k))
end

Hopefully that's self-explanatory.

This next function is also critical: we need to know how probable it is that we can get a certain number of hits. Like, how likely is it a war sun will get 1 hit, or 2, or 3, etc.

# calculate a hash that gives you the probability of having X hits.
def make_hit_prob(fleet)
  results = {}
 
  # iterate over all possible hit states, starting with all zeros for hits
  s = [0] * fleet.length
 
  # simple way to check to see if we are done
  # just check if we get back to all zeros
  finished = [0] * fleet.length
 
  while not nil
    # total hits
    hits = sum(s)
 
    # start with 1.0, since this is an "and" condition
    prob = 1.0
 
    # for each ship
    0.upto(fleet.length - 1) do |i|
      # succeeded s[i] number of times
      prob *= choose(fleet[i].attack_times, s[i]) * (fleet[i].prob ** s[i]) * ((1.0 - fleet[i].prob) ** (fleet[i].attack_times - s[i]))
    end
 
    # add the result to previous for this number of hits, or create it
    results[hits] = 0.0 unless results[hits]
    results[hits] += prob
 
    # next set of hits
    s = next_hit(s, fleet)
    break if s == finished
  end
  results
end

The tricky part to this was in the middle: if we have a probability p of hitting, and we have, say, 2 hits and 1 miss, then our probability of that scenario is p × p × (1 - p). Except, there's 3-choose-2 ways of getting 2 hits and 1 miss, so we need to add together a few of these to get the right amount.

Finally, we have the code that simulates a battle properly with probability theory in mind:

def calc_win(mine, yours)
  # calculate probabilities of various hits
  myhitprob = make_hit_prob(mine)
  yourhitprob = make_hit_prob(yours)
 
  # start with 0
  win = 0.0
 
  # for every possible amount of hits that each can do
  myhitprob.keys.each do |m|
    yourhitprob.keys.each do |n|
      # if both 0, then both missed, and it's a do-over, so don't count it
      next if m == 0 and n == 0
 
      # if I lose, don't count
      next if n >= fleet_size(mine)
 
      # I won
      if m >= fleet_size(yours)
        win += myhitprob[m] * yourhitprob[n]
 
      # we both took hits, but neither fleet destroyed
      # could optimize this case using dynamic programming
      else
        win += myhitprob[m] * yourhitprob[n] * calc_win(remove_hp(mine, n), remove_hp(yours, m))
      end
    end
  end
 
  # correct for do-overs:
  # have to divide by 1 - probability of a do-over
  win / (1.0 - myhitprob[0] * yourhitprob[0])
end

This is pretty straight-forward, except for this last bit. We have to correct for the case when neither fleet hits anything: if we aren't careful, we can get into an infinite loop. So the solution is to ignore it, and then use some basic math to account for what actually occurs in this case. Essentially, math tells us to take our normal probability of winning and dividing it by the probability of both missing subtracted from 1. You can think of it like "rescaling" the probabilities so that you can ignore this case.

Sorry about the length of this post: I didn't see an easy way of splitting this material, so I threw it all together.