曾因不知NP困难怕被导师拒绝，滕尚华游戏中找到人生经验，两次获哥德尔奖

选自《量子杂志》

作者：Ben Brubaker

机器之心编译

编辑：王楷

滕尚华教授曾两次获得理论计算机科学领域的最高荣誉哥德尔奖，在他的研究中，理论问题和实践问题长期以来一直交织在一起，然而如今他却转头聚焦于一些其他事情。

滕尚华

对于滕尚华而言，理论计算机科学从来都不是纯理论性的。现年 58 岁的滕尚华是南加州大学计算机科学系教授，曾两次获得哥德尔奖，该奖项每年颁发一次，旨在表彰开创性的理论工作。而他的独到之处在于经常潜心于以既实用又有趣的方式将抽象理论与日常生活联系起来。

滕尚华教授于 1964 年生于北京，1985 年毕业于上海交通大学，而后前往美国攻读研究生学位，本欲学习计算机体系结构，但他很快改变了其研究方向，专注于更抽象的数学理论。1991 年，他证明了如何最好的进行图分区（partition graph）这一数学定理，并获得了卡内基梅隆大学的博士学位。

虽然是理论研究，但这项工作有实际应用 —— 他发现，实际应用往往会带来新的理论见解。在 1993 年美国宇航局夏季奖学金项目期间，滕尚华教授加入了一个使用「有限元」方法模拟流体动力学的团队，该方法将复杂结构建模为众多小块模型的组合。这些组合可以被视为图，滕尚华教授的任务是将他研究生期间研究的图分区方法进行调整并应用到这种新环境中。但他对 NASA 团队之前使用的分区技术产生了好奇心，并开始与同事 Daniel Spielman（现为耶鲁大学计算机科学系教授）一起研究其底层数学结构。经过长达数十年的合作，该联合研究项目为他们赢得了两项哥德尔奖。

这并非他唯一一次看到理论与实践之间的深刻联系。「每一次，这些看似完全实用的东西背后都隐藏着这种美丽的数学，」滕尚华教授说。

最近，滕尚华教授将注意力转向井字棋（tic-tac-toe）、国际象棋和围棋等游戏博弈背后的美妙数学。在这种组合博弈游戏中，没有机会因素，而且双方玩家总是对棋盘状态了如指掌。然而，组合博弈具有挑战性，因为博弈玩法可能多得令人眼花缭乱。

博弈论研究人员喜欢将此类博弈推广到更大的棋盘，例如，将井字棋从 3×3 方格扩大到 n×n，并量化在给定一些初始棋盘状态的情况下确定哪个玩家将更易获胜。

滕尚华教授展示了一个数学定理是如何启发创作出一个漂亮的棋盘游戏。

在游戏中找到人生教训

近日，在《量子杂志》的一次采访中，滕尚华教授谈到了他的计算机科学之路、棋盘游戏博弈之下的数学思维以及父亲对他的影响。下面是对采访内容的整理。

量子杂志：你是如何选择计算机科学的？

滕尚华教授：高中毕业后我想学生物学，但不知道为何父亲（滕尚华教授的父亲是大学的土木工程系主任）对此并不太开心。我的数学成绩不错，他问我是否想钻研数学，我拒绝了。然后他说，「你知道，有一个新的学科叫计算机科学，它真的很棒。」也不知怎的，他推动着我主修了计算机科学。

当时的教育非常基础，无法接触到很多有用的东西，计算机科学甚至不是一个系。但由于偶然的机会，我得到了微积分数学方面的训练，学到了一些对我最终成为理论家有用的知识。如果没有这一点，我可能就没有机会成为今天这样的人。

滕尚华教授在南加州大学的校园中 

量子杂志：知识上的差距是如何影响你在研究生期间学习经历的？

滕尚华教授：有一天，在一次学术讨论中，我的导师 Gary Miller 发现我竟从未听说过 NP-hard。导师一脸震惊，我却一脸茫然。

我以为那会是我和他一起工作的最后一天，令我没想到的是，他还是继续教授我，并告诉我这个定义。他说，如果你不知道，那没关系，只要你能主动思考就好。他的话对我产生了巨大的影响。

量子杂志：你主要是一名理论家，但在职业生涯中，你曾涉足工业，实践工作与你的理论研究有何联系呢？

滕尚华教授：在我的论文中，我研究了一些用于图分区的几何方法。我能够证明，这一系列几何方法为有限元图带来了可证明的良好切割。

在导师的推荐下，我开始在 NASA 和波音航空公司进行演讲。在波音航空公司，我记得其中一个机翼的 3D 模型已经有将近一百万个元素 —— 他们甚至无法将其加载到一台机器中。所以他们想把这个图分割成不同的部分，把它们放到具有相似计算负载的不同机器上，并尽量减少通信。这就是为何从数学的角度而言，公式就是一个图分区。

在理论计算机科学中，即使问题的表象发生了从最优化理论到博弈论的巨大变化，但其背后的数学原理往往保持不变。当你做这项研究时，并非会感受到剧烈变化。

量子杂志：提到博弈论，我看到你帮助设计了一个棋盘游戏。这个过程是如何发生的？

滕尚华教授：我喜欢桌游！它与复杂性理论有着非常美妙的联系。我在波士顿大学做过一场斯波纳引理 （Sperner's lemma）的离散定理演讲。该引理在一维世界中非常简单，即你有一个线段，其中一端为红色，一端为蓝色。然后将其划分为子分段（两端均有节点），并将每个新节点着色为红色或蓝色。无论你如何给它们上色，我们知道一定有一个片段同时具有这两种颜色。

从二维来看，你有一个三角形，有三种颜色：一个角是红色，一个角是蓝色，还有一个角是绿色。将此三角形分割为较小的三角形，那么每条边都会分割为线段。每个外边缘都遵循一维规则：其上的节点只能使用两端的颜色。在这三角形内，你可以任意选择三种颜色的一种。斯波纳引理表明，无论你怎样划分，只要你按照规定着色，一定有一个三角形，它有三种颜色。

我的一位学生 Kyle Burke，从事过数值分析的研究。他对我说可能会有一个奇妙的有关斯波纳引理的棋盘游戏：两个玩家轮流给一个棋盘上色，谁先拼出一个三色三角形，谁就会输掉这场游戏。一般来讲，棋牌游戏都有赢家，而不会平局，显然有人会赢，因为有斯波纳引理的存在。

我咨询了朋友 David Eppstein，讨论打造一个好的棋盘游戏需要什么。他说，一个好的游戏需要有简单的规则和漂亮的棋盘，而且必须是 PSPACE-hard（PSPACE 是计算复杂度理论中能被确定型图灵机利用多项式空间解决的判定问题集合）的。

后来 Kyle 问这个游戏简单吗？我回答道很简单！Kyle 又表示如果自己证明它是 PSPACE-hard 的，能拿到博士学位吗？我说可以，于是他做到了。他的定理中有许多不同的部分，它揭示了关于定点的某些东西，这是数学中一个非常美妙的概念。

滕尚华教授与学生 Kyle Burke（左）和现在的研究生 Matthew Ferland（中）。

量子杂志：我可以玩这个游戏吗？

滕尚华教授：可以，它是在线提供的。

游戏地址：http://kyleburke.info/combGames/atropos.html

量子杂志：你喜欢玩什么游戏呢？

滕尚华教授：我是博弈理论家，我和女儿玩过一些游戏，但我并不是玩游戏长大的，也不像我的学生，他们经常玩游戏。

量子杂志：关于棋盘游戏，你在数学方面还做了哪些工作？

滕尚华教授：我们发表过一篇关于开放性问题的论文《Winning the War by (Strategically) Losing Battles: Settling the Complexity of Grundy-Values in Undirected Geography》 ，论文中探讨了如果你把两个多项式时间可解的博弈并排放在一起，这会让它们变成 PSPACE-hard 吗？每一步你只能玩其中一个游戏。这叫做博弈总和（summation of games）。

量子杂志：把两个博弈放在一起意味着什么？

滕尚华教授：在古老的围棋对弈中，当落下足够多的棋子时，你会拥有许多独立的竞技战场，所以从某种意义上说，你是在玩一个博弈总和。你必须考虑所有的角落，想赢得整局棋却并不意味着你必须在每一个独立的区域都获得胜利。

从哲学来讲很有趣， 就像参加一场战役，它有很多场战斗，但你的注意力是有限的。每一刻都只能在其中一个战场上做出单独的决策，而你的敌人可以在另一个战场上做出回应或加倍下注。我曾试图向父亲解释这件事，当你玩一局博弈总和游戏时，它实际上意味着：你如何有策略地输？

我们用两个博弈证明了这一点，但你也可以将三个博弈放在一起，这个定理仍然成立：三个多项式时间博弈放在一起会成为 PSPACE-hard。

滕尚华教授在棋盘游戏的数学思维中学习到了更多知识。

量子杂志：自从受父亲影响研究计算机科学以来，他对你多年来所做的不同工作有何反应？

滕尚华教授：父亲经常问我为何要这么做？后来他渐渐明白，理论性的工作往往多年难出成果。早些时候我可以谈论有限元方法，他也在土木工程中教授这个方法。但是我想不明白该如何谈论这种趣味数学。

而后我想到了中国四大名著《三国演义》中的一个俗语：三个臭皮匠，顶个诸葛亮。这句俗语与书中的一个角色诸葛亮（几乎是一个完美的军事家）紧密相关。这句话以一种轻松愉快的方式，指出三个普通人集思广益时可以变得完美。

我对父亲说，这正是我们用博弈证明的定理。战场将领正是 [用于求解的算法] 多项式时间博弈应用代表：在每个战场上，他们都知道如何取胜。但困难的地方在于知道该什么时候输，而非如何去赢得每场战斗。如果有人可以进行那种困难的博弈，那么他们就是最好的战略家。战场将领不会做出这些深层次的逻辑决策，但如果你将他们很好地安排在一起，他们将不会比这个完美的战略家差。

我对父亲说：我终于悟出这个与著名俗语相当的数学定理了！那时他已 94 岁高龄，非常削瘦，他说，这是一个很好的尝试。不过我没有完全让他信服。那也是我与他的最后一次技术对话；几个月后父亲去世了。每当我考虑解释我的工作时，这些领悟就是我的亮点。

原文链接：

https://www.quantamagazine.org/the-computer-scientist-who-finds-life-lessons-in-board-games-20230125/

© THE END 

转载请联系本公众号获得授权

投稿或寻求报道：content@jiqizhixin.com