AI首次赢得填字游戏比赛冠军，纵横字谜新霸主也将诞生？

新智元报道

编辑：小乖熊

【新智元导读】「美国纵横字谜锦标赛」刚刚落下帷幕，人工智能Dr. Fill首次在纵横字谜中战胜人类并获得胜利。尽管如此，该领域人工智能的发展面仍临着诸多挑战，人类依然被认为在解决现实世界问题方更佳现更佳。

2021年4月底，一年一度的美国填字游戏锦标赛（American Crossword Puzzle Tournament，ACPT）上，一个名为Dr.Fill的人工智能计算机程序取得了最高分，大幅领先得分最高的人类选手，这是AI第一次在正式填字游戏中拔得头筹。

填字游戏是一种很常见的益智游戏。游戏一般给出由若干个大小相同方格组成的一个矩形表格，其中有的方格已有文字，有的是等待填些的空白。游戏参与者根据题目所提供的有关信息，将答案填入这些行与列之中。中文游戏可填入中文字，英文游戏则填入英文字母（见图1）。

图1：英文填字游戏

填字游戏是一种「约束满足问题（CSP）」

从数学定义上来讲，填字游戏属于一种「约束满足问题（Constraint-Satisfaction Problem，CSP）」。

它可以定义为一组对象，而这些对象需要满足一些限制或条件。除了填字游戏之外，类似的还包括数独、八皇后问题、图着色问题等。现实生活中的实例包括资源配置、最优规划等。

CSP将其问题中的单元表示成在变量上有限条件的一组同质集合, 这类问题通过「约束补偿方法」来解决。CSP通常呈现高复杂性, 需要同时通过启发式搜索和联合搜索的方法，在合理的时间内解决问题。在人工智能（AI）流行起来后，很多人想通过AI算法来解决CSP问题。

博士毕业于牛津大学的天体物理学家和计算机科学家马特·金斯伯格（Matt Ginsberg）创建了「填字博士」（Dr.Fill）算法，他在2011年发表在《人工智能研究杂志》（Artificial Intelligence Research）上的一篇文章中首次描述了Dr.Fill（图2）。

金斯伯格还是一位特技飞行员、桥牌玩家、小说家和魔术师。十年前，当他开始这个项目时，他的动机很简单，「我被填字游戏所吸引，但有时想半天想不出答案，这让我很生气。」

图2：关于Dr.Fill的论文截图

这篇论文里讲述了许多严格的数学定义和推理，并给出了使用当时（在机器学习成为热潮之前）的AI方法来解填字游戏的算法。

金斯伯格用庞大的填字游戏答题数据库、网站填字答案、所有维基百科和其他知识数据库对Dr.Fill进行了训练。2012年，金斯伯格带着这套软件去参加了每年举办一次的，参赛者包括新手、充满热情的业余爱好者和解题高手。这次ACPT首次亮相，Dr.Fill在一千多人参加的比赛中排名第141位。

在这之后，金斯伯格对其算法和程序作了进一步改进。在2017年的比赛中，Dr.Fill排名上升到第11位。

金斯伯格希望总有一天他能在比赛大厅里，把笔记本电脑举过头顶挥动，来展示他作为冠军的喜悦。就在今年4月的的ACPT 2021锦标赛中，Dr.Fill一举夺得锦标赛冠军，击败了参加比赛的近1300名人类选手。它在一分钟之内解决了大多数难题，仅出现了三个错误。

虽然因为比赛是虚拟举行的，金斯伯格没能在现场挥舞笔记本电脑，但他实现了愿望。这次胜利不但是金斯伯格个人的胜利，也象征着AI在解决CSP难题这方面胜过了人类。

两种AI算法的完美结合

今年Dr.Fill赢得冠军的一个主要原因是金斯伯格与加州大学伯克利分校自然语言处理小组合作，首次将Dr.Fill与加州大学伯克利分校的填字游戏解决方案结合起来，从而增强了功能。

Dr.Fill来自更早时期的AI算法——依靠人类可理解的逻辑和搜索，基于传统数学方法，如同20世纪90年代深蓝进行搜索和排布几百万个象棋位置那样。

而加州大学伯克利分校的神经网络解决方案是一个黑匣子机器学习系统，可以处理语言的抽象和泛化，它更有创意，例如类似的AlphaGo征服了围棋场上的人类对手。

尽管这两种算法代表了不同历史时期的方法，此前并没有进行过「合作」，但是金斯伯格表示很高兴看到更早的AI方法和较新的机器学习方法最终被结合起来，解决了它们各自很难解决的问题。

加州大学伯克利分校自然语言处理小组的负责人丹·克莱恩（Dan Klein）和他的学生们一样，当呆在家里有了大把时间，对填字游戏就非常感兴趣。

他的小组正在着手研究如何采用诸如Siri或Alexa之类的问答系统形式，来解填字游戏。他们的神经网络接受了600万条线索和答案的训练，学习了「概括和抽象」，使机器可以理解人类语言。

金斯伯格和伯克利团队在比赛开始前两周开始合作。他们将伯克利的系统嵌入到Dr.Fill的程序里，最终只用了几天就完成了。这样一个匆忙构建的系统，最终获得冠军是一个奇迹。

计算机科学家一直在利用游戏来证明算法的性能，游戏代表了现实世界的一小部分特征，因此引起了人工智能研究者的兴趣。跳棋、西洋双陆棋、国际象棋、围棋、扑克和其他游戏都见证了智能机器的介入。在AI面前棋手们一个接一个地落败。现在，AI又拿下了填字游戏。

这次参赛人中间成绩最好的是泰勒·辛曼（Tyler Hinman），他在三分钟内完成了难题。而Dr.Fill在49秒内完美地解决了问题。参赛者在得知冠军被AI机器夺走时有何反应呢？

过去，每当宣布Dr.Fill犯了一个错误时，大厅里常有一阵欢呼声。许多参赛者并不欢迎金斯伯格的Dr.Fill来参赛。今年，在宣布该程序获得第一名后，聊天室里充满了嘘声——有些是开玩笑的，有些不是。

锦标赛的主持人认为，「没有人希望在他们擅长的方面被机器击败！」但是他说他也「已经意识到金斯伯格AI项目在科技方面的重要性，虽然我不太情愿。」

解决了跳棋问题的计算机科学家乔纳森·舍弗说，「Dr.Fill的胜利最终是人类的胜利。就像我们在其他游戏和拼图游戏中看到的一样，在填字游戏中AI击败人类是技术与创造力的组合。」

Dr.Fill有没有可能更快？

Dr.Fill今年的战绩是49秒内完成填字，那么它有没有可能更快，会不会在将来甩开人类选手更大的距离，让人类在这个项目上望尘莫及呢？答案是肯定的，对Dr.Fill 来说，就是走AI芯片的路线。

ACPT官网和笔者看到的其他媒体报道没有提及Dr.Fill运行的硬件平台，但考虑到这次金斯伯格是在比赛开始前两周才启动了把伯克利系统「嵌入」到Dr.Fill的改造工程，那Dr.Fill应该是运行在通用计算机平台上，比如笔记本电脑。

工程界如果想最大化一个程序或算法的运行速度，一个常用的方案是把它固化到硬件里，做成专门的芯片，就专门干这一件事，心无旁骛，速度当然快。

比如图像和视频如果交给CPU来处理，速度就比较慢，可能无法支撑高分辨率或者画面快速变化。但如果是显卡来处理，那就速度飞快，可能4K画面都能流畅转换，这就是很多大型游戏需要单独配备显卡才能跑起来的原因。

最新的Dr.Fill引入了加州大学伯克利分校自然语言处理小组的深度神经网络（Deep Neural Network，DNN）方法，从而大大加速。什么样的硬件方案可以进一步加速它呢？那就是专门处理深度神经网络任务的深度学习芯片，也就是现在主流的AI芯片。

目前绝大多数AI芯片设计团队正在利用传统的数字电路设计技术，寻求提供硬件加速，以实现高能效、高吞吐量和低时延的DNN 计算，同时避免牺牲神经网络精度。

不管在系统级还是在芯片级，他们都大量采用异质架构，如CPU 加GPU、CPU 加FPGA，或在FPGA 里再增加「AI 引擎」（专用集成电路芯片，ASIC）等。对AI 芯片研发人员而言，了解并考虑这些数字加速器不断取得的进展至关重要。

接下来我们看一下AI芯片、也就是AI赖以运行的硬件平台的总体发展步伐，就会了解人类在下棋、填字游戏等完全信息和结构化环境下的确定性问题方面，是如何一步步被AI超越的。

AI芯片的发展步伐

过去，大部分AI 模型的建立或算法的运算，都是在以CPU 为核心的计算机里进行模拟的结果。

近些年来，正如摩尔定律所揭示的，业界通过在芯片上放置越来越多的晶体管使CPU 实现更高的性能。然而，由于严格的功耗限制，片上时钟频率无法跟随这种上升趋势。使用多核处理器可以在不提高时钟频率的情况下提高计算性能。

因此，从2005 年开始，主流厂商转而采用多核处理器作为克服该问题的替代解决方案。但是很可惜，这种解决方案从长期来看可扩展性并不好。通过在芯片内部添加更多处理器核所实现的性能提升，是以各种快速增长的复杂性为代价的，如核与核之间的通信、内存一致性，还有最重要的功耗问题。

在早期的芯片工艺技术发展节点中，从一个节点到下一个节点允许的晶体管频率几乎加倍，并且可以通过降低电源电压，使功率密度几乎保持恒定。随着工艺技术进一步发展，虽然从一个节点到另一个节点的晶体管密度仍会增加，但它们的最大频率大致相同，并且电源电压不会相应地降低。结果，现在每个新技术节点的功率密度都在增加。因此，现在最大的挑战是降低单位平方毫米的功耗和热量耗散。

这种趋势很快就会限制内核数量的扩展，就像十多年前单个CPU 核时钟频率被限制的情况那样。很多技术论文将这种情形表述为「暗硅」（Dark Silicon）效应——芯片在工作的时候，其中一部分区域必须保持断电以符合热量耗散约束条件。

用一个简单的比喻来说，就好像房间里装了很多几百瓦的大灯泡，不能同时打开，只能让其中一部分点亮，如果同时打开，该房间的线路就会因高温被烧毁。解决此问题的一种方法是使用硬件加速器。硬件加速器可帮助处理器降低工作负载，提高总吞吐量并降低能耗。

现在的绝大多数 AI 芯片，就是这种硬件加速器。目前市场上第一批用于AI 的芯片包括现成的CPU、GPU、FPGA 和DSP，以及它们的各种组合。虽然英特尔、谷歌、英伟达（NVIDIA）、高通和IBM等公司已经推出或正在开发新的芯片设计，但目前还很难说哪家一定会胜出。

一般来说，总是需要至少一个CPU来控制系统，但是当数据流需要并行处理时，将需要各种类型的协处理器（即硬件加速器），这就是专用集成电路（Application Specific Integrated Circuit，ASIC）芯片。

如图3所示，CPU、GPU、FPGA 及ASIC 这4 种芯片有不同的架构。下面分别讨论这4 种芯片。

图3：4种芯片的不同架构（图片来源：《AI芯片：前沿技术与创新未来》）

CPU

AI算法（包括深度学习算法）可以在通用CPU上实现。由于CPU的普及和通用编程能力，神经网络技术在开始时期被大量推广和应用。一些关键的算法验证都是在CPU上完成的。

但是，CPU并不是实现神经网络的理想硬件。CPU以提供复杂的控制流而闻名，这对于更常规的、基于规则的计算可能是有益的，但对像使用数据驱动方法那样的神经网络却不是那么重要。神经网络的运行过程几乎不需要控制，因此在神经网络计算中，数据流是计算的主要部分，而不是控制流。

另外，对于AI算法的硬件实现和大规模应用来说，高吞吐量和低时延计算的需求在不断增长，而通用CPU是基于冯·诺依曼体系结构的处理器，存在不少结构限制；摩尔定律发展的放慢也意味着CPU的性能无法再得到快速改善。

GPU

GPU最初用于快速图形渲染，它适用于SIMD并行处理，能快速进行图形渲染相关的浮点密集型计算。GPU架构的发展非常迅速，从一开始的可重构GPU，发展到可编程的大规模并行协处理器，这使它非常适合AI这样需要高性能并行计算的场景。

为了满足更快和更高精度AI的需求，人们正在继续推动越来越多并行GPU的开发。现在，具有超过1000个处理核和很大容量片上存储器的GPU，其功耗仅为几瓦。尽管如此，对一些终端应用来说，这样的能效还不够高。

从本身的架构来说，GPU的设计还存在一些缺陷。例如，很难快速地为GPU加载数据以使它们保持忙碌状态等。因此，很多人在继续研究新的GPU架构。无论如何，在模拟大型人工神经网络时，GPU还是发挥了非常大的作用。

FPGA

现场可编程门阵列（Field Programmable Gate Array，FPGA）是一种「可重构」芯片，具有模块化和规则化的架构，主要包含可编程逻辑模块、片上存储器及用于连接逻辑模块的可重构互连层次结构。

此外，它还可能包含数字信号处理模块和嵌入式处理器核。从电路级设计来看，FPGA可以通过使用触发器来实现时序逻辑，通过使用查询表来实现组合逻辑。通过执行时序分析，可以插入流水线级以提高时钟频率。

FPGA的优点是非常明显的。即使在被制造出来以后，FPGA都可以在运行之前和运行期间对硬件进行重构，这给硬件应用带来了极大的灵活性。因此在20世纪80年代末，赛灵思（Xilinx）公司在最初推出FPGA时就宣称，它是芯片业界的一场革命。

近年新发布的一些FPGA采用了嵌入式ARM内核的片上系统设计方法。如今，具有约10亿个逻辑门复杂度和几兆字节（MB）内部静态随机存取存储器的SoC设计可以用最先进的FPGA实现。

它的时钟频率接近吉赫兹（GHz）范围，因此算力可以在几瓦的功耗下达到GFLOPS的数量级。因此，FPGA为并行实现人工神经网络提供了一个有吸引力的替代方案，具有灵活性高和上市时间短的优势。

开发FPGA和ASIC设计的时间基本相当，但FPGA的一大优势是不需要制造时间，在用有效的EDA工具电路综合之后，即可直接测试新设计。而且FPGA的并行化程度可以做得很高。但是，与ASIC相比，FPGA的缺点是速度更慢、面积更大、功耗更高。

ASIC

ASIC指专用集成电路（Application Specific Integrated Circuit）。它是定制的专用AI芯片，可以在芯片架构和电路上进行优化，以满足特定的应用需求。无论从性能、能效、成本角度，还是算法的最佳实现方面，ASIC都是标准芯片无法比拟的。

随着AI算法和应用技术的发展，ASIC逐渐展现出自己的优势，非常适合各种AI应用场景。现在大部分AI芯片的初创公司，都是以开发一种独特、新颖的ASIC为目标。

把AI算法「硬件化」，即用ASIC来实现，带来了高性能、低功耗等突出优点，但缺点也是十分明显的。ASIC芯片的开发需要很高的成本，一旦设计完毕，交由芯片代工厂流片（即制造芯片），首先需要支付一大笔一次性工程费用。这种费用一般不会低于1000万美元。

这对中小型企业，尤其是初创公司来说，是一道很高的门槛。而AI又属于一个技术迭代速度很快的领域，现在几乎每隔几个月就会有新的算法和模型出现，这对于开发芯片的公司来说，意味着很大的商业风险。

ASIC芯片一旦开始批量生产，就无法再改动里面的硬件架构。万一市场对AI芯片功能的需求出现重大变化，或者研发成功了新的AI算法，那这款芯片就只能被淘汰而由芯片设计者继续开发新的芯片。

有的公司为了及时使用新的算法，甚至需要中途从代工厂召回正在生产的ASIC芯片，以更新芯片设计。

为了避免这种风险，除了选用灵活性很高的FPGA来实现之外，还可以采用模块化设计方法，即形成一个IP核（知识产权核，Intellectual Property Core）的库，可以根据设计需要来选取。

图4为不同种类的AI芯片及其计算范式。

图4：AI 芯片的种类及其计算范式（图片来源：《AI芯片：前沿技术与创新未来》）

目前比较前沿的研究是设计「可进化」芯片，它基本上接近通过芯片的「自学习」来提升芯片自身的性能。AI芯片的最终目标是能够「自学习」，即芯片能够自己学习「如何学习」；

另外一个重要目标是做到智能机器之间（相当于AI芯片之间）的相互学习和协调，从而使智能机器自己得到更多的知识。这种「自学习」的性能，很可能随时间呈指数级提升，并将最终导致智能机器的智能水平超越人类（可能将不只是在填字游戏中战胜人类那么简单）。

这条路虽然还很漫长，但是一些研究人员已经开始起步。

图书信息

书名：AI芯片：前沿技术与创新未来

作者：张臣雄

书号：9787115553195

出版社：人民邮电出版社

AI家，新天地。西山新绿，新智元在等你！

【新智元高薪诚聘】主笔、高级编辑、商务总监、运营经理、实习生等岗位，欢迎投递简历至wangxin@aiera.com.cn (或微信: 13520015375)

办公地址：北京海淀中关村软件园3号楼1100

AI首次赢得填字游戏比赛冠军，纵横字谜新霸主也将诞生？ | 留言赠书

新智元报道

【新智元导读】「美国纵横字谜锦标赛」刚刚落下帷幕，人工智能Dr. Fill首次在纵横字谜中战胜人类并获得胜利。尽管如此，该领域人工智能的发展面仍临着诸多挑战，人类依然被认为在解决现实世界问题方更佳现更佳。