Playing Games with Algorithms: Algorithmic Combinatorial Game Theory
Playing Games with Algorithms: Algorithmic Combinatorial Game Theory
复制标题
用算法玩游戏：算法组合博弈论
DOI：
10.1007/3-540-44683-4_3
复制
发表时间：
2001
期刊：
影响因子：
--
通讯作者：
E. Demaine
中科院分区：
文献类型：
--
作者：
E. Demaine
组合博弈在算法和复杂性理论中引出了几个有趣的、清晰的问题，其中许多问题仍然是开放的。本文的目的是提供该领域的概述，以鼓励进一步的研究。特别是，我们开始一般背景的组合博弈论，分析理想发挥完美的信息游戏。然后，我们调查结果的复杂性，确定理想的发挥在这些游戏中，解决难题的相关问题，在多项式时间算法和计算的棘手性的结果。我们对背景的回顾和对算法结果的调查绝不是完整的，但应该作为一个有用的入门。
Combinatorial games lead to several interesting, clean problems in algorithms and complexity theory, many of which remain open. The purpose of this paper is to provide an overview of the area to encourage further research. In particular, we begin with general background in combinatorial game theory, which analyzes ideal play in perfect-information games. Then we survey results about the complexity of determining ideal play in these games, and the related problems of solving puzzles, in terms of both polynomial-time algorithms and computational intractability results. Our review of background and survey of algorithmic results are by no means complete, but should serve as a useful primer.