• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>AI communications >Search in the patience game 'Black Hole'
【24h】

Search in the patience game 'Black Hole'

机译：在耐心游戏“黑洞”中搜索

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

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.
机译：我们提出了对适用于自然规划问题的不同AI搜索范例的评估。我们研究的问题是一个名为Black Hole的特定纸牌游戏。对于诸如SAT和约束编程这样的范例，该游戏具有特别的优势，即所有解决方案的长度相同。我们证明黑洞的一般版本是NP完全的。然后，我们报告了许多AI范例在该问题上的应用，即计划，约束编程，SAT，混合整数编程和专用求解器。黑洞的一个重要特征是在搜索过程中出现对称性。我们显示解决这些问题可以显着改善搜索，并且可以缓存搜索期间发生的状态。我们作为SAT，约束规划和计划问题的实施方式高效且具有竞争力，可以对每种方法的优缺点进行详细的经验评估。我们的经验评估表明，黑洞大约有87％的时间是可获胜的，并且给定的实例可以轻松解决，易于解决，难以解决甚至难以解决，具体取决于用于获取解决方案的AI方法。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号