CIT 591 Assignment 9: Game Theory: Mixed Strategies
Fall 2010, David Matuszek

Purposes of this assignment

• To give you more experience with classes and arrays
• To give you more Java practice

General idea of the assignment

Combine this assignment with the earlier Saddle Points assignment to create a fairly complete `GameTheory` program.

In your SaddlePoints project, in the `saddlepoints` package, create a new class called `GameTheory`. This class will sit alongside your `SaddlePoints` class and make use of methods from it. You can correct any actual errors you find in your `SaddlePoints` class, but you should not make any other changes or additions to it.

Your program should read in arrays, one at a time. For each array, the program should determine (and print out):

• The array,
• Whether the array has a saddle point, and
• if so, where the saddle point is (row and column) and what its value is, or
• if not, the mixed strategy that should be followed by each player.

You should have a different partner from the earlier assignment, so you should have two different versions of the `SaddlePoints` class to work with. You should use your own `SaddlePoints` class, and your partner should use his/her own. Your new `GameTheory` class should work equally well with either.

I will provide you with a method to read in arrays. The `SaddlePoints` class already has a method you can use to print the arrays, and other methods you can use.

Details

Remember how the game is played: Max chooses a row, Min chooses a column, and where they intersect is the amount Min pays to Max. In some games there is a saddle point--that is, a "best" row and a "best" column. Players would be wise to always play to the saddle point.

In other games, there is no single "best" move, because the best move depends on how the opponent is likely to move. In the game below, for example, if Max always chooses the same row, then Min knows which column to choose to get a negative number. Likewise, if Max knows how Min is going to play, Max can always win. Hence, both players should use a mixed strategy, sometimes making one choice and sometimes another.

Although Max and Min should randomize their play, that doesn't mean that every row and every column should be chosen equally often. In this game, Max should choose the first row more than twice as often as the second row, and Min should more often choose the first column. How do we know this?

The purpose of this assignment is not to play the game, but to compute how frequently the players should choose each row and each column, for any size array.

Finding a mixed strategy

Min

0
1
2
Max 0
 1 -2 3 -6 5 -4 7 -8 9
1
2

Suppose there is no saddle point, as in this game. Then players must choose between two or more rows or columns. Also, the other player shouldn't be able to predict their moves, so they need to play somewhat randomly, but still choosing the best rows or columns more often than the worse ones. This is called a mixed strategy.

For example, a mixed strategy for Max might be `[20, 50, 30]`, meaning that Max chooses row zero 20% of the time, row one 50% of the time, and row two 30% of the time (and similarly for Min).

By the way, these numbers don't have to add up to exactly 100. If Max's strategy is ` [2, 5, 3]` or ` [400, 1000, 600]`, these are both equivalent to `[20, 50, 30]` (and to each other).

You can compute an approximate best mixed strategy by simply (sort of) playing the game a large number of times (say, a thousand). Here's how. Each player starts with a strategy of `[1, 1, 1]` (or ```[1, 1, 1, 1]```, or however many rows or columns there are to choose from). Then repeatedly do the following:

• Max looks at Min's current strategy, chooses a row based on that, and updates his own strategy accordingly.
• Min looks at Max's current strategy, chooses a column based on that, and updates her own strategy accordingly.

In the above example, suppose Max and Min both start with a strategy of `[1, 1, 1]`.

• Let's look at Max first:
• Max knows that Min's current strategy is `[1, 1, 1]` -- that is, equal probabilities.
• If Max plays row `0`, he will get `1` or `-2` or `3` with equal probabilities. So ```(1*1 + 1*(-2) + 1*3)/3 = 2/3``` is his expected payoff.
• If Max plays row `1`, he will get `-6` or `5` or `-4` with equal probabilities. So ```(1*(-6) + 1*(5) + 1*(-4))/3 = -5/3``` is his expected payoff.
• If Max plays row `2`, he will get `7` or `-8` or `9` with equal probabilities. So ```(1*7 + 1*(-8) + 1*9)/3 = 8/3``` is his expected payoff.
• Max prefers the largest of these, `8/3`, so his choice is row `2`. He updates his strategy to `[1, 1, 2]`.
• Note that we are always dividing by the same number (the total of Min's `[1, 1, 1]`, which is `3`). Since we just want to know which number is the largest, we can skip the division, and just compare the numbers `2`, `-5`, and `8`.
• Now we do basically the same thing for Min:
• Min knows that Max's current strategy is now `[1, 1, 2]`.
• If Min plays column `0`, she will get `1`, `-6`, or `7` with odds `1:1:2`. So `(1*1 + 1*(-6) + 2*7)/4 = 9/4`. Or, skipping the division, `9`.
• If Min plays column `1`, she will get `-2`, `5`, or `-8` with odds `1:1:2`. So` (1*(-2) + 1*5 + 2*(-8))/4 = -13/4`; or, just use `-13`.
• If Min plays column `2`, she will get `3`, `-4`, or `9` with odds `1:1:2`. So `(1*3 + 1*(-4) + 2* 9)/4 = 17/4`. Or, just use `17`.
• Min prefers the smallest of these, `-13`, so her choice is column `1`. She updates her strategy to `[1, 2, 1]`.
• Now it's Max's turn again:
• Max knows that Min's strategy is now `[1, 2, 1]`.
• Etc.

Extended example

We will have the two players take turns (again, we are not playing the game, we are figuring out the best mixed strategy.) For each turn, the player whose turn it is chooses the best move based on how the opponent has been playing.

To implement this, we need two additional arrays; one to keep track of how many times the row player has chosen each row, and one to keep track of how many times the column player has chosen each column. To get things started, each of these arrays will be filled with `1`s. In Figure 1 (below), we start by having the row player choose row 0, as indicated by the 1 in the array on the right.

Min

 0 1

Max
 0 1
 4 -3 -5 12
 1 1

 1 1

Min

 0 1

Max
 0 1
 4 -3 -5 12
 1 2

 1 1

Min

 0 1

Max
 0 1
 4 -3 -5 12
 1 2

 2 1

Min

 0 1

Max
 0 1
 4 -3 -5 12
 2 2

 2 1

Figure 1. The initial setup (all rows and columns have equal probability). Figure 2. Max knows Min's strategy is 1:1, so he will do better with
row 1 (1*(-5)+1*12)=7 than
row 0 (1*4+1*(-3))=1.
Figure 3. Now Min knows Max's strategy is 1:2, so she will do better with
column 0 (1*4+2*(-5)) than
column 1 (1*(-3)+2*12).
Figure 4. Max's turn:
row 0: (2*4+1*(-3))=5
row 1: (2*(-5)+1*12)=2
so choose row 0.

Min

 0 1

Max
 0 1
 4 -3 -5 12
 2 2

 3 1

Min

 0 1

Max
 0 1
 4 -3 -5 12
 3 2

 3 1

Min

 0 1

Max
 0 1
 4 -3 -5 12
 3 2

 4 1

Min

 0 1

Max
 0 1
 4 -3 -5 12
 4 2

 4 1

Figure 5. Min's turn:
col 0: (2*4+2*(-5))=-2
col 1: (2*(-3)+2*12)=18
so choose column 0.
Figure 6. Max's turn:
row 0: (3*4+1*(-3))=9
row 1: (3*(-5)+1*12)=-3
so choose row 0.
Figure 7. Min's turn:
col 0: (3*4+2*(-5))=2
col 1: (3*(-3)+2*12)=15
so choose column 0.
Figure 8. Max's turn:
row 0: (4*4+1*(-3))=13
row 1: (4*(-5)+1*12)=-8
so choose row 0.

This procedure eventually results in the "best" strategy for each player; the side and bottom arrays give the relative number of times each row and each column, respectively, can be played. In the above game, if the results are given in percentages, they should be(approximately): Max, [70.8%, 29.2%]; Min, [62.5%, 37.5%].

Classes and methods

Create a class `GameTheory`. This class should have a constructor `public GameTheory(int[][] array)`. The constructor will save this array in a local variable, and many of the methods will use this "game."

Notice that at each turn, one of the players chooses a move randomly, according to his or her current mixed strategy. The other player then chooses the best response to that move, and updates his/her mixed strategy. To implement this, you should have the following methods:  The preceding three sentences are cruel and misleading, and should be ignored.

`public static void main(String[] args)`
Any class can have this method. You can start the program from any class with a `main` method, and the program will do whatever the `main` method for that class says to do. This `main` method should use the provided method to ask the reader for an array to read in, print the array, and tell whether it has a saddle point, and how each player should play. It should repeat this for as many arrays as desired, quitting when the provided method returns `null` instead of an array.

`static int chooseRandomly(int[] weights)`
Returns a number in the range `0..weights.length`, chosen randomly according to the ratios in the `weights` array. For example, if the `weights` array is `{2, 5, 3}`, then the method will return: `0`, 20% of the time; `1`, 50% of the time; and `2`, 30% of the time.
Hint: This is most easily done with one call to `random.nextInt(int)`. Can you figure out how?
This method can be used to play the game, but is not used when determining optimal strategies.
`int chooseBestRowForMax(int[] minsStrategy)`
Returns the row number that is best for Max, when Min uses the given strategy.
``` int chooseBestColumnForMin(int[] maxsStrategy)```
Returns the column number that is best for Min, when Max uses the given strategy.
``` void computeMixedStrategies()```
Computes the best mixed strategy for Max, and the best mixed strategy for Min, for this game. These strategies are not returned by the method, but are instead kept in `int[] `fields of this `Game` object.
``` double[] getStrategyForMax()```
If `computeMixedStrategies()` has been called for this game, return an array of `double`s containing the best mixed strategy for Max. These `double`s should sum to `1.0`. (For example, if the int array contains `{2, 7, 5, 6}`, the array returned by this method should be` {0.10, 0.35, 0.25, 0.3}`. If `computeMixedStrategies()` has not been called, this method returns `null`.
``` double[] getStrategyForMin()```
If `computeMixedStrategies()` has been called for this game, return return an array of `double`s containing the best mixed strategy for Min. These `double`s should sum to `1.0`. If `computeMixedStrategies()` has not been called, this method returns `null`.

Supplied code

Your `SaddlePoints` class should be working properly. You can test it with DavesSaddlePointsTest.java.

In order to read in two-dimensional integer arrays, I have supplied a `readIntArray` method. It is included in a complete program, IntArrayReader.java, but you should copy just the method (and the necessary `import`s) and put them in your `GameTheory` class. The `readIntArray` method can throw exceptions; you should catch these exceptions in your code, and print a message to the user, but your program should continue to run.

Java is a good language--really!--but it does make file I/O ridiculously complex. Please do not ask me to explain to you how the `readIntArray` method works. If you are interested, this would make a good weekend project with a Java book.

JUnit tests

Write comprehensive JUnit tests for each of the above methods. Put these in a class named `GameTheoryTest`.

Since it's unwise to test floating-point numbers for equality (and since you won't get exact results in any case), you will need to use the following JUnit method:
```static void assertEquals(double expected, double actual, double delta) ```
where the `expected` value and the `actual` value should be within `delta` of each other in order to be considered approximately equal.

Include your earlier `SaddlePointsTest` class. If you had to make any changes in your `SaddlePoints` methods, make sure your unit tests still work.

Add Javadoc comments to all non-private classes, fields, and methods. Javadoc is optional for private fields and methods. You don't need to document your unit test methods--but use internal comments for anything unusual or confusing. The Javadoc for your `GameTheory` class must include `@author` tags for both yourself and your partner.
Thursday, November 11, before midnight. Zip your entire project folder, and submit it via Blackboard. The project should contain the new code (`GameTheory.java` and `GameTheoryTest.java`), and one copy of the previously-written `SaddlePoints.java` and `SaddlePointsTest.java` files (I don't care whose, yours or your partner's). Email submissions will go directly into the trash bin.