一种新的计算机算法可以近乎完美地玩最流行的扑克变体之一。其创造者表示，它实际上“不可能在公平游戏中输给任何对手”。
这超越了计算机程序击败顶尖人类玩家的成就，正如IBM的国际象棋程序“深蓝”在1997年对阵当时的国际象棋世界冠军加里·卡斯帕罗夫时所做的那样。由计算机科学家迈克尔·鲍林及其在加拿大埃德蒙顿阿尔伯塔大学的同事，以及芬兰软件开发人员奥斯卡里·塔梅林设计的扑克程序，在所有意图和目的上都表现得完美无缺。
这意味着这种特定的扑克变体，称为单挑无限注德州扑克 (HULHE)，可以被认为是已被解决。该算法在一篇发表于《科学》杂志的论文中进行了描述。
支持科学新闻事业
如果您喜欢这篇文章，请考虑通过以下方式支持我们屡获殊荣的新闻事业 订阅。通过购买订阅，您正在帮助确保有关塑造我们当今世界的发现和思想的具有影响力的故事的未来。
作者们计算出的策略非常接近完美，“以至于对这个游戏的进一步研究变得毫无意义”，位于加利福尼亚州门洛帕克的计算机扑克研究员埃里克·杰克逊说。
“我认为，对于专家来说，如此庞大的一个游戏这么快就被解决，会让他们感到惊讶，”杰克逊补充道。
之前已经有一些其他流行的游戏被解决了。特别是，在2007年，来自阿尔伯塔大学同一计算机科学系的团队——包括最新研究的合著者尼尔·伯奇——破解了跳棋，也称为国际跳棋。
但扑克比跳棋更难解决。国际象棋和跳棋是完全信息博弈的例子，在完全信息博弈中，玩家完全了解所有过去的事件和游戏中的当前情况。相比之下，在扑克中，玩家有一些事情不知道：最关键的是，其他玩家被发了什么牌。不完全信息博弈类别对经济学家和博弈论家尤其有趣，因为它包括实际问题，例如为拍卖和谈判寻找最佳策略。
抱歉
在扑克中，主要的挑战是处理游戏中可能出现的无数种玩法。鲍林和他的同事们研究了最流行的形式之一，称为德州扑克。只有两名玩家时，游戏变为单挑，当游戏具有固定的下注大小和固定的加注次数时，它是一个“限注”游戏。HULHE 可以达到 3.16 × 1017 个状态，以及玩家必须做出决定的 3.19 × 1014 个可能点。
鲍林和他的同事们设计的算法使其能够从经验中学习，达到冠军级技能需要进行超过 1,500 场比赛。一开始，它随机做出决定，但随后它通过为每个决定附加一个“遗憾”值来更新自己，具体取决于它的表现有多差。
这个过程被称为反事实遗憾最小化，已在自 2006 年以来举办的年度计算机扑克大赛中被广泛采用。但鲍林和他的同事们通过允许算法重新评估在早期训练轮次中被认为较差的决策，从而改进了它。
另一个关键的创新是处理开发和使用该策略所需的大量信息，这些信息大约为 262 太字节。如此大的数据量需要磁盘存储，而磁盘存储的访问速度很慢。研究人员找到了一种数据压缩方法，将数据量减少到更易于管理的 11 太字节，并且仅将磁盘存储的使用计算时间增加了 5%。
“我认为反事实遗憾算法是主要的进步，”英国曼彻斯特大学的计算机科学家乔纳森·夏皮罗说。“但他们还做了其他一些非常聪明的事情，使这个问题在计算上可行。”
虚张声势的游戏
作为其发展策略的一部分，计算机学会在其游戏中注入一定剂量的虚张声势。虽然虚张声势看起来像是游戏中非常人性化的心理因素，但它实际上是博弈论的一部分——并且通常是计算机扑克的一部分。“虚张声势从游戏的数学原理中自然而然地产生，”鲍林说，你可以计算出你应该多久虚张声势才能获得最佳结果。
当然，没有扑克算法可以从数学上保证赢得每场比赛，因为该游戏包含很大的机会成分，这取决于你拿到的牌。但鲍林和他的同事们已经证明，他们的算法在长期来看总是会赢。
这个问题只是研究人员所说的“基本上已解决”，这意味着在理论上，计算机可能因技能而非机会而被击败的边际极小。但在实践中，这个边际可以忽略不计。
鲍林说，这种方法可能在人们必须在信息不完整的情况下做出决定的现实生活中很有用——例如，用于管理投资组合。该团队现在正专注于将他们的方法应用于医疗决策，与糖尿病专家合作。
本文经许可转载，首次发表于 2014 年 1 月 8 日的《自然》杂志。 更多内容： 物理学家揭示德州扑克的秘密