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

Purposes of this assignment

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):

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:

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

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 1s. 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 doubles containing the best mixed strategy for Max. These doubles 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 doubles containing the best mixed strategy for Min. These doubles 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 imports) 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.

Added requirements

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.

Be sure your source code is properly formatted, according to Java (not C) standards.

Due date

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.