;;;======================================================================
;;; Two Player Prisoner's Dilemma in Scheme
;;;======================================================================
;;; This file is separated into four sections:
;;;
;;; +   Part I  : Choice histories
;;; +   Part II : Sample strategies discussed in assignment
;;; +   Part III: Functions for playing rounds
;;; +   Part IV : A sample 40-round match for reference
;;;
;;; Note that because of Part IV, when you load this file in Scheme it
;;; automatically plays a 40-round match and prints out the results.
;;;======================================================================

;;;======================================================================
;;; ------------------ Part I: Choice Histories -------------------------
;;;======================================================================
;;; As rounds are being played, each player's choices are accumulated
;;; in a "history."  In later rounds, a strategy can refer to its own
;;; or its opponent's history to decide on its next choice.  Basically,
;;; this choice history is stored as a plain list of 1's and -1's.  The
;;; most recent choice is first in the list, with the oldest at the rear.
;;;
;;; This data structure is so simple that most of the operations that
;;; manipulate history lists are simply renamings of basic list
;;; functions.  Giving them new names improves the readability of
;;; functions that manipulate histories, however.  This illustrates a
;;; common approach to data abstraction in Scheme.
;;;======================================================================

;------------------------------------------------------------------------
; the-empty-history
;------------------------------------------------------------------------
; This constant (or parameterless function) represents an empty history
; list.
;------------------------------------------------------------------------
(define the-empty-history '())


;------------------------------------------------------------------------
; empty-history? history
;------------------------------------------------------------------------
; This predicate (boolean-valued function) returns true if its argument
; is an empty history, and false otherwise.
;------------------------------------------------------------------------
(define empty-history? null?)


;------------------------------------------------------------------------
; extend-history new-choice old-history
;------------------------------------------------------------------------
; This function produces a new history list from old-history by adding
; new-choice to the front.
;------------------------------------------------------------------------
(define extend-history cons)


;------------------------------------------------------------------------
; most-recent-choice history
;------------------------------------------------------------------------
; This function returns the more recent choice from a history list.
;------------------------------------------------------------------------
(define most-recent-choice car)


;------------------------------------------------------------------------
; rest-of-choices history
;------------------------------------------------------------------------
; This function returns a list of all choices except the most recent.
;------------------------------------------------------------------------
(define rest-of-choices cdr)



;;;======================================================================
;;; ---------------- Part II: Sample Strategies -----------------------
;;;======================================================================
;;; A sampler of strategies, as described in the assignment.
;;;
;;; Any strategy for the two-player (or N-player) game is a function
;;; that takes two (or N) history lists as parameters, with "your"
;;; history as the first argument and the histories of opponents as the
;;; remaining arguments.  A strategy function should return 1 for
;;; cooperate and -1 for defect.
;;;======================================================================

;------------------------------------------------------------------------
; meanie-2P my-history other-history
;------------------------------------------------------------------------
; This strategy always defects.
;------------------------------------------------------------------------
(define (meanie-2P my-history other-history)
    -1
)


;------------------------------------------------------------------------
; sucker-2P my-history other-history
;------------------------------------------------------------------------
; This strategy always cooperates.
;------------------------------------------------------------------------
(define (sucker-2P my-history other-history)
    1
)


;------------------------------------------------------------------------
; spastic-2P my-history other-history
;------------------------------------------------------------------------
; This strategy randomly cooperates or defects with equal probability.
;------------------------------------------------------------------------
(define (spastic-2P my-history other-history)
    (if (= (random 2) 0)
	1
	-1
    )
)


;------------------------------------------------------------------------
; democratic-2P my-history other-history
;------------------------------------------------------------------------
; This strategy counts the opponent's choices and then makes the same
; choice that was most commonly made by the opponent.  If the opponent
; has made exactly the same number of defections and cooperations,
; then the strategy chooses to cooperate.
;------------------------------------------------------------------------
(define (democratic-2P my-history other-history)
    ; To compare choices, we can simply add all elements in the
    ; history and test against 0.  If you don't know what the reduce
    ; function does, you can look it up in the Scheme reference manual.
    (if (> 0 (reduce + 0 other-history))
	-1
	1
    )
)


;------------------------------------------------------------------------
; eye-for-eye-2P my-history other-history
;------------------------------------------------------------------------
; This strategy always does the same thing the opponent did in the last
; round.
;------------------------------------------------------------------------
(define (eye-for-eye-2P my-history other-history)
    (if (empty-history? my-history)
	1
	(most-recent-choice other-history)
    )
)



;;;======================================================================
;;; ------ Part III: Functions for Playing a Set of Rounds --------------
;;;======================================================================

;------------------------------------------------------------------------
; play-N-rounds-2P N strategy1 strategy2
;------------------------------------------------------------------------
; This is the main function for playing a set of rounds.  It repeatedly
; plays rounds between the given strategies, collecting history lists for
; each one.  It repeats the process for a total of N rounds.  It is built
; upon the play-N-more-rounds-2P function defined below.
;
; histories is a local variable that contains a list of history lists
; for the entire series of N rounds--one history list for each player.
;------------------------------------------------------------------------
(define (play-N-rounds-2P N strategy1 strategy2)
    ; First, compute the histories by playing N rounds
    (let ((histories (play-N-more-rounds-2P
			N
			strategy1 the-empty-history
			strategy2 the-empty-history
		     )))
	; Now report results
	(print-out-results-2P (first histories) (second histories) N)
    )
)


;------------------------------------------------------------------------
; play-N-more-rounds-2P N strategy1 history1 strategy2 history2
;------------------------------------------------------------------------
; This function takes two strategies and two associated histories.
; It plays N more rounds, extending the history lists.  It returns
; a list of two new (longer) histories as its result.
;------------------------------------------------------------------------
(define (play-N-more-rounds-2P N strategy1 history1 strategy2 history2)
    (cond
	((> N 0)
	 ; More rounds to play, so play one
	 (play-N-more-rounds-2P
	     (- N 1)
	     strategy1 (extend-history
			   ; Call strategy 1 with old histories
			   (strategy1 history1 history2)
			   ; Add result to old history
			   history1)
	     strategy2 (extend-history
			   ; Call strategy 2 with old histories
			   (strategy2 history2 history1)
			   ; Add result to old history
			   history2)
	 )
	)
	(else
	    ; otherwise, no more to play, so return histories unchanged
	    (list history1 history2)
	)
    )
)


;------------------------------------------------------------------------
; print-out-results-2P history1 history2 number-of-games
;------------------------------------------------------------------------
; This function is used to print out a human-readable score summary
; derived from the histories it is given.
;------------------------------------------------------------------------
(define (print-out-results-2P history1 history2 number-of-games)
    (let ((score (get-scores-2P history1 history2)))
	(newline)

	; Player 1's information
	(display "Player 1 Score:  ")
	(display (first score))
	(display " (Average = ")
	(display (exact->inexact (/ (first score) number-of-games)))
	(display ")")
	(newline)

	; Player 2's information
	(display "Player 2 Score:  ")
	(display (second score))
	(display " (Average = ")
	(display (exact->inexact (/ (second score) number-of-games)))
	(display ")")
	(newline)
    )
)


;------------------------------------------------------------------------
;  2-player-game-score-table
;------------------------------------------------------------------------
; This value represents the score matrix for the game.  It consists of
; a list of pairs, where each pair consists of a list of player choices
; (whether each player cooperates or defects) together with a list of
; the scores earned by each player.  In effect, each separate cell in
; the game matrix is represented by one pair in this list.
;------------------------------------------------------------------------
(define 2-player-game-score-table
    '( ; A's choice  B's choice   A's score  B's score
       ((    1           1     ) (    3          3    ))
       ((    1          -1     ) (    0          5    ))
       ((   -1           1     ) (    5          0    ))
       ((   -1          -1     ) (    1          1    ))
    )
)


;------------------------------------------------------------------------
;  make-game choice1 choice2
;------------------------------------------------------------------------
; This function takes a set of choices for all players and combines them
; into a "game" (i.e., a plain list).  It is primarily used to form a
; search key for looking up scores in the game score table.
;------------------------------------------------------------------------
(define make-game list)


;------------------------------------------------------------------------
;  get-scores-from-game-2P game
;------------------------------------------------------------------------
; This function takes a game (a list of choices, 1 per player).  It looks
; up the game in the game score table and returns the corresponding list
; of player scores.
;------------------------------------------------------------------------
(define (get-scores-from-game-2P game)
    (second
	(list-search-positive
	    2-player-game-score-table
	    (lambda (table-cell)
		(equal? (first table-cell) game)
	    )
	)
    )
)


;------------------------------------------------------------------------
;  get-player-score-2P player-number game
;------------------------------------------------------------------------
; This function takes a player-number and a game.  It uses
; get-scores-from-game-2P, then extracts the given player's score form
; the score list.
;------------------------------------------------------------------------
(define (get-player-score-2P player-number game)
    (list-ref (get-scores-from-game-2P game) player-number)
)


;------------------------------------------------------------------------
;  get-scores-2P history1 history2
;------------------------------------------------------------------------
; This function takes two player histories and computes the cumulative
; scores for both players.
;------------------------------------------------------------------------
(define (get-scores-2P history1 history2)
    ; Read this one inside out, instead of top to bottom.
    (reduce
	; This reduction operates on the list of round scores
	; produced by the map expression below.  Computation starts
	; with the initial value (the (0 0) below), and this lambda
	; function is used to "accumulate" each round's set of scores
	; with this initial value so that the final result is a list
	; of cumulative scores for each player.
	(lambda (game-score-1 game-score-2)
	    ; Note that each of the parameters is a list of scores
	    ; with one entry for each player.  Simply add the
	    ; corresponding elements in the two game scores to get
	    ; a result
	    (map + game-score-1 game-score-2)
	)
	; This is an initial value for the reduction (both
	; players initially have a score of zero).
	'(0 0)
	; Generate a list of score lists, corresponding to the
	; player scores achieved in each round, from the history
	; lists.
	(map
	    (lambda (choice1 choice2)
		; Take choices from the two players and convert them
		; into a list of two scores for this round
		(get-scores-from-game-2P (make-game choice1 choice2))
	    )
	    history1
	    history2
	)
    )
)



;;;======================================================================
;;; -------------- Part IV: A Sample Set of Rounds ----------------------
;;;======================================================================

(display "40 rounds: spastic-2P vs. sucker-2P")
(newline)
(play-N-rounds-2P 40 spastic-2P sucker-2P)