c# - 优化 Poker-Monte-Carlo-Simulation 的手牌评估算法

Question

我已经为 Hold'em Poker 编写了一个平衡器作为一个业余项目。它工作正常，但还有一件事我不满意:在整个模拟手的过程中，评估手的过程大约占用了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;

    }

此递归方法返回所有可能的 5 张牌组合的最大值。这个方法被最终的公共(public)方法调用:

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

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

    }

最多可交付 7 张卡片。

更新

到目前为止:每次调用 public 函数时有 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

Answer 1

我过去写过一个相当快的扑克手评估器。我使用了与您的完全不同的表示，我认为这是性能的关键。

我用一个 64 位整数表示了一手最多 7 张牌；位 4 是红心二，位 5 是方 block 二，六是黑桃二，七是梅花二，八是红心三，依此类推。

您首先检查同花顺；形成 hh = h & (h>>4) & (h>>8) & (h>>12) & (h>>16)。如果 hh 不为零，那么您的同花顺从高位开始。

然后检查四种类型；形成 hh = h & (h>>1) & (h>>2) & (h>>3) & 0x1111...1。如果 hh 是非零的，那么您就得到了一个 4。

在这一点上，您想要找出哪些行列具有同类三项，哪些行列具有对子。与同类四的情况类似，形成位掩码告诉您哪些等级至少有三张牌，哪些等级至少有两张牌，哪些等级至少有一张牌。 (考虑对手牌的每个半字节进行排序。)如果 popcount(threes) + popcount(twos) >= 2，您可以找到满屋子。

平直条件很容易检查。而且，在这一点上，同类三项、两对和配对条件也是如此。

这种方法的一个很好的特点是它可以直接返回一个代表手牌等级的整数，将手牌比较减少到一堆位摆弄以预处理手牌然后一个整数比较。 (正如您所做的那样，现在我再次查看了您的帖子。)如果编写得当，它还可以直接对 7 张牌进行操作，从而无需迭代手牌中 5 张牌的所有子集。