人工智能当前,棋牌游戏留给人类的堡垒不多了

最近半年在写一个棋牌游戏的环境:RoomAI,目的是为方便自己和他人在棋牌游戏 AI 方面进行一些探索和研究。在 RoomAI 中,选手获得游戏环境给出的信息,当前选手选择合适的动作,游戏环境根据该动作推进游戏逻辑;重复上述过程,直到分出胜负;整个过程如下所示。

在开发过程中,查看了一些棋牌游戏相关的资料,在这里分享给大家。

1. 棋牌游戏

之前为了写一个棋牌游戏相关的专利,去查棋牌游戏的定义,发现搜狗百科 “棋牌游戏是棋类游戏和牌类游戏的统称”。这和没说有什么区别,囧。但这也说明,棋类游戏和牌类游戏是不同的,它们有其鲜明的特点。棋类游戏是明牌,专业说法是完全信息游戏。典型的棋类游戏有中国象棋、国际象棋和围棋等。牌类游戏是暗牌,专业说法是非完全信息游戏。典型的牌类游戏有斗地主、七鬼五二三、桥牌和德州扑克等。

另外,棋类游戏的游戏形式比较简单,一般是两位选手一对一对决。牌类游戏的游戏形式多种多样,不仅有两位选手一对一对决,还有多位选手博弈,甚至允许或者要求某些选手组成同盟。比如,斗地主有三位选手,两位农民对战一位地主。

2. 棋牌游戏和人工智能

信息是否完全决定一款游戏是棋类游戏还是牌类游戏,也决定了其 AI 算法。

2.1. 基于搜索的棋类游戏 AI

棋类游戏的典型代表是国际象棋和围棋,它们分别由 DeepBlue[1] 和 AlphaGo[3] 解决。DeepBlue 建立在极大极小值搜索 (max-min search) 基础上。极大极小值搜索在当前局面下展开游戏的树状结构,当前玩家节点选择价值最大的分支(极大), 对手节点选择价值最小的分支(极小), 其流程如下所示。

因为国际象棋复杂度很高,极大极小值搜索不可能搜索到叶子节点。DeepBlue 解决方案是限制搜索深度,超过搜索深度的节点用精心挑选的评估函数计算其价值。DeepBlue 的搜索深度为 12 步棋,而一名人类象棋专家大约搜索10步棋。

AlphaGo 建立在蒙特卡洛树搜索 (Monte Carlo Tree Search, MCTS) 基础上。 MCTS 的搜索结构是树状结构,如下所示。

树中每一个节点 s 代表了一个围棋盘面,并带有两个数字。一个是访问次数N(s),另一个质量度Q(s),质量度Q(s)表示这个节点下 AlphaGo 的优势程度。当对手落了一子,AlphaGo 迅速读入当前盘面,将之当作搜索的根节点,展开搜索。MCTS 搜索的流程如下图所示,一共分为四个步骤:

1. 选择 从根节点 R 开始,递归选择某个子节点直到达到叶子节点 L。我们选择子节点不应该乱选,而是应该选择那些优质的子节点。 2. 扩展 如果 L 节点上围棋对弈没有结束,那么可能创建一个节点 C。 3. 模拟 用价值网络和快速走子计算节点 C 的质量度。 4. 反向传播 根据 C 的质量度,更新它爸爸爷爷祖先的质量度。

上述搜索步骤反复进行,直到达到某个终止条件。搜索结束后,MCTS 选择根节点的质量度最高的子节点作为 AlphaGo 的走法。从上面描述来看,AlphaGo 建立在 MCTS 之殇,机器学习模主要用于减少搜索宽度和减少搜索深度两个方面。策略网络用于使得搜索朝着几个恰当的候选集中,从而减少了搜索宽度。价值网络和快速走子用在评估叶子节点质量度上,使得搜索就不用继续往下搜索,从而减少了搜索的深度。

2.2. 基于博弈论的牌类游戏 AI

牌类游戏中,选手不知道对手的私有信息,不能确定某个动作之后的状态,从而使用 maxmin search 和 MCTS 来求解。最近战胜德州顶级人类的 Libratus 是建立在反事实遗憾最小 (CounterFactual Regret Minimization, CRM)[4] 算法之上。 CRM 算法也是将游戏展开搜索。在某一个节点,当前玩家只能使用其知道的非完全信息,因此会造成不同节点的非完全信息一样。对于玩家来说,非完全信息相同的不同节点被归入同一个信息集合 (Information Set)。

如上图所示,在节点玩家按照上一轮得到的动作选择概率 p(action)Tp(action)T p(action)^{T},选择动作进入不同分支;搜索不同分支得到不同分支的价值(价值表示胜负、得分和奖励之类的效用);然后按照下面的公式更新。

(1)

其中 regretaction1regretaction1 regret_{action1} 表示不选择 action1 的遗憾值或者损失值。

CRM 被证明可以对纳什平衡建模,是一个强大算法。CRM 遍历所有节点,并保存所有非完全信息下不同动作的概率值。即使可以进行一些优化和压缩,CRM 也需要巨大的计算能力和存储空间。这就是为什么 Libratus 开发人员使用匹兹堡超级计算中心(PSC)新升级的超级计算机 Bridges 进行开发。

另一号称超过人类专家的德州 AI 是 DeepStack [5] 也是用了 CRM, 同时用深度学习模型近似所有非完全信息下不同动作的概率值。

3. 留给人类的堡垒们

几千年以来,棋牌游戏是人类智力的竞技场。值此人工智能大发展之际,人类用棋牌游戏构建了其中一条保卫人类智力优越感的防线。人类公元 1997 年,国际象棋首先被计算机系统深蓝攻陷,人们开始寄希望于复杂度奇高的围棋; 人类公元 2016 年 3 月,围棋被计算机系统 AlphaGo 攻破,因为国际象棋和围棋是完全信息游戏,人们又寄希望于非完全信息的德州扑克;不想不满一年,2017 年 1 月,计算机系统 Libratus 攻克了德州扑克。这段激动人心的历程是要载入人类(机器人)史的。但在当下,人类在这条防线上还拥有一些堡垒。

连围棋都被攻克了,完全信息的棋类游戏没有办法再担当人类堡垒之职,我们只能把目光放在牌类游戏中。虽然 Libratus 在德州扑克中超越了人类,但那只是两位选手对局情况。如果是多人对局的德州,我们就没有办法使用 CRM 了,需要设计不同的算法框架。按照 Tuomas Sandholm 教授本人的观点,那就是一个 “totally different story”。更进一步的情况,某些牌类游戏不仅允许多人对局,还允许或者要求某些选手之间合作。比如,斗地主有三位选手,两位农民对战一位地主。再比如桥牌和四国军棋,两位选手组成一队,两队进行对局。这些情况也是现有没有考虑过的问题。

4. 总结

随着计算机科学与技术的不断发展,人工智能在不同棋牌游戏中超过了人类,但还在一些游戏中探索。基于这个认知,我个人觉得在未来一段时间牌类游戏依然是一个有意思的点,因此想在上面做一些研究和探索。工欲善其事必先利其器,为了方便自己和他人,我开始开发 RoomAI。RoomAI 的目标是提供一些非完整信息游戏环境,目前已经支持德州和梭哈。

参考文献

[1] Campbell, Murray, A. Joseph Hoane, and Feng-hsiung Hsu. “Deep blue.” Artificial intelligence 134.1-2 (2002): 57-83. [2] 几种智能算法在黑白棋程序中的应用,柏爱俊 [3] Silver, David, et al. “Mastering the game of Go with deep neural networks and tree search.” Nature 529.7587 (2016): 484-489. [4] Neller, Todd W., and Marc Lanctot. “An Introduction to Counterfactual Regret Minimization.” (2013). [5] Morav?ík, Matej, et al. “Deepstack: Expert-level artificial intelligence in no-limit poker.” arXiv preprint arXiv:1701.01724 (2017).

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏镁客网

仅用3天,AlphaGo Zero就凭借自学以100:0击败AlphaGo,柯洁表示人类太多余了

1530
来自专栏量子位

德扑人机大战落幕:AI赢了200万美元,这里是一份超详细的解读

作者 | 量子位 舒石 ? △ 今日凌晨产生的人机大战最终结果 176万,美元。 经过20天的鏖战之后,四位顶级人类扑克高手,在这场德州扑克人机大战中,总共输给...

3265
来自专栏企鹅号快讯

解密!德扑界的AlphaGo:击败顶级德扑玩家的AI赌神Libratus

“AlphaGo退休了,我们还有赌神Libratus。” 今年上半年,AlphaGo多次升级连克人类高手,甚至以3:0一举击败如今世界排名第一的柯洁。而在德州扑...

24110
来自专栏企鹅号快讯

AlphaGo打败人类后,又打败了“自家兄弟”?

话说2017年人工智能发展的重大事件,那就是AlphaGo战胜棋手柯洁,并横扫了整个围棋界选手。在战胜柯洁后短短的五个月,谷歌deepmind团队在10月份公布...

2180
来自专栏奇点大数据

游戏AI小试牛刀(1)

现在大家在各种领域使用机器人的事情是越来越多,包括在家政领域和教学领域等等这些在我们身边每天都能接触到的领域。而游戏中使用AI也是一件非常有趣的事情。 为此,我...

3627
来自专栏企鹅号快讯

德州扑克被AI攻破?刚进行到围棋九路盘而已

德州扑克被AI攻克?才刚开始 作者:余小鲁 作者系理论物理博士,人工智能专家。新浪扑克学院特邀讲师 Sunday, 31 December 2017 余小鲁博士...

2369
来自专栏量子位

AI再乱围棋圈:“食言之战”柯洁落败;首例素人作弊引风波

去年12月底,曾经放言不再与AI进行正式比赛的柯洁,公开宣布“食言”。现在,这场柯洁的“实验之战”胜负已分。

741
来自专栏专知

【业界】你也能与AlphaGo谈笑风生了, AlphaGo教学工具上线

【导读】12月11日晚,大家期待已有的 AlphaGo教学工具正式上线了,DeepMind资深研究员黄士杰和DeepMind围棋大使樊麾在Facebook和其新...

3164
来自专栏新智元

【AlphaGo2.0乌镇首局击败柯洁】人机最伟大对弈剖解,超级AI阿老师将围棋3维化

【新智元发自中国乌镇】在围棋峰会开幕式致辞中,DeepMind CEO Demis 表示,樊麾已经成为 AlphaGo 开发团队中的一位重要成员。樊麾表示,自己...

2795
来自专栏量子位

柯洁食言:明年四月,再战AI

李根 发自 凹非寺 量子位 报道 | 公众号 QbitAI “我说不再跟AI下棋,现在食言了。” 刚刚,人类围棋第一人柯洁九段宣布:明年4月,将再次与围棋AI...

2863

扫码关注云+社区

领取腾讯云代金券