Abstraction for Solving Large Incomplete-Information Games
Abstraction for Solving Large Incomplete-Information Games
复制标题
求解大型不完全信息博弈的抽象
DOI：
--
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
T. Sandholm
中科院分区：
文献类型：
--
作者：
T. Sandholm
大多数现实世界的游戏和许多娱乐游戏都是不完全信息的游戏。在过去的十几年里，抽象已经成为解决大型不完全信息游戏的关键推动力。首先，对游戏进行抽象，生成一个在策略上与原始游戏相似的更小的抽象游戏。其次，在抽象博弈中计算近似均衡。第三，将抽象博弈的策略映射回原始博弈。在本文中，我将回顾该领域的主要发展。我提出了抽象游戏的原因，并指出抽象病理学的问题。然后，我回顾了信息抽象和动作抽象的实用算法。然后，我涵盖了最近的理论突破，从抽象的游戏，当在原来的游戏测量的战略的质量产生的界限。然后，我讨论了如何反向映射到抽象的对手的行动，如果对手作出的举动，是不是在抽象。最后，我讨论了当前和未来研究的其他主题。
Most real-world games and many recreational games are games of incomplete information. Over the last dozen years, abstraction has emerged as a key enabler for solving large incomplete-information games. First, the game is abstracted to generate a smaller, abstract game that is strategically similar to the original game. Second, an approximate equilibrium is computed in the abstract game. Third, the strategy from the abstract game is mapped back to the original game. In this paper, I will review key developments in the field. I present reasons for abstracting games, and point out the issue of abstraction pathology. I then review the practical algorithms for information abstraction and action abstraction. I then cover recent theoretical breakthroughs that beget bounds on the quality of the strategy from the abstract game, when measured in the original game. I then discuss how to reverse map the opponent's action into the abstraction if the opponent makes a move that is not in the abstraction. Finally, I discuss other topics of current and future research.