Search in the patience game ‘Black Hole’
Ian P. Gent, Christopher Jefferson, Tom Kelsey, Inês Lynce, Ian Miguel, Peter W. Nightingale, Barbara M. Smith, Ş. Armağan Tarim · 2007
We propose card games for one player as a valuable domain for studying search problems. They are a natural AI problem, as they are a widely enjoyed recreation for which solving techniques are generally not studied. We focus on a particular patience, called Black Hole. We show that a general version of it is NP-complete. Then we show that we can fruitfully study a number of mature AI paradigms applied to this single problem. An important feature of Black Hole is the presence of symmetries which arise during the search process, and we show that tacking these can improve search dramatically. Our empirical evaluation shows that Black Hole is winnable approximately 87 % of the time. 1