Project 2: Genetic Algorithm for Blotto

Objectives

• to use a list ADT
• to implement list ADTs using dynamically allocated arrays

Introduction

Blotto is a simultaneous game for two players in which the players distribute resources over a number of locations. The resources could be, for example, campaign staff in an election, and the locations could be battleground states. The number of battlegrounds is determined before the game, as is a value assigned to each battleground. Each player has a set number of units of resources to distribute, each unit is equivalent to each other unit, and a unit must be allocated entirely to a single battleground. For each battleground, the player who allocates more units to it wins the points for it (with the points split evenly in case of a tie, including a 0-0 tie). The winner of the game is the player with the most total points, with a drawn game ($\frac{1}{2}$ win for each player) if the player's totals are the same.

For example, suppose there are four battlegrounds worth 4, 3, 2, and 1 points respectively and each player has 10 units of resources to distribute. If player 1's distribution is $(4, 2, 2, 2)$ and player 2's distribution is $(1, 2, 4, 3)$ then player 1 wins battleground 1, player 2 wins battlegrounds 3 and 4, and the players tie on battleground 2. Player 1's score is then $4 + 1.5 = 5.5$ and player 2's score is $1.5 + 2 + 1 = 4.5$. Player 1 wins.

In an iterated version of a Blotto game, players repeat the process many times with the same number of battlegrounds and values, but may allocate their resources differently each time. If a player tends to allocate their resources in the same way each time, then the opposing player can easily adjust their own strategy to always win or tie. For that reason, the optimal policy in such a game is often a mixed strategy: a list of possible resource distributions to choose from randomly, with each item given a possibly different probability of being chosen. If we associate each possible distribution with a nonnegative weight, then we can let the probability of each distribution be its weight divided by the total weight of all the distributions.

For example in the above game, if P1 chooses $(4, 2, 2, 2)$ with weight $\frac{2}{3}$ and $(5, 5, 0, 0)$ with weight $\frac{1}{3}$ and player 2 chooses between $(1, 2, 4, 3)$ and $(5, 0, 4, 1)$ both with weight $\frac{1}{2}$, then the expected number of wins per game for P1 is $\frac{1}{3} \cdot 1 + \frac{1}{3} \cdot 0 + \frac{1}{6} \cdot 1 + \frac{1}{6} \cdot \frac{1}{2} = \frac{7}{12}$.

A genetic algorithm attempts to find better solutions to a problem by combining pieces of good solutions with pieces of other good solutions. Some of the resulting possible solutions will be poor, but some may be better than the starting solutions. After removing the poor solutions, the process repeats until a quality threshold is reached or the algorithm runs out of time.

A genetic algorithm for Blotto could start with a population of strategies and then combine them in an attempt to find strategies that beat the other strategies in the population more often than not. One way to combine two strategies could be to take some individual distributions and weights from one strategy, and some from the other to create a new strategy. For example, we could take the first distribution and weight from P1 above and the second from P2 to obtain a strategy that plays $(4, 2, 2, 2)$ with weight $\frac{2}{3}$ and $(5, 0, 4, 1)$ with weight $\frac{1}{2}$ (and so respective probabilities of $\frac{4}{7}$ and $\frac{3}{7}$ after dividing by $\frac{2}{3} + \frac{1}{2} = \frac{7}{6}$). We could also take the second distribution from P1 and the first from P2 to get a strategy that plays $(5, 5, 0, 0)$ with weight $\frac{1}{3}$ and $(1, 2, 4, 3)$ with weight $\frac{1}{2}$ (and so respective probabilities $\frac{2}{5}$ and $\frac{3}{5}$). (Note that while we have computed the probabilities for illustrative purposes, it is the weights that define the strategies, and the weight for a distribution remains unchanged as they are copied together from generation to generation.)

Assignment

Complete the strategy and population modules and write a program called BlottoGA using those modules in order to implement a basic genetic algorithm for Blotto strategies. The strategy and population modules must be implemented according to the specifications in the corresponding header files in /c/cs223/hw92/Required, which you may not change. Incomplete implementations are given in /c/cs223/hw92/Optional, along with some helper modules. You may add to the helper modules, but you must leave the existing function declarations and definitions unchanged. The strategy and population modules will be tested separately from your BlottoGA program with a series of unit tests in the program Unit, which is built from all of the modules and the main in /c/cs223/hw92/Optional/ga_unit.c.

Input

For the BlottoGA program, the values of the locations, the names of the files containing the mixed strategies to add to the initial population, and the operations to perform on the population will be given as command-line arguments. Those arguments will be as follows.

• The first command-line arguments will be a non-empty list of positive integers giving the values of each battleground.
• The first command-line argument that is not a positive integer is the first of a non-empty list of filenames that don't start with a dash (-), where the files contain the strategies in the initial population. Each strategy should be added to the population in the order it appears on the command line. Each file will contain one line per possible distribution in the strategy, with each distribution described by a positive floating point weight followed by a non-negative list of unit counts, one per battleground. Each item on the line will be separated by a single space. The sum of the unit counts will be the same for all lines, and the sum of each line in one file will be the same as the sum of each line in the other files. There will be at least one line per file.
• The first command-line argument that starts with a dash is the first in a series of operations that define how the genetic algorithm operates. There are three possible operations, given below, and they are performed left to right.
  • -o sorts the current population in order of expected number of wins when each strategy in the population is played one-on-one against each other strategy in the population, with a draw counting $\frac{1}{2}$ a win and with ties in the total expected number of wins broken arbitrarily.
  • -d deletes strategies from the end of the current population. -d will be followed by a positive integer less than the size of the current population that gives the number of strategies to remove.
  • -x adds the offspring resulting from crossover of strategies from the beginning of the current population to the end of the population. The behavior of crossover is the same as that performed by the strategy_crossover function. -x will be followed by a positive integer at least 2 and less than the size of the current population giving the number of strategies to perform with. Each possible pair among those strategies then creates two offspring that are added in order to the end of the population. All pairs involving the first member of the population are crossed over first, in order starting with the pair formed with the second member. Then all pairs involving the second member are crossed over in order starting with the pair formed with the third member, and so on. When creating the offspring from a particular pair, the parent with the lower index is considered the first parent.

Output

Once all command-line arguments have been processed, the program prints the final population in a format like the following

INDIVIDUAL 0
[4, 2, 2, 2] 4.000
[5, 5, 0, 0] 2.000
INDIVIDUAL 1
[1, 2, 4, 3] 3.000
[5, 0, 4, 1] 3.000

where the strategies are printed in the order they appear in the final population, and each distribution with a strategy is printed as a comma-and-single-space-separated list in square brackets followed by a single space and the weight given to 3 decimal places.

Efficiency

• strategy_create, strategy_count_locations, and strategy_count_units must run in $O(1)$ time
• strategy_add_distribution must run in $O(nm)$ time, where $n$ is the number of distributions in the strategy and $m$ is the number of locations (although this can be done in $O(m \log n + n)$ time)
• strategy_expected_wins must run in $O(n_1 \cdot n_2 \cdot m)$ time where $n_1$ and $n_2$ are the number of distributions in each strategy
• strategy_crossover must run in $O(n_1 \cdot n_2 \cdot m)$ time
• strategy_copy must run in $O(nm)$ time
• strategy_print must run in $O(nm)$ time
• strategy_destroy must run in $O(n)$ time
• population_create, population_size, and population_get must run in $O(1)$ time
• population_add_strategy must run in $O(1)$ amortized time
• population_remove_last must run in $O(k)$ amortized time where $k$ is the number of strategies removed
• population_order must run in $O(n^2 \cdot m \cdot q^2)$ time where $n$ is the number of strategies in the population, $m$ is the number of locations, and $q$ is the number of distributions in the largest strategy
• population_destroy must run in $O(n + p)$ time where $p$ is the total number of distributions over all strategies in the population

All time bounds are under the assumption that malloc and free (but not calloc and realloc!) work in $O(1)$ time.

Error Handling

If any of the input (one of the strategies files, or the command-line arguments) is invalid for any reason, then your program must behave gracefully (it must not crash or hang).

In all cases, your BlottoGA program must execute with no valgrind errors, and your strategy and population modules must not introduce valgrind errors into any program that uses those modules according to their specifications. The behavior of your modules when the preconditions of the functions are not met and when there are memory allocation errors is left undefined and will not be tested.

Approach

The code given in /c/cs223/hw92/Optional has many of the strategy functions working for pure strategies (strategies with only one distribution). That means you can start anywhere: make strategy work with mixed strategies, test on the unit tests (and more tests of your own devising), and then work on the other parts; complete population, make sure it passes the unit tests for pure strategies and your additional tests, and then work on the other parts; or write BlottoGA, test on the public test cases for pure strategies and your own tests, and then complete the other parts.

Examples

(base) [jrg94@giraffe code]$ ./BlottoGA 4 3 2 1 /c/cs223/hw92/Tests/adriana_2.in /c/cs223/hw92/Tests/bob_2.in
INDIVIDUAL 0
[4, 2, 2, 2] 4.000
[5, 5, 0, 0] 2.000
INDIVIDUAL 1
[1, 2, 4, 3] 3.000
[5, 0, 4, 1] 3.000
(base) [jrg94@giraffe code]$ ./BlottoGA 10 9 8 7 6 5 4 3 2 1 /c/cs223/hw92/Tests/adriana_3.in /c/cs223/hw92/Tests/bob_3.in /c/cs223/hw92/Tests/chuma_3.in /c/cs223/hw92/Tests/dilip_3.in /c/cs223/hw92/Tests/eren_3.in -o -d 1 -x 3 -o -d 6 -x 3 -d 6
INDIVIDUAL 0
[0, 5, 5, 5, 5, 1, 1, 1, 1, 1] 1.000
[3, 3, 3, 3, 3, 2, 2, 2, 2, 2] 1.000
[5, 5, 5, 5, 5, 0, 0, 0, 0, 0] 1.000
INDIVIDUAL 1
[3, 3, 3, 3, 3, 2, 2, 2, 2, 2] 1.000
[4, 4, 3, 3, 3, 2, 2, 2, 1, 1] 0.500
[10, 0, 8, 6, 0, 1, 0, 0, 0, 0] 2.500
INDIVIDUAL 2
[4, 4, 3, 3, 3, 2, 2, 2, 1, 1] 0.500
[5, 0, 5, 0, 5, 0, 5, 0, 5, 0] 1.000
[10, 0, 8, 6, 0, 1, 0, 0, 0, 0] 2.500
INDIVIDUAL 3
[0, 5, 5, 5, 5, 1, 1, 1, 1, 1] 1.000
[5, 0, 5, 0, 5, 0, 5, 0, 5, 0] 1.000
[5, 5, 5, 5, 5, 0, 0, 0, 0, 0] 1.000

Submissions

Submit your makefile, your log file, and your source code necessary to build the executables BlottoGA and Unit using your makefile as assignment 92. Your makefile should have targets for both executables and a default target that builds both (to achieve this, you can make the first rule have target all, prerequisites Unit and BlottoGA, and no commands; see Prof. Aspnes's notes for an example, albeit with only one prerequisite for all). Your makefile should assume that the files from /c/cs223/hw92/Required have been copied into the current directory but not that they are still in their original locations, and you should not submit those files.