Geek
双人限注德州扑克已被程序破解
[-]
如果你认为 IBM 的国际象棋超级电脑深蓝(Deep Blue)很牛逼，那下面这个可要颠覆你的认知了——双人限注德州扑克玩法已被破解！在于世界上真正的德州扑克高手面对面切磋时，这个名为“仙王座”(Cepheus)的电脑程序可从不会输，不信你可以自己试试挑战它。
仙王座由芬兰的开发者 Oskari Tammelin 联合由计算机科学家 Michael Bowling 领头的，来自加拿大阿尔伯特大学(University of Albert)的研究组开发的，它的设计初衷就是为了打败所有前来挑战双人限注德州扑克的玩家。研究成果在很多方面都令人惊讶，其中最大的成就就是这个叫做“虚拟条件反悔最小化”("counterfactual regret minimization")的算法。在扑克人工智能领域，虚拟条件反悔最小化(以下将简称为 CRM )指的是电脑程序通过评估分析之前犯的错误而重新校准游戏策略的能力。德州扑克中的重要技巧，也是 CRM 中在最优化游戏策略时用到的一招就是诈唬(Bluffing)。
研究组的另一个成就则是他们的压缩方法(compression method)。在双人对战德州扑克中有 3.16 × 10的17次方种玩家可能碰到的局势以及 3.19 × 10的14次方种玩家需要做出选择的情况。要记录所有这些情况，在过去需要调用大约 262T 的存储空间——研究组将所需存储压缩到了 11T，这让程序真正流畅运行有了可能，只有在这时候算法才能真正帮助计算机实时调整出牌策略。
从每一局的概率上来说，仙王座偶尔还是会输(概率永远都存在，拿到一手烂牌加更烂的公牌，偶尔的败仗是难免的)，但从长远来看，仙王座基本都是胜局。援引自《自然》上的文章：
这意味着，德州扑克中的双人限注德州扑克算是被破解了...程序开发者的游戏策略时分接近完美，基本上未来已经没有必要再这上面再做文章了...破解扑克游戏比跳棋之类的难。国际象棋和跳棋是典型的完全信息博弈(perfect-information games)，玩家很清楚对手之前的一切动向和目前的局势，而扑克则相反：有很多信息玩家无法掌握，其中最致命的当然就是你不知道对方手中拿着什么牌。博弈论学者和经济学家历年来对这种不完全信息博弈很感兴趣，因为这其中的理论可以解决很多现实问题，比如拍卖场与谈判桌上的最优策略。
卡耐基梅隆大学的计算机科学家 Tuomas Sandholm 说这是目前被破解的最复杂的不完全信息博弈。猛击我可以进入项目主页亲自挑战仙王座！
[keep_beating via io9]