一句话：将 WCN 谜题生成建模为程序合成问题，设计 PuzzlerLang 并用学习模型优化吸引度，自动生成类人谜题。
“下一个是什么”（WCN）谜题要求从给定图形序列推断逻辑上紧随其后的图形，广泛出现在各类能力测试中。本文提出自动合成此类谜题，关键洞见是把 WCN 问题的生成视为程序合成问题。作者设计了小型但表达力强的语言 PuzzlerLang 来描述 WCN 谜题的解，它足以解释所收集的几乎所有人工谜题，同时规模小到能在合理时间内完成合成。为使生成的谜题对人类有吸引力，作者训练机器学习模型近似人类对谜题的吸引度，并在合成器中将其作为优化目标，从而生成既吸引人又构造正确的谜题。工具 PuzzleGen 平均每个谜题约 3.4 秒；用户研究回答的统计检验表明，其生成的谜题与人类创作的谜题难以区分。
What-Comes-Next (WCN) puzzles challenge us to identify the next figure that "logically follows" a provided sequence of figures. WCN puzzles are a favorite of interviewers and examiners—there is hardly any aptitude test that misses WCN puzzles. In this work, we propose to automatically synthesize WCN puzzles. The key insight to our methodology is that generation of WCN problems can be posed as a program synthesis problem. We design a small yet expressive language, PuzzlerLang, to capture solutions to WCN puzzles. PuzzlerLang is expressive enough to explain almost all human generated WCN puzzles that we collected, and yet, small enough to allow synthesis in a reasonable time. To ensure that the generated puzzles are appealing to humans, we infer a machine learning model to approximate the appeal factor of given WCN puzzle to humans. We use this model within our puzzle synthesizer as an optimization function to generate highly appealing and correct-by-construction WCN puzzles. We implemented our ideas in a tool, PuzzleGen; we found that PuzzleGen is fast, clocking an average time of about 3.4s per puzzle. Further, statistical tests over the responses from a user-study supported that the PuzzleGen generated puzzles were indistinguishable from puzzles created by humans.
@inproceedings{LahiriKCV024,
title = {Program Synthesis Meets Visual What-Comes-Next Puzzles},
author = {Sumit Lahiri and Pankaj Kumar Kalita and Akshay Kumar Chittora and Varun Vankudre and Subhajit Roy},
booktitle = {ASE},
year = {2024},
doi = {10.1145/3691620.3695015}
}