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 2

(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

(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