Are my units balanced?
Using Clustering algorithms to see what your data tells about your units
Hello!
We have finished a (long?) series of posts about how to create an Artificial Intelligence agent that is able to play a war game, Warhammer 40K, by reading the rules encoded. I pretend to come back to automated planning or other algorithm to create AI players, but for today we will see another topic, also related to war games.
In war games, even in some board games, it is commonplace to have statistics for every type of unit. And some of these units are classified in different categories according to some role they may perform during the game. But are units inside the same category, for example elite units, evenly balanced? In this post we will look at some of the troops used in the precedent example, plus a lot of other troops from the Warhammer 40K game (Admechs, Tyranids and all the Space Marines factions, good or evil), and we will see if they all might be grouped (clustered) into similar categories or not, using clustering algorithms.
In this post we will give an overview of clustering algorithms, describing some of the most commonly used algorithms and testing them using data from different Warhammer units.
Data Overview
First we will extract some useful information about the units. We start by looking at how many different roles we have, and the number of units for each role:
+---------------+--------+
| Role | Number |
+---------------+--------+
| Troops | 1938 |
| HQ | 2335 |
| Elites | 3074 |
| Fast Attack | 1447 |
| Heavy Support | 1474 |
| Flyers | 237 |
+---------------+--------+The number of units is not balanced, and that may affect the performance of the algorithms. If we represent these units by plotting them using their cost in points and the output damage, we will see that there are more dots from some roles than others. And that they may be all mixed. For example look at the following plot:
You can see a lot of brown dots, purple and green. Green and brown are in the extremes, so they have no other points in-between, but it is possible to see that purple dots hide a lot of red and blue dots, meaning that there are a lot of HQ units with values similar to the Heavy Support troops, and even Elite units hidden between these and the basic Troops. In this chart we have only plotted 2 -Dimensions (Cost x Damage), but it is possible to use all the different stats of a unit, that is, all the dimensions (the WARP!) to group all units into common groups? Well…let me introduce Clustering.
Clustering algorithms
Now that we have seen a bit of the data, it is time to introduce the clustering algorithms. A cluster is a group of similar things occurring together. And in Artificial Intelligence, a cluster is a set of observations, events or rows that are similar according to some measure unit. Then, clustering is the task automatically groups these sets of objects, such that each group consists of the observations with similar attributes. For convenience, and according to the scientific literature we will call each row, register or unit in the data, as observation.
In the previous scatter plot (the one with dots above), brown dots represent the troop units, that is, the most basic of units for each army. As we can expect, most of these troops should cost relatively few, so they should group to the left. On the other side, the green dots flyers represent aerial support, generally in the form of space ships, so their cost is higher. Notice that in-between these two kind of units, there are other units. Will it be possible to classify the units according only to these two measures? Not likely, because as it is shown above, most of the roles overlap their units, except in some extreme cases.
In the figure above we have only considered two different dimensions, the cost in points and the damage output. What if we consider other dimensions, for example Movement x Cost? In this case, the troops stay at the bottom left, because (normally) troop are not able to move fast:
In any case, it is possible to see that there are some units that cost less than some troops, and have a better damage output, or move faster. Or the inverse, units costing more than the basic troops and having somewhat worse stats. Are units balanced? Surely not, and that is part of the game, because there are some special abilities and strategies not included in the data above that might affect it and buff it in some way. But can we see if some units might be grouped into another class? For example, some troops may have better stats than some other elite units. So, one thing we can do to verify this balance, is to use clustering algorithms to group the units, and then verify if those groups are homogeneous regarding the role, or if they are a mixed bag of units.
K-Means
K-means algorithm is a well known clustering algorithm. This algorithm works by selecting a centroid, that is, an observation (or a point) that serves as the center for a group on each step, and assigning the points that are nearest to this centroid to the same group. Roughtly, the algorithm does the following steps:
- Select the number of clusters, and its centroids. This selection can be done randomly;
- Each observation is then assigned to the nearest cluster, by computing its mean and difference to the centroids;
- New centroids are computed for each cluster;
- Repeat 2–3 until the clusters do not change.
Let us illustrate the algorithm with a small example on the W40K data. We ran the algorithm Kmeans (using the library sklearn) and we selected also 6 groups, the same as the role of each unit. However, the units do not fit into these groups as the roles might suggest. So there is not a direct equivalence between clusters and roles. Look at the following table:
+---------------+------+------+-----+------+------+------+
| - | 0 | 1 | 2 | 3 | 4 | 5 |
+---------------+------+------+-----+------+------+------+
| Troops | 0,52 | 0 | 0 | 0 | 0 | 0,42 |
| Fast_Attack | 0,33 | 0 | 0 | 0 | 0,09 | 0,33 |
| Heavy_Support | 0,15 | 0,04 | 0 | 0 | 0,6 | 0,24 |
| Flyers | 0 | 0,01 | 0 | 0 | 0,2 | 0 |
| HQ | 0 | 0,72 | 0,3 | 0,21 | 0,06 | 0 |
| Elites | 0 | 0,23 | 0,7 | 0,79 | 0,05 | 0 |
+---------------+------+------+-----+------+------+------+The different roles are distributed unevenly in the different 6 clusters. For example, the role troops is present in the cluster 0 and in the 5. And the Fast and Heavy support are also present in the same clusters. This may be a clue that indicates that these 3 roles are in some way more close to each other than to the other roles. This make sense, because some of the Heavy Support may consists of basic troops with upgraded weapons (Hellblasters for instance…). On the other hand, HQ and Elites appear in other clusters together. This may represent an HQ using an Elite equipment.
The sklearn library allows us to obtain the center of each cluster, that is the (theoretical) unit that is located in the center of the cluster:
Now we can see it more clearly. Clusters 0 and 5 do have stats that may be common for any troop (a little bit better in fact for any non-Marine Equivalent unit): weapons (WS) and ballistic skill (BS) of 3+, 4 Toughness (T) and 2 and 3 wounds (W). Cluster 1 has a higher Leadership and better skills, suitable for an HQ and some elite units. Cluster 2 and 3 have worse stats than Cluster 1, but still better than 0 and 5. And Cluster 4 has a bit of everything, having a higher cost and wound count, and a higher weapons skills and movement of 0, indicating that this may be a cluster containing vehicles, because of the weapon skill (no tank has the ability to use a melee weapon).
Hierarchical clustering
Another clustering algorithm is the hierarchical clustering. This algorithm starts by considering each observation its own cluster. And in each step it joins the two closest observations, until all clusters have been grouped into a single cluster. Hierarchical clustering produce dendograms which are useful visualization tools, that we will explain below. We ran the Hierarchical clustering with the same data as before and we obtained the following dendogram:
A dendogram is a plot that show different categories and how each other relate by grouping them. In the X axis there are the labels for each cluster, and in the example above, we have selected the label of the most common unit in the cluster. And in the Y axis, a dendogram plots the distance between the different cluster. When two clusters merge, they unite with a line at a y value. This means that if we consider a distance of y to be a threshold, with distances > y, the two clusters would be merged, and vice versa. In the image above, we have cut the dendograms when we have 7 clusters (the line at y=18), that is, the number of clusters equal the number of intersections of this line and the clustering lines. Or, in other words, if we consider that the maximum distance from one cluster to another is y=18, we will have 7 clusters.
Looking at the dendogram, we can see that a lot of HQ get mixed in different categories. A (probably) cause for this may be the high number of HQ units, that sometimes consist in other type of units (Troops and Elite mainly) with different weapons (like the Chaos Lords, for instance).
Conclusions
In this post we have seen some clustering algorithms and we have clustered the units into common groups. In the W40K rules, these troops are not easily divided, so we have seen that the groups are not uniform, and they are more of mixed bags of units, with one predominant trait, either a high leadership, or good ballistic skills, or even a high number of wounds.
As a Data Scientist, I consider that clustering the data do not answered my question fully: Are my units balanced?, because not every troop, or elite is the same. This opened new questions as: what do units have in common such that some of the troops were clustered together? Clustering produce groups that have some common stat lines. I do not claim to know all the stats of all armies, but I am familiar with some, and it helped me to interpret some of the results.
In this post I wanted to try different clustering algorithms. But some of the algorithms I used did not work properly, or they never converge (Affinity propagation, Mean Shift) so I did not considered them. I wanted to change the focus from Automated Planning to Machine Learning. In the next posts I will continue to explore Machine Learning and Computer science in the universe of Warhammer 40K.
Stay safe!