计算机程序的构造和解释(SICP) Assignment 6 Prisoner's dilemma

这次回顾Assignment 6 Prisoner’s dilemma。

学习资料：

https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-001-structure-and-interpretation-of-computer-programs-spring-2005/index.htm

https://github.com/DeathKing/Learning-SICP

https://mitpress.mit.edu/sites/default/files/sicp/index.html

https://www.bilibili.com/video/BV1Xx41117tr?from=search&seid=14983483066585274454

作业地址：

https://mitpress.mit.edu/sites/default/files/sicp/psets/index.html

参考资料：

https://stackoverflow.com/questions/13079658/clarification-of-assoc-syntax-in-racket

Problem 0

这里写了一个函数来遍历所有可能性：

(load "ps4prs.scm")

(define strats
    (list (cons 'all-defect all-defect)
          (cons 'poor-trusting-fool poor-trusting-fool)
          (cons 'random-strategy random-strategy)
          (cons 'random-strategy random-strategy)
          (cons 'tit-for-tat tit-for-tat)))

(define (get-res strats)
    (let ((n (length strats)))
         (define (iter i j)
             (cond ((and (< i n) (= j n)) (iter (+ i 1) 0))
                   ((and (< i n) (< j n)) (display-res i j) (iter i (+ j 1)))))
         (iter 0 0)))

(display strats)

(get-res strats)

实验结果：

1 ]=> (get-res strats)
all-defect vs all-defect

Player 1 Score: 1
Player 2 Score: 1

all-defect vs poor-trusting-fool

Player 1 Score: 5
Player 2 Score: 0

all-defect vs random-strategy

Player 1 Score: 325/97
Player 2 Score: 40/97

all-defect vs random-strategy

Player 1 Score: 319/103
Player 2 Score: 49/103

all-defect vs tit-for-tat

Player 1 Score: 53/51
Player 2 Score: 101/102

poor-trusting-fool vs all-defect

Player 1 Score: 0
Player 2 Score: 5

poor-trusting-fool vs poor-trusting-fool

Player 1 Score: 3
Player 2 Score: 3

poor-trusting-fool vs random-strategy

Player 1 Score: 147/92
Player 2 Score: 181/46

poor-trusting-fool vs random-strategy

Player 1 Score: 87/53
Player 2 Score: 207/53

poor-trusting-fool vs tit-for-tat

Player 1 Score: 3
Player 2 Score: 3

random-strategy vs all-defect

Player 1 Score: 47/97
Player 2 Score: 297/97

random-strategy vs poor-trusting-fool

Player 1 Score: 203/50
Player 2 Score: 141/100

random-strategy vs random-strategy

Player 1 Score: 119/54
Player 2 Score: 62/27

random-strategy vs random-strategy

Player 1 Score: 35/16
Player 2 Score: 235/96

random-strategy vs tit-for-tat

Player 1 Score: 219/94
Player 2 Score: 107/47

random-strategy vs all-defect

Player 1 Score: 50/103
Player 2 Score: 315/103

random-strategy vs poor-trusting-fool

Player 1 Score: 395/101
Player 2 Score: 165/101

random-strategy vs random-strategy

Player 1 Score: 209/93
Player 2 Score: 184/93

random-strategy vs random-strategy

Player 1 Score: 189/97
Player 2 Score: 239/97

random-strategy vs tit-for-tat

Player 1 Score: 47/23
Player 2 Score: 183/92

tit-for-tat vs all-defect

Player 1 Score: 108/109
Player 2 Score: 113/109

tit-for-tat vs poor-trusting-fool

Player 1 Score: 3
Player 2 Score: 3

tit-for-tat vs random-strategy

Player 1 Score: 229/100
Player 2 Score: 117/50

tit-for-tat vs random-strategy

Player 1 Score: 213/97
Player 2 Score: 213/97

tit-for-tat vs tit-for-tat

Player 1 Score: 3
Player 2 Score: 3
;Unspecified return value

Problem 1

a

每次要遍历history，假设history长度为$l$，那么时间复杂度为$O(l)$。

b

时间复杂度为$O(1)$，因为每次只看首元素即可。

显然新版本更快。

Problem 2

结合problem 3一起完成：

(load "ps4prs.scm")

(define (make-fit-for-n-tats k)
    (define (tit-for-k-tats my-history other-history)
        (define (iter cnt)
            (cond ((empty-history? my-history) 'c)
                ((= cnt k) 'd)
                ((eq? (most-recent-play other-history) 'c) 'c)
                (else (iter (+ cnt 1)))))
        (iter 0))
    tit-for-k-tats)

(define tit-for-two-tats (make-fit-for-n-tats 2))

(define strats
    (cons (cons 'tit-for-two-tats tit-for-two-tats) strats))

(define (get-res-i strats i)
    (let ((n (length strats)))
         (define (iter i j)
             (cond ((and (< j n)) (display-res i j) (iter i (+ j 1)))))
         (iter i 0)))

(get-res-i strats 0)

实验结果：

1 ]=> (get-res-i strats 0)
tit-for-two-tats vs tit-for-two-tats

Player 1 Score: 3
Player 2 Score: 3

tit-for-two-tats vs all-defect

Player 1 Score: 96/97
Player 2 Score: 101/97

tit-for-two-tats vs poor-trusting-fool

Player 1 Score: 3
Player 2 Score: 3

tit-for-two-tats vs random-strategy

Player 1 Score: 104/47
Player 2 Score: 213/94

tit-for-two-tats vs random-strategy

Player 1 Score: 241/101
Player 2 Score: 241/101

tit-for-two-tats vs tit-for-tat

Player 1 Score: 3
Player 2 Score: 3
;Unspecified return value

Problem 3

同problem 2：

(load "ps4prs.scm")

(define tit-for-three-tats (make-fit-for-n-tats 3))

(define strats
    (cons (cons 'tit-for-three-tats tit-for-three-tats) strats))

(get-res-i strats 0)

实验结果：

1 ]=> (get-res-i strats 0)
tit-for-three-tats vs tit-for-three-tats

Player 1 Score: 3
Player 2 Score: 3

tit-for-three-tats vs all-defect

Player 1 Score: 106/107
Player 2 Score: 111/107

tit-for-three-tats vs poor-trusting-fool

Player 1 Score: 3
Player 2 Score: 3

tit-for-three-tats vs random-strategy

Player 1 Score: 249/110
Player 2 Score: 249/110

tit-for-three-tats vs random-strategy

Player 1 Score: 11/5
Player 2 Score: 236/105

tit-for-three-tats vs tit-for-tat

Player 1 Score: 3
Player 2 Score: 3
;Unspecified return value

Problem 4

a

代码：

(load "ps4prs.scm")

; a
(define (make-dual-strategy strat0 strat1 switch-point)
    (let ((cnt 0))
        (define (f my-history other-history)
            (cond ((< cnt switch-point)
                  (begin (set! cnt (+ cnt 1))
                         (strat0 my-history other-history)))
                  (else (strat1 my-history other-history))))
    f))

(define strat-dual (make-dual-strategy all-defect poor-trusting-fool 2))

(play-loop strat-dual random-strategy)

实验结果：

1 ]=> (play-loop strat-dual random-strategy)
Player 1 Score: 49/31
Player 2 Score: 362/93
;Unspecified return value

b

代码：

; b
; 假设 switch-point1 < swit
(define (make-triple-strategy strat0 strat1 strat2 switch-point1 switch-point2)
    (cond ((= switch-point1 switch-point2) (error "switch-point1 should not equal to switch-point2" switch-point1 switch-point2))
          ((> switch-point1 switch-point2) (make-triple-strategy strat0 strat1 strat2 switch-point2 switch-point1))
          (else (make-dual-strategy 
                    (make-dual-strategy strat0 strat1 switch-point1)
                    strat2
                    switch-point2))))

(define strat-triple (make-triple-strategy all-defect poor-trusting-fool random-strategy 3 5))

(play-loop strat-triple tit-for-tat)

实验结果：

1 ]=> (play-loop strat-triple tit-for-tat)
Player 1 Score: 243/106
Player 2 Score: 119/53

Problem 5

代码：

(load "ps4prs.scm")

(define (niceify strat niceness-factor)
    (lambda (my-history other-history)
        (let ((res (strat my-history other-history)))
             (cond ((eq? res 'c) 'c)
                   ((< (random 1.0) niceness-factor) 'c)
                   (else 'd)))))

(define slightly-nice-all-defect (niceify all-defect 0.1))

(define slightly-nice-tit-for-tat (niceify tit-for-tat 0.1))

(play-loop slightly-nice-all-defect slightly-nice-tit-for-tat)

实验结果：

1 ]=> (play-loop slightly-nice-all-defect slightly-nice-tit-for-tat)
Player 1 Score: 67/45
Player 2 Score: 52/45

Problem 6

代码：

(load "ps4prs.scm")

(define (play-loop strat0 strat1 strat2)
  (define (play-loop-iter strat0 strat1 strat2 count history0 history1 history2 limit)
    (cond ((= count limit) (print-out-results history0 history1 history2 limit))
          (else (let ((result0 (strat0 history0 history1 history2))
                      (result1 (strat1 history1 history0 history2))
                      (result2 (strat2 history2 history0 history1)))
                  (play-loop-iter strat0 strat1 strat2 (1+ count)
                                  (extend-history result0 history0)
                                  (extend-history result1 history1)
                                  (extend-history result2 history2)
                                  limit)))))
  (play-loop-iter strat0 strat1 strat2 0 '() '() '() (+ 90 (random 21))))


(define (print-out-results history0 history1 history2 number-of-games)
  (let ((scores (get-scores history0 history1 history2)))
    (newline)
    (display "Player 1 Score: ")
    (display (/ (car scores) number-of-games))
    (newline)
    (display "Player 2 Score: ")
    (display (/ (cadr scores) number-of-games))
    (newline)
    (display "Player 3 Score: ")
    (display (/ (caddr scores) number-of-games))
    (newline)))

(define (get-scores history0 history1 history2)
  (define (get-scores-helper history0 history1 history2 score0 score1 score2)
    (cond ((empty-history? history0) (list score0 score1 score2))
          (else (let ((game (make-game (most-recent-play history0)
                                       (most-recent-play history1)
                                       (most-recent-play history2))))
                  (get-scores-helper (rest-of-plays history0)
                                     (rest-of-plays history1)
                                     (rest-of-plays history2)
                                     (+ (get-player-points 0 game) score0)
                                     (+ (get-player-points 1 game) score1)
                                     (+ (get-player-points 2 game) score2))))))
  (get-scores-helper history0 history1 history2 0 0 0))


(define *game-association-list*
  '(((c c c) (7 7 7))
    ((c c d) (3 3 9))
    ((c d c) (3 9 3))
    ((d c c) (9 3 3))
    ((c d d) (0 5 5))
    ((d c d) (5 0 5))
    ((d d c) (5 5 0))
    ((d d d) (1 1 1))))

Problem 7

a

代码：

(load "ps6.scm")

; a
(define (all-defect-3 my-history other-history1 other-history2)
  'd)

(define (poor-trusting-fool-3 my-history other-history1 other-history2)
  'c)

(define (random-strategy-3 my-history other-history1 other-history2)
  (if (= (random 2) 0) 'c 'd))

(play-loop all-defect-3 poor-trusting-fool-3 random-strategy-3)

(play-loop random-strategy-3 random-strategy-3 random-strategy-3)

实验结果：

1 ]=> (play-loop all-defect-3 poor-trusting-fool-3 random-strategy-3)
Player 1 Score: 683/99
Player 2 Score: 47/33
Player 3 Score: 401/99
;Unspecified return value

1 ]=> (play-loop random-strategy-3 random-strategy-3 random-strategy-3)
Player 1 Score: 370/99
Player 2 Score: 124/33
Player 3 Score: 139/33
;Unspecified return value

b

代码：

; b
(define (tough-tit-for-tat my-history other-history1 other-history2)
  (cond ((empty-history? my-history) 'c)
        ((or (eq? (most-recent-play other-history1) 'd)
             (eq? (most-recent-play other-history2) 'd)) 'd)
        (else 'c)))

(define (soft-tit-for-tat my-history other-history1 other-history2)
  (cond ((empty-history? my-history) 'c)
        ((and (eq? (most-recent-play other-history1) 'd)
              (eq? (most-recent-play other-history2) 'd)) 'd)
        (else 'c)))

(play-loop random-strategy-3 random-strategy-3 soft-tit-for-tat)

(play-loop random-strategy-3 random-strategy-3 soft-tit-for-tat)

实验结果：

1 ]=> (play-loop random-strategy-3 random-strategy-3 soft-tit-for-tat)
Player 1 Score: 91/18
Player 2 Score: 44/9
Player 3 Score: 166/45
;Unspecified return value

1 ]=> (play-loop random-strategy-3 random-strategy-3 soft-tit-for-tat)
Player 1 Score: 463/90
Player 2 Score: 9/2
Player 3 Score: 164/45
;Unspecified return value

Problem 8

代码：

(load "p6.scm")

(define (get-probability-of-c hist-0 hist-1 hist-2)
    (let ((n (length hist-0)))
         (define (iter i cc ccc cd ccd dd cdd)
             (cond ((= i n) (get-res cc ccc cd ccd dd cdd))
                   ((and (eq? (list-ref hist-1 i) 'c)
                         (eq? (list-ref hist-2 i) 'c))
                    (if (eq? (list-ref hist-0 (- i 1)) 'c)
                        (iter (+ i 1) (+ cc 1) (+ ccc 1) cd ccd dd cdd)
                        (iter (+ i 1) (+ cc 1) ccc cd ccd dd cdd)))
                   ((and (eq? (list-ref hist-1 i) 'd)
                         (eq? (list-ref hist-2 i) 'd))
                    (if (eq? (list-ref hist-0 (- i 1)) 'c)
                        (iter (+ i 1) cc ccc cd ccd (+ dd 1) (+ cdd 1))
                        (iter (+ i 1) cc ccc cd ccd (+ dd 1) cdd)))
                   (else
                    (if (eq? (list-ref hist-0 (- i 1)) 'c)
                        (iter (+ i 1) cc ccc (+ cd 1) (+ ccd 1) dd cdd)
                        (iter (+ i 1) cc ccc (+ cd 1) ccd dd cdd)))))
         (define (get-res cc ccc cd ccd dd cdd)
            (define (iter i r1 r2 r3)
                (cond ((= i 0)
                       (if (eq? cc 0)
                           (iter (+ i 1) r1 r2 r3)
                           (iter (+ i 1) (/ (* ccc 1.0) cc) r2 r3)))
                      ((= i 1)
                       (if (eq? cd 0)
                           (iter (+ i 1) r1 r2 r3)
                           (iter (+ i 1) r1 (/ (* ccd 1.0) cd) r3)))
                      ((= i 2)
                       (if (eq? dd 0)
                           (iter (+ i 1) r1 r2 r3)
                           (iter (+ i 1) r1 r2 (/ (* cdd 1.0) dd))))
                      (else (list r1 r2 r3))))
            (iter 0 '() '() '()))
         (iter 1 0 0 0 0 0 0)))

(define (is-he-a-fool? hist0 hist1 hist2)
    (equal? '(1 1 1) (get-probability-of-c hist0 hist1 hist2)))

(define (could-he-be-a-fool? hist0 hist1 hist2)
    (equal? (list true true true)
            (map (lambda (elt) (or (null? elt) (eqv? elt 1)))
                 (get-probability-of-c hist0 hist1 hist2))))

(get-probability-of-c '(c c c c) '(d d d c) '(d d c c))

(get-probability-of-c '(c c c d c) '(d c d d c) '(d c c c c))

; b
; p(ddd/dd) = 1
(define (whether-soft-tit-for-tat hist0 hist1 hist2)
    (or (eq? 0.0 (caddr (get-probability-of-c hist1 hist0 hist2)))
        (eq? 0.0 (caddr (get-probability-of-c hist2 hist0 hist1)))))

; p(ccc/cc) = 1
; 其余为'()
(define (whether-one-poor-trusting-fool hist0 hist1 hist2)
    (and (eq? 1.0 (car (get-probability-of-c hist0 hist1 hist2)))
         (eq? '() (cadr (get-probability-of-c hist0 hist1 hist2)))
         (eq? '() (caddr (get-probability-of-c hist0 hist1 hist2)))))

(define (whether-poor-trusting-fool hist0 hist1 hist2)
    (and (whether-one-poor-trusting-fool hist1 hist0 hist2)
         (whether-one-poor-trusting-fool hist2 hist0 hist1)))

(define (dont-tolerate-fools my-history other-history1 other-history2)
    (let ((cnt 0))
        (define (f my-history other-history1 other-history2)
            (cond ((< cnt 10)
                   (begin (set! cnt (+ cnt 1))
                          'c))
                  (else
                    (if (whether-poor-trusting-fool my-history other-history1 other-history2)
                        'd
                        'c))))
        (f my-history other-history1 other-history2)))

(define (gen-dont-tolerate-fools)
    (let ((cnt 0))
        (define (f my-history other-history1 other-history2)
            (cond ((< cnt 10)
                   (begin (set! cnt (+ cnt 1))
                          'c))
                  (else
                    (if (whether-poor-trusting-fool my-history other-history1 other-history2)
                        'd
                        'c))))
        f))

(define dont-tolerate-fools (gen-dont-tolerate-fools))

(define (dont-tolerate-fools my-history other-history1 other-history2)
    (let ((cnt 0))
        (cond ((< cnt 10)
                (begin (set! cnt (+ cnt 1))
                        'c))
                (else
                (if (whether-poor-trusting-fool my-history other-history1 other-history2)
                    'd
                    'c)))))

(define (poor-trusting-fool-3 my-history other-history1 other-history2)
  'c)

(define (all-defect-3 my-history other-history1 other-history2)
  'd)

(play-loop dont-tolerate-fools poor-trusting-fool-3 poor-trusting-fool-3)

(play-loop dont-tolerate-fools all-defect-3 poor-trusting-fool-3)

实验结果：

1 ]=> (play-loop dont-tolerate-fools poor-trusting-fool-3 poor-trusting-fool-3)
Player 1 Score: 7
Player 2 Score: 7
Player 3 Score: 7
;Unspecified return value

1 ]=> (play-loop dont-tolerate-fools all-defect-3 poor-trusting-fool-3)
Player 1 Score: 3
Player 2 Score: 9
Player 3 Score: 3
;Unspecified return value

Problem 9

代码：

(load "p6.scm")

(define (make-combined-strategies strat0 strat1 combine)
    (lambda (history0 history1 history2)
        (let ((r1 (strat0 history0 history1))
              (r2 (strat1 history0 history2)))
             (combine r1 r2))))

(define strat0
    (make-combined-strategies
        tit-for-tat tit-for-tat
        (lambda (r1 r2) (if (or (eq? r1 'd) (eq? r2 'd)) 'd 'c))))

(define strat1
    (make-combined-strategies
        tit-for-tat go-by-majority
        (lambda (r1 r2) (if (= (random 2) 0) r1 r2))))

(define (all-defect-3 my-history other-history1 other-history2)
    'd)

(play-loop strat0 strat1 all-defect-3)

实验结果：

1 ]=> (play-loop strat0 strat1 all-defect-3)
Player 1 Score: 49/46
Player 2 Score: 93/92
Player 3 Score: 26/23