前言:
最近在研究德州扑克的AI, 也想由浅入深的看下, 在网上找了一圈, 发现很多文章都提到了一篇文章: Programming Poker AI. 仔细拜读了一下, 觉得非常不错. 这里作下简单的翻译工作, 可能加些自己的一些理解, 权当做一回大自然的搬运工, ^_^.
扑克数据模型抽象(Poker Data Type):
本文的作者倾向于使用位/字节级别来描述牌的数据模型(Hand=玩家手牌+公共牌), 也算一种高阶的抽象.
花色(Suit), 其值范围为0..3, 并假定梅花(Clubs)=0, 方块(Diamonds)=1, 红心(Hearts)=2, 黑桃(Spades)=3.
等级(rank), 其值范围为0..12, 赋予 2(deuce)=0, 3=1, ..., King=11, Ace=12.
牌(Card)其就对应一个0..51的整数, 三者满足如下等式:
card = suit*13 + rank.
Suit = card/13
Rank = card%13 Hand就可以用一个52bit的表示, 其中每一位都代表一个具体的牌. 可以借用4个16位字节来简单实现, 其中每个16位字节(word)覆盖一组花色牌.
对于牌类型(Hand Type), 这边设定:
高牌(no pair) = 0
一对(pair) = 1
两对(two pair) = 2
三条(trips) = 3
顺子(straight) = 4
同花(flush) = 5
葫芦(full house) = 6
金刚(quads) = 7
同花顺(straight flush) = 8注: 这边的Hand, 我的理解是对应玩家手牌+公共牌组合后的结果.
牌力编码(Encoding Hand Values):
牌力的编码可以用32位正整数来标识, 其值的大小和牌力是正相关.
牌力编码设计为6个半字节(4位)的组合, 最高的半字节代表牌类型, 接下来的5个半字节代表依序的数值.
样例一: AH,QD,4S,KH,8C 是高high牌型, 所以牌型半字节为0. 数值排序为(A, K, Q, 8, 4), 其经值转换后为(12, 11, 10, 6, 2). 用16进制来表示, 则变为(C, B, A, 6, 2). 最终的32位整数为: 0x000CBA62.
样例二: 4D,JD,3D,4C,AD 是一对牌型, 所以牌型半字节为1. 数值排序为(4, A, J, 3), 16进制表示为(2, C, 9, 1). 最终的32位整数位: 0x0012C910.
样例三: 7C,6C,5C,4C,3D 是顺子牌型, 所以牌型半字节为4. 数值排序(7), 16进制表示为(5). 最终的32位整数位: 0x00450000. 注: 顺子类型选取最高的数值代表.
结合这些样例, 你会发现, 其牌力和代表的数值, 是符合正相关的. 因此牌力的比较变得非常的容易.
计算牌力(Calculating Hand Values):
我们需要定义一个函数, 能够快速的计算hand到牌力值的转换. 这边提供了一些思路.
比如同一花色的13位可以有8192种组合(2的13次方=8192), 这个数值不大. 它给我们了一种思路去优化计算, 就是提供一个预计算好的8K大小的table表, 用于加速评估. 比如快速找到同花, 顺子等等.
再比如计算每个牌数的不同花色数, 利用有不同花色的rank, 然后快速确定牌型.
这个函数最终涉及按位操作, 表查询和简单比较, 那它的性能将非常的快.
计算胜率(Calculating Hand Strength):
胜率(HS)是一个0.0到1.0之间的一个数值, 它代表赢得当前局的概率. 比如HS=0.33意味着, 33%的概率赢得胜率.
这边胜率计算方式, 采用了模拟法(俗称的蒙特卡洛算法). 比如随即模拟1000次, 你赢得423局, 那么你的HS为423/1000=0.423.
这个模拟过程, 可以用如下伪代码来表示:
Create a pack of cards
Set score = 0
Remove the known cards (your hole cards, and any community cards)
Repeat 1000 times (or more, depending on CPU resources and desired accuracy)
Shuffle the remaining pack
Deal your opponent's hole cards, and the remaining community cards
Evaluate all hands, and see who has the best hands
If you have the best hand then
Add 1/(number of people with the same hand value) to your score (usually 1)
End if
end repeat
Hand Strength = score/number of loops (1000 in this case).
真实的胜率评估可能要比这要复杂, 你需要考虑其他玩家位置, 行为, 筹码量, 盲注等. 所以计算胜率的过程, 需要一定程度的修改. 当然这是个开放性的话题.
底池赔率(Pot Odds):
底池赔率是指你的加注/跟注和最终底池的比例值.
比如你加注$20, 加注前底池总额为$40. 那么底池赔率为20/(40+20)=0.333.
收益率(Rate Of Return):
收益率也可以称为回报率, 我们如下定义它:
Rate Of Return = Hand Strength / Pot Odds.
决策(The Fold/Call/Raise Decision):
定义FCR为每一轮棋牌/跟住/加注的策略行动. 同时定义RR为回报率(Rate Of Return).
If RR < 0.8 then 95% fold, 0 % call, 5% raise (bluff)
If RR < 1.0 then 80%, fold 5% call, 15% raise (bluff)
If RR <1.3 the 0% fold, 60% call, 40% raise
Else (RR >= 1.3) 0% fold, 30% call, 70% raise
If fold and amount to call is zero, then call. 对于上面的阈值, 可以适当的进行调整.
同时这边也加入一些模糊策略, 包括在牌力不强情况下的诈唬.
注: 这边的诈唬, 某种角度也可以理解为半诈唬, 是自带防守, 就算诈唬失败依旧有机会逆转.
筹码保护(Stack Protection):
当你的筹码很深且盲注很小时, 上述的简单规则会表现的很出色. 但是自身处于短筹或者盲注变高时, 需要做些保护策略, 否则很容易All-In而失去所有.
比如你手牌为AD, 2D, 此时公共牌为QC, KC, 2C. 此时你2一对, 但对手可能是同花牌. 如果底池为$500, 而对家raise $100. 刚好你筹码只有$100. 这种情况下, 你的Pot Odds(底池赔率)为100/(500+100)=0.1666, HS(胜率)为0.297. 这样RR=0.297/0.1666=1.8, 按照上述决策, 应该call. 但是这种情况下, 你有70%的大概率会失去所有, 请不要这样决策.
为了处理这种情况, 引入一个简答的启发式条件: 除非大概率胜率, 否则不轻易压上全部/大部分筹码.
添加如下规则:
if (stack- bet) < (blind * 4) and (HS < 0.5) then fold
更多的工作(More Work):
当前的AI策略, 还有如下需要加强的地方:
1). 翻前手牌胜率预估(Pre-flop hand strength tables)
2). 对手模型(Opponent modeling)
3). 隐含赔率(Implied Odds)
4). 个性化建模(Personality modeling)
5). 基于位置的策略(Positional play)
6). 概率搜索空间(Probabilistic search space)
7). 游戏理论和纳什均衡(Game theory and Nash Equilibrium)
AI测试:
总的来说, AI效果还是很赞的. 包括网上的很大大拿, 实现了该算法之后, 都竖起了大拇指. 当然这个算法, 遇到蛮不讲理的玩家, 把把All In, 它的弃牌率有些高. 其实真实玩家去玩, 也会是类似的囧境, 只不过人是可以根据对手的打法动态的调整策略, 这一点确实是该AI算法的不足. 还有就是对玩家的反raise, 该算法没有相应策略应对.
评价:
其实这个AI算法, 最让我眼前一亮的, 其实是它的数据模型抽象, 以及牌力值函数设计, 对于快速计算也提供一种很好思路, 确实很赞. 算法本身借助蒙特卡洛算法, 隐含了当前牌力/发展面(抽牌命中率), 对手的可能牌力分布, 这些综合的因素, 完美而简洁地现实了效果. 总的来说, 这是一个很好的文章, 其数据模型可被后续很多AI算法继续沿用.
个人站点:
个人游戏作品集站点(尚在建设中...): www.mmxfgame.com