填字游戏是人类最受欢迎的消遣方式之一。它们由一组线索组成，线索的答案构成相互重叠的单词网格。目标是完成网格。
填字游戏是人类在机器上显著胜出的一个领域。事实上，最负盛名的比赛是美国填字游戏锦标赛，每年都会举行，并且一直由人类获胜。
2017年，一个名为Dr Fill的机器在六百多名参赛者中获得了令人尊敬的第11名。但一台机器从未赢得过美国填字游戏锦标赛。直到去年。
隆重推出 Berkeley Crossword Solver，这是一个由 Eric Wallace 和加州大学伯克利分校自然语言编程团队的其他成员，以及 Dr Fill 程序的原始开发者 Matt Ginsberg 开发的自动填字游戏解算程序。
第一名
该新程序在2021年美国填字游戏锦标赛中超越了所有人类竞争对手。“[这]标志着计算机程序首次在该赛事中超越人类表现，”研究人员说。“我们的系统以第一名的成绩击败了1100名顶级人类解算者。”
机器发现填字游戏很难，因为它们包含几种不同类型的线索，需要不同的方法来解决。例如，基于知识的线索需要对历史、流行文化或其他形式的琐事有所了解。该团队举了以下例子：线索：《所罗门之歌》之后的书 A：以赛亚。
文字游戏线索要求玩家对字母异位、双关语或意义相似的单词进行推理。例如，线索：后面什么都没有的数字，A：十。
常识线索需要对现实世界有切实的理解。例如，线索：造成污迹的原因，A：湿墨。
由多个单词组成的答案对于程序来说尤其棘手，因为可能的答案数量会急剧增加。
相比之下，单词定义通常对机器来说很容易通过数据挖掘自动找到。例如，线索：有獠牙的草原居民 A：疣猪。
Berkeley Crossword Solver 的方法很简单。它首先使用一个神经问答算法，该算法为所有线索生成候选答案，并附带一个分数，表明该答案可能是多么好。
该算法在包含过去70年历史填字游戏中的六百多万个问答对的庞大数据库上进行训练。它还使用一种名为 GPT-2 的开源自然语言人工智能来帮助进行单词分割。
接下来，它使用这些建议的答案来填充网格。由于存在大量冲突，如果没有一套完美的答案，这个过程会很棘手，需要优先考虑一个候选答案而不是另一个。
伯克利团队使用一种称为信念传播（Belief Propagation）的流程来解决这个问题。这旨在产生一个与预期解决方案重叠度最高的解决方案，而不是优先考虑问答过程中得分更高的单词的解决方案。
结果是一个通常接近正确的解决方案，但带有各种小错误。因此，最后阶段是程序的第二次迭代，在此阶段，程序会检查距离当前解决方案只有微小编辑的替代解决方案。程序对生成的解决方案进行评分，并重复此过程，直到不再可能进行改进为止。
强大的解算器
其结果是一个功能强大的填字游戏解算程序。“我们的系统甚至超越了最优秀的人类解算者，并且能够以完美的准确性解决各种领域的谜题，”团队说。
然而，他们不遗余力地指出，填字游戏尚未“被攻克”。相反，Berkeley Crossword Solver 针对美国流行的某些类型的谜题进行了优化，例如著名的《纽约时报》填字游戏。“与现有方法相比，我们的系统在《纽约时报》的填字游戏中，将精确解题率从 57% 提高到 82%，”团队说。
但它在其他类型上表现不佳。特别是，该程序无法解决在英国流行的那种神秘填字游戏。“神秘填字游戏涉及一套不同的约定和挑战，例如，更多的元语言推理线索（如字母异位），并且很可能需要与我们提出的方法不同的方法，”伯克利团队承认。
这项有趣的工作显示了比以前的解算器有显著的进步。它也表明，在填字游戏的领域，人类仍然占主导地位；但还能统治多久，很难说。
参考：自动填字游戏解算：arxiv.org/abs/2205.09665
