Design Of Computer Programs(1):A Poker Program

来源:优达学城 Design Of Computer Programs by Peter Norvig

这是一个python实现的德州扑克的程序,而且讲解居然是Peter Norvig
!然而那些扑克规则真是把我给整懵了...在此做些记录以期理顺逻辑。

一、基本设定

  • hand:手牌。一把手牌中有五张扑克牌。
  • rank&suit:手牌点数&花色。比如一张♦5,花色(suit)是方片(diamond),点数(rank)是5。
  • 牌型hand rank。牌型有这样几种,大小由大到小排列:

    1. straight flush:同花顺。同花色的顺子。
    2. 4-kind:手牌中有4张同点数的牌。
    3. full house: 三张同点数+两张同点数,如 10 10 10 6 6。
    4. flush: 五张同花色。
    5. straight:顺子。如 5 6 7 8 9。
    6. 3-kind: 手牌中三张同点数牌。
    7. two pairs: 两对同点数的牌加一张散牌。
    8. pair: 一对同点数的牌加三张散牌。
    9. high card:不符合以上任何一种。大小由点数最大的牌决定。(大小顺序为A K Q J 10 9 8 7 6 5 4 3 2)。

二、程序主体

  • 主要完成的程序是poker(hands:list)->handpoker可以接受一个hand列表,返回最大的那个hand。
  • hand_rank(hand)hand_rank可以指出手牌hand的牌型。比如对于一副♥J ♠J ♦2 ♣2 ♦5的手牌,hand_rank会指出这是一副two pair

三、问题

(1) Q: python的内置函数中有与poker函数功能相类似的吗?

A: 有啊,maxmax中的key参数允许对被比较的主体进行映射,比如用abs将原来的值变成绝对值。这里可以用让poker返回max(hands, key=hand_rank),将手牌映射为牌型。这样一来,poker的逻辑就可以被简洁地表示为:

def poker(hands):
    "return the best hand: poker([hand,...]) => hand"
    return max(hands, key=hand_rank)

(2)如何表示一手牌(hand)?

如果用字符串表示一张牌,字符串列表就不错。["TC","9D","10D","JH","5C"]中,"TC"表示 club 10,"JH"表示jack heart。

(3) Q:如何表示牌型,使得牌型能被max函数比较?比如,将straight flush赋值为8,4-kind赋值为7,... ,high card赋值为0。这样就可以了吗?

A:不行。4-kind之间(10 10 10 10 7 和 9 9 9 9 6)怎么比较呢?可以用一个元组表示牌型。比如10 10 10 10 7表示为(7,10,7),9 9 9 9 9 6表示为(7,9,6)。python中元组间也是可以互相比较的!比较方法是对每一个元素依次进行比较。比如(7,10,7)就大于(7,9,6),因为第1个位置上10>9。
如何将其他的牌型用类似的方式表达出来?

  • straight flush:"straight flush, jack high!" 也就是说J是同花顺中最大的牌。知道了最大的牌就可以比较两手同花顺的大小。(8,11)就能完全描述手牌情况。
  • 4-kind:"four aces, and a queen kicker!" 四张A带一张Q,表示为(7,14,12)。
  • full house:"full house, eight over kings!" (6,8,13)表示三张8带两张K。
  • flush:这个就需要列出所有牌的点数才能比大小。(5,[10,8,7,5,3])表示同花色、点数为的 10,8,7,5,3 手牌。
  • straight:"straight, jack high!"这个也只需要最大点数的手牌就能完全比较大小——(4,11)。
  • 3-kind:(3, 7, [7, 7, 7, 5, 2]) 表示 7 7 7 5 2。
  • two pair:(2, 11, 3, [13, 11, 11, 3, 3]) 表示 11 11 3 3 13。
  • pair:(1, 2, [11, 6, 3, 2, 2]) 表示 2 2 3 11 6。
  • high card:(0,7,5,4,3,2) 表示 7 5 4 3 2。

这些规则用代码表示就是:

def hand_rank(hand):
    "Return a value indicating the ranking of a hand"
    ranks = card_ranks(hand)  # ranks指所有手牌点数
    if straight(ranks) and flush(hand):
        return (8, max(ranks))
    elif kind(4, ranks):  # 即手牌中有4张点数相同的牌
        return (7, kind(4, ranks), kind(1, ranks))
    elif kind(3, ranks) and kind(2, ranks):
        return (6, kind(3, ranks), kind(2, ranks))
    elif flush(hand):
        return (5, ranks)
    elif straight(ranks):
        return (4, max(ranks))
    elif two_pair(ranks):
        return (2, two_pair(ranks), ranks)
    elif kind(2, ranks):
        return (1, kind(2, ranks), ranks)
    else:
        return (0, ranks)

#### (4)Q:如何实现card_ranks, 给出手牌的点数?
A:card_ranks给出手牌中牌的点数。简单而言,只要提取出card字符串的第一个字符即可。比如:

def card_ranks(hand):
    ranks = [r for r,s in cards]
    ranks.sort(reverse=True)
   return ranks

但对于"AC"(梅花A)这种牌该怎么办呢?
最开始的想法是这样的:弄个字典,储存TJQKA对应的数值。

def card_ranks(cards):
    "Return a list of the ranks, sorted with higher first."
    modifier_dict={
        'T':10,
        'J':11,
        'Q':12,
        'K':13,
        'A':14
    }
    def modifier(x):
        if x in modifier_dict.keys():
            return modifier_dict[x]
        else:
            return int(x)
    ranks = [r for r,s in cards]
    ranks = list(map(modifier, ranks))
    ranks.sort(reverse=True)
    return ranks            

就完事儿。然后还想,这种“找得到键返回键对应值,找不到就返回另一个值”不是很像dict.get()吗,那就改成:

def modifier(x):
    modifier_dict={
        'T':10,
        'J':11,
        'Q':12,
        'K':13,
        'A':14
    }
    return modifier_dict.get(x, int(x))

诶他就不行了。会报错不存在int('A')这种操作。因为无论找不找得到键get都会把int给执行了,自作聪明。

然而Peter只用了一行:

def card_ranks(hand):
    "Return a list of the ranks, sorted with higher first."
    ranks = ['--23456789TJQKA'.index(r) for r,s in hand]
    ranks.sort(reverse=True)
    return ranks

用列表中的位置对应手牌点数,就很秀。

(4)如何判断straight(顺子)和flush(同花色)?

顺子,也就是说点数是5个连续整数。比较巧妙的方法是判断这5个数互不相同,且最大值减去最小值为4。
max(ranks) - min(ranks) == 4 and len(set(ranks)) == 5
同花色,也就是取转化成集合后只有一个元素。
len(set(suit))==1

这套规则不仅能用来判断扑克里的同花顺,还可以判断五子棋的输赢:五个棋子横坐标相同,纵坐标为五个连续值,那就算是赢了。

(5) 如何实现kind(ranks, n)函数,给出手牌中正好有n张的牌?

最简单的办法,遍历 + list.count()。我的想法也差不多,用collections.Counter数一遍。但是没有必要,不需要把所有的元素个数都数出来。

def kind(n, ranks):
    for r in ranks:
        if ranks.count(r) == n:
            return r
    return None

(6) 如何实现two_pair, 判断手牌里是否有两组成对的牌,有则返回这两组牌的点数?

我的想法:先对手牌用一次kind(ranks, 2), 得到返回值r0, 然后从列表里弹出所有点数为r0的牌,对剩下的列表再用一次kind(ranks, 2), 得到返回值r1。
Peter的想法:对手牌用一次kind(ranks, 2)得到r0, 将列表逆序,再用一次kind(ranks, 2)得到r1,r0若不等于r1则是two_pair。
嗯,充分利用数据和函数的特性...特性在于kind只会返回第一个手里恰好有n张牌的点数,ranks又是有序排列的。

(7) 如何处理平局?

poker函数使用了max来比较手牌大小,但是max只会返回第一个最大值,这在平局的情况下是不公平的。所以我们要实现自己的max,它能返回所有的最大值。这并不难做到:

def allmax(iterable, key=None):
    result, maxval = [], None
    key = key or (lambda x: x)
    for x in iterable:
        xval = key(x)
        if not result or xval > maxval:
            result, maxval = [x], xval
        elif xval == maxval:
            result.append(x)
    return result

(8)如何发牌?

我们需要给每个玩家发随机的n张牌。
复杂的写法:

def deal(numhands, n=5, deck=None):
    deck = copy(deck) or [r + s for r in '23456789TJQKA' for s in 'SHDC']
    hands = []
    for num in range(0, numhands):
        hand = []
        for _ in range(0, n):
            card = random.choice(deck)
            if deck:
                deck.remove(card)
                hand.append(card)
        hands.append(hand)
    return hands

简洁的写法:

def deal(numhands, n=5, deck=None):
    deck = copy(deck) or [r + s for r in '23456789TJQKA' for s in 'SHDC']
    random.shuffle(deck)
    return [deck[n*i: n*(i+1)] for i in range(numhands)]

下面这种写法不仅是在算法实现上简洁,也更符合日常生活中的情况:谁打牌会每次抽牌的时候都随机选取啊,肯定是先把整个牌组打乱然后每人给n张牌嘛。

四、测试

wikipedia给出了每一种牌型出现的概率。其中最罕见的同花顺概率为0.0015%,最常见的杂牌出现概率为50.11%。我们可以通过多次运行程序得到所有牌型的出现频率,如果与wikipedia的结果一致,则说明我们的程序是正确的。那么,我们应该运行程序多少次呢?
尽管次数多多益善,但实际中必须考虑对机器的负担。关键是让最罕见的牌型也出现足够多的次数,以此保证结果的稳健性。我们可以期望让同花顺出现10次左右,则程序应运行10 / 0.0015% 次,即大约700,000次。

五、重构

hand_rank函数重复用到了好多次rank,犯了自我重复的忌讳:有没有四张同点数的牌?哦,没有,那有没有三张同点数的牌?哦,也没有...那不如一开始就算清楚手里有哪些点数的牌,各自有几张。

def group(items):
    groups = [(items.count(x), x) for x in set(items)]
    return sorted(groups, reverse=True) # 把数量最多的放在最前面,数量相同的话,将点数最大的放在前面


def hand_rank(hand):
    groups = group(['--23456789TJQKA'.index(r) for r,s in hand])
    counts, ranks = unzip(groups)  #7 10 7 9 7 => (3, 1, 1), (7, 10, 9)
    if ranks == (14, 5, 4, 3, 2):
        ranks = (5, 4, 3, 2, 1)  # 特殊情况下的规则
    straight = (len(ranks) == 5) and (max(ranks) - min(ranks) == 4)
    flush = (len(set([s for r, s in hand])) == 1)
    return (9 if (5,) == counts else
            8 if straight and flush else
            7 if (4, 1) == counts else
            6 if (3, 2) == counts else
            5 if flush else
            4 if straight else
            3 if (3, 1, 1) == counts else
            2 if (2, 2, 1) == counts else
            1 if (2, 1, 1, 1) == counts else
            0), ranks

这样做不仅效率更高,还清楚地展示了德州扑克的特点:它有序地拆分了数字5。
5 = 4 + 1
   = 3 + 2
   = 3 + 1 + 1
   = 2 + 2 + 1
   = 2 + 1 + 1 + 1
   = 1 + 1 + 1 + 1 + 1。

你可能感兴趣的