AAAI

Association for the Advancement of Artificial Intelligence

Home > Proceedings / Proceedings of the International Conference on Automated Planning and Scheduling, 32 > Book One

Crossword Puzzle Resolution via Monte Carlo Tree Search

Authors

Lihan Chen,Jingping Liu,Sihang Jiang,Chao Wang,Jiaqing Liang,Yanghua Xiao,Sheng Zhang,Rui Song

Shanghai Key Laboratory of Data Science, School of Computer Science, Fudan University,Shanghai Key Laboratory of Data Science, School of Computer Science, Fudan University,Shanghai Key Laboratory of Data Science, School of Computer Science, Fudan University,Shanghai Key Laboratory of Data Science, School of Computer Science, Fudan University,Shanghai Key Laboratory of Data Science, School of Computer Science, Fudan University,Shanghai Key Laboratory of Data Science, School of Computer Science, Fudan University Fudan-Aishu Cognitive Intelligence Joint Research Center,North Carolina State University, Raleigh, US,North Carolina State University, Raleigh, US


Proceedings:

Book One

Volume

Issue:

Book One

Track:

Main Track

Downloads:

Download PDF

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.

DOI:

10.1609/icaps.v32i1.19783


ICAPS

Book One