\documentstyle[noweb]{article}
\begin{document}
\filename{prisoners-dilemma.nw}
\begindocs{0}
% -*- LaTeX -*- @(#) $Header: /home/bambam/leavens/src/c++/prisoners/RCS/prisoners-dilemma.nw,v 1.1 1993/04/29 15:56:08 leavens Exp leavens $

\title{Cooperation: The Prisoner's Dilemma}
\author{Gary T. Leavens\thanks{This work is supported in part
by the National Science Foundation under the Grant CCR-9108654.}\\
Department of Computer Science, 229 Atanasoff Hall\\
Iowa State University, Ames, Iowa 50011-1040 USA\\
leavens@cs.iastate.edu}
\date{\today}
\maketitle

\section{The Prisoner's Dilemma}

The iterated prisoner's dilemma is described in Douglas
Hofstadeter's book
{\em Metamagical Themas: Questing for the essence of mind and pattern\/}
(Basic Books, New York, 1985), chapter 29,
and more fully in Robert Axelrod's book
{\em The Evolution of Cooperation\/}
(Basic Books, New York, 1984).
In a prisoner's dilemma, two prisoners can each choose to either
cooperate or defect.
If both cooperate, they are rewarded by a payoff $R$.
If both defect their reward is smaller, the punishment $P$.
If one cooperates and the other defects, the defector gets
the temptation $T$, while cooperator gets the sucker's payoff $S$.
The conditions for a prisoner's dilemma are that
\begin{eqnarray}
& T > R > P > S \\
& (T+S)/2 < R
\end{eqnarray}
The second condition ensures that alternating cooperation and defection
makes the payoffs smaller than continual cooperation.

The iterated prisoner's dilemma is like the prisoner's dilemma,
only repeated over many encounters.

\enddocs
\begindocs{1}

\section{The Program}

The program is divided into several files.
The file {\tt main.C} holds the main program.
This program uses an instance of the class \code{}World\edoc{}
to do the real work.
After running the example tournament, the results are printed.
\enddocs
\begincode{2}
\moddef{main.C}\endmoddef
#include "World.h"
main() \{
  \LA{}create the \code{}World\edoc{} instance \code{}w\edoc{}\RA{}
  w->example();
  w->print_results(cout);
  return(0);
\}

\endcode
\begindocs{3}

To allow maximum flexibility in coding and debugging,
the creation of the world is handled by a separate function.
This allows derived classes of \code{}World\edoc{} to be used
without changing the main program.
\enddocs
\begincode{4}
\moddef{create the \code{}World\edoc{} instance \code{}w\edoc{}}\endmoddef
  extern World *WorldMaker();
  World* w = WorldMaker();

\endcode
\begindocs{5}

\section{Worlds}

\subsection{Class World}

The class \code{}World\edoc{} is an abstract base class
that describes the protocol that worlds must follow to be used
by the main program.
Its interface is described in the file {\tt World.h}.
Objects of class \code{}World\edoc{} are collections of prisoners.
A world is responsible for playing the prisoners against each other
according to the rules of the dilemma (the member function \code{}example\edoc{}),
and for printing itself on an \code{}ostream\edoc{}.

\enddocs
\begincode{6}
\moddef{World.h}\endmoddef
#if !defined(_WORLD_H)
#define _WORLD_H

#include <iostream.h>
#include "Prisoner.h"

class World \{
public:
  virtual void example(int numRounds = 20) = 0;
    // MODIFIES: *this
    // EFFECT: run the prisoner's dilemma for numRounds rounds.
  virtual void print_results(ostream& o) = 0;
    // MODIFIES: o
    // EFFECT: Write a printed representation for the results
    // of w's tournament on o.
protected:
  void play_against(Prisoner* fst, Prisoner* snd, int numRounds) \{
    // MODIFIES: *fst, *snd
    // EFFECT: play *fst against *snd for numRounds
    // newRound really means ``new partner''
    fst->newRound();   // These were fixed.
    snd->newRound();
    for (int i = 1; i <= numRounds; i++) \{
      one_round(fst, snd);
    \}
  \}
  virtual void one_round(Prisoner* fst, Prisoner* snd);
    // MODIFIES: *fst, *snd
    // EFFECT: play *fst against *snd for numRounds
\};
#endif

\endcode
\begindocs{7}

The file \code{}World.C\edoc{} contains the implementation of the \code{}one_round\edoc{}
member function of World.  Both prisoners are asked for their decisions,
and then both are informed of the choices.
A prisoner does not have to remember its own choice.
\enddocs
\begincode{8}
\moddef{World.C}\endmoddef
#include "World.h"

void World::one_round(Prisoner* fst, Prisoner* snd) \{
  Decision fsts, snds;
  fsts = fst->decide();
  snds = snd->decide();
  fst->yours_others(fsts, snds);
  snd->yours_others(snds, fsts);
\}

\endcode
\begindocs{9}

\subsection{WorldMaker}

The function \code{}WorldMaker\edoc{} is placed in a separate file.
This allows derived classes of the class \code{}World\edoc{} to be used.
This version of \code{}WorldMaker\edoc{} uses the the class \code{}StdWorld\edoc{}.
The header file {\tt StdWorld.h} itself includes the header file {\tt World.h},
so the latter need not be included here.

\enddocs
\begincode{10}
\moddef{WorldMaker.C}\endmoddef
#include "StdWorld.h"
#include "PrisonerTypes.h"

\LA{}addTwice macro definition\RA{}

World * WorldMaker()
\{
  StdWorld *w = new StdWorld;
  \LA{}add a bunch of Prisoners to the world\RA{}
  return(w);
\}

\endcode
\begindocs{11}

Each kind of prisoner is added to the world twice,
so that its strategy can be played against itself.
Since prisoners may be confused if they are playing against themselves,
it will not do to add the same prisoner object twice.
What has to be done is to create each strategy twice.
The following definition helps with this task,
as it creates two new objects of the same strategy.
It is a macro because in C++ classes are not first-class values.

\enddocs
\begincode{12}
\moddef{addTwice macro definition}\endmoddef
#define addTwice(strategy) \\
 \{ w->addPrisoner(new strategy); w->addPrisoner(new strategy); \}

\endcode
\begindocs{13}

In this version of the program, there are only two strategies
(types of prisoners).
\enddocs
\begincode{14}
\moddef{add a bunch of Prisoners to the world}\endmoddef
  addTwice(AllC);
  addTwice(AllD);

\endcode
\begindocs{15}

\subsection{The Standard World}

The standard world is a collection of prisoners (strategies).
Derived classes of \code{}World\edoc{} might allow tracing, or evolution, etc.

\enddocs
\begindocs{16}

The interface of \code{}StdWorld\edoc{} is derived from \code{}World\edoc{}.
The member functions \code{}example\edoc{} and \code{}print_results\edoc{} need to be redefined,
because they are not pure virtual in StdWorld, but will be implemented.
The \code{}StdWorld\edoc{} class also provides the \code{}addPrisoner\edoc{} member function;
this is not in the interface of \code{}World\edoc{} because the main program
does not need to know about it.  However, it is needed by \code{}WorldMaker\edoc{}.

\enddocs
\begincode{17}
\moddef{StdWorld.h}\endmoddef
#if !defined(_STDWORLD_H)
#define _STDWORLD_H

#include "World.h"
\LA{}\code{}StdWorld\edoc{} representation's include files\RA{}

class StdWorld : public World \{
public:
  StdWorld()
    // CONSTRUCTS: *this
    // EFFECT: initialize *this to have no prisoners.
    : contestants() \{\}
  virtual void addPrisoner(Prisoner* p);
     // MODIFIES: *this
     // EFFECT: add p to this world.
  void example(int numRounds);
  void print_results(ostream& o);
\LA{}\code{}StdWorld\edoc{}'s protected and private parts\RA{}
\};
#endif

\endcode
\begindocs{18}


The world keeps track of a list of Prisoners.
A list is better than an array or some other static structure,
since the \code{}addPrisoner\edoc{} operation must be able to add Prisoners dynamically.

We use an implementation of lists from a
``Library of Efficient Data Types and Algorithms'' (LEDA) by Stefan N\"{a}her
(available by anonymous ftp from ftp.uni-sb.de).
The inclusion of the LEDA header file \code{}<LEDA/list.h>\edoc{} makes the lists
from LEDA available.
The \code{}typedef\edoc{} makes it easier to refer to a list of pointers to prisoners.
The list is not actually a list of prisoners,
so that objects of several derived classes of prisoners can be included
in the list.

\enddocs
\begincode{19}
\moddef{\code{}StdWorld\edoc{} representation's include files}\endmoddef
#include "Prisoner.h"
#include <LEDA/list.h>
typedef list<Prisoner *> PrisonerList;


\endcode
\begincode{20}
\moddef{\code{}StdWorld\edoc{}'s protected and private parts}\endmoddef
private:
   PrisonerList contestants;

\endcode
\begindocs{21}

The file {\tt StdWorld.C} contains the implementation of the standard world.
\enddocs
\begincode{22}
\moddef{StdWorld.C}\endmoddef
#include "StdWorld.h"

\LA{}\code{}StdWorld\edoc{}'s \code{}addPrisoner\edoc{} member function\RA{}
\LA{}\code{}StdWorld\edoc{}'s \code{}example\edoc{} member function\RA{}
\LA{}\code{}StdWorld\edoc{}'s \code{}print_results\edoc{} member function\RA{}

\endcode
\begindocs{23}

The \code{}addPrisoner\edoc{} member function simply delegates
to the \code{}contestants\edoc{} list member function \code{}append\edoc{}.
\enddocs
\begincode{24}
\moddef{\code{}StdWorld\edoc{}'s \code{}addPrisoner\edoc{} member function}\endmoddef
void StdWorld::addPrisoner(Prisoner* p)
\{
  contestants.append(p);
\}

\endcode
\begindocs{25}

The member function \code{}example\edoc{} must run the tournament.
The \code{}forall_items\edoc{} macro is defined by LEDA do the body (in \code{}\{\}\edoc{})
for each \code{}list_item\edoc{} in the list of contestants, with the \code{}list_item\edoc{}
assigned to the variable \code{}fst\edoc{}.
The member function \code{}inf\edoc{} for lists gets the information
(in this case a pointer of type \code{}Prisoner*\edoc{}) from a \code{}list_item\edoc{}.
\enddocs
\begincode{26}
\moddef{\code{}StdWorld\edoc{}'s \code{}example\edoc{} member function}\endmoddef
void StdWorld::example(int numRounds = 20)
\{
  list_item fst, snd;
  forall_items(fst, contestants) \{
    for (snd = contestants.succ(fst); snd ; snd = contestants.succ(snd)) \{
      play_against(contestants.inf(fst), contestants.inf(snd), numRounds);
    \}
  \}
\}

\endcode
\begindocs{27}

The \code{}forall\edoc{} macro is also defined by LEDA.
\enddocs
\begincode{28}
\moddef{\code{}StdWorld\edoc{}'s \code{}print_results\edoc{} member function}\endmoddef
void StdWorld::print_results(ostream& o)
\{
  Prisoner* p;
  forall(p, contestants) \{
    p->print_results(o);
  \}
\}


\endcode
\begindocs{29}

\section{Decisions}

A decision is either to cooperate or defect.
This is represented by an enumeration type.
The \code{}payoffFor\edoc{} function returns the payoff

\enddocs
\begincode{30}
\moddef{Decision.h}\endmoddef
#if !defined(_DECISION_H)
#define _DECISION_H

enum Decision \{cooperate = 0, defect = 1\};

extern int payoffFor(Decision mine, Decision yours);
    // EFFECT: return the payoff for me if I decided mine and you yours.
#endif

\endcode
\begindocs{31}

The actual payoff matrix is kept in a static variable, so it is local
to the file {\tt Decision.C}.
\enddocs
\begincode{32}
\moddef{Decision.C}\endmoddef
#include "Decision.h"

static int payoffs[2][2] = \{ \{-1, -5\}, \{0, -3\}\};

int payoffFor(Decision mine, Decision yours)
\{
  return(payoffs[mine][yours]);
\}

\endcode
\begindocs{33}

\section{Prisoners}

The header file \code{}Prisoner.h\edoc{} contains the definition of the abstract base
class \code{}Prisoner\edoc{}.
All types of prisoners will be defined as subtypes of this type.
To define a subtype, one must, at a minimum, redefine the pure virtual
member functions \code{}newRound\edoc{}, \code{}decide\edoc{}, and \code{}name\edoc{}.
\enddocs
\begincode{34}
\moddef{Prisoner.h}\endmoddef
#if !defined(_PRISONER_H)
#define _PRISONER_H
#include <iostream.h>
#include "Decision.h"

class Prisoner \{
public:
  virtual void newRound() = 0;
    // MODIFIES: *this
    // EFFECT: discard any history information,
    // as a new partner in the dilemma has arrived.
  virtual Decision decide() = 0;
    // MODIFIES: *this
    // EFFECT: decide whether to cooperate or defect.
  virtual void yours_others(Decision yours, Decision others) \{
    // MODIFIES: *this
    // EFFECT: record the winnings from this round.
    // You will need to override this to update any history variables.
    won += payoffFor(yours, others);
  \}
  virtual const char *name() const = 0;
    // EFFECT: return the name of this strategy
  int winnings() const \{
    // EFFECT: return this prisoner's winnings
    return won;
  \}
  virtual void print_results(ostream& o) const \{
    o << name() << " won " << winnings() << "\\n";
  \}
private:
  int won;  // perhaps ``years_in_jail'' would be better
\};
#endif

\endcode
\begindocs{35}

The header file {\tt PrisonerTypes.h}
collects the declarations of all the prisoners types.
Note that {\tt Prisoner.h} has to guard against being included several times.
In this version of the program there are only two types of prisoners.
\enddocs
\begincode{36}
\moddef{PrisonerTypes.h}\endmoddef
#include "Prisoner.h"
#include "AllC.h"
#include "AllD.h"

\endcode
\begindocs{37}

Prisoners of type \code{}AllC\edoc{} always cooperate.
\enddocs
\begincode{38}
\moddef{AllC.h}\endmoddef
#include "Prisoner.h"
class AllC : public Prisoner \{
public:
  void newRound() \{\}
  const char* name() const \{ return "AllC"; \}
  Decision decide() \{
    return cooperate;
  \}
\};

\endcode
\begindocs{39}

Prisoners of type \code{}AllC\edoc{} always cooperate.
\enddocs
\begincode{40}
\moddef{AllD.h}\endmoddef
#include "Prisoner.h"
class AllD : public Prisoner \{
public:
  void newRound() \{\}
  const char* name() const \{ return "AllD"; \}
  Decision decide() \{
    return defect;
  \}
\};


\endcode
\end{document}