ACM通信
研究突出了
技术视角:解决不完全信息博弈
对游戏的研究和计算机科学本身一样古老。巴贝奇、图灵和香农设计了下棋的算法和硬件。博弈论始于卡牌游戏和国际象棋中的最优策略问题，后来被冯·诺伊曼发展为一种正式的系统。国际象棋后来成为果蝇或者是普通果蝇，它是人工智能研究中被研究最多的生物。国际象棋和其他游戏的早期成功塑造了AI的新兴领域:许多最初用于游戏的规划算法成为后续研究的支柱;强化学习最初是为下棋程序开发的;游戏程序的表现也经常被用来衡量人工智能的进展。
这项研究的大部分集中在完美信息博弈上，在这种博弈中，所有的事件都被所有的玩家观察到，最终的程序在跳棋、国际象棋、奥赛罗、双陆棋和最近的围棋中击败了人类世界冠军。然而，现实世界中的许多应用程序都有不完美的信息:每个agent观察不同的事件。这就产生了欺骗的可能性和丰富的社交策略。不完全信息游戏提供了这些社交互动的一个缩影，同时将现实世界的混乱抽象化。
在不完全信息博弈中，扑克以其巨大的知名度和策略深度成为研究最广泛的博弈。人类玩的最小的竞争变体，也是电脑玩的最广泛的一种，是双人游戏，被称为“抬头限位扑克”(HULHE)。在这种游戏中，每个玩家除了持有五张公共牌外，还持有两张私人牌。对这一博弈的20年研究已经产生了强大的方法，如反事实后悔最小化(CFR)，以逼近纳什均衡。几年前，一个名为polarisis的程序由以下论文的许多作者创建，在HULHE中首次击败了一个人类职业扑克玩家。
用于解决扑克游戏的方法相当普遍，因此其潜在应用范围远不止这一种游戏。
然而，“北极星”还远远不够完美;事实上，回想起来，它是可以利用的，因为它做了很大的近似。剩下的一个明显的问题是，一个“近乎完美”的解决方案是否可以成为一个如此接近纳什均衡的基本策略，以至于它在玩家的一生中都无法被区分。
下面的文章将把之前工作中使用的CFR方法进一步提升。通过一些创新和几百台机器年的计算，他们能够找到一个近乎完美的HULHE解决方案。他们的解决方案还提供了对游戏本身的洞察，显示出庄家拥有显著优势，看似糟糕的手牌应该经常被玩。
对于扑克游戏来说，超越HULHE的下一步是无限扑克，它有更大的行动空间。这一点最近也被破解了，Libratus(来自CMU)和DeepStack(同样来自阿尔伯塔)程序都使用cfr变体击败了人类专业人员，尽管接近完美的解决方案仍然无法实现。最后的挑战将是人类最广泛使用的变体:多人无限扑克。
用于解决扑克游戏的方法相当普遍，因此其潜在应用范围远不止这一种游戏。人类玩的许多其他不完全信息游戏，包括各种各样的纸牌游戏、桌游和电子游戏，都可以使用这些方法。此外，还有许多现实世界的应用，如拍卖、谈判和安全，在这些应用中，代理接收不同的信息，并必须做出一系列决定以最大化最终回报，因此与HULHE属于同一类不完全信息游戏。
解决一个问题在一个领域达到完美。已解决领域的边界是当前计算机能力的一个无可争议的衡量标准。现在，这一领域又向前迈出了重要的一步，第一次包含了一个具有挑战性的不完美信息游戏。
数字图书馆是由计算机协会出版的。版权所有©2017 ACM股份有限公司
没有发现记录