Index of /courseware/cse3322/2005/A1

 Name                    Last modified       Size  Description

 Parent Directory        11-Oct-2006 10:29      -  
 game.sml                21-Jul-2005 15:44     2k  

CSE3322, 2005, SML Assignment 1, due 6pm Friday 5 August

The online copy is the reference document. Check it regularly -- Thursday, 22-Jun-2006 18:55:48 EST.

The Iterated Prisoner's Dilemma [1-5] is a well-known non-zero-sum game. It is also deceptively simple. There are only two moves: cooperate 'C', and defect 'D'. Moves are made simultaneously, in secret, and then revealed. The payoff function is

  fun payoff C C = 3
    | payoff D C = 5
    | payoff C D = 0
    | payoff D D = 1;

E.g. If player-1 moves 'D' and player-2 moves 'C' then player-1 gets 5 (and player-2 gets 0). The game is iterated over 'n' rounds.

(The game's origins are in a story of two suspects who are held by the police. If they cooperate with each other (not with the police) by keeping quiet, they each get a 2-year sentence. If one dobs the other in, the first goes free and the other gets a 5-year sentence. If they each dob the other in, they each get a 4-year sentence. The payoff function shows the reduction in sentence. Similar payoffs are thought to occur in various real-world situations. Key features are:  payoff D C > payoff C C,  payoff D D > payoff C D,  2*(payoff C C) > payoff D C + payoff C D.)

The game is thought to explain or to model aspects of some forms of altruistic behaviour between animals, and maybe even between people and nations.

The SML program 'game.sml' contains a 'playClean' function which plays two players against each other. It also contains three simple player strategies:

  fun good _ _ = C;     (* always cooperate *)

  fun bad  _ _ = D;        (* always defect *)

  fun mad _     (D::_) = D   (* mutually    *)
    | mad (D::_) _     = D   (* assured     *)
    | mad _      _     = C;  (* destruction *)

Each player function is given the past history as two parameters; the first is a 'Move list' of its own past moves and the second is a 'Move list' of its opponent's moves, both in reverse order from most recent to least recent.

Player 'good' always cooperates and 'bad' always' defects, regardless; they make no use of the history. 'mad' starts by cooperating, but if its opponent ever defects then mad defects on the next move and ever after.

If we play the three different strategies against one another, we see that bad beats good 500:0, good draws with mad 300:300, and bad beats mad, but only by a small margin, 104:99.

  - use "game.sml";
  ...

  - playClean 100 good bad;
  val it = (0,500) : int * int

  - playClean 100 good mad;
  val it = (300,300) : int * int

  - playClean 100 bad mad;
  val it = (104,99) : int * int

So it seems that bad is the best strategy.

But, in an environment with several copies of mad or similar strategies, they will gain 3*n points every time that they play each other, but bad will gain only n+4 points when it plays one of them. bad may beat each one of them individually but end up with the lowest total! Being more cooperative will win overall.

Now, the real world is not always clean! The 'play' function implements a "noisy" version of the game where a certain fraction, 'frac', of the moves are changed or "misunderstood" by the environment of the game's world. This has serious consequences for "reactive" players such as 'mad'.

Assignment 1

You must write some SML code. Put all of your code in a single file, 'a1.sml'. Do not change 'game.sml'. The first line of your file must contain, as a comment, your name (family name in upper case), student number, and monash email.

1. Write at least one new player function which uses the past history in some interesting and non-trivial way to play well, e.g. like mad but better.
   (Your function(s) must run "quickly" and must not be "extravagant" with memory -- so that it will be feasible to run it in a large tournament.)
   [1.5 marks]
2. 'play' your strategy v. bad, good and mad for frac=0.0, 0.02 and 0.1, and n=100 or more, more than once.
   Record the results and write a 1-page summary of them, explaining why players win or lose, as an SML comment, (*...*), immediately following your code in 'a1.sml'.
   [1.5 marks]
3. Write a new function 'playList frac n players', which accepts a list of players. It must:
   1. play every player against every other player for n rounds of the noisy game,
   2. eliminate the lowest scoring player,
   3. repeat (with initial scores reset to zero) until a single winner remains.
   What happens with, say, two goods, two bads, two mads and two of your players?
   [2 marks]
   [Total 5 marks]

We will use your code thus:

  - use "game.sml";
  - use "a1.sml";
  - playList <frac> <n> <some player list>;

and we might throw in some new players of our own.

Read 'Assessment' on the CSE3322 2005 home page; note 'late penalties' and 'extensions'. We are marking how well you use the functional programming paradigm, not only how well your code operates. You must write all of your code yourself. You can only use predefined functions if they are "top-level", i.e. not in special SML 'structures'. Use of "impure" non-functional features of SML, notably ref and :=, is not allowed.

Submission

If possible, get your assignment marked in a CSE3322 tutorial. In any case, submit your file 'a1.sml' electronically. Instructions will be posted later [above, 1/8/05].

References

[1] R. Axelrod. Effective choice in the prisoner's dilemma. J. Conflict Resolution, 24(1), pp.3-25, March 1980.

[2] R. Axelrod, W. D. Hamilton. The evolution of cooperation. Science, 211, pp.1390-1396, 1981.

[3] L. A. Dugatkin. Do guppies play tit for tat during predator inspection visits? Behavioral Ecology and Sociobiology, 23, pp.395-399, 1988.

[4] H. C. J. Godfray. The evolution of forgiveness. Nature, 355, pp.206-207, 1990.

[5] D. S. Wilson, L. A. Dugatkin. Nepotism vs tit for tat, or, why should you be nice to your rotten brother. Evol. Ecology, 5N, pp.291-299, 1991.