% CS 105 Fall 98, Project

\documentclass[12pt]{report}

% \setlength{\textwidth}{6.5in}
% \setlength{\textheight}{8in}
% \setlength{\oddsidemargin}{0in}
% \setlength{\evensidemargin}{0in}
% \setlength{\topmargin}{0in}

\begin{document}

\sloppy

\begin{center}

{\Large CS 105---Fundamentals of Computer Programming}\\
\vspace{2pt}
{Fall 1998 Project}\\
\vspace{10pt}
{\large \textbf{Prisoner's Dilemma}\\
\vspace{2pt}
\emph{adapted from an assignment in CS 6.001 at MIT}
}

\end{center}

\section*{The Project Assignments}

In the final project for Com Sci 105, you will define a number of
small \emph{Scheme} procedures, similar in scope to those that you
write for homework assignments. But, you will also use the procedures
that you write, along with some code provided by your instructors, to
perform interesting computational experiments that provide insight
into the way that cooperative behavior may arise out of selfishness.

The project contains 8 problems, each of which you must solve by
defining one or more procedures in \emph{Scheme}. Hand in problems
1--4 online before midnight on Thursday, 3 December, and bring printed
output to class on Friday, 4 December. Hand in problems 5--8 online
before midnight on Wednesday, 9 December (the last day of classes). If
you finish early, you may bring printed output to the last
class. Otherwise, you may hand in printed output in the main Computer
Science office, Ryerson 152, before noon on Thursday 10
December. Please print 5--6 and 7--8 on separate pages, so they can be 
separated and graded simultaneously by different TAs.

Problems 1, 6, and 7 require you to define \emph{Scheme} procedures
implementing strategies for the repeated Prisoner's Dilemma game,
described below. Demonstrate your strategies on 2--4 tiny inputs, to
show that they behave as required. Then, play your strategies against
themselves and a few other interesting strategies. In problem 1, use
the 2-player \texttt{play-loop} procedure provided on \emph{Johnny
Three}. In problems 6 and 7, use the 3-player procedure
\texttt{play3-loop} that you define in problem 5.

Problems 2--4 and 8 require you to define \emph{Scheme} procedures
that take old strategies and numerical parameters as inputs, and
create new strategies. In all cases, you need to use \texttt{lambda}
expressions to describe the outputs of these strategy-transforming
procedures, since the outputs are also procedures. Testing a strategy
transformer is a bit more complicated than testing a strategy. You
must choose a small number of different inputs to your strategy
transformer, then test each of the resulting strategies. Then, play 2
or 3 of the strategies produced by your strategy transformer against
other strategies.

Problem 5 requires you to modify the 2-player game supervision code
provided by the instructors so that it works for 3 players. Hand in
the \emph{Scheme} code for each of the procedures that you
modify. The game supervision code will be tested in problems 6--8. Be
very careful, though. An error in problem 5 will ruin your work on
problems 6--8.

For 10 points extra credit, you may submit a strategy to participate
in a tournament described in the last section. hand in your entry
online on \emph{Johnny Three}. Do not submit printed copy. You will get
credit for participation no matter how well or poorly your strategy
fares, but your procedure must include the required comments and it
must not be disqualified by generating an error. The deadline for
tournament entries is midnight on Monday, 7 December.

\section*{The Prisoner's Dilemma: A Fable}

In the mid-1920's, the Nebraska State Police achieved what may still
be their finest moment. After a 400-mile car chase over dirt roads and
corn fields, they finally caught up with the notorious bank robbers
Bonnie and Clyde. The two criminals were brought back to the police
station in Omaha for further interrogation.

Bonnie and Clyde were questioned in separate rooms, and each was
offered the same deal by the police. The deal went as follows (since
both are the same, we need only describe the version presented to
Bonnie):

``Bonnie, here's the offer that we are making to both you and Clyde.
If you both hold out on us, and don't confess to bank robbery, then we
admit that we don't have enough proof to convict you. However, we
\emph{will} be be able to jail you both for one year, for reckless driving
and endangerment of corn. If you turn state's witness and help us
convict Clyde (assuming he doesn't confess), then you will go free,
and Clyde will get twenty years in prison. On the other hand, if you
don't confess and Clyde does, then \emph{he} will go free and \emph{you}
will get twenty years.''

``What happens if both Clyde and I confess?'' asked Bonnie.

``Then you both get ten years,'' said the interrogator.

Bonnie, who had been a math major at Cal Tech before turning to crime,
reasoned this way: ``Suppose Clyde intends to confess.  Then if I
don't confess, I'll get twenty years, but if I do confess, I'll only
get ten years. On the other hand, suppose Clyde intends to hold out on
the cops. Then if I don't confess, I'll go to jail for a year, but if
I do confess, I'll go free.  So no matter what Clyde intends to do, I
am better off confessing than holding out. So I'd better confess.''


Naturally, Clyde employed the very same reasoning. Both criminals
confessed, and both went to jail for ten years.\footnote{Actually,
they didn't go to jail. When they were in court, and heard that they
had both turned state's witness, they strangled each other.  But
that's another story.} The police, of course, were triumphant, since
the criminals would have been free in a year had both remained silent.


\section*{The Prisoner's Dilemma}

The Bonnie and Clyde story is an example of a situation known in
mathematical game theory as the ``prisoner's dilemma.'' A prisoner's
dilemma always involves two ``game players,'' and each has a choice
between ``cooperating'' and ``defecting.'' If the two players
cooperate, they each do moderately well; if they both defect, they
each do moderately poorly. If one player cooperates and the other
defects, then the defector does extremely well and the cooperator does
extremely poorly. (In the case of the Bonnie and Clyde story,
``cooperating'' means cooperating with one's partner---i.e., holding
out on the police---and ``defecting'' means confessing to bank
robbery.) Before formalizing the prisoner's dilemma situation, we need
to introduce some basic game theory notation.


\subsection*{A Crash Course in Game Theory}

In game theory, a \emph{two-person binary-choice game} is represented
as a two-by-two matrix. Figure 1 shows a hypothetical game matrix.
The two players in this case are called \textbf{A} and \textbf{B}, and
the choices are called ``cooperate'' and ``defect.''

\enlargethispage*{0.5in}
\begin{center}
\begin{tabular}{c|c|c|}
             & B cooperates   & B defects  \\
\cline{2-3}
A cooperates & A gets 5       & A gets 2   \\
             & B gets 5       & B gets 3   \\
\cline{2-3}
A defects    & A gets 3       & A gets 1 \\
             & B gets 2       & B gets 1 \\
\cline{2-3}
\end{tabular}
\end{center}

\centerline{\emph{Figure 1:\/} A hypothetical game matrix}

\smallskip

Players \textbf{A} and \textbf{B} can play a single game by separately (and
secretly) choosing to either cooperate or defect. Once each player has
made a choice, he announces it to the other player; and the two then
look up their respective scores in the game matrix.  Each entry in the
matrix is a pair of numbers indicating a score for each player,
depending on their choices. Thus, in Figure 1, if Player \textbf{A}
chooses to cooperate while Player \textbf{B} defects, then \textbf{A} gets 2
points and \textbf{B} gets 3 points. If both players defect, they each
get 1 point. Note, by the way, that the game matrix is a matter of
public knowledge; for instance, Player \textbf{A} knows before the game
even starts that if he and \textbf{B} both choose to defect, they will
each get 1 point.

In an \emph{iterated game}, the two players play repeatedly: thus,
after finishing one game, \textbf{A} and \textbf{B} may play another.
(Admittedly, there is a little confusion in the terminology here: you
can think of each individual game as a single ``round'' of the larger,
iterated game.) There are a number of ways in which iterated games may
be played; in the simplest situation, \textbf{A} and \textbf{B} play for
some fixed number of rounds (say, 200), and before each round they are
able to look at the record of all previous rounds. For instance,
before playing the tenth round of their iterated game, both \textbf{A}
and \textbf{B} are able to study the results of the previous nine rounds.


\subsection*{An Analysis of a Simple Game Matrix}

The game depicted in Figure 1 is a particularly easy one to analyze.
Let's examine the situation from Player \textbf{A}'s point of view
(Player \textbf{B}'s point of view is identical):

``Suppose \textbf{B} cooperates. Then I do better by cooperating
myself (I receive five points instead of three). On the other
hand, suppose \textbf{B} defects. I still do better by cooperating
(since I get two points instead of one). So no matter what
\textbf{B} does, I am better off cooperating.''

Player \textbf{B} will, of course, reason the same way, and both will
choose to cooperate. In the terminology of game theory, both \textbf{A}
and \textbf{B} have a \emph{dominant} choice---i.e., a choice that gives
a preferred outcome no matter what the other player chooses to do.
Figure 1, by the way, does \emph{not} represent a prisoner's dilemma
situation, since when both players make their dominant choice, they
also both achieve their highest personal scores.  We'll see an example
of a prisoner's dilemma game very shortly.

To recap: in any particular game using the matrix of Figure 1, we
would expect both players to cooperate; and in an iterated game, we would
expect both players to cooperate repeatedly, on every round.

\subsection*{The Prisoner's Dilemma Game Matrix}

Now consider the game matrix shown in Figure 2.

\begin{center}
\begin{tabular}{c|c|c|}
             & B cooperates   & B defects  \\
\cline{2-3}
A cooperates & A gets 3       & A gets 0   \\
             & B gets 3       & B gets 5   \\
\cline{2-3}
A defects    & A gets 5       & A gets 1 \\
             & B gets 0       & B gets 1 \\
\cline{2-3}
\end{tabular}
\end{center}

\centerline{\emph{Figure 2:\/} Prisoner's Dilemma Game Matrix}

\smallskip

In this case, Players \textbf{A} and \textbf{B} both have a dominant
choice---namely, defection. No matter what Player \textbf{B} does,
Player \textbf{A} improves his own score by defecting, and vice versa.

However, there is something odd about this game. It seems as though
the two players would benefit by choosing to cooperate. Instead of
winning only one point each, they could win three points each.  So the
``rational'' choice of mutual defection has a puzzling
self-destructive flavor.

The matrix of Figure 2 is an example of a prisoner's dilemma game
situation. Just to formalize the situation, let \emph{CC} be the number
of points won by each player when they both cooperate; let \emph{DD} be
the number of points won when both defect; let \emph{CD} be the number
of points won by the cooperating party when the other defects; and let
\emph{DC} be the number of points won by the defecting party when the
other cooperates. Then the prisoner's dilemma situation is
characterized by the following conditions:

\begin{eqnarray*}
DC > CC > DD > CD \\
CC > (DC + CD) / 2
\end{eqnarray*}

In the game matrix of Figure 2, we have:

\begin{eqnarray*}
DC = 5 \\
CC = 3 \\
DD = 1 \\
CD = 0
\end{eqnarray*}

\noindent so both conditions are met. In the Bonnie and Clyde story,
by the way, you can verify that:

\begin{eqnarray*}
DC = 0 \\
CC = -1 \\
DD = -10 \\
CD = -20
\end{eqnarray*}


\noindent Again, these values satisfy the prisoner's dilemma conditions.

\section*{Axelrod's Tournament}

In the late 1970's, political scientist Robert Axelrod held a computer
tournament designed to investigate the prisoner's dilemma
situation.\footnote{Actually, there were two tournaments. Their rules
and results are described in Axelrod's book {\sl The Evolution of
Cooperation}.} Contestants in the tournament submitted computer
programs that would compete in an iterated prisoner's dilemma game of
approximately two hundred rounds, using the same matrix shown in
Figure 2. Each contestant's program played five iterated games against
each of the other programs submitted, and after all games had been
played the scores were tallied.

The contestants in Axelrod's tournament included professors of
political science, mathematics, psychology, computer science, and
economics. The winning program---the program with the highest
average score---was submitted by Anatol Rapoport, a professor of
psychology at the University of Toronto. In this problem set, we will
pursue Axelrod's investigations and make up our own Scheme programs to
play the iterated prisoner's dilemma game. The second (optional) part
of this problem set is itself an experiment in the spirit of Axelrod's
tournament: a contest of programs that play a \emph{three-person}
prisoner's dilemma game.

Before we look at the two-player program, it is worth speculating on
what possible strategies might be employed in the iterated prisoner's
dilemma game. Here are some examples:

\begin{description}

\item[All-Defect]
A program using the \textbf{all-defect} strategy simply defects on
every round of every game.

\item[Poor-Trusting-Fool]
A program using the \textbf{poor-trusting-fool} strategy cooperates
on every round of every game.

\item[Random]
This program cooperates or defects on a random basis.

\item[Go-by-Majority]
This program cooperates on the first round. On all subsequent rounds,
\textbf{go-by-majority} examines the history of the other player's
actions, counting the total number of defections and cooperations by
the other player. If the other player's defections outnumber her
cooperations, \textbf{go-by-majority} will defect; otherwise this
strategy will cooperate.

\item[Tit-for-Tat]
This program cooperates on the first round, and then on every subsequent
round it mimics the other player's previous move. Thus, if the other
player cooperates (defects) on the $n$th round, then \textbf{tit-for-tat}
will cooperate (defect) on the $(n + 1)$th round.
\end{description}

All of these strategies are extremely simple. (Indeed, the first three
do not even pay any attention to the other player; their responses are
uninfluenced by the previous rounds of the game.)  Nevertheless,
simplicity is not necessarily a disadvantage.  Rapoport's first-prize
program employed the \textbf{tit-for-tat} strategy, and achieved the
highest average score in a field of far more complicated programs.


\section*{The Two-Player Prisoner's Dilemma Program}

\smallskip

A Scheme program for an iterated prisoner's dilemma game is shown at
the end of this problem set. The procedure \texttt{play-loop} pits two
players (or, to be more precise, two ``strategies'') against one another
for approximately 100 games, then prints out the scores for each of
the two players.

Player strategies are represented as procedures. Each strategy takes
two inputs---its own ``history'' (that is, a list of all of its
previous ``plays'') and its opponent's ``history.'' The strategy
returns either the symbol \texttt{c} (for ``cooperate'') or the symbol
\texttt{d} (for ``defect'').

At the beginning of an iterated game, each history is an empty list.
As the game progresses, the histories grow (via \texttt{extend-history})
into lists of \texttt{c}'s and \texttt{d}'s. Note how each strategy must
have its \emph{own} history as its first input. So in
\texttt{play-loop-iter}, \texttt{strat0} has \texttt{history0} as its
first input, and \texttt{strat1} has \texttt{history1} as its first
input.

The values from the game matrix are stored in a list named
\texttt{*game-association-list*}. This list is used to calculate the scores at
the end of the iterated game.

Some sample strategies are given at the end of the program. \texttt{
All-defect} and \texttt{poor-trusting-fool} are particularly simple; each
returns a constant value regardless of the histories. \texttt{
Random-strategy} also ignores the histories and chooses randomly
between cooperation and defection. You should study \texttt{
go-by-majority} and \texttt{tit-for-tat} to see that their behavior is
consistent with the descriptions in the previous section.

\paragraph{Practice Problem 0 (no write-up necessary)}
Do this one just for practice and understanding of the concepts in
Prisoner's Dilemma. Do not hand in anything for Practice Problem
0. Use \texttt{play-loop} to play games among the five defined
strategies. Play each strategy against itself (since two different
players may use the same strategy), as well as playing against the
other strategies. Notice how a strategy's performance varies sharply
depending on its opponent.  For example, \texttt{poor-trusting-fool}
does quite well against \texttt{tit-for-tat} or against another
\texttt{poor-trusting-fool}, but it loses badly to
\texttt{all-defect}. Pay special attention to
\texttt{tit-for-tat}. Notice how it never beats its opponent---but it
never loses badly.

\paragraph{Problem 1}
Write a new strategy \texttt{tit-for-two-tats}. The strategy should always
cooperate unless the opponent defected on both of the previous two
rounds. (Looked at another way: \texttt{tit-for-two-tats} should cooperate if
the opponent cooperated on either of the previous two rounds.) Play
\texttt{tit-for-two-tats} against other strategies, and against
itself.

\paragraph{Problem 2}
Write a procedure \texttt{make-tit-for-n-tats}. This procedure should
take a number as input and return the appropriate
\texttt{tit-for-tat}-like strategy. For example,
\texttt{(make-tit-for-n-tats 2)} should return a strategy equivalent
to \texttt{tit-for-two-tats}. Remember, a ``strategy'' is a procedure, 
so the value returned by \texttt{(make-tit-for-n-tats \emph{n})} is a
procedure, given by a \texttt{lambda} expression.

\paragraph{Problem 3}\ \\
\emph{a.} Write a procedure \texttt{make-dual-strategy} which takes as
input two strategies (say, \texttt{strat0} and \texttt{strat1}) and an
integer (say, \texttt{switch-point}). \texttt{Make-dual-strategy}
should return a strategy which plays \texttt{strat0} for the first
\texttt{switch-point} rounds in the iterated game, then switches to
\texttt{strat1} for the remaining rounds.

\emph{b.} Use \texttt{make-dual-strategy} to define a procedure
\texttt{make-triple-strategy} which takes as input three strategies
and two switch points.

\paragraph{Problem 4}
Write a procedure \texttt{niceify}, which takes as input a strategy (say,
\texttt{strat}) and a number between 0 and 1 (call it \texttt{
niceness-factor}). The \texttt{niceify} procedure should return a
strategy that plays the same as \texttt{strat} except: when \texttt{strat}
defects, the new strategy should have a \texttt{niceness-factor}
chance of cooperating.  (If \texttt{niceness-factor} is 0, the returned
strategy is exactly the same as \texttt{strat}; if \texttt{niceness-factor}
is 1, the returned strategy is the same as \texttt{poor-trusting-fool}.)

Use \texttt{niceify} with a low value for \texttt{niceness-factor}---say,
0.1---to create two new strategies: \texttt{slightly-nice-all-defect}
and \texttt{slightly-nice-tit-for-tat}.

\section*{The Three-Player Prisoner's Dilemma}

So far, all of our prisoner's dilemma examples have involved two
players (and, indeed, most game-theory research on the prisoner's
dilemma has focused on two-player games). But it is possible to create
a prisoner's dilemma game involving three---or even more---players.

Strategies from the two-player game do not necessarily extend to a
three-person game in a natural way. For example, what does \texttt{
tit-for-tat} mean? Should the player defect if \emph{either} of the
opponents defected on the previous round? Or only if \emph{both}
opponents defected? And are either of these strategies nearly as
effective in the three-player game as \texttt{tit-for-tat} is in the
two-player game?

Before we analyze the three-player game more closely, we must
introduce some notation for representing the payoffs. We use a
notation similar to that used for the two-player game. For example, we
let DCC represent the payoff to a defecting player if both opponents
cooperate. Note that the first position represents the player under
consideration. The second and third positions represent the opponents.

Another example: CCD represents the payoff to a cooperating player if
one opponent cooperates and the other opponent defects.  Since we
assume a symmetric game matrix, CCD could be written as CDC. The
choice is arbitrary.

\smallskip

Now we are ready to discuss the payoffs for the three-player game. We
impose three rules:\footnote{Actually, there is no universal
definition for the multi-player prisoner's dilemma. The constraints
used here represent one possible version of the three-player
prisoner's dilemma.}

\smallskip

\noindent 1) Defection should be the dominant choice for each player.
In other words, it should always better for a player to defect,
regardless what the opponents do. This rule gives three constraints:


\begin{eqnarray*}
DCC > CCC  & {\rm (both\ opponents\ cooperate)}\\
DDD > CDD  & {\rm (both\ opponents\ defect)}\\
DCD > CCD  & {\rm (one\ opponent\ cooperates,\ one\ defects)}
\end{eqnarray*}

\smallskip

\noindent 2) A player should always be better off if more of his
opponents choose to cooperate. This rule gives:

\begin{eqnarray*}
DCC > DCD > DDD \\
CCC > CCD > CDD
\end{eqnarray*}

\smallskip

\noindent 3) If one player's choice is fixed, the other two players should be
left in a two-player prisoner's dilemma. This rule gives the following
constraints: 

\begin{eqnarray*}
CCD > DDD \\
CCC > DCD \\
CCD > (CDD + DCD) / 2 \\
CCC > (CCD + DCC) / 2
\end{eqnarray*}
\pagebreak
\begin{eqnarray*}
CDD = 0 \\
DDD = 1 \\
CCD = 3 \\
DCD = 5 \\
CCC = 7 \\
DCC = 9
\end{eqnarray*}

\paragraph{Problem 5}
Revise the Scheme code for the two-player game to make a three-player
iterated game. The program should take three strategies as input, keep
track of three histories, and print out results for three players. You
need to change only three procedures: \texttt{play-loop},
\texttt{print-out-results}, and \texttt{get-scores}. Give your revised 
procedures the new names \texttt{play3-loop},
\texttt{print-out-results3}, and \texttt{get-scores3} You also need to 
replace \texttt{*game-association-list*} by
\texttt{*game3-association-list*} as follows:

{\ttfamily
\begin{verbatim}
(define *game3-association-list*
  '(((c c c) (7 7 7))
    ((c c d) (3 3 9))
    ((c d c) (3 9 3))
    ((d c c) (9 3 3))
    ((c d d) (0 5 5))
    ((d c d) (5 0 5))
    ((d d c) (5 5 0))
    ((d d d) (1 1 1))))
\end{verbatim}
}

\paragraph{Problem 6}
\emph{a.} Write strategies \texttt{poor-trusting-fool-3},
\texttt{all-defect-3}, and \texttt{random-strategy-3} that will work
in a three-player game. Try them out to make sure your
game-supervision code is working.

\emph{b.} Write two new strategies: \texttt{tough-tit-for-tat} and
\texttt{soft-tit-for-tat}. \texttt{tough-tit-for-tat} should defect if
\emph{either} of the opponents defected on the previous round.
\texttt{soft-tit-for-tat} should defect only if \emph{both} opponents
defected on the previous round. Play some games using these two new
strategies.

\paragraph{Problem 7}
A natural idea in creating a prisoner's dilemma strategy is to
try and deduce what kind of strategies the \emph{other} players might
be using. In this problem, we will implement a simple version of
this idea.

First, we need a procedure that takes three histories as arguments:
call them \texttt{hist-0}, \texttt{hist-1}, and \texttt{hist-2}. The idea is
that we wish to characterize the strategy of the player responsible
for \texttt{hist-0}. Our procedure will return a list of three numbers:
the probability that the \texttt{hist-0} player cooperates given that the
other two players cooperated on the previous round, the probability
that the \texttt{hist-0} player cooperates given that only one other
player cooperated on the previous round, and the probability that the
\texttt{hist-0} player cooperates given that both others defected on the
previous round. To fill out some details in this picture, let's look
at a couple of examples. We will call our procedure \texttt{
get-probability-of-c}; here are a couple of sample calls.

{\ttfamily
\begin{verbatim}
> (get-probability-of-c '(c c c c) '(d d d c) '(d d c c))
(1 1 1)

> (get-probability-of-c '(c c c d c) '(d c d d c) '(d c c c c))
(0.5 1 ())
\end{verbatim}
}

In the top example, the returned list indicates that the first player
cooperates with probability 1 no matter what the other two players do.
In the bottom example, the first player cooperates with probability
0.5 when the other two players cooperate; the first player cooperates
with probability 1 when one of the other two players defects; and
since we have no data regarding what happens when both other players
defect, our procedure returns \texttt{()} for that case.

Write the \texttt{get-probability-of-c} procedure. Using this procedure,
you should be able to write some predicate procedures that help
in deciphering another player's strategy. For instance, here are
two possibilities:

{\ttfamily
\begin{verbatim}
(define (is-he-a-fool? hist0 hist1 hist2)
  (equal? '(1 1 1) (get-probability-of-c hist0 hist1 hist2)))

(define (could-he-be-a-fool? hist0 hist1 hist2)
  (equal? (list true true true)
          (map (lambda (elt) (or (null? elt) (= elt 1)))
               (get-probability-of-c hist0 hist1 hist2))))
\end{verbatim}
}

Use the \texttt{get-probability-of-c} procedure to write a predicate that
tests whether another player is using the \texttt{soft-tit-for-tat}
strategy from Problem 7. Also, write a new strategy named \texttt{
dont-tolerate-fools}.  This strategy should cooperate for the first
ten rounds; on subsequent rounds it checks (on each round) to see
whether the other players might both be playing \texttt{
poor-trusting-fool}.  If our strategy finds that both other players
seem to be cooperating uniformly, it defects; otherwise, it
cooperates.

\paragraph{Problem 8}
Write a procedure \texttt{make-combined-strategies} which takes as input
two \emph{two-player} strategies and a ``combining'' procedure.  \texttt{
Make-combined-strategies} should return a \emph{three-player} strategy
that plays one of the two-player strategies against one of the
opponents, and the other two-player strategy against the other
opponent, then calls the ``combining'' procedure on the two two-player
results. Here's an example: this call to \texttt{
make-combined-strategies} returns a strategy equivalent to \texttt{
tough-tit-for-tat} in Problem 7.

{\ttfamily
\begin{verbatim}
(make-combined-strategies
  tit-for-tat tit-for-tat
  (lambda (r1 r2) (if (or (equal? r1 'd) (equal? r2 'd)) 'd 'c)))
\end{verbatim}
}

The resulting strategy plays \texttt{tit-for-tat} against each
opponent, and then calls the combining procedure on the two results.
If either of the two two-player strategies has returned \texttt{d}, then
the three-player strategy will also return \texttt{d}.

Here's another example. This call to \texttt{make-combined-strategies}
returns a three-player strategy that plays \texttt{tit-for-tat} against
one opponent, \texttt{go-by-majority} against another, and chooses randomly
between the two results:

{\ttfamily
\begin{verbatim}
(make-combined-strategies
  tit-for-tat go-by-majority
  (lambda (r1 r2) (if (= (random 2) 0) r1 r2)))
\end{verbatim}
}

\section*{Extra Credit: The Three-Player Prisoner's Dilemma Tournament}

As decribed earlier, Axelrod held two computer tournaments to
investigate the two-player prisoner's dilemma. This year we are going
to hold a three-player tournament. Past three-player tournament
results have indicated that basically cooperative strategies do very
well. In one tournament, for instance, the winning strategy defected
only if both opponents had each defected twice in a row. And the third
place strategy (out of more than fifty entries) was simply
\texttt{poor-trusting-fool-3}!

You can participate this year by designing a strategy for the
tournament. You might submit one of the strategies developed in the
problem set, or develop a new one. The only restriction is that the
strategy must work against any other legitimate entry. Any strategies
that cause the tournament software to crash will be
disqualified. Include a comment at the beginning of your submission
containing your name, a brief mnemonic name for your strategy, and a
short paragraph (2-4 sentences) explaining why you chose the
strategy. You may choose a strategy in hopes that it wins, or just
because its behavior is interesting in some way (e.g., you might try
to sabotage one of the known strategies).

\section*{The Game Supervision Code}

A printed copy of the game supervision code is attached below. This
code is also in the file
{\ttfamily
\begin{verbatim}
MacLab Resources:Courses:Autumn 1998:CS105:Prisoner:prisoner.scm
\end{verbatim}
}
on the \emph{Johnny Three} server.

\setlength{\textheight}{8in}
\setlength{\topmargin}{0in}

\pagebreak

{\small

{\ttfamily
\begin{verbatim}
;;; Code for Prisoner's Dilemma.

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;
;;  The PLAY-LOOP procedure takes as its arguments two prisoner's 
;;  dilemma strategies, and plays an iterated game of approximately
;;  one hundred rounds. A strategy is a procedure that takes
;;  two arguments: a history of the player's previous plays and 
;;  a history of the other player's previous plays. The procedure 
;;  returns either the symbol C (for "cooperate") or D ("defect").
;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

(define (play-loop strat0 strat1)
  (define (play-loop-iter strat0 strat1 count history0 history1 limit)
    (cond ((= count limit) (print-out-results history0 history1 limit))
          (else (let ((result0 (strat0 history0 history1))
                      (result1 (strat1 history1 history0)))
                  (play-loop-iter strat0 strat1 (+ 1 count)
                                  (extend-history result0 history0)
                                  (extend-history result1 history1)
                                  limit)))))
  (play-loop-iter strat0 strat1 0 '() '() (+ 90 (random 21))))


;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;
;; The following procedures are used to compute and
;; print out the players' scores at the end of an
;; iterated game.
;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

(define (print-out-results history0 history1 number-of-games)
  (let ((scores (get-scores history0 history1)))
    (newline)
    (display "Player 1 Score: ")
    (display (/ (car scores) number-of-games))
    (newline)
    (display "Player 2 Score: ")
    (display (/ (cadr scores) number-of-games))
    (newline)))
\end{verbatim}
}

\pagebreak

{\ttfamily
\begin{verbatim}
(define (get-scores history0 history1)
  (define (get-scores-helper history0 history1 score0 score1)
    (cond ((empty-history? history0) (list score0 score1))
          (else (let ((game (make-game (most-recent-play history0)
                                       (most-recent-play history1))))
                  (get-scores-helper (rest-of-plays history0)
                                     (rest-of-plays history1)
                                     (+ (get-player-points 0 game) score0)
                                     (+ (get-player-points 1 game) score1))))))
  (get-scores-helper history0 history1 0 0))

(define (get-player-points num game)
  (list-ref (get-point-list game) num))

(define (get-point-list game)
  (cadr (assoc game *game-association-list*)))
  

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;
;; This list provides the "game matrix". It is used
;; by the scorekeeping procedures above.
;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

(define *game-association-list*
  '(((c c) (3 3))
    ((c d) (0 5))
    ((d c) (5 0))
    ((d d) (1 1))))
  

;; Some selectors and constructors

(define make-game list)


(define extend-history cons)
(define empty-history? null?)

(define most-recent-play car)
(define rest-of-plays cdr)
\end{verbatim}
}

\pagebreak

{\ttfamily
\begin{verbatim}
;; A sampler of strategies

(define (all-defect my-history other-history)
  'd)

(define (poor-trusting-fool my-history other-history)
  'c)

(define (random-strategy my-history other-history)
  (if (= (random 2) 0) 'c 'd))

(define (go-by-majority my-history other-history)
  (define (count-instances-of symbol hist)
    (cond ((empty-history? hist) 0)
          ((equal? (most-recent-play hist) symbol)
           (+ 1 (count-instances-of symbol (rest-of-plays hist))))
          (else (count-instances-of symbol (rest-of-plays hist)))))
  (let ((ds (count-instances-of 'd other-history))
        (cs (count-instances-of 'c other-history)))
    (if (> ds cs) 'd 'c)))


(define (tit-for-tat my-history other-history)
  (if (empty-history? my-history)
      'c
      (most-recent-play other-history)))


;;; other possibly useful procedures

(define (get-nth-from-last-play n history)
  (list-ref history n))

(define (get-players-action player-no game)
  (list-ref game player-no))

(define (get-nth-from-last-game n my-history other-history)
  (make-game (get-nth-from-last-play n my-history)
             (get-nth-from-last-play n other-history)))
\end{verbatim}
}

}

\end{document}