The Two-Player Prisoner's Dilemma Program

A Scheme program for an iterated prisoner's dilemma game is shown at the end of this problem set. The procedure 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 c (for ``cooperate'') or the symbol d (for ``defect'').

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

The values from the game matrix are stored in a list named *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. All-defect and poor-trusting-fool are particularly simple; each returns a constant value regardless of the histories. Random-strategy also ignores the histories and chooses randomly between cooperation and defection. You should study go-by-majority and tit-for-tat to see that their behavior is consistent with the descriptions in the previous section.

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 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, poor-trusting-fool does quite well against tit-for-tat or against another poor-trusting-fool, but it loses badly to all-defect. Pay special attention to tit-for-tat. Notice how it never beats its opponent--but it never loses badly.

Problem 1

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

Problem 2

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

Problem 3

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

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

Problem 4

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

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