Create-A-Class

5 December 2019 · # Optimization · 1031 words

Create-A-Class is a loadout customization system in the first-person shooter franchise Call Of Duty.

In multiplayer matches, players are pit against each other in deathmatch or objective capture game modes. Good gunplay and weapon customization is an important part of the competitive experience. Your loadout can make or break a match.

Modern Warfare, the latest entry in the Call Of Duty series, takes weapon customization a step further than its predecessors. Players can modify weapons extensively in the Gunsmith component of Create-A-Class.

I wondered whether it would be possible to determine the "best" modifications for a weapon without trying out every permutation of attachments.

Gunsmith

In the game world, each weapon has a set of base attributes that define how it handles. These include, but are not limited to, the weapon's range, its damage and the recoil it imparts.

For example, submachine guns like the MP5 are easier to control than assault rifles but typically do less damage at longer ranges.1

In Gunsmith, players can add attachments to up to five different places on a weapon. For the sake of gameplay balance, generally, each attachment or modification improves some attributes and worsens others.

For example, a short-barrelled MP5K will be more manoeuvrable than a regular MP5, but it will suffer from high recoil.2 Depending on how you play, this might be an acceptable tradeoff.

To proceed, the key insight we need is to recognize that choosing a loadout is the same as solving a microeconomic optimization problem. Effectively, we seek to maximize a player’s utility subject to cost constraints imposed by game mechanics. Here, utility describes the increased performance a player derives from using their preferred loadout.

Weapon Utility

Let's model utility UU as a function of the weapon attributes, represented as a vector x\mathbf{x}.

Game mechanics dictate that the model should have the following properties:

  1. Each attribute xix_i contributes independently to an increase in utility3
U(x)=iUi(xi)U(\mathbf{x}) = \displaystyle\sum_i U_i(x_i)
  1. For a given attribute, larger values are always preferred to smaller ones
Uxi>0  i\dfrac{\partial U}{\partial x_i} > 0 \ \forall \ i

Note that the second property corresponds to the non-satiation assumption in utility theory.

The attribute vector itself comprises a base term x0\mathbf{x_0} and the sum of contributions from attachments. If we denote the presence of the j-th attachment in the i-th slot by a boolean variable Xij{0,1}X_{ij} \in \{0, 1\}, we can then write

x=x0+imjniXijΔxij\mathbf{x} = \mathbf{x_0} + \displaystyle\sum_i^m \displaystyle\sum_j^{n_i} X_{ij}\mathbf{\Delta x}_{ij}

Apart from the integrality constraint on XijX_{ij}, there are two other constraints to state:

  1. Game mechanics mean we are restricted to making five modifications
imjniXij5\displaystyle\sum_i^m \displaystyle\sum_j^{n_i} X_{ij} \leq 5
  1. We cannot make more than one modification in the same place or "slot"
jniXij1  i\displaystyle\sum_j^{n_i} X_{ij} \leq 1 \ \forall \ i

Combinatorial optimization

Combinatorics can be used to gauge the size of the problem we are trying to solve.

Suppose every slot supports at least three modifications, and every weapon has at least five slots, so that ni3  in_i \geq 3 \ \forall \ i, and m5m \geq 5. Then we can obtain a lower bound for NN, the number of distinct ways of modifying a typical weapon:

Nk=05m!k!(mk)!3kk=055!k!(5k)!3k=(1+3)5=1024\begin{aligned} N &\geq \displaystyle\sum_{k=0}^5 \dfrac{m!}{k!(m-k)!} 3^k \\ &\geq \displaystyle\sum_{k=0}^5 \dfrac{5!}{k!(5-k)!} 3^k \\ &= (1+3)^5 = 1024 \end{aligned}

Note that we used the binomial theorem to derive the last line.

Now suppose ni9  in_i \leq 9 \ \forall \ i, and m7m \leq 7, again for all weapons. This leads us to an upper bound for NN:

Nk=05m!k!(mk)!9k=m!5!k=055!k!(mk)!9km!5!k=055!k!(5k)!9k=7!5!(1+9)5=4,200,000\begin{aligned} N &\leq \displaystyle\sum_{k=0}^5 \dfrac{m!}{k!(m-k)!} 9^k \\ &= \dfrac{m!}{5!}\displaystyle\sum_{k=0}^5 \dfrac{5!}{k!(m-k)!} 9^k \\ &\leq \dfrac{m!}{5!}\displaystyle\sum_{k=0}^5 \dfrac{5!}{k!(5-k)!} 9^k \\ &= \dfrac{7!}{5!}(1+9)^5 = 4,200,000 \end{aligned}

There are few slots supporting nine modifications in practice, so our bound for NN should be tighter.4

To get further, we need to propose a form for utility, our objective function. Composing it from a weighted sum of attribute contributions is a simple and intuitive model. More importantly, it will transform the problem into a tractable one that does not demand a brute force solution.

U(x)=iUi(xi)=iuixi=ux\begin{aligned} U(\mathbf{x}) &= \displaystyle\sum_i U_i(x_i) \\ &= \displaystyle\sum_i u_ix_i \\ &= \mathbf{u} \cdot \mathbf{x} \end{aligned}

Every utility coefficient uiu_i needs to be positive to satisfy the non-satiation assumption.

The Knapsack Problem

Observe that maximizing the original objective UU is the same as maximizing a transformed one UU':

U(x)=U(x)ux0=u(imjniXijΔxij)=imjniXij×uΔxij=imjniPijXij\begin{aligned} U'(\mathbf{x}) &= U(\mathbf{x}) - \mathbf{u} \cdot \mathbf{x_0} \\ &= \mathbf{u} \cdot \left(\displaystyle\sum_i^m \displaystyle\sum_j^{n_i} X_{ij}\mathbf{\Delta x}_{ij} \right) \\ &= \displaystyle\sum_i^m \displaystyle\sum_j^{n_i} X_{ij} \times \mathbf{u} \cdot \mathbf{\Delta x}_{ij} \\ &= \displaystyle\sum_i^m \displaystyle\sum_j^{n_i} P_{ij} X_{ij} \end{aligned}

Restating the whole problem, with constraints, for completeness:

maximjniPijXij\max \displaystyle\sum_i^m \displaystyle\sum_j^{n_i} P_{ij}X_{ij}

subject to

imjniXij5jniXij1  iXij{0,1}  i,j\begin{aligned} \displaystyle\sum_i^m \displaystyle\sum_j^{n_i} X_{ij} &\leq 5 \\ \displaystyle\sum_j^{n_i} X_{ij} &\leq 1 \ \forall \ i \\ X_{ij} &\in \{0, 1\} \ \forall \ i, j \end{aligned}

where Pij=uΔxijP_{ij} = \mathbf{u} \cdot \mathbf{\Delta x}_{ij}.5

Thus the optimization problem reduces to a variant of the Multiple-Choice Knapsack Problem where each "price" PijP_{ij} may be real-valued, but all the "objects" have the same weight -- 1.

This simplification, courtesy of the problem domain, enables us to devise a simpler optimization algorithm to solve the Multiple-Choice Knapsack Problem than those reported in research papers.6

  1. Sort the modifications in descending order of price P[i][j]
  2. While modification slots are still available, select the next modification (i, j) provided:
    • its slot i is vacant
    • its price P[i][j] is positive

The runtime of this algorithm is dominated by sorting, which can be done in linearithmic time. Memory usage is linear in the number of available modifications. The following Java code implements this algorithm and incorporates a couple of practical improvements:

public class WeaponOptimizer implements Optimizer<Weapon, Loadout> {

  private final List<Double> utilityCoefficients;

  public WeaponOptimizer(List<Double> utilityCoefficients) {
    this.utilityCoefficients = utilityCoefficients;
  }

  @Override
  public Pair<Double, Loadout> run(Weapon weapon) {
    var attachments = new ArrayList<Triple<Slot, Attachment, Double>>();
    for (var slot : weapon.slots()) {
      for (var attachment : slot.availableAttachments()) {
        var price = attachment.price(utilityCoefficients);
        // Disregard chosenAttachments with negative prices from the outset
        if (price > 0) {
          // Cache the computed price for sorting later
          attachments.add(new Triple<>(slot, attachment, price));
        }
      }
    }
    attachments.sort(priceComparator.reversed());

    var utility = weapon.utility(utilityCoefficients);
    var loadout = new Loadout(weapon);

    for (var triple : attachments) {
      var slot = triple.first();
      var attachment = triple.second();
      var price = triple.third();
      if (loadout.isFull()) {
        break;
      }
      if (!loadout.containsAttachment(slot)) {
        utility += price;
        loadout.putAttachment(slot, attachment);
      }
    }
    return new Pair<>(utility, loadout);
  }
}

Price and base utility calculators are namespaced in Attachment and Weapon, respectively:

public record Attachment(List<Double> attributes) {
  /**
   * Contribution of this attachment to weapon utility.
   */
  public double price(List<Double> utilityCoefficients) {
    var total = 0;
    for (var i = 0; i < attributes.size(); i++) {
      total += utilityCoefficients.get(i) * attributes.get(i);
    }
    return total;
  }
}

public record Slot(Set<Attachment> availableAttachments) {}

public record Weapon(List<Double> attributes, Set<Slot> slots) {
  /**
   * Base utility of a weapon.
   */
  public double utility(List<Double> utilityCoefficients) {
    var total = 0;
    for (var i = 0; i < attributes.size(); i++) {
      total += utilityCoefficients.get(i) * attributes.get(i);
    }
    return total;
  }
}

Loadout is a class that enforces game mechanics; i.e. it makes sure we can never

  1. populate a slot with a foreign attachment, or
  2. add more than five attachments to the weapon, or
  3. populate a slot more than once.
public class Loadout {

  public static final int MAX_ATTACHMENTS = 5;
  public final Weapon weapon;
  private final HashMap<Slot, Attachment> attachments = new HashMap<>();

  public Loadout(Weapon weapon) {
    this.weapon = weapon;
  }

  public boolean isFull() {
    return attachments.size() == MAX_ATTACHMENTS;
  }

  public boolean containsAttachment(Slot slot) {
    return attachments.containsKey(slot);
  }

  public void putAttachment(Slot slot, Attachment attachment) {
    if (!weapon.slots().contains(slot)) {
      throw new IllegalArgumentException();
    }
    if (!slot.availableAttachments().contains(attachment)) {
      throw new IllegalArgumentException();
    }  // 1
    if (isFull()) {
      throw new UnsupportedOperationException();
    }  // 2
    if (containsAttachment(slot)) {
      throw new UnsupportedOperationException();
    }  // 3
    attachments.put(slot, attachment);
  }
}

So far, the algorithm we have devised finds the best loadout for a single weapon. We can do better and determine the best loadout for all weapons.

Observe that attachment choice is tied to weapon choice. So we can decompose the problem by:

  1. maximizing utility for every weapon independently (as before), and,
  2. finding the weapon in this set with the highest utility.

In Java,

public class LoadoutOptimizer implements Optimizer<List<Weapon>, Loadout> {

  private final Optimizer<Weapon, Loadout> weaponOptimizer;

  public LoadoutOptimizer(Optimizer<Weapon, Loadout> weaponOptimizer) {
    this.weaponOptimizer = weaponOptimizer;
  }

  @Override
  public Pair<Double, Loadout> run(List<Weapon> weapons) {
    return weapons
      .stream()
      .map(weaponOptimizer::run)
      .max(Comparator.comparing(Pair::first))
      .orElseThrow(IllegalArgumentException::new);
  }
}

This optimizer accepts any underlying optimizer conforming to the Optimizer<Weapon, Loadout> interface, so we can stub out WeaponOptimizer when testing LoadoutOptimizer.

Model correctness

It is difficult to verify the usefulness of applying utility theory in this context mainly because of the lack of in-game weapon data. When I wrote this article, most weapon data reported online for Modern Warfare was obtained experimentally. It was also far from complete.


  1. This is the case in real life, too.

  2. The K in MP5K stands for Kurz, German for "short."

  3. For the sake of gameplay balance, this might not be entirely true. I bet the game won't allow you to eliminate recoil by stacking every recoil-reducing attachment on a weapon.

    Also, some modifications prevent others from being made: for instance, you cannot attach a compensator to the muzzle of an MP5SD because it has a sound suppressor built directly into its receiver. These exceptions are rare enough that we can ignore them.

  4. Either way, NN is a large number.

  5. PijP_{ij} is the additional utility we derive from having the j-th slot populated with the i-th attachment.

  6. Research papers like Bednarczuk E. (2018) and Pisinger D. (1995).