江苏龙网

  1. 首页 > 人文 > >

行者然沐 苏联曾经的AI有多强？一段几乎已被世人遗忘的往事( 二 )


当时计算机科学领域一个热门研究主题是离散算法的计算复杂性 ， 克朗罗德团队对此亦有贡献 。 该团队的两位成员G.Adelson-Velsky和E.Landis提出了首个自平衡二叉查找树 ， 现在被称为AVL树 。
行者然沐 苏联曾经的AI有多强？一段几乎已被世人遗忘的往事
文章图片
向AVL树注入元素 ， AVL树方法来自ITEP 。
引入了最早的多项式可解问题和NP完全问题后 ， 该实验室希望找到能快速求解各种问题的算法 。
大多数问题都可以很快地分类到P或NP完全问题类别中 ， 但线性规划和图同构（graphisomorphism）却很难分类 。
后来 ， 另一位苏联数学家LeonidKhachiyan提出了一种用于线性规划问题的多项式时间算法 ， 但人们仍不知道图同构问题是否属于P类别 。
很自然 ， 包括AndreyLeman和BorisWeisfeiler在内的克朗罗德实验室成员对图同构问题很感兴趣 。 他们的第一个重大成果就是今天的Weisfeiler-Leman算法（1968） 。
行者然沐 苏联曾经的AI有多强？一段几乎已被世人遗忘的往事
文章图片
AndreyLeman和BorisWeisfeiler
近来随着图机器学习及图神经网络的发展 ， 人们对Weisfeiler-Leman算法的兴趣与日俱增 。
【行者然沐 苏联曾经的AI有多强？一段几乎已被世人遗忘的往事】对图同构问题的这项研究成就了AndreyLeman在克朗罗德指导下的第一篇论文 ， 但是 ， 由于克朗罗德与高级认证委员会（HAC）负责人之间存在个人恩怨 ， 这篇论文以「不是数学」的理论被拒了 。
「我不是数学家 ， 我是程序员 。 」Andrey痛苦地回应道 。
然后 ， 他的研究兴趣从组合学转向了更偏程序员的问题 ， 并在1973年捍卫了自己在V.Arlazarov指导下写的第二篇论文——一个关于数据库管理的研究成果 。 他为苏联第一个数据库INES做出了重大贡献 ， 而且因为这个数据库在苏联得到了广泛的使用 ， 苏联还授予了他部长理事会奖 。
Andrey没有止步于数据库编程 ， 他还研究了软件工程的其它问题 。 其中之一是开发能玩国际象棋的AI程序 ， 而且他开发的AI程序还成为国际象棋AI比赛的首个世界冠军 。
国际象棋AI
行者然沐 苏联曾经的AI有多强？一段几乎已被世人遗忘的往事
文章图片
克劳德·香农、约翰·麦卡锡、EdFredkin与约瑟夫·维森鲍姆（1966）
在阿兰·图灵发明了「通用图灵机」概念一年之后 ， 信息论之父克劳德·香农想要教会计算机下国际象棋 。 后来 ， 这个思路日渐流行 ， 美国和苏联都各自有团队在开发能下国际象棋的算法 。
美国这边 ， 约翰·麦卡锡在MIT带一群学生在做这件事 。 约翰·麦卡锡是1952年与图灵等人共同确定「artificialintelligence」这一术语的人之一 ， 是AI领域当之无愧的先驱人物 。
而在苏联这边 ， 开发国际象棋AI程序的正是ITEP的克朗罗德团队 。 克朗罗德实验室的开发工作始于1963年 ， 很多天才数学家参与其中 ， 其中包括G.Adelson-Velskyi、V.Arlazarov和AndreyLeman 。 苏联的《Komsomolka》报组织过一场读者与该程序的比赛 ， 而这些读者最后决定将这个程序命名为Kaissa——国际象棋女神 。
1965年 ， 约翰·麦卡锡造访苏联并与克朗罗德达成协议 ， 举办两个程序之间的首场国际比赛 。 1967年 ， 两个程序迎来首次交锋 。 比赛共4场 ， Kaissa凭借在开局知识和分析技术上的强大能力 ， 以3:1的成绩赢得比赛 。 但这只是世界杯之前的热身赛 。
行者然沐 苏联曾经的AI有多强？一段几乎已被世人遗忘的往事
文章图片
国际象棋计算机程序的首次国际竞赛：苏联（白棋）vs美国（黑棋）
1969年 ， 克朗罗德与其他一些数学家签署了一封呼吁信 ， 以捍卫另一位遭受不公正谴责的苏联数学家Esenin-Volpin 。 在苏联 ， 这种在大学里的运动是被严格禁止的 ， 于是克朗罗德不幸被开除了 ， 他的实验室也惨遭解散 。


推荐阅读


上一篇：电脑之家 OPPO Reno4系列视频拍摄全能，抖动黑暗全不怕

下一篇：IT之家 UWB 芯片正迈向成功，iPhone 11 、新汽车刺激，超宽带