Assignment 2: Lisp / Prisoner's Dilemma

• Lisp problems
• IPD game rules
• Agent requirements
• Monitor requirements
• Deliverables
• Grading criteria
• Back to class website

1. Describe what happens when the following expressions are evaluated: (2 points)

a. (+ (- 5 1) (+ 3 7))
b. (list 1 (+ 2 3))
c. (if (listp 1) (+ 1 2) (+ 3 4))
d. (list (and (listp 3) t) (+ 1 2))



2. What do these functions do? (2 points)

a. (defun enigma (x) (and (not (null x)) (or (null (car x)) (enigma (cdr x)))))
b. (defun mystery (x y) (if (null y) nil (if (eql (car y) x) 0 (let ((z (mystery x (cdr y)))) (and z (+ z 1))))))


3. Write a recursive function zerosump(lis) that accepts a list of integers as input and returns T if any two of them add up to zero, and returns nil otherwise (2 points)

A round is a series of games where every participant plays a number of games. Each game is played one-on-one with each person taking a turn to make a move. A player (or agent) has only two choices in each turn: 'C' for cooperation and 'D' for defection. Agents are unaware of their opponents' move. The outcome of the turn is evaluated by the monitor program after both agents have produced their output. The monitor calculates the point assignment after each turn according to the following table:

P1/P2 payoff matrix

• Every time an agent plays (C or D) there's a F% chance that the player's hand is flipped (from C to D or vice versa). The chance of a flip occurring is calculated separately for each agent, for every turn. Thus it cannot be assumed that if an agent's hand is flipped this turn, the opponent's hand is also flipped this turn or that either will be more or less likely to be flipped later.

• The chance of being flipped (F) will decay linearly according to this formula: F = F₁ - (I)(M) where F₁ is the initial F value given to the monitor. I is the decay factor and M is the number of moves that have been played in the game by the agent.

• This means, the F number could be decreased by a constant factor, I, each turn. For example at the beginning: F=.25(25%) and I=.025. The chance of flipping on the first turn is 25%; on second turn it's 24.975%; on third turn it's 24.950%; etc.

• Each game consists of a number of turns. The number of turns is semi-randomly determined between Lmin and Lmax and is uniformly applied for all agents, each round.

• Each agent continues to accumulate points according to the payoff matrix throughout the game and carry over their points to the next round throughout the entire championship.

• Each round is really a round-robin tournament. That is, every agent plays every other agent once. At the end of the round, the agent with the lowest score is dropped. If there's a tie for the lowest score, then all agents with that score are dropped out of the tournament.

• This yields N-1 round-robins at most, where there are N agents participating.

• The championship continues until all agents are eliminated. The agent or agents (if there is a tie) eliminated last win. But for the purposes of our assignments, all agents in the top quartile receive the same amount of points. All ties and special circumstances are to be resolved at TA's discretion.

Lastname1Lastname2

where each Lastname is the last name of team members capitalized. If there's only one person in the team, then there will be only one Lastname. If there are more, then list them alphabetically.

The declaration for the agent function should be like the following example:

(defun Khosmood (hist)

....

)

• hist is a list of plays so far this game assuming the agent goes first:
  plays are (agent opponent) pairs, with the most recent play as the first item in the list.

example of an agent being called in a game that already has had 3 turns with the score of 10-5, the agent is leading over its opponent.

(Khosmood '((C D) (D C) (D C)) )

Such a call should return a move which will be played one at a time against an opponent. For example:

C

Your agent is not allowed permenant storage or any code outside the agent function. It should not access any global variables or any monitor functions/data, doing so will be grounds for disqualification. Your agent cannot take an excessive amount of time to respond. Any response of 1 second or longer given a 300 turn game disqualifies your agent. Your agent can't produce any debug output as this interferes with the monitor, so be sure to get rid of all side-affect output from your agent.

Internally the monitor has a responsibility of running some number of rounds. For each round a semi-random gameLength is used for all games in that round. And for each game, there are flipParams that determine the chance of random flips on each move. Within each round, the monitor passes the game history and score-thus-far to each pair of agents in each game and receives those agents' moves in order to calculate the winner and point assignments.

Declaration of the monitor is the following:

(defun monitor (flipParams gameLength agents)

...

)

• flipParams is a list of two items: '(F I)
  • F is the initial flip rate, the chance that each players move is flipped.
  • I is the increment of decay for F. If I is 0, then F remains the chance of flip for all turns in each game.
• gameLength is a list of two items: '(Lmin Lmax) that determine the upper and lower bounds for a random game length per round. (1 30) means all the games in the round have T turns, where T is a random number between 1 and 30 inclusive. (25 25) means that all games in the entire tournament will be of length 25 turns.
• agents is a list of defined agent functions who will be participating in this championship.

example of a monitor being called:

(monitor '(.25 .1) '(10 50) '(#'random #'titfortat #'bobs #'joes #'stoc #'coin #'janes #'dianefeinsteins #'chocalate #'cooperate))

• output: the monitor will output an ordered list of all agents, sorted by the order of elimination. The last member of the list is the agent that was eliminated first and the first member of the list is the winner of the tournament, unless the first few agents had the same score.

example 1: ( (agentx 300) (agenty 225) )

example 2: ( (agentx 575) (agenty 425) (agentz 225) )

• Answers to the lisp problems and your ipd agent must be sent by email
• Your ipd agent function must begin with a line of comment dashes ";---------------------", and another line of comment dashes must appear after the function.
• Provide brief 2-3 lines of comments about your agents algorithm
• emails must be sent in plaintext, no HTML or XML enhancements.
• emails must be sent from your cruzmail account
• email subjects must be "[CMPS 140 Assignment 2]", and the first line of the body must contain your full name and date.
• test all your functions on sbcl on the unix.ic machines before submitting
• email must be received by midnight of the due date (above)

• 6 points for the Lisp problems.
• 1 point if your ipd agent runs and returns the correct output format
• 1 point per tournament if your agent finishes in the 3rd quartile or better
• 1 point per tournament if your agent finishes in the 2nd quartile or better
• 1 point per tournament if your agent finishes in the 1st quartile
• 1 point maximum if your agent finishes as the top agent without ties in any tournament
• We will run two tournaments with different initial parameters, for a maximum theoretical score of 14 out of 10 points