Assignment
5: Game Theory II Fall 2006, David Matuszek 
chooseRandomly
method. Write and
test it anyway; it's worth knowing how to do.chooseBestRowForMax
and chooseBestColumnForMin
now take,
as parameter, an array giving the other player's mixed strategy. Combine this assignment with the previous assignment to create a fairly complete GameTheory program.
Your program should read in arrays, one at a time. For each array, the program should determine (and print out):
You will have a different partner from the last assignment, so you should have
two different versions of the SaddlePoint
class to work with. Choose
one of themif they both work, it shouldn't make much difference which one
you use.
I will provide you a class containing a method that will make it easy to read
in arrays. Just use print
and println
statements to
do the output.
In some games there is a saddle pointthat is, a "best" row and a "best" column that should always be chosen. In other games, the best move depends on how the opponent moves.
If one player plays predictably, the other player can take advantage of that fact. For example, if the row player always chooses the second row (hoping to get the 12), the column player can choose the first column (containing the 5). Hence, both players should use a mixed strategy, sometimes making one choice and sometimes another. However, the rows and columns shouldn't be chosen equally often; in this game, the row player should choose the first row more than twice as often as the second row, and the column player should more frequently choose the first column. How do we know this?
In this assignment we will not be playing the game, but instead we will compute how frequently the players should choose each row and each column, for any size array.
Min


0

1

2


Max  0 


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
,
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
or
, 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
(or
,
or however many rows or columns there are to choose from). Then repeatedly
do the following:
Note: Corrected algorithm from here on down
In the above example, suppose Max and Min both start with a strategy of
.
[1, 1, 1]

that is, equal probabilities.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.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.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.8/3
, so his choice is row 2
.
He updates his strategy to [1, 1, 2]
.[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
. [1, 1, 2]
.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
.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
.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
.13
, so her choice is column
1
. She updates her strategy to [1, 2, 1]
.[1, 2, 1]
.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.





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 row 0 
Figure 3. Now Min knows Max's strategy is 1:2,
so she will do better with column 0 column 1 
Figure 4. Max's turn: row 0: row 1: so choose row 0. 





Figure 5. Min's turn: col 0: col 1: so choose column 0. 
Figure 6. Max's turn: row 0: row 1: so choose row 0. 
Figure 7. Min's turn: col 0: col 1: so choose column 0. 
Figure 8. Max's turn: row 0: row 1: 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%].
Create a class Game
. This class should have a constructor
.
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:
static int chooseRandomly(int[] weights)
0..weights.length
, chosen randomly
according to the ratios in the weights
array. For example, if
the weights
array is {2, 5, 3}
0
, 20% of the time; 1
,
50% of the time; and 2
, 30% of the time.
random.nextInt(int)
.
Can you figure out how?
int chooseBestRowForMax(int[] minsStrategy) // Note change in parameter
int chooseBestColumnForMin(int[] maxsStrategy)
//
Note change in parameter
void computeMixedStrategies()
int[]
fields of this Game
object.
double[] getStrategyForMax()
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()
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
.Write comprehensive JUnit tests for each of the above methods. Put these in
a class named GameTest
.
Since it's unwise to test floatingpoint 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 all your JUnit tests for the previous program, which should be in a
class named SaddlePointTest
. If you had to make any changes in
your SaddlePoint
methods, make sure your unit tests still work.
I am providing an ArrayReader
class, in ArrayReader.java.
You can use it to read in an array like this:
int myArray[][];
myArray = ArrayReader.getArray();
(I'm also providing a simple ArrayReaderTest.java
class with a main
method, so you can see what ArrayReader
does.)
Your program should use getArray()
to read in an array. Print
out the array. If the array has a saddle point, print out its row, column, and
value. If the array doesn't have a saddle point, print out the mixed strategies
for each player. Repeat as many times as the user desires.
If the user cancels array input (by clicking the Cancel
button in the ArrayReader
), the getArray()
method
will return null
. Exit the program when this happens.
Before you leave the lab today, you should estimate how much time you will
spend on this project; your partner should do the same. As you work on the project,
keep track of the amount of time you actually spend. Include these numbers (estimated
and actual time for each of you) in a file named readme.txt
.
Add Javadoc comments to all nonprivate classes, fields, and methods. Javadoc is optional for private fields and methods. Don't use Javadoc in your JUnit testsbut use internal comments for anything unusual or confusing.
Be sure your source code is properly formatted, according to Java (not C) standards.
Thursday, October 19, before midnight.