Hello, I enjoy playing games, videogames usually moreso. More importantly, I enjoy winning games. As a result, I also believe that games are more fun when played well. Recently, I have come across game theory; this provides for a formal excuse to study and play games. In this project, we will study and play a class of games called Blotto. Here is one instance:
There are 10 castles, numbered 1, 2, 3, \(\dots\), 10, and worth 1, 2, 3, \(\dots\), 10 points respectively. You have 100 soldiers, which you can allocate between the castles however you wish. Your opponent also (independently) does the same. The number of soldiers on each castle is then compared, and for each castle, whoever has the most soldiers on that castle wins its points (in the case of a tie, no one gets points). In a given match, castles are fought in order (starting with castle 1). If at any point a player wins 3 consecutive castles, that player is automatically awarded all remaining castles. For example, here is one potential match: $$\begin{array}[!htbp] \centering \begin{array}{|c||c|c|c|c|c|c|c|c|c|c||} \hline & & & \\[-8pt] {} & C1 & C2 & C3 & C4 & C5 & C6 & C7 & C8 & C9 & C10 \\[8pt] \hline \hline & & & \\[-8pt] Alice & 10 & 10 & 10 & 10 & 20 & 0 & 0 & 0 & 20 & 20 \\[3pt] \hline \\[-8pt] Carol & 20 & 0 & 10 & 5 & 10 & 5 & 10 & 20 & 0 & 0 \\[3pt] \hline \end{array} \end{array}$$ Well played, Carol! In the example match above, Alice wins castles 2, 4, and 5, for a total of 11 points. Carol wins castles 1, 6, 7, and 8 — and then castles 9 and 10 — for a total of 41 points. (No one wins castles 3, since that was a tie. Alice does not win castles 9 or 10 because those were awarded to Carol after she won castles 6 through 8.).
In order to find the optimal strategy, it is quickly realized that it would not be computationally cheap to
play through a round-robin game tournament using a nested for-loop with
a runtime of \(O(n^2)\), where, in this instance, \(n\), which represents
the size of the universe of possible strategies, is equal to \({109
\choose 9} \approx 4.2634215113 * 10^{12}.\)
Note here that \(n\)
is found by solving the stars-and-bars problem.
I have solved the game with 3, 4, 5, 6, 7, 8, 9, and 10 troops considered amongst 3, 4, 5, 6, 7, 8, 9, and 10 castles as well as 11 troops considered amongst 3, 4, 5, 6, 7, 8, and 9 castles. The solutions are presented in Table 1.
The set of combinations of castles of interest is: (3, 6, 9, 10); (1, 3, 5, 9, 10); (1, 3, 6, 8, 10); (2, 3, 5, 8, 10); (2, 3, 6, 7, 10); (2, 3, 6, 8, 9); (2, 4, 5, 7, 10); (2, 4, 5, 8, 9); (2, 4, 6, 7, 9); (2, 5, 6, 7, 8); (3, 4, 5, 7, 9); (3, 4, 6, 7, 8); (1, 2, 3, 5, 7, 10); (1, 2, 3, 5, 8, 9); (1, 2, 3, 6, 7, 9); (1, 2, 4, 5, 7, 9); (1, 2, 4, 6, 7, 8); (1, 3, 4, 5, 6, 9); (1, 3, 4, 5, 7, 8); (2, 3, 4, 5, 6, 8). See Figure 1 for a visualization of these combinations.
I am open to any other game suggestions. Another game I would enjoy solving is Catan. Here's a free online alternative of the game: Colonist.io