This post is about applying combinatorial optimisation to the weapon modification system "Create-A-Class" present in the multiplayer mode of the recently released Call Of Duty game Modern Warfare.
For those who are not aware, in Call Of Duty games, players are pit against each other in deathmatch or objective capture game modes. Good gunplay and weapon customisation is an important part of the competitive multiplayer experience.
Modern Warfare takes weapon customisation a step further than its predecessors, enabling players to modify weapons extensively in the Gunsmith component of "Create-A-Class." I wondered whether it would be possible to determine the optimal modifications for a weapon without inspecting every permutation of attachments.
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 range of the weapon, its damage and the recoil it imparts.
In Gunsmith, players can modify 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.
This optimisation problem mirrors a microeconomic one. Effectively, we seek to maximise 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 weapon loadout.
In this model, utility
U is a multi-valued function of the weapon attributes, represented as a vector
x. Game mechanics dictate that the model should have the following properties:
x[i]contributes independently to an increase in utility
For a given attribute, larger values are always preferred to smaller ones
The attribute vector itself comprises of a base term and the sum of attachment contributions. If we denote the presence of the j-th attachment in the i-th slot by a boolean variable, we can then write
Apart from the integrality constraint, there are two other limits to state:
Gameplay mechanics mean we are restricted to making five modifications
We cannot make more than one modification in the same place
Note that we can assume, without any loss of generality, that the player has fully ranked a weapon so that every attachment is available.
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 allow us to transform the problem into more tractable one later.
Apart from advancing a particular utility model for every player, we made some other assumptions implicitly:
- Modifications can be made independently of each other
- All modifications imbue characteristics that can be modelled as changes to weapon attributes
Of these, the second assumption is the hardest one to reconcile with our model. Although one modification rarely prevents another from being made entirely, there are suspicions that their combined effect on weapon attributes is not merely additive.
The Knapsack Problem
Observe that maximising the original objective
U is the same as maximising a transformed one
Thus the optimisation problem reduces to a variant of the Multiple-Choice Knapsack Problem where each "price"
P[i][j] may be real-valued, but all the "objects" have the same weight -- 1.
- Sort the modifications in descending order of price
- While modification slots are still available, select the next modification
- its slot
- its price
- its slot
The runtime of this algorithm is dominated by the sorting, which can be done in linearithmic time. Memory usage is linear in the number of available modifications. The following Python code implements this algorithm, and incorporates a couple of practical improvements:
class Attachment: def __init__(self, values): self.values = values def price(self, coeffecients): total = 0 for coeffecient, price in zip(coeffecients, self.values): total += coeffecient * price return total class Slot: def __init__(self, available_attachments = ): self.available_attachments = available_attachments class Weapon: def __init__(self, slots = ): self.slots = slots def knapsack(coefficients): def by_price(triple): (_, _, price) = triple return price def attachments(weapon): with_price =  for slot in weapon.slots: for attachment in slot.available_attachments: price = attachment.price(coefficients) # Disregard attachments with negative prices at the outset if price > 0: # Cache the computed price for sorting later with_price.append((slot, attachment, price)) with_price.sort(key=by_price, reverse=True) filled_slots = set() chosen_attachments = set() for (slot, attachment, _) in with_price: if len(chosen_attachments) > 5: break if not slot in filled_slots: chosen_attachments.add(attachment) filled_slots.add(slot) return chosen_attachments return attachments
Loadouts and Classes
So far, the algorithm we have devised finds the best loadout for a playstyle, given a weapon. We can do better and determine the best loadout among all weapon and attachment permutations.
Observe that attachment choice is tied solely to weapon choice. So we can decompose the problem by:
- maximising utility for every weapon independently (as before), and,
- finding the weapon in this set with the largest utility.
Such an algorithm is efficient only because there are a limited number of weapons in-game (about 30).
A class is typically comprised of:
- A long gun
- A sidearm
- Two pieces of explosive or tactical equipment
- Three Perks
Optimising on the class-level is more of an art than a science. For this reason, it is not worth attempting.
It is difficult to verify the usefulness of applying utility-theory in this context mainly because of the lack of in-game weapon data. At the time of writing this article, most weapon data reported online has been obtained experimentally and is far from being exhaustive.
Additionally, recall that modifications do not have independent effects; this makes it harder to determine raw weapon data from experiments.