CS 61A   Project #1   (Twenty-One)    Solutions


(Note:  Although these posted solutions do not include transcripts,
the handout required you to provide transcripts showing that your
procedures work correctly.  One of the things you are supposed to
be learning is how to test a program.  For example, in this project,
it's not good enough to test a strategy just by playing a game with
it and seeing that it doesn't blow up, like this:
	> (twenty-one some-strategy)
	-1
The transcript must show that the strategy procedure actually
carries out the desired strategy, either by invoking the procedure
directly with well-chosen arguments or by playing several games
with the strategy procedure traced.)


1.  best-total

The most straightforward way to do this is to go through the
hand, keep track of total points (with some fixed value for
aces) and also keep track of the number of aces, and perhaps
adjust the total once the whole hand has been tallied.  Because
you need to keep track of two values at once, this is a case
where an iterative subprocedure with extra state variables
is useful.

Should you initially count aces as 1 or as 11?  Either is possible.
Here is a solution counting aces as 11:

(define (best-total hand)
  (define (value rank)
    (cond ((number? rank) rank)
	  ((equal? rank 'A) 11)
	  (else 10)))
  (define (lower aces points)
    (cond ((<= points 21) points)
	  ((= aces 0) points)
	  (else (lower (- aces 1) (- points 10))) ))
  (define (total aces points hand)
    (if (empty? hand)
	(lower aces points)
	(let ((rank (bl (first hand))))
	  (total (if (equal? rank 'A) (+ aces 1) aces)
		 (+ points (value rank))
		 (bf hand)) )))
  (total 0 0 hand))

The final computation is a little simpler (avoiding the
recursive call in LOWER) if you realize that at most one
ace should be counted as 11 points.  If you initially
count aces as 1, you end up with this:

(define (best-total hand)
  (define (value rank)
    (cond ((number? rank) rank)
	  ((equal? rank 'A) 1)
	  (else 10)))
  (define (raise aces points)
    (if (and (<= points 11) (> aces 0))
	(+ points 10)
 	points ))
  (define (total aces points hand)
    (if (empty? hand)
	(raise aces points)
	(let ((rank (bl (first hand))))
	  (total (if (equal? rank 'A) (+ aces 1) aces)
		 (+ points (value rank))
		 (bf hand)) )))
  (total 0 0 hand))

I used BUTLAST rather than FIRST to extract the rank of a card
because tens have a two-character rank.  (bl '10s) is the correct
10 but (first '10s) is just 1.


2.  stop-at-17

One way that people messed up on this problem was to try to copy the
code in play-dealer.  But the latter isn't a strategy procedure; that
is, it doesn't take a hand and a card as arguments and return #t or
#f as its value.  The decision process is the same, but the
context is different.

(define (stop-at-17 my-hand dealer-up-card)
  (< (best-total my-hand) 17))

It's tempting to feel that an IF or COND is needed here, because there
are two different possible answers:

     (if (< (best-total my-hand) 17)
	 #t
	 #f)

but in fact this approach is redundant, although it will give the
right answer.  The value of the (< ... ...) expression is already
#t or #f; the IF just says, "if it's true return #t, if it's
false return #f."

It can be argued that best-total is not the best way for a customer
strategy to count hands with aces.  If you wanted to use a different
point counting rule, that's fine.


3.  play-n

The structure of this procedure is not unlike the acumulation examples in
the book: the value of one expression is added to the accumulated values
of other expressions.  In fact it would be possible to write PLAY-N using
the book's SUM procedure:

(define (play-n strategy n)
  (sum (lambda (x) (twenty-one strategy))
       1
       (lambda (x) (+ x 1))
       n))

Here the first argument to SUM is a rather peculiar, but legal, procedure
that pays no attention to its argument.  A more straightforward solution
doesn't use SUM but does have a similar structure:

(define (play-n strategy n)
  (if (= n 0)
      0
      (+ (twenty-one strategy)
	 (play-n strategy (- n 1)) )))


4.  another strategy

(define (dealer-sensitive my-hand dealer-up-card)
	(or (and (< (best-total my-hand) 17) 
	    	 (member (bl dealer-up-card) '(7 8 9 10 j q k)))
            (and (< (best-total my-hand) 12)
                 (member (bl dealer-up-card) '(2 3 4 5 6)))))

5. test-strategies
Note that we cannot simply use the play-n procedure since we want to compare the number of games won. play-n returns the number of games won minus the number of games lost.

(define (test-strategies strat1 strat2 num)
	(>= (count-win strat1 num)
	    (count-win strat2 num)))

(define (count-win strategy num)
  (cond ((= num 0) 0)
  	((= (twenty-one strategy) 1) (+ 1 (count-wins strategy (- num 1))))
	(else (count-wins strategy (- num 1)))))


6.  stop-at

The key here is to understand that stop-at is not itself a strategy
procedure (that is, it doesn't take hands or cards as arguments and
return #t or #f); it's a procedure whose return value is a
strategy procedure.

(define (stop-at n)
  (lambda (my-hand dealer-up-card)
    (< (best-total my-hand) n) ))


7.  majority

(define (majority s1 s2 s3)
  (lambda (my-hand dealer-up-card)
    (define (use-strategy strat)
      (if (strat my-hand dealer-up-card) 1 0))
    (>= (+ (use-strategy s1)
	   (use-strategy s2)
	   (use-strategy s3))
	2) ))

Of course the above is not the only way to find the majority vote.
I think converting each strategy's true/false into a number and
adding the results is probably the simplest way, but here is
another:

(define (majority s1 s2 s3)
  (lambda (my-hand dealer-up-card)
    (if (s1 my-hand dealer-up-card)
	(or (s2 my-hand dealer-up-card) (s3 my-hand dealer-up-card))
	(and (s2 my-hand dealer-up-card) (s3 my-hand dealer-up-card)) )))

The key point is that majority takes three strategies as arguments
and returns a strategy, i.e., a predicate with a hand and a card as
arguments.

[Note for experts: Remember when we asked if there were any reasons
for preferring to have AND and OR as ordinary procedures rather than
special forms?  Well, if they were, we could write

(define (majority s1 s2 s3)
  (lambda (my-hand dealer-up-card)
    ((if (s1 my-hand dealer-up-card)
	  or
	  and)
     (s2 my-hand dealer-up-card)
     (s3 my-hand dealer-up-card)) ))

but this doesn't work with special forms.]


8.  reckless strategy

(define (reckless strat)
  (lambda (my-hand dealer-up-card)
    (strat (butlast my-hand) dealer-up-card) ))


9.  jokers

What needs to be modified?  Procedure TWENTY-ONE and its internally defined
subprocedures don't look directly at cards; they just invoke BEST-TOTAL to
get the total point value of a hand.  So TWENTY-ONE doesn't have to be
changed at all.  The necessary changes are in BEST-TOTAL and MAKE-DECK
(and its subprocedure MAKE-ORDERED-DECK).

How should we represent a joker?  There is no single right answer to this.
Any representation will do, as long as the BUTLAST of that representation
isn't the same as one of the other card ranks.  For example, the word
JOKER will work, even though it starts with J, as long as you are using
BUTLAST and not FIRST to find the rank of a card.

Adding the jokers to the deck is the easy part:

(define (make-ordered-deck)
  (define (make-suit s)
    (every (lambda (rank) (word rank s)) '(A 2 3 4 5 6 7 8 9 10 J Q K)) )
  (se (make-suit 'H) (make-suit 'S) (make-suit 'D) (make-suit 'C)
      '(JOKER JOKER)) )   ;; Add two jokers to the ordered deck.

(define (make-deck)
  (define (shuffle deck size)
    (define (move-card in out which)
      (if (= which 0)
	  (se (first in) (shuffle (se (bf in) out) (- size 1)))
	  (move-card (bf in) (se (first in) out) (- which 1)) ))
    (if (= size 0)
	deck
    	(move-card deck '() (random size)) ))
  (shuffle (make-ordered-deck) 54) )   ;; The only change is 54 instead of 52.

Modifying BEST-TOTAL is a little harder because we have to think about the
correct algorithm before we write the code.  A joker can be worth anywhere
from 1 to 11 points.  If the hand contains between 10 and 20 points, plus a
joker, we should count it as 21.  If it contains 21 or more points plus a
joker, we should count the joker as 1, but it doesn't really matter because
the hand is a bust.  If the hand contains fewer than 10 other points, we
should count the joker as 11.  But what if there are two jokers in the
hand, or a joker and an ace?  Two jokers are worth between 2 and 22 points,
so if the other cards add up to 19 or less, we should just call the hand
21 points; 20 or more plus two jokers is a bust.

As for aces, in the original BEST-TOTAL we raised an ace from 1 to 11 if
the hand's total was 11 or less.  The only necessary change is that if
there is a joker, we raise the ace only for 10 or less; with two jokers
we raise the ace only for 9 or less.  If we initially consider the joker
as worth 1 point, this change will be automatic, but we have to compensate
for that 1-point difference in the numbers listed in the paragraph above.

I've used the version of best-total in which aces are initially counted
as 1, because in that version RAISE isn't recursive, and that makes the
change a little easier.

(define (best-total hand)
  (define (value rank)
    (cond ((number? rank) rank)
	  ((equal? rank 'A) 1)
	  ((EQUAL? RANK 'JOKE) 1)
	  (else 10)))
  (DEFINE (FIX-JOKER JOKERS POINTS)
    (COND ((= JOKERS 0) POINTS)
	  ((AND (= JOKERS 1) (<= POINTS 10)) (+ POINTS 10))
	  ((<= POINTS 21) 21)
	  (ELSE POINTS) ))
  (define (raise aces JOKERS points)
    (FIX-JOKER JOKERS
    	       (if (and (<= points 11) (> aces 0))
		   (+ points 10)
 		   points )))
  (define (total aces JOKERS points hand)
    (if (empty? hand)
	(raise aces JOKERS points)
	(let ((rank (bl (first hand))))
	  (total (if (equal? rank 'A) (+ aces 1) aces)
		 (IF (EQUAL? RANK 'JOKE) (+ JOKERS 1) JOKERS)
		 (+ points (value rank))
		 (bf hand)) )))
  (total 0 0 0 hand))

The dealer's strategy (basically stop-at-17) is no longer rational, if
the dealer has a joker.  Consider the hand (7S JOKER); BEST-TOTAL will
give this 18 points, so the dealer will stand, but the dealer would
certainly do better by drawing to this hand.  You weren't required to
think about this, but if you wanted to fix it, you'd modify a subprocedure
of TWENTY-ONE:

  (define (play-dealer customer-hand dealer-hand-so-far rest-of-deck)
    (cond ((> (best-total dealer-hand-so-far) 21) 1)
	  (OR (< (best-total dealer-hand-so-far) 17)	; ***
	      (AND (< BEST-TOTAL DEALER-HAND-SO-FAR 21)	; ***
		   (MEMBER? 'JOKER DEALER-HAND-SO-FAR))); ***
	   (play-dealer customer-hand
			(se dealer-hand-so-far (first rest-of-deck))
			(bf rest-of-deck)))
	  ((< (best-total customer-hand) (best-total dealer-hand-so-far)) -1)
	  ((= (best-total customer-hand) (best-total dealer-hand-so-far)) 0)
	  (else 1)))