Graph all the things

analyzing all the things you forgot to wonder about

Humans versus Zombies


A friend and former college Humans vs. Zombies (HvZ) moderator gave me this problem: suppose we set up a game where an equal number of humans and zombies can disperse among 3 battlefields, and whichever faction wins on at least 2 battlefields is the overall winner. To simplify things, each team has the same number of total players, and each battle is won by the team with more players on that battlefield. What is the optimal way to allocate your players?

Every allocation is beaten by some other allocation. For instance, if I send my people equally to all battles (\frac13, \frac13, \frac13), my opponent can win with (\frac12, \frac12, 0). That strategy in turn could be beaten by (0, \frac34, \frac14), which is beaten by (\frac13, \frac13, \frac13).

I solved the game numerically, and here's what the solution looks like:

Beautiful probability density heat map on an equilateral triangle between the points (0, 0, 1), (0, 1, 0), and (1, 0, 0). The inner hexagram's edges are high-probability, and the outer subtriangles have no probability.

It's pretty cool, but let's first learn rock, paper, scissors.

Rock, Paper, Scissors (RPS)

In RPS, rock beats scissors, scissors beats paper, and paper beats rock. You get one point for beating the other person's choice, 1/2 a point for choosing the same thing, and 0 points for getting beaten.

I have a friend Mimee (who also helped me think through part of this problem) whose RPS strategy is to always play rock. This is great against anyone predisposed to play scissors, but doesn't work very well after people catch on. You can beat this strategy 100% of the time by playing paper.

My favorite strategy is to play whatever the other person's previous play would have beat. This works against many people because they rarely play the same thing twice in a row, but it still isn't a very good strategy. It would loose about 100% of the time to a stubborn person who keeps playing rock.

For competitive play, the best technique is of course to choose randomly, with equal probability to rock, paper, and scissors. This way, no matter what technique the opponent uses, they can't get more points than you on average. In general, if your chances of playing rock, paper, or scissors are x_r, x_p, x_s respectively, you have an expected outcome of x_p + \frac12 x_r against someone playing rock, and so forth. This can be simply written as

\begin{bmatrix} 0.5 & 1 & 0 \\ 0 & 0.5 & 1 \\ 1 & 0 & 0.5 \end{bmatrix} \begin{bmatrix} x_r \\ x_p \\ x_s \end{bmatrix} = \begin{bmatrix} y_r \\ y_p \\ y_s \end{bmatrix}
where y_r is your expected number of points against rock, and so forth. We can derive the optimal technique by demanding that we average at least 0.5 points; that y_r, y_p, y_s \ge 0.5. If we don't, the opponent could average more points by always playing what we lose to on average. If we do, the opponent can't beat us more than 50% of the time regardless of their technique.

Generalizing RPS

We can easily generalize this problem. Suppose there are i = 1, 2, 3, \ldots n possible plays, and play j always has probability a_{ij} to beat play i. Then if we choose to make play i with probability x_i, our expected number of points against each opponent's play can be written as

\begin{bmatrix}a_{11} & a_{12} & \ldots & a_{1n} \\ a_{21} & a_{22} & \ldots & a_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{n1} & a_{n2} & \ldots & a_{nn}\end{bmatrix}\begin{bmatrix}x_1 \\ x_2 \\ \vdots \\ x_n\end{bmatrix} = \begin{bmatrix}y_1 \\ y_2 \\ \vdots \\ y_n\end{bmatrix}
Each a_{ii} must be 1/2 and each a_{ij} + a_{ji} = 1. To write that more concisely, if this matrix is A, then A = 1-A^T. It would be nice to just let \vec{y} = \vec{1/2} and invert A to find the probability vector \vec{x} we need to win half the time.

For example, if I modify RPS so that paper beats rock 80% of the time, scissors beat paper 60% of the time, and rock beats scissors 70% of the time, then the ideal strategy is to use x_r = 1/6, x_p = 1/3, x_s = 1/2, which is obtained by inverting the matrix. Unfortunately, the solution is not always so simple.

First of all, there might be no solution for \vec{x} to A\vec{x} = \vec{1/2}. That's not to stay there is no best strategy, you just might not beat everything with exactly 50% probability. For instance, if we add in a useless fourth play (eye?) to RPS which loses to everything else, then inverting the matrix tells us to play eye with negative probability, which of course cannot be done. The best strategy is to play the original 3 plays with equal probability, which beats eye 100% of the time rather than 50%.

Second of all, there might be too many solutions (if the matrix is not invertible). For instance, if we add a fourth play (anti-rock?) to RPS which draws with rock, beats paper, and loses to scissors, then the normal RPS technique is optimal, but you can also incorporate anti-rock into your technique and still be optimal.

I can prove that a best strategy exists, and the proof can also be followed through to construct a solution. However, the proof is surprisingly difficult, and this next part will get mathy quickly. First let's deal with the case that we have an even number of possible plays. Our original intent was to find a \vec{x} with A\vec{x} \ge \vec{1/2}, but if we define B = A - 1/2 (a matrix with all entries equal to 1/2), this is equivalent to proving that

B\vec{x} \ge 0

since x sums to 1. Also, since A = 1 - A^T, we have that B = -B^T. In other words, B is skew-symmetric. Because it has even dimension, gives it the property that it can be decomposed into Q\Sigma Q^T, where Q is orthogonal (a rotation matrix) and \Sigma is a matrix which rotates each consecutive, disjoint pair of coordinates (first coordinates 1 and 2 by 90^\circ, then coordinates 3 and 4 by 90^\circ, and so forth) and then scales each pair (read the Wikipedia article to see what the matrix looks like). Since Q is a rotation matrix, we may as well redefine our axes to be in line with its change of basis, so our problem is equivalent to proving that there exists a probability vector \vec{x'} with \Sigma x' \ge \vec{0}.

Fortunately, \Sigma deals with each consecutive pair of coordinates independently from each other consecutive pair, so this problem can be further simplified to showing that it works in 2 dimensions. This is finally simple; we want to show there exists a \vec{x'} \in \mathbb{R_+}^2 with

\begin{bmatrix}0 & \lambda_1 \\ -\lambda_1 & 0\end{bmatrix}\begin{bmatrix}{x_1}' \\ {x_2}'\end{bmatrix} \ge \vec{0}

which is definitely satisfied by a vector with {x_1}' = 0, {x_2}' > 0. Therefore, if we choose our transformed x''s to satisfy these conditions, we have a solution in x.

In the case when there are an odd number of plays, add an additional play that always loses to everything else. Then the solution will be the same, since no best strategy could possibly use the useless play. But now we have an even number of plays, and the same proof holds. Therefore a solution must also exist in the odd case. This completes the proof of existence.

The Solution

Returning to the HvZ problem, the set of possible plays is a triangle in (a, b, c) space defined by a + b + c = 1, a \ge 0, b \ge 0, c \ge 0:

a point (a1, b1, c1) on the triangle between a, b, and c, each of which is a component vector

What plays does (a_1, b_1, c_1) beat? Any play with a_2 > a_1, b_2 < b_1, and c_2 < c_1 would work. Similarly if a_2 < a_1, b_2 > b_1, and c_2 < c_1; or a_2 < a_1, b_2 < b_1, and c_2 > c_1. Plotting these possibilities, where the things (a_1, b_1, c_1) beats are in blue, makes it a lot clearer what beats what:

that same triangle colored in 6 sections alternating between beating (a1, b1, c1) and being beaten by it

If we discretize this problem, it becomes a generalized RPS game; each play in the space has a probability to beat each other play in the space (either 0, 1/2, or 1). The full problem is just a continuous version of the discrete games we were considering earlier.

I wrote a numerical algorithm which efficiently converged to the solution. The optimum strategy is to sample from this probability density function over the set of plays:

Beautiful probability density heat map on an equilateral triangle between the points (0, 0, 1), (0, 1, 0), and (1, 0, 0). The inner hexagram's edges are high-probability, and the outer subtriangles have no probability.

Wow! It's actually really pretty! Basically, play frequently near the edges of the main hexagon, with occasional forays into its interior. This wins against each possible play in the interior with 50% probability, and near the corners with more:

A plot on the equilateral triangle of expected points the optimal strategy gets against the play. The middle hexagon has 0.5 expected points, and the outer subtriangles have higher.

The numerical method works by discretizing the space into a triangular grid, then minimizing a cost function. Our goal is to not lose more than 50% of the time, so if the chance of beating each possible play is y_{i,j}, my cost function is E(y) = ||\min(y-0.5, 0)||_2. I then applied a gradient descent algorithm to find the optimal probability x_{i,j} of each play.

To account for the normalization (that \sum_{i,j} x_{i,j} = 1), I had the gradient descent take into account not only the change in each y_{k,l} with respect to each x_{i,j}, but also the incremental normalization on all coordinates that would be incurred by increasing any x_{i,j}. Explicitly, this adds -\sum_{i,j} \sum_{k,l} x_{i,j}\frac{\partial y_{k,l}}{\partial x_{i,j}}\frac{\partial E}{\partial y_{k,l}} to each gradient. Without taking this geometry of the problem into account (by just doing dumb gradient descent without constraints), the algorithm did not even converge to the right solution. I coded the right algorithm in a computationally efficient manner.

Closing Thoughts

I'm probably never going to play RPS, or this HvZ problem, using the optimum strategy. It's no fun to win half the time regardless of what the other person does.

Edit: Analytic Solution

This is apparently a case of the continuous Colonel Blotto game, and two researchers pretty much solved it in this working paper. The hexagon strategy shown here is a real solution, but there are additional solutions in which you play on smaller hexagons near the vertices of that hexagon, or yet smaller hexagons near the vertices of those hexagons, and so forth. I think that's interesting, because as you use smaller and smaller hexagons, the total area of the support of your strategy shrinks to 0; you are playing on a type of Cantor set.