My solution works by expanding a nested "probability hash." Each card is a key in this probability hash which contains another probability hash equivalent to what would happen if the dealer were to next gain that card. For example, the information on the situation in which the dealer starts with a 2 up and an ace down and then hits a jack would be contained in $probs[2][:A][:J]. In addition, each hash contains the following:
1)The hand of the dealer . E.g.: $probs[1][:A][:K][:hand]==[1,:A,:K]
2)The remaining deck, as represented by a card=>number of instances of that card remaining hash.
3)The probability of this situation occurring. This is easily calculated as the probability of the parent situation occurring times the probability of a the new card being drawn.
The program starts with the base case of full decks, empty hand, and probability of 1, and then expands down the sub-situations down to the point of 0-probability, bust, or dealer's hand being above 17. The probabilities of all the sub-situations of an upcard are then summed and outputted.
Interestingly, while most of my table is within rounding error of Dennis's, the results for the aces are remarkably different.
17 18 19 20 21 BUST
2 13.94% 13.33% 13.07% 12.40% 11.93% 35.33%
3 13.28% 13.07% 12.46% 12.18% 11.54% 37.48%
4 13.07% 12.02% 12.10% 11.64% 11.31% 39.85%
5 12.10% 12.28% 11.73% 10.90% 10.73% 42.25%
6 16.62% 10.62% 10.67% 10.12% 9.75% 42.21%
7 37.05% 13.82% 7.80% 7.88% 7.34% 26.11%
8 12.97% 36.12% 12.90% 6.89% 6.96% 24.16%
9 12.09% 11.20% 35.41% 12.11% 6.10% 23.09%
10 11.29% 11.22% 11.30% 33.56% 11.31% 21.32%
J 11.29% 11.22% 11.30% 33.56% 11.31% 21.32%
Q 11.29% 11.22% 11.30% 33.56% 11.31% 21.32%
K 11.29% 11.22% 11.30% 33.56% 11.31% 21.32%
A 12.85% 13.09% 13.02% 13.12% 36.34% 11.59%
Here's my program:
CARDS = (2..10).inject({}){|h,n|h[n]=n;h}.merge(
{:J=>10,
:Q=>10,
:K=>10,
:A=>nil})
MAX_HAND = 21
HIT_THRESHOLD = 17
NUM_DECKS = 2
HIGH_ACE = 11
LOW_ACE = 1
CARD_REPS = 4
class Array
def count(obj)
select{|el|el==obj}.size
end
def sum
inject(0){|s,n|s+n}
end
end
def sum_hand(hand)
sum = hand.map{|c|CARDS[c]}.compact.sum
sum += hand.count(:A)*HIGH_ACE
hand.count(:A).times{sum -= (HIGH_ACE-LOW_ACE) if sum > MAX_HAND}
sum <= MAX_HAND ? sum : nil
end
def expand_prob_hash(prob_hash)
return if 0 == prob_hash[:prob] or nil == sum_hand(prob_hash[:hand]) or
HIT_THRESHOLD<=sum_hand(prob_hash[:hand])
CARDS.keys.each do |c|
mod_deck = prob_hash[:deck].clone
mod_deck[c] -= 1
prob_hash[c] = {:hand=>prob_hash[:hand]+[c],
:deck=>mod_deck,
:prob=>prob_hash[:prob]*
prob_hash[:deck][c]/prob_hash[:deck].values.sum}
expand_prob_hash(prob_hash[c])
end
end
def sum_probs(prob_hash)
probs=((HIT_THRESHOLD..MAX_HAND).to_a+[nil]).inject({}){|h,n|h[n]=0.0;h}
if prob_hash.has_key? :A
CARDS.keys.each do |c|
prob_part = sum_probs(prob_hash[c])
prob_part.each_pair {|k,v| probs[k] += v}
end
elsif 0 == prob_hash[:prob]
#do nothing
else
probs[sum_hand(prob_hash[:hand])] += prob_hash[:prob]
end
probs
end
$probs = {:hand=>[],
:deck=>CARDS.keys.inject({}){|h,c|h[c]=CARD_REPS*NUM_DECKS;h},
:prob=>1.0}
expand_prob_hash($probs)
puts " "+((HIT_THRESHOLD..MAX_HAND).to_a+["BUST"]).map{|el|
"%8s"%[el]}.join
[2,3,4,5,6,7,8,9,10,:J,:Q,:K,:A].each do |c|
p = sum_probs($probs[c])
printf "%2s ",c
((HIT_THRESHOLD..MAX_HAND).to_a+[nil]).each{|n|printf "%6.2f%% ",p[n]*100*CARDS.size}
puts
end
----- Original Message ----
From: Ruby Quiz <james / grayproductions.net>
To: ruby-talk ML <ruby-talk / ruby-lang.org>
Sent: Friday, January 4, 2008 7:04:45 AM
Subject: [QUIZ] Studying Blackjack (#151)
The three rules of Ruby Quiz:
1. Please do not post any solutions or spoiler discussion for this
quiz until
48 hours have passed from the time on this message.
2. Support Ruby Quiz by submitting ideas as often as you can:
http://www.rubyquiz.com/
3. Enjoy!
Suggestion: A [QUIZ] in the subject of emails about the problem helps
everyone
on Ruby Talk follow the discussion. Please reply to the original quiz
message,
if you can.
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
The majority of the strategy in Blackjack hinges around the dealer's
hand. The
reasons are likely obvious to most of you: that's the hand you have to
beat and
the dealer plays by fixed rules we can predict.
For those unfamiliar with Blackjack, you only need to know a tiny bit
about the
game for the purposes of this exercise. The goal for both the player
and the
dealer is to draw cards to make a hand with the highest total possible,
without
going over 21. Going over 21 is called "busting" and it means you lose
the
hand. Face cards count for ten, aces are one or eleven (whichever is
better for
the hand), and all other cards count for their face value. You start
with two
cards and, if they happen to be a ten valued card and an ace (a count
of 21),
the hand is called a "natural." A natural is an automatic win in most
cases.
The dealer begins with one of his two cards face up and one face down.
We call
the former the "upcard." The dealer will "hit" or take more cards
until he
reaches a count of 17 or higher. After that he will "stand" or leave
the hand
where it is. That tells us that there are only seven possible outcomes
for the
dealer: get dealt a natural, bust, or hit to a total of 17, 18, 19,
20, or 21.
We start every hand knowing half of what the dealer holds thanks to the
upcard.
Believe it or not, you can make pretty reliable guesses about how the
hand will
go with just that knowledge.
Write a Ruby program that shows the percent chance of a dealer reaching
each
possible outcome based on the upcard showing.
I'll give you some hints to verify your results. Basic Blackjack
strategy
teaches that we should assume the dealer "has a ten in the hole" (as
the face
down card). It's not always true, of course, but 17 is a common
outcome for a
dealer with an upcard of seven. Finally, we call five and six "the
dealer's
bust cards" for reasons that will become obvious if you are outputting
correct
percentages.
In the casinos Blackjack is often played with more than one deck
shuffled
together. One, two, six, and eight deck games are common. You may
want to
offer the option to adjust the deck size your program uses. Either
way, let's
default to two decks as an average of what a player will face.
____________________________________________________________________________________
Never miss a thing. Make Yahoo your home page.
http://www.yahoo.com/r/hs