蒙特卡洛法求解“惯蛋”中“同花顺”出现的概率

蒙特卡洛法求解“惯蛋”中“同花顺”出现的概率

背景知识

“惯蛋”

“惯蛋”使用两幅标准扑克牌 (4*13+2/副), 有4个玩家, 每个玩家轮流随机抽取27张牌.

“同花顺”

“同花顺”为玩家所持有的牌中花色相同且数字连续的五张牌的组合. 同时, 10 J Q K A 为一种特殊的同花顺组合.

思路

采用蒙特卡洛随机数值模拟方法

若采用枚举法, 有 ${}^{108}{\mathrm{C}}_{27}=2.10\times 10^{25}$ 种牌的组合, 无法在有限时间内完成运算.

分步骤解决问题

Step 1

只有相同花色才可能组同花顺. 因此先将牌区分花色. 同时大等于5张牌才可能, 因此移除 (不考虑) 小于5张牌的花色.

Step 2

对于每一种花色:(即一个数组):

分别用两种方法计算其中的同花顺个数,取二者最大值.

• 方法一: 由10开始遍历,
  看10 J Q K A 是否都有一张或一张以上的牌. 若有, n(即用这种方法计算的同花顺的数量)加一, 并这5张牌数量-1. 循环此步骤直到按这种方法计算没有同花顺了(用Flag变量实现判断还有没有).
  再看0 … 4, 1 … 5, …, 8 … 12是否有一张或一张牌以上. 若有, n +1, 有的五张牌牌数-1.
• 方法二: 由A开始遍历. 其余同上. 开始方法二前须再次初始化牌数组,因为数组中的牌数量已在1中改变.

用两个方法的原因:
例如对于A 2 3 4 5 6 10 J Q K的序列, 由10开始遍历, 则得2组. 由A开始遍历,则得1组;
对于9 10 J Q K A 2 3 4 5的序列, 由10开始遍历, 则得1组. 由A开始遍历, 则得2组.

对于不同随机抽取的27张牌, 通过上述两个步骤, 计算出这27张牌中的同花顺的个数. 重复多次, 获得近似概率.

实验代码:

import random


class Solve:  # Start with 0, A
    def __init__(self):
        pass

    def update_card(self, cards):
        self.cards = cards

    def split_color_and_sort(self):

        self.splited = []

        color_0 = []
        color_1 = []
        color_3 = []
        color_2 = []

        for i in range(len(self.cards)):
            card = self.cards[i]
            if card[1] == 0:
                color_0.append(card[0])
            elif card[1] == 1:
                color_1.append(card[0])
            elif card[1] == 2:
                color_2.append(card[0])
            else:
                color_3.append(card[0])

        # color_0.sort()
        # color_1.sort()
        # color_2.sort()
        # color_3.sort()

        if len(color_0) > 4:
            self.splited.append(color_0)
        if len(color_1) > 4:
            self.splited.append(color_1)
        if len(color_2) > 4:
            self.splited.append(color_2)
        if len(color_3) > 4:
            self.splited.append(color_3)

    def has_n_in_splited(self):
        t_n = 0
        for splited_sub in self.splited:

            # Start with 1:
            n_start_with_1 = 0

            arr = [0 for i in range(13)]
            for card_no in splited_sub:
                arr[card_no] += 1

            arr.append(arr[0])

            while True:
                have_left = False
                for i in range(10):
                    flag = True
                    for j in range(5):
                        if arr[i + j] <= 0:
                            flag = False

                    if flag:
                        have_left = True
                        n_start_with_1 += 1
                        for j in range(5):
                            arr[i + j] -= 1
                        if i == 0:
                            arr[-1] -= 1
                        elif i == 9:
                            arr[0] -= 1
                if not have_left:
                    break

            # Start with 10
            n_start_with_10 = 0

            arr = [0 for i in range(13)]
            for card_no in splited_sub:
                arr[card_no] += 1

            for i in [9, 10, 11, 12, 0]:
                if arr[i] <= 0:  # No card
                    break
            else:
                # Continous
                n_start_with_10 += 1
                for i in [9, 10, 11, 12, 0]:
                    arr[i] -= 1

            while True:
                have_left = False
                for i in range(9):
                    flag = True
                    for j in range(5):
                        if arr[i + j] <= 0:
                            flag = False

                    if flag:
                        have_left = True
                        n_start_with_10 += 1
                        for j in range(5):
                            arr[i + j] -= 1
                if not have_left:
                    break

            t_n += n_start_with_1 if n_start_with_1 >= n_start_with_10 else n_start_with_10
        return t_n


def random_select(cards, n=27):
    _cards = cards[:]
    selected = []

    for i in range(n):
        # print(_cards)
        index = random.randint(0, len(_cards) - 1)
        selected.append(_cards[index])
        _cards.pop(index)

    return selected


whole = []
for color in range(4):
    for num in range(13):
        whole.append([num, color])
whole.append([-1, -1])
whole.append([-1, -1])
whole *= 2
print(whole)

rst = {}

S = Solve()

for i in range(100000):
    # print("W", whole)
    selected = random_select(whole)
    S.update_card(selected)
    S.split_color_and_sort()
    n = S.has_n_in_splited()

    if n in rst:
        rst[n] += 1
    else:
        rst.update({n: 1})

print(rst)

实验结果

重复$100,000$次, 获得输出

{0: 67352, 1: 29454, 2: 3123, 3: 71}

则