Homework 5 - Peace War Tournament
The
Prisoner's
Dilemma problem is a classic problem in
game theory that attempts to
explain agreement and dissension among two parties. Here is a description of
the game taken from Wikipedia:
Two men are arrested, but the police do not possess enough information for a
conviction. Following the separation of the two men, the police offer both a
similar deal- if one testifies against his partner (defects / betrays), and the
other remains silent (cooperates / assists), the betrayer goes free and the
cooperator receives the full one-year sentence. If both remain silent, both are
sentenced to only one month in jail for a minor charge. If each 'rats out' the
other, each receives a three-month sentence. Each prisoner must choose to either
betray or remain silent; the decision of each is kept quiet. What should they
do?
If the two convicts are cooperating, then the clear choice is to both remain
silent. That way, each serves only the minimum one month sentence instead of
one person receiving a full year or both receiving three months. However, if
both convicts distrust the other, then it turns out that the optimal decision to
be made by both is to rat the other convict out. To see this, let's examine the
payoff matrix that describes the time each prisoner gets based on the
decisions they make.
|
A is silent |
A rats out B |
B is silent |
A and B get 1 month |
A goes free; B gets 1 year |
B rats out A |
A gets 1 year; B goes free |
A and B get 3 months |
From this we can see that, for example, if prisoner A decides to be silent,
then he will either 1 month or 1 year of team. On the other hand, if prisoner A
rats out B, then he'll get either serve no time or 3 months. Clearly if A does
not trust B, then ratting him out is the best idea.
The traditional prisoner's dilemma consists of only a single opportunity for
the prisoners to be silent or rat out their partner. Academics have also
considered the
iterated prisoner's dilemma in which the prisoners make
several such decisions in a row, potentially changing their strategies based on
previous rounds. Of course, this is slightly unrealistic, so instead we phrase
the iterated prisoner's dilemma game in terms of another game called A
Peace War Game
Peace War Games
The peace and war game is similar to the prisoner's dilemma except that
instead of prisoners we have neighboring countries. And instead of either
staying silent or ratting, each year the countries declare peace or war against
the opposing country, scoring a number of points based on who declares peace or
war. The game continues for a number of years and the winner is the country
with the most points.
The pay-off matrix for the peace and war game is as follows:
|
A declares peace |
A declares war |
B declares peace |
A and B get 3 points |
A gets 5 points; B gets no points |
B declares war |
A gets no points; B gets 5 points |
A and B get 1 point |
Our goal is to write a program,
PeaceWarGame that plays a series of peace
and war games against an AI opponent. Each game last 10 turns/years which
should be represented in your program by a class constants (similar to homework
2). After the game, the program prompts the user if they would like to play
again. When the user indicates they no longer want to play, the program prints
out the total number of games played, the number of games the player won, the
resulting win percentage, and then exits.
Sample Output
Here is a sample execution of the peace war game program in action. Like
previous assignments, you should reproduce this output exactly. Because of the
length of the sample output (two games at 10 turns a piece), I've included it as
a text file linked below.
hw5-sample-output.txt
The following sections outline the specific format for the output of each
part of the program.
Format of output
Years. Each round of the peace war game consists of a single
year with a particular format of output. The general format is given below:
=====
Year <# of year>
Our score: <player's score>
Their score: <AI's score<
What is your strategy this year? <Input echoed by Scanner>
You chose <Player's strategy>
They chose <AI's strategy>
<Peace war message>
The peace war message is based on the strategies the player and AI chooses
as follows:
|
Player declares peace |
Player declares war |
AI declares peace |
>>> Peace for everyone! |
>>> We crushed them! |
AI declares war |
>>> They crushed us! |
>>> Everyone to arms! |
Keep in mind that the ">>>" is part of the output so that you can
visually tell the outcome of the year easily.
Final report. At the end of a game, a final report is given
similar to the format of the output for each year:
=====
Final
Our score: <player's score>
Their score: <AI's score<
<winner message>
The winner message is based on who won the game and has the following
format:
- >>>>> We win! <<<<<
- >>>>> They win! <<<<<
- >>>>> It's a tie! <<<<<
Like above, the > and < are part of the output.
Summary. Finally, the program reports statistics about the
games played before exiting. The format of this final part is:
Total games played: <total games played>
Total games won: <total games won>
Win percentage: <win percentage>
The win percentage should be given as a two place decimal of the form
X.XX. You should use
printf for this task.
Repeated and generous prompting
Unlike the previous homework, with
while loops, we can now enforce
that the user enters the correct input and repeatedly prompt them until they get
it right. There are two places where the program prompts the user for input.
Here are examples of repeated prompting in action for each of them:
What is your strategy this year? cat
Invalid strategy. Enter "peace" or "war": 5
Invalid strategy. Enter "peace" or "war": peace
...
Play again? donkey
Invalid response. Please enter "y" or "n". y
The valid inputs for the first prompt are
peace or
war
, and the valid inputs for the second prompt are
y or
n.
You should duplicate these error-and-reprompt messages exactly in your
program. I highly recommend reviewing chapter 5.4 of the text to review how to
handle user error in a robust way.
Furthermore, your handling of user input should be generous and allow
the user to enter text of any case. For example, the following exchange should
be valid:
What is your strategy this year? PeAcE
You chose peace.
They chose peace.
>>> Peace for everyone!
Note how even though the inputted text is
PeAcE, we still print out
peace in lowercase letters. You will find the
toLowerCase and
equalsIgnoreCase methods of the String class helpful to emulate this
behavior.
The peace war AI
Your program will need play rounds of peace and war against the player. For
the initial version of your program, your program should
randomly choose
between peace and war each year. The
random class should be
helpful in implementing this behavior.
For the purposes of the tournament described below, we would like you to
implement this behavior in a specific way. Create a class named
AI in
a file called
AI.java. Your class should take on the following form:
public class AI {
// Returns the strategy the computer should do this turn, either "war" or
// "peace". Takes a Random object and the last play made by the player in
// the previous year, a number that is the current year being played, and a
// String that represents the last strategy chosen by the player (not the
// AI). This will also be "peace" or "war".
public static String getStrategy(Random rand, int currentYear, String lastStrat) {
// Implement me!
}
// Returns your AI's name that will be used during the tournament. This
// can be your name or any nickname as long as it is not offensive or
// otherwise inappropriate.
public static String getName() {
// Implement me!
}
}
You must use this
getStrategy method in your
PeaceWarGame
game when the AI needs to make a move. Remember that this is a public static
method in another class, so you should use dot notation to call the
getStrategy within the
AI class that you make.
The parameters of
getStrategy allow your AI to make more complex
decisions.
currentYear is current year that is being played (starting
at 1).
lastStrat is the strategy chosen by the player in the previous
year. For the first year, you should pass "peace" in for lastStrat, i.e.,
assume that the playr was peaceful before the game began.
For your initial implementation, the AI will choose strategies at random
and thus ignore these parameters, but even if you end up using this initial
implementation in your final submission, we will check to make sure that you are
passing the correct values for these parameters in your program.
The Tournament
We will be holding a class-wide
Peace War Tournament using the AI
classes that you make. The tournament will begin with a
round robin group stage of
approximately 12 people per group. The top two AIs (by point totals) from each
group will advance to the finals where they will play to determine the winner.
The format of the finals will be a second round robin consisting of the
advancing players from each bracket. We will cast the finals live over the
Internet later in the semester. Note that this is different from traditional
peace war/prisoner's dilemma tournaments in that those are usually purely round
robin tournaments.
Here are the rules:
- To be eligible for the tournament, all you need to do is to complete the
homework assignment and have a compilable AI class described above. Both of
your methods in this class should also not go into an infinite loop.
- For this tournament, you will play one match against every other person in
the class. In the finals, you will play one match against each of the
finalists. Games will consist of a random number of rounds/years set at the
start of group play and the finals.
- There is an extra credit point available for writing an AI that does
anything other than randomly choose peace or war each round. See below for
details. There are no extra credit points for winning the tournaments, but
you'll be recognized in class and on the course website if you do!
Once you are done with your initial program, you may implement any algorithm
you wish in the
getStrategy method to decide if the AI declare peace or
war each year (subject to the "no infinite loops" and 'return only "peace" or
"war"' constraints). In particular you may use any programming APIs or
constructs that you wish, even those not yet discussed in class. For
inspiration, read about strategies for prisoner's dilemma from
wikipedia and feel free to search around for ideas.
Extra credit: you will receive
1 point of extra credit if you
- Implement a non-random getStrategy method in your AI class.
- Include a brief description of your algorithm that you implement in your AI
class's header comment.
Note that we will only award extra credit to students that are able to get
their main program (mostly) working. So please focus on the the main problem
before getting into the extra credit. But otherwise, feel free to have fun with
it!
For your final submission, you only need to turn in your final AI. In
particular, you do not need to submit a random AI if you decide to implement
something fancier.
Design
Like the previous assignment, this is a more traditional programming task
than the first three homeworks. There are no visual patterns for you to
decompose, but the principles of decomposition still apply! There are at least
two static methods we'd like you to include:
- A method to play a single game of peace and war. Recall that a
single game of peace and war for our purposes is 10 rounds/years of play. In
particular, it should not be responsible for prompting the user to play another
game.
- A method to print out the final statistics for all the games played.
This method should do not other work other than printing these statistics to the
screen.
In addition to these methods,
main, and the required methods in
your AI class, please include
three other useful static methods in your
program. You are of course welcome to include more methods if it makes
sense to do so (and given the number of checks and prompts you need to do, it
seems very reasonable).
Also, make sure that you use a class constant to represent the number of
years/rounds each game should last. Make sure that if you change this value
(e.g., if you want to test your AI for more rounds in preparation for the
tournament) that you change it back to 10 for your final submission.
Submission
Please
submit
your Java source files,
PeaceWarGame.java and
AI.java,
electronically via the course website. You will need to place these files into
a zip archive called
hw05.zipand submit that archive. On Windows you can
create a new "Compressed (zipped) Folder" by right-clicking your desktop and
selecting "New". On OSX, you can select your files in Finder, right-click and
select "Compress".