IBM名为“深蓝”的电脑击败世界象棋冠军加里·卡斯帕罗夫已经将近20年了。自从1997年那个令人震惊的时刻以来,计算机算法已经通过分析所有可能的游戏并且从每个游戏的开始为每个动作找出完美的策略解决了诸如连接四和跳棋之类的游戏。未来的程序甚至可能掌握古老的围棋游戏。但是电脑在持续赢牌方面面临着不同的挑战,因为每个玩家都有两张隐藏的牌,代表了对手隐藏的信息。通过解决诸如扑克之类的“不完美信息游戏”,计算机算法还可以潜在地处理具有相似不确定水平的真实场景。
加拿大阿尔伯塔大学计算机科学博士生尼尔·伯奇(Neil Burch)说:“解决不完美信息游戏需要计算机处理不知道游戏状态等附加复杂问题,比如不知道对手的手。”这种技术需要更多的计算机内存和计算能力。
Burch和他的合著者在发表在2014年1月8日的《科学》杂志上的一篇论文中阐述了他们的算法的解决方案。在计算机科学方面,它只是一个“薄弱”的解决方案,针对一个特定版本的德克萨斯举行'他们只有两个玩家,固定的赌注大小和固定的赌注增加数量。但是它仍然足够好,以至于在扑克游戏的一生中,从统计学意义上来说,几乎不可能将算法的解与完美的游戏区分开来。这篇论文将游戏的终身定义为在70年的时间里,每天12小时每小时200次扑克。
卡内基梅隆大学的计算机科学家托马斯·桑德霍尔姆说:“虽然对于更大的不完美信息游戏也已经计算出了强有力的策略,但据我所知,这是迄今为止最大型的不完美信息游戏,也是人类首次竞相玩的游戏,现在已经基本解决了。”在匹兹堡,在《科学》杂志的一篇透视文章中。
该算法由其创建者命名为CFR+,它使用了一种叫做反事实后悔最小化(CFR)的技术的改进版本。过去的CFR算法试图通过在每个决策点使用几个步骤来解决扑克:提出代表不同游戏结果的反事实值;应用遗憾最小化方法来找出导致最佳结果的策略;以及利用所有过去的策略平均化最新策略。
但是过去的CFR算法实际上从来没有试图解决德州扑克SD555点卡姆游戏中正面限制的全局问题,因为需要大量的内存;大约262TB的内存。这大约是iPhone 6可用的1G内存的268288倍。
相反,CFR算法解决了简化版本的扑克,并使用所得到的策略不完全地玩扑克游戏的完整版本。这种算法经常在一年一度的计算机扑克比赛中相互竞争,该比赛正值人工智能促进协会的主要会议。
据了解CFR+算法在以下几个方面对以往的CFR算法进行了改进。一个变化是,它如何使用稍微不同的遗憾最小化技术来在每一步中选择最佳策略。另一个变化涉及跳过通常的步骤,将最新策略与之前的所有策略平均化;该算法只是使用最新的策略。