在游戏中找到人生教训的计算机科学家

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

腾生于中国文化大革命前夕的北京，他来到美国读研究生，计划学习计算机体系结构，但他很快改变了方向，专注于更抽象的数学理论。 他于 1991 年在卡内基梅隆大学获得博士学位，以证明关于如何最好地划分图形的定理——点或节点的网络，由线或边连接。

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

这不是他唯一一次看到理论与实践之间的深刻联系。 “每一次，这些看似完全实用的东西背后都有这种美丽的数学，”滕说。

最近，滕将注意力转向井字游戏、国际象棋和围棋等游戏背后的美妙数学。 在这种“组合”游戏中，没有机会因素，而且双方玩家总是了解棋盘状态的一切。 然而，组合游戏仍然具有挑战性，因为游戏的玩法可能多得令人眼花缭乱。

博弈论研究人员喜欢将此类游戏推广到更大的棋盘——将 tic-tac-toe 从 3×3 正方形扩大到 n逐n，例如——并量化在给定某些初始棋盘状态的情况下确定哪个玩家将获胜的难度。 不同的可能答案将游戏归类为相同的“复杂度等级” 在整个理论计算机科学中突然出现。

一个著名的复杂性类以平淡无奇的名称 P 表示“多项式时间”，粗略地说，它包含可以在合理时间内解决的问题。 同样著名的 NP 类问题可能需要花费不合理的时间来解决，但它们的解决方案很容易检查。 对于另一个称为 PSPACE 的复杂性类别中的问题，即使是这种有效的验证也无法保证。 当研究人员考虑双人游戏的“深层逻辑”时——“如果你做 X，然后如果我做 Y，然后如果你做 Z”等等——他们经常发现自己在谈论 PSPACE。 但正如滕帮助证明的那样，组合游戏的数学并不总是直截了当的。

广达 最近与 Teng 交谈，讨论了他的计算机科学之路、棋盘游戏背后的数学以及他父亲的影响。 为清楚起见，对访谈进行了压缩和编辑。

在中国接受教育是什么感觉？

我出生在文化大革命前不久，父亲是大学土木工程系主任。 革命发生时，他被囚禁在校园里。 然后将整个校园送入农村深处。

我曾经收集垃圾卖到我几乎读完初中，然后中国突然变了。 如果你学习了，你就可以上大学，而且我们没有其他希望找到任何固定工作。 我醒了，我说，“我需要学习。”

你是如何选择计算机科学的？

我想在高中毕业后学习生物学。 我不知道为什么，但我父亲对此不是很满意。 我数学还行，他问我想不想学数学。 我说不。 [笑]然后他说，“你知道，有一门新学科叫做计算机科学，它真的很棒。” 不知何故，他促使我主修计算机科学。

那时候的教育很基础。 大多数事情我们都没有接触过，计算机科学甚至不是一个系； 那是电气工程专业。 但幸运的是，我们接受了微积分方面的数学训练，我学到了一些最终对成为理论家有用的东西。 没有它，我可能通过考试的机会为零。 现在的孩子们更有天赋了：从高中开始，他们就是比我来到这个国家时更有天赋的数学家。

您知识上的这些差距如何影响您在研究生院的经历？

有一天 [我的导师 Gary Miller] 发现我从未听说过 NP。 这是在讨论中。 他说，“这个问题看起来是 NP-hard”。 我说：“嗯嗯。” 他说：“你不相信我？” 然后他开始证明它，进行到一半他突然转向我，因为我正坐在那里，他说，“你知道什么是 NP-hard 吗？” 我说不。

我以为那是我和他一起工作的最后一天，但他继续告诉我定义。 他说：“不知道也没关系，只要你能想。” 他对我产生了巨大的影响。

您主要是一名理论家，但在您的整个职业生涯中，您都涉足了工业领域。 这项实际工作如何与您的理论研究联系起来？

在我的论文中，我开发了一些用于划分图形的几何方法。 我能够证明这一系列几何方法对有限元图给出了可证明的良好切割。

在导师的推荐下，我开始在 NASA 和 Boeing Aerospace 做演讲。 在波音公司，我记得其中一个机翼的 3D 模型已经有将近一百万个元素——他们甚至无法将其加载到一台机器中。 所以他们想把这个图切割成不同的组件，将它们放到具有相似计算负载的不同机器上，并尽量减少通信。 这就是为什么数学上公式是图形切割的原因。

在理论计算机科学中，即使问题的外观从优化到博弈论发生了巨大变化，基本的数学原理通常也不会改变。 当您进行研究时，感觉不会发生剧烈变化。

说到博弈论，我看到你帮助设计了一个棋盘游戏。 那是怎么发生的？

哦，我喜欢棋盘游戏！ 与复杂性理论有着美妙的联系。 但大多数时候我是我学生的学生。

我在波士顿大学做了一个关于一个美丽的离散定理的演讲，这个定理叫做 Sperner 引理。 它在一维中非常简单。 你有一条线段，一端是红色，一端是蓝色。 您将它分成子段 [两端都有节点] 并将每个新节点着色为红色或蓝色。 然后 [无论你如何给它们着色] 我们知道必须有一个具有两种颜色的片段。

在两个维度上，它非常迷人。 你有一个三角形，现在你有三种颜色：一个角是红色的，一个是蓝色的，一个是绿色的。 你把这个三角形分成更小的三角形，所以边被分成几段。 每条外边都遵循一维规则：节点只能使用两端的颜色。 在三角形内，您可以随心所欲地使用所有三种颜色。 Sperner 的引理说，无论您如何划分它，如果您进行这种着色，则必须存在一个具有所有三种颜色的三角形。

凯尔·伯克 (Kyle Burke) 是我的学生，当时从事数值分析工作。 他来到我的办公室，说可以有一个漂亮的斯佩纳引理的棋盘游戏：两个玩家反复给棋盘上色，谁得出三色三角形，谁就输了。 最好的棋盘游戏有赢家而不是平局，而在这里，显然有人会赢。 为什么？ 因为 Sperner 的引理！

我打电话给我来自尔湾的朋友 David Eppstein，讨论什么是好的棋盘游戏。 他说，“一款好的游戏有简单的规则和漂亮的棋盘，而且必须是 PSPACE-hard。” 因为如果你能在多项式时间内解决它，计算机就会一直打败你。

所以我们通过了这些标准。 凯尔说：“这个游戏简单吗？” 我说：“是的，这是一个句子！” 他说：“这个游戏是彩色的吗？” 我说，“按设计！” 然后他说，“如果我证明它是 PSPACE-hard，我能拿到博士学位吗？” 我说是的，他做到了。 他的定理有许多不同的方面。 它揭示了关于不动点的某些东西，这是数学中一个非常美丽的概念。

我可以在任何地方玩游戏吗？

它是可用的，有一些调整， 在线.

你喜欢玩什么游戏？

我是游戏理论家。 [笑]我和我女儿玩了一点，但我不是玩他们长大的。 不像我的学生，他们一辈子都在玩游戏。

你在棋盘游戏的数学方面做了哪些其他工作？

我们有一个 纸 最近关于一个悬而未决的问题：如果将两个多项式时间可求解的游戏并排放在一起，这会使它们成为 PSPACE-hard 吗？ 在每一步你只能玩其中一个。 这称为游戏总和。

把两个游戏放在一起是什么意思？

在古老的围棋游戏中，当你放下足够多的棋子时，你会得到许多独立的竞技场，所以从某种意义上说你是在玩一个游戏的总和。 你必须担心这个角落和那个角落。 你想赢得全部，但这并不意味着你必须赢得每一部分。

这在哲学上很有趣，对吧？ 这就像你有一场战争，它有很多场战斗，但你的注意力是有限的。 在任何时候你只能在其中一个战场上做出单一决定，你的对手可以在另一个战场上做出回应或加倍下注。 我试图向父亲解释这件事。 当你玩一局总和的时候，真正的意思是：你怎么有策略地输？

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

自从他把你推向计算机科学以来，你父亲对你多年来所做的不同工作有何反应？

他经常问我，“你为什么要这样做？” 理论上的工作，往往多年没有结果，他渐渐明白了。 早些时候我可以谈论有限元方法——他们也在土木工程中教授它。 但是我想不通如何谈论这种消遣性的数学。

然后我想到了这本中国著名小说中的一个成语，叫做 三国演义. 其中一个角色诸葛亮几乎是一个完美的军事家，俗话说“三只鞋匠不如诸葛亮”。 它以这种轻松愉快的方式使用，表示三个普通人在集思广益时可以变得完美。 但是翻看这个成语的历史，不同地区发音不同，“shoe fixer”和“field general”同音。 所以说：“三位将领，胜过这位万能的谋士。”

我对父亲说，这正是我们用博弈求和证明的定理。 战地将军代表 [求解算法] 多项式时间博弈：在每个战场上，他们都知道如何取胜。 但困难的部分是知道什么时候输，而不是如何赢得每场比赛。 如果有人可以玩那种艰苦的游戏，那么他们就是最好的战略家。 战地将军不会做出这些深层次的逻辑决定，但不知何故，如果你把它们很好地放在一起，他们并不比这个完美的战略家差。

我对爸爸说：“我终于悟出了这个数学定理，相当于我们的一句成语！” 那时他 94 岁，非常敏锐，他说：“这是一次很好的尝试。” 我没有完全说服他。 那是我与他的最后一次技术对话； 几个月后他去世了。 每当我考虑解释我的工作时，这就是我的亮点。