扑克牌-蒙特卡罗仿真中手牌评估算法的优化
本文关键字:评估 算法 优化 蒙特卡罗 仿真 扑克牌 | 更新日期: 2023-09-27 17:50:29
我为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 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。
什么可能是一个好的哈希函数来分配每个可能的组合到一个数组索引?
创建了一个新的问题:哈希函数映射5到7张牌的组合
更新:关于公认答案的进一步改进,请看:随机选择设置位的有效方法
我以前写过一个相当快的扑克牌手值评估器。我用了和你完全不同的表达方式,我认为这是表现的关键。
我用64位整数表示最多7张牌的手;第4位是红桃2,第5位是方块2,第6位是黑桃2,第7位是梅花2,第8位是红桃3,以此类推。
首先检查是否直接冲洗;形式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张牌的所有子集的需要。