Search in the patience game ‘Black Hole’
Search in the patience game ‘Black Hole’
复制标题
在耐心游戏“黑洞”中搜索
DOI：
--
复制
发表时间：
2007
期刊：
影响因子：
--
通讯作者：
Armagan Tarim
中科院分区：
文献类型：
--
作者：
Ian P. Gent;Christopher Jefferson;T. Kelsey;I. Lynce;Ian Miguel;Peter William Nightingale;Barbara M. Smith;Armagan Tarim
我们提出了一个评估不同的AI搜索范式应用于自然规划问题。我们研究的问题是一个名为黑洞的玩家的特定纸牌游戏。对于SAT和约束编程这样的范例，这个游戏有一个特别的优点，所有的解都是相同的长度。我们证明了黑洞的一般版本是NP完全的。然后，我们报告了一些AI范式的应用问题，即规划，约束编程，SAT，混合编程和专门的求解器。黑洞的一个重要特征是在搜索过程中出现的对称性。我们表明，解决这些问题可以显着提高搜索，可以缓存状态发生在搜索过程中。我们的实现SAT，约束编程和规划问题是高效和有竞争力的，允许详细的经验评估的优势和劣势，每种方法。我们的经验评估表明，黑洞在大约87%的时间内是可以获胜的，并且给定的实例可以被简单地解决，容易解决，难以解决，甚至难以解决，这取决于用于获得解决方案的AI方法。
We present an evaluation of different AI search paradigms applied to a natural planning problem. The problem we investigate is a particular card game for one player called Black Hole. For paradigms such as SAT and Constraint Programming, the game has the particular advantage that all solutions are the same length. We show that a general version of Black Hole is NP-complete. Then we report on the application of a number of AI paradigms to the problem, namely Planning, Constraint Programming, SAT, Mixed-Integer Programming and a specialised solver. An important feature of Black Hole is the presence of symmetries which arise during the search process. We show that tackling these can improve search dramatically, as can caching states that occur during search. Our implementations as SAT, Constraint Programming and Planning problems are efficient and competitive, allowing detailed empirical evaluation of the strengths and weaknesses of each methodology. Our empirical evaluation shows that Black Hole is winnable approximately 87% of the time, and that given instances can be trivially solved, easy to solve, hard to solve and even intractable, depending on the AI methodology used to obtain solutions.