Crossword Puzzle Resolution via Monte Carlo Tree Search
Lihan Chen, Jingping Liu, Sihang Jiang, Chao Wang, Jiaqing Liang, Yanghua Xiao, Sheng Zhang and Rui Song
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.
*This password protected talk video will only be available after it was presented at the conference.
