Search in the Patience Game Black Hole

Thursday, 24th March, 2005
Ian Gent, University of St Andrews

Patiences (aka Solitaire games) are a neglected field of study for AI search techniques. We study a particular game, Black Hole, and show its generalisation to be NP-Complete. We show the role of symmetry in the problem, and describe five different approaches to solving it using different AI techniques.