TY - JOUR AU - Chen, Lihan AU - Liu, Jingping AU - Jiang, Sihang AU - Wang, Chao AU - Liang, Jiaqing AU - Xiao, Yanghua AU - Zhang, Sheng AU - Song, Rui PY - 2022/06/13 Y2 - 2024/03/28 TI - Crossword Puzzle Resolution via Monte Carlo Tree Search JF - Proceedings of the International Conference on Automated Planning and Scheduling JA - ICAPS VL - 32 IS - 1 SE - Main Track DO - 10.1609/icaps.v32i1.19783 UR - https://ojs.aaai.org/index.php/ICAPS/article/view/19783 SP - 35-43 AB - Although the development of AI in games is remarkable, intelligent machines still lag behind humans in games that require the ability of language understanding. In this paper, we focus on the crossword puzzle resolution task. Solving crossword puzzles is a challenging task since it requires the ability to understand natural language and the ability to execute a search over possible answers to find an optimal set of solutions for the grid. Previous solutions are devoted to exploiting heuristic strategies in search to find solutions while having limited ability to explore the search space. We propose a solution for crossword puzzle resolution based on Monte Carlo tree search (MCTS). As far as we know, we are the first to model the crossword puzzle resolution problem as a Markov Decision Process and apply the MCTS to solve it. We construct a dataset for crossword puzzle resolution based on daily puzzles from New York Times with detailed specifications on both the puzzle and clue database selection. Our method can achieve an accuracy of 97% on the dataset. ER -