Search in the Patience Game `Black Hole'

Ian Philip Gent, Thomas William Kelsey, C Jefferson, I Lynce, Ian James Miguel, P Nightingale, BM Smith, S Armagan Tarim

Research output: Contribution to journalArticlepeer-review

Abstract

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.

Original languageEnglish
Pages (from-to)211-226
Number of pages16
JournalAI Communications
Volume20
Issue number3
Publication statusPublished - 2007

Keywords

  • constraint programming
  • planning
  • empirical evaluation

Fingerprint

Dive into the research topics of 'Search in the Patience Game `Black Hole''. Together they form a unique fingerprint.

Cite this