优化德州扑克蒙特卡罗模拟手牌评估算法

Question

优化德州扑克蒙特卡罗模拟手牌评估算法

3

我已经写了一个德州扑克的均衡器作为一个爱好项目。它的功能是正确的，但还有一件事我不太满意：在模拟手牌的整个过程中，评估手牌的过程约占用35%的时间。与迭代和克隆大型数组等其他操作相比，这似乎相当耗时。有没有什么想法可以使其更加高效呢？以下是代码:

    private static int getHandvalue(List<Card> sCards)
    {

        // --- Auf Straight / Straight Flush prüfen ---
        if ((sCards[0].Value - 1 == sCards[1].Value) && (sCards[1].Value - 1 == sCards[2].Value) && (sCards[2].Value - 1 == sCards[3].Value) && (sCards[3].Value - 1 == sCards[4].Value))
        {

            if ((sCards[0].Color == sCards[1].Color) && (sCards[1].Color == sCards[2].Color) && (sCards[2].Color == sCards[3].Color) && (sCards[3].Color == sCards[4].Color))
                return (8 << 20) + (byte)sCards[0].Value; // Höchste Karte Kicker

            else
                return (4 << 20) + (byte)sCards[0].Value; // Höchste Karte Kicker (Straight)

        }

        // --- Auf Wheel / Wheel Flush prüfen ---
        if ((sCards[4].Value == Card.CardValue.Two) && (sCards[3].Value == Card.CardValue.Three) && (sCards[2].Value == Card.CardValue.Four) && (sCards[1].Value == Card.CardValue.Five) && (sCards[0].Value == Card.CardValue.Ace))
        {

            if ((sCards[0].Color == sCards[1].Color) && (sCards[1].Color == sCards[2].Color) && (sCards[2].Color == sCards[3].Color) && (sCards[3].Color == sCards[4].Color))
                return(8 << 20) + (byte)sCards[1].Value; // Zweithöchste Karte Kicker

            else
                return(4 << 20) + (byte)sCards[1].Value; // Zweithöchste Karte Kicker (Straight)

        }


        // --- Auf Flush prüfen ---
        if ((sCards[0].Color == sCards[1].Color) && (sCards[1].Color == sCards[2].Color) && (sCards[2].Color == sCards[3].Color) && (sCards[3].Color == sCards[4].Color))
            return (5 << 20) + ((byte)sCards[0].Value << 16) + ((byte)sCards[1].Value << 12) + ((byte)sCards[2].Value << 8) + ((byte)sCards[3].Value << 4) + (byte)sCards[4].Value;


        // --- Auf Vierling prüfen ---
        if (((sCards[0].Value == sCards[1].Value) && (sCards[1].Value == sCards[2].Value) && (sCards[2].Value == sCards[3].Value)) || ((sCards[1].Value == sCards[2].Value) && (sCards[2].Value == sCards[3].Value) && (sCards[3].Value == sCards[4].Value)))
            return (7 << 20) + (byte)sCards[1].Value; // Wert des Vierlings (keine Kicker, da nicht mehrere Spieler den selben Vierling haben können)


        // --- Auf Full-House / Drilling prüfen ---
        // Drilling vorne
        if ((sCards[0].Value == sCards[1].Value) && (sCards[1].Value == sCards[2].Value))
        {

            // Full House
            if (sCards[3].Value == sCards[4].Value)
                return (6 << 20) + ((byte)sCards[0].Value << 4) + (byte)sCards[3].Value; // Drilling (höher bewerten)

            // Drilling
            return (3 << 20) + ((byte)sCards[0].Value << 8) + ((byte)sCards[3].Value << 4) + (byte)sCards[4].Value; // Drilling + Kicker 1 + Kicker 2

        }

        // Drilling hinten
        if ((sCards[2].Value == sCards[3].Value) && (sCards[3].Value == sCards[4].Value))
        {

            // Full House
            if (sCards[0].Value == sCards[1].Value)
                return (6 << 20) + ((byte)sCards[2].Value << 4) + (byte)sCards[0].Value; // Drilling (höher bewerten)

            // Drilling
            return (3 << 20) + ((byte)sCards[2].Value << 8) + ((byte)sCards[0].Value << 4) + (byte)sCards[1].Value; // Drilling + Kicker 1 + Kicker 2

        }

        // Drilling mitte
        if ((sCards[1].Value == sCards[2].Value) && (sCards[2].Value == sCards[3].Value))
            return (3 << 20) + ((byte)sCards[1].Value << 8) + ((byte)sCards[0].Value << 4) + (byte)sCards[4].Value; // Drilling + Kicker 1 + Kicker 2                            


        // --- Auf Zwei Paare prüfen ---
        // Erstes Paar vorne, zweites Paar mitte
        if ((sCards[0].Value == sCards[1].Value) && (sCards[2].Value == sCards[3].Value))
            return (2 << 20) + ((byte)sCards[0].Value << 8) + ((byte)sCards[2].Value << 4) + (byte)sCards[4].Value; // Erstes Paar + Zweites Paar + Kicker

        // Erstes Paar vorne, zweites Paar hinten
        if ((sCards[0].Value == sCards[1].Value) && (sCards[3].Value == sCards[4].Value))
            return (2 << 20) + ((byte)sCards[0].Value << 8) + ((byte)sCards[3].Value << 4) + (byte)sCards[2].Value; // Erstes Paar + Zweites Paar + Kicker

        // Erstes Paar mitte, zweites Paar hinten
        if ((sCards[1].Value == sCards[2].Value) && (sCards[3].Value == sCards[4].Value))
            return (2 << 20) + ((byte)sCards[1].Value << 8) + ((byte)sCards[3].Value << 4) + (byte)sCards[0].Value; // Erstes Paar + Zweites Paar + Kicker


        // --- Auf Paar prüfen ---
        // Paar vorne
        if (sCards[0].Value == sCards[1].Value)
            return (1 << 20) + ((byte)sCards[0].Value << 12) + ((byte)sCards[2].Value << 8) + ((byte)sCards[3].Value << 4) + (byte)sCards[4].Value; // Paar + Kicker 1 + Kicker 2 + Kicker 3

        // Paar mitte-vorne
        if (sCards[1].Value == sCards[2].Value)
            return (1 << 20) + ((byte)sCards[1].Value << 12) + ((byte)sCards[0].Value << 8) + ((byte)sCards[3].Value << 4) + (byte)sCards[4].Value; // Paar + Kicker 1 + Kicker 2 + Kicker 3

        // Paar mitte-hinten
        if (sCards[2].Value == sCards[3].Value)
            return (1 << 20) + ((byte)sCards[2].Value << 12) + ((byte)sCards[0].Value << 8) + ((byte)sCards[1].Value << 4) + (byte)sCards[4].Value; // Paar + Kicker 1 + Kicker 2 + Kicker 3

        // Paar hinten
        if (sCards[3].Value == sCards[4].Value)
            return (1 << 20) + ((byte)sCards[3].Value << 12) + ((byte)sCards[0].Value << 8) + ((byte)sCards[1].Value << 4) + (byte)sCards[2].Value; // Paar + Kicker 1 + Kicker 2 + Kicker 3


        // --- High Card bleibt übrig ---
        return ((byte)sCards[0].Value << 16) + ((byte)sCards[1].Value << 12) + ((byte)sCards[2].Value << 8) + ((byte)sCards[3].Value << 4) + (byte)sCards[4].Value; // High Card + Kicker 1 + Kicker 2 + Kicker 3 + Kicker 4

    }

这个方法会为扑克牌中每一种有序的5张牌组合返回一个精确值。它是由另一个方法调用的：

    private static int getHandvalueList(List<Card> sCards)
    {

        int count = sCards.Count;
        if (count == 5) return getHandvalue(sCards);

        int HighestValue = 0;
        Card missingOne;
        int tempValue;

        for (int i = 0; i < count - 1; i++)
        {

            missingOne = sCards[i];
            sCards.RemoveAt(i);

            tempValue = getHandvalueList(sCards);
            if (tempValue > HighestValue) HighestValue = tempValue;

            sCards.Insert(i, missingOne);

        }

        missingOne = sCards[count - 1];
        sCards.RemoveAt(count - 1);

        tempValue = getHandvalueList(sCards);
        if (tempValue > HighestValue) HighestValue = tempValue;

        sCards.Add(missingOne);
        return HighestValue;

    }

这个递归方法返回所有可能的五张牌中的最高点数。这个方法由最终的公共方法调用：

    public static int GetHandvalue(List<Card> sCards)
    {

        if (sCards.Count < 5) return 0;
        sCards.Sort(new ICardComparer());
        return getHandvalueList(sCards);

    }

它最多可以发出7张牌。

更新

目前为止：每次公共函数被调用时都会传递7张牌（这在大多数情况下是这样），它必须调用手牌评估方法21次（每个可能的5张牌组合一次）。

我考虑了将每个可能的5到7张牌的值缓存到哈希表中，然后只需查找它。但如果我没错的话，它将不得不存储超过133,784,560个32位整数值，约为500MB。

有什么好的哈希函数可以将每个可能的组合分配给一个数组索引吗？

在此创建了一个新问题：Hashfunction to map combinations of 5 to 7 cards

更新：有关已接受答案的进一步改进，请参见： Efficient way to randomly select set bit

- Martin Tausch

如果您使用的是高级别的Visual Studio，请使用性能向导查看时间花费在哪里。否则，您可以通过收集计时信息来自行完成其中的一些工作。如果不知道哪些部分较慢，就无法真正进行优化。 - crashmstr

好的，我会这样做并更新问题。 - Martin Tausch

我在编码时发现最快的方法是预先计算所有可能的手牌（5张牌），并将其存储在数据库中（例如在安装时）。执行时的简单请求会给您一个值和/或您的手牌列表中的最大值。 - Xaruth

来到了相同的想法^^看一下这个问题：http://stackoverflow.com/questions/22477192/hashfunction-to-map-combinations-of-5-to-7-cards - Martin Tausch

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- tmyklebu · Accepted Answer

我以前写过一个相当快的扑克牌手评估器。我使用了与你不同的表示方法，我认为这是性能的关键。

我用一个64位整数来表示最多7张牌的手牌；第4位是红心二，第5位是方块二，第6位是黑桃二，第7位是梅花二，第8位是红心三，以此类推。

首先检查同花顺；形成hh = h & (h>>4) & (h>>8) & (h>>12) & (h>>16)。如果hh非零，则在其高位开始有一个同花顺。

然后检查四条；形成hh = h & (h>>1) & (h>>2) & (h>>3) & 0x1111...1。如果hh非零，则你拥有四条。

此时，您想找出哪些等级有三条和哪些等级有对子。类似于四条的情况，形成位掩码，告诉您哪些等级至少有三张牌，哪些等级至少有两张牌，哪些等级至少有一张牌。（考虑对手牌的每个半字节进行排序。）如果popcount(threes) + popcount(twos) >= 2，则你有一个满堂红要找。

同花和顺子条件很容易检查。此时，三条、两对和一对条件也很容易检查。

这种方法的一个好处是，它可以直接返回表示手牌等级的整数，将手牌比较减少为一堆位操作来预处理手牌，然后进行单个整数比较。（正如你现在所做的那样，现在我再看一遍你的帖子。）如果正确编写，它还可以直接操作7张牌的手牌，消除了迭代手牌所有5张子集的需要。