Crossword Puzzle Resolution via Monte Carlo Tree Search

Authors

  • Lihan Chen Shanghai Key Laboratory of Data Science, School of Computer Science, Fudan University
  • Jingping Liu Shanghai Key Laboratory of Data Science, School of Computer Science, Fudan University
  • Sihang Jiang Shanghai Key Laboratory of Data Science, School of Computer Science, Fudan University
  • Chao Wang Shanghai Key Laboratory of Data Science, School of Computer Science, Fudan University
  • Jiaqing Liang Shanghai Key Laboratory of Data Science, School of Computer Science, Fudan University
  • Yanghua Xiao Shanghai Key Laboratory of Data Science, School of Computer Science, Fudan University Fudan-Aishu Cognitive Intelligence Joint Research Center
  • Sheng Zhang North Carolina State University, Raleigh, US
  • Rui Song North Carolina State University, Raleigh, US

Keywords:

Monte Carlo Tree Search, Crossword Puzzle Solution, Natural Language Processing, Reward Learning

Abstract

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.

Downloads

Published

2022-06-13

How to Cite

Chen, L., Liu, J., Jiang, S., Wang, C., Liang, J., Xiao, Y., Zhang, S., & Song, R. (2022). Crossword Puzzle Resolution via Monte Carlo Tree Search. Proceedings of the International Conference on Automated Planning and Scheduling, 32(1), 35-43. Retrieved from https://ojs.aaai.org/index.php/ICAPS/article/view/19783