文章基本信息

标题：Strategy-Stealing Is Non-Constructive
本地全文：下载
作者：Greg Bodwin ; Ofer Grossman
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2020
卷号：151
页码：1-12
DOI：10.4230/LIPIcs.ITCS.2020.21
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：In many combinatorial games, one can prove that the first player wins under best play using a simple but non-constructive argument called strategy-stealing. This work is about the complexity behind these proofs: how hard is it to actually find a winning move in a game, when you know by strategy-stealing that one exists? We prove that this problem is PSPACE-Complete already for Minimum Poset Games and Symmetric Maker-Maker Games, which are simple classes of games that capture two of the main types of strategy-stealing arguments in the current literature.
关键词：PSPACE-hard; Hex; Combinatorial Game Theory