An analysis of Single-Player Monte Carlo Tree Search performance in Sokoban

作者：

Highlights：

• Sokoban requires domain knowledge to be solved.

• MCTS has been successful in several domains including puzzle games.

• The best available Sokoban solver is based on IDA*

• MCTS with domain knowledge can reach interesting performance in Sokoban.

• IDA* still provides the best performance.

摘要

•Sokoban requires domain knowledge to be solved.•MCTS has been successful in several domains including puzzle games.•The best available Sokoban solver is based on IDA*•MCTS with domain knowledge can reach interesting performance in Sokoban.•IDA* still provides the best performance.

论文关键词：Artificial intelligence,Puzzle games,Monte Carlo Tree Search,Sokoban

论文评审过程：Received 30 July 2020, Revised 8 May 2021, Accepted 11 November 2021, Available online 1 December 2021, Version of Record 28 December 2021.

论文官网地址：https://doi.org/10.1016/j.eswa.2021.116224