python - 如何找到在 Blackjack 中获得 21 的方法数？

Question

一些假设:

1. 使用一副 52 张牌
2. 图片卡算作 10
3. A 算作 1 或 11
4. 顺序并不重要(即 Ace + Queen 与 Queen + Ace 相同)

我想我会依次尝试所有可能的组合，看看哪些组合加起来是 21，但是混合卡片的方法太多了(52 种!方式)。这种方法也没有考虑到顺序并不重要，也没有考虑到任何一张牌最多只有 4 种类型(黑桃、梅花、方 block 、红心)这一事实。

现在我是这样想这个问题的:

我们有 11 个“插槽”。这些插槽中的每一个都可以有 53 种可能的东西:52 张卡片中的 1 张或根本没有卡片。之所以是 11 个插槽，是因为 11 张牌是可以发牌的最大数量，加起来仍然是 21；超过 11 张卡片加起来必须超过 21。

然后“最左边”的插槽将递增 1，并检查所有 11 个插槽是否加起来为 21(0 表示插槽中没有卡片)。如果不是，则右边的下一个插槽将递增，然后是下一个，依此类推。

一旦前 4 个插槽包含相同的“卡片”(在四次递增后，前 4 个插槽都将是 1)，第五个插槽不能也是那个数字，因为有 4 个任何类型的数字。第五个插槽将成为剩余可用卡中下一个最小的数字；在有四个 1 的情况下，第五个槽将变为 2，依此类推。

你会如何处理这个问题？

Answer 1

通过利用以下知识进行分而治之:如果您有 13 张并选择 10 张，您只需要选择卡片总和为 3 张即可查看...请注意，此解决方案可能很慢(我的大约需要 180 秒)框...这绝对不是最佳的)..

def sum_to(x,cards):
    if x == 0: # if there is nothing left to sum to
        yield []

    for i in range(1,12): # for each point value 1..11 (inclusive)
        if i  > x: break # if i is bigger than whats left we are done
        card_v = 11 if i == 1 else i
        if card_v not in cards: continue  # if there is no more of this card
        new_deck = cards[:] # create a copy of hte deck (we do not want to modify the original)
        if i == 1: # one is clearly an ace...
           new_deck.remove(11)
        else: # remove the value
           new_deck.remove(i)
        # on the recursive call we need to subtract our recent pick
        for result in sum_to(x-i,new_deck):
            yield [i] + result # append each further combination to our solutions

如下设置你的卡片

deck = []
for i in range(2,11): # two through ten (with 4 of each)
    deck.extend([i]*4)

deck.extend([10]*4) #jacks
deck.extend([10]*4) #queens
deck.extend([10]*4) #kings
deck.extend([11]*4) # Aces

然后调用你的函数

for combination in sum_to(21,deck):
    print combination

不幸的是，这确实允许一些重复项潜入...... 为了获得独特的条目，您需要对其进行一些更改

在 sum_to 的最后一行将其更改为

  # sort our solutions so we can later eliminate duplicates
  yield sorted([i] + result) # append each further combination to our solutions

然后当你得到你的组合时，你必须做一些深暗的巫毒风格的 python

 unique_combinations = sorted(set(map(tuple,sum_to(21,deck))),key=len,reverse=0)

 for combo in unique_combinations: print combo

从这个很酷的问题中，我学到了以下内容(请记住，在真实游戏中，您可能会让庄家和其他玩家也从同一副牌中移除)

there are 416 unique combinations of a deck of cards that make 21
there are 300433 non-unique combinations!!!

the longest number of ways to make 21 are as follows
with 11 cards there are 1 ways
[(1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3)]
with 10 cards there are 7 ways
with 9 cards there are 26 ways
with 8 cards there are 54 ways
with 7 cards there are 84 ways
with 6 cards there are 94 ways
with 5 cards there are 83 ways
with 4 cards there are 49 ways
with 3 cards there are 17 ways
with 2 cards there are 1 ways
[(10, 11)]

there are 54 ways in which all 4 aces are used in making 21!!
there are 106 ways of making 21 in which NO aces are used !!!

请记住，这些通常是次优玩法(即考虑 A,10 -> 1,10 和击球)