CH02 计算学科中的科学问题 概 述.

Presentation on theme: "CH02 计算学科中的科学问题 概 述."— Presentation transcript:

1 CH02 计算学科中的科学问题 概 述

2 2.1 科学问题的定义 科学问题是指一定时代的科学认识主体，在已完成的科学知识和科学实践的基础上，提出的需要解决且有可能解决的问题。它包含一定的求解目标和应答域，但尚无确定的答案。(例如IPv4——IPv6） 能否在所从事的工作中提出关键和重要的科学问题，对我们每个人来说都是一个挑战。

3 2.1 科学问题的主要特征 时代性：每一个时代都有它自己的科学问题 混沌性：渴望对新知识的追求，追求开始的时候是模糊不清的。 可解决性 可变异性：能引出另外具有可解决性的科学问题 可待解性：绝非永远不可解决。

4 2.1 科学问题的方法论作用 科学问题的裂变式作用 如对“数学基础问题”的研究，导致了“形式系统相容性问题”的研究， 最后出现“能行性问题”的研究， 最终于20世纪30年代由图灵、哥德尔、丘奇和波斯特等人共同奠定了计算学科的理论基础 实现了人类对计算认识问题的重大突破。

5 2.1 科学问题的方法论作用 科学问题的聚变式作用——殊途同归 对不同科学问题的研究最终导致同一科学问题的发现 科学问题的激励作用 它召唤和激励着人们为解决这些富有挑战性的问题而勇往直前。 本章仅对反映计算学科本质的根本问题、学科各领域的基本问题、在学科中起重要作用的典型问题，以及人工智能中的若干哲学问题进行分析。

6 CH02 计算学科中的科学问题 计算的本质 计算学科的定义及其根本问题

7 2.2 计算本质的认识历史

8 形式化方法和理论的研究起源于对数学的基础研究。
康托尔的集合论和罗素悖论 形式化方法和理论的研究起源于对数学的基础研究。 康托尔（G.Cantor，1845～1918）从1874年开始，对数学基础作了新的探讨，发表了一系列集合论方面的著作，从而创立了集合论。 “罗素悖论”，从而导致了数学发展史上的第三次危机。

9 希尔伯特（D.Hilbert）在数学基础的研究中提出了一个设想
希尔伯特纲领 希尔伯特（D.Hilbert）在数学基础的研究中提出了一个设想 将每一门数学的分支形式化，构成形式系统或形式理论，并在以此为对象的元理论即元数学中，证明每一个形式系统的相容性，从而导出全部数学的相容性。 目标是要寻找通用的形式逻辑系统，该系统应当是完备的，即在该系统中，可以机械地判定任何给定命题的真伪。

10 库尔特·哥德尔（K．Godel） 认为《数学原理》所定义的系统既是一致的，也是完备的 任何系统的完备和一致性，可以由系统本身得到证明。 1931年，“希尔伯特纲领”被奥地利逻辑学家Godel搠出一个大窟窿 Godel认为没有一种公理系统可以导出数论中所有的真实命题，除非这种系统本身就有悖论。 推翻“希尔伯特纲领”，还直逼《数学原理》，说它本身就是不一致的。

11 “希尔伯特纲领”的研究基础是逻辑和代数，即布尔代数 Gödel提出的关于形式系统的“不完备性定理”中指出
这种形式系统是不存在的，从而宣告了著名的“希尔伯特纲领”的失败。 表明形式系统不能穷尽全部数学命题，任何形式系统中都存在着该系统所不能判定其真伪的命题。

12 “希尔伯特纲领”是在保存全部古典数学的前提下去排除集合论悖论的，它给数学基础问题的研究带来了全新的转机
希尔伯特纲领的历史意义 “希尔伯特纲领”是在保存全部古典数学的前提下去排除集合论悖论的，它给数学基础问题的研究带来了全新的转机 希尔伯特纲领的提出使元数学得到了确立和发展 希尔伯特纲领的失败启发人们应避免花费大量的精力去证明那些不能判定的问题，而应把精力集中于解决具有能行性的问题。

13 图灵对计算本质的揭示 “哥德尔定理”的提出使整个逻辑和数学领空中阴云四布。 天才的图灵在数理逻辑大本营的剑桥大学提出一个设想：能否有这样一台机器，通过某种一般的机械步骤，能在原则上一个接一个地解决所有的数学问题。 图灵从计算一个数的一般过程入手对计算的本质进行了研究，从而实现了对计算本质的真正认识。 图灵用形式化方法成功地表述了计算这一过程的本质：所谓计算就是计算者（人或机器）对一条两端可无限延长的纸带上的一串0和1执行指令，一步一步地改变纸带上的0或1，经过有限步骤，最后得到一个满足预先规定的符号串的变换过程。

14 图灵机反映的是一种具有能行性的用数学方法精确定义的计算模型，而现代计算机正是这种模型的具体实现。
现代计算机的产生以及计算学科的定义 图灵机反映的是一种具有能行性的用数学方法精确定义的计算模型，而现代计算机正是这种模型的具体实现。 计算学科是对描述和变换信息的算法过程，包括对其理论、分析、设计、效率、实现和应用等进行的系统研究。 来源于对算法理论、数理逻辑、计算模型、自动计算机器的研究，并与存储式电子计算机的发明一起形成于20世纪40年代初期。

15 计算学科的根本问题是：什么能被（有效地）自动进行。
“能行性”这个计算学科的根本问题决定了计算机本身的结构和它处理的对象都是离散型的，甚至许多连续型的问题也必须在转化为离散型问题以后才能被计算机处理。例如，计算定积分就是把它变成离散量，再用分段求和的方法来处理的。 计算学科所有分支领域的根本任务就是进行计算，其实质就是字符串的变换。

16 从计算的角度认知思维、视觉和生命过程 以1975年图灵奖共同获得者西蒙（H.A.Simon）和纽厄尔（A.Newell）为代表的符号主义者认为：认知是一种符号处理过程。他们还提出了人类思维过程也可用某种符号来描述的思想，即思维就是计算（认知就是计算）的思想。除了思维、认知之外，有关视觉认知理论的学者也把视觉看作是一种计算。 1994年11月美国科学家L.M.Adleman在《 Science 》上发表了论文“Molecular Computation of Solutions to Combinatorial Problems” ，论证了DNA（脱氧核糖核酸）计算技术的可行性，并用DNA计算机解决了一个简单的有向哈密尔顿路径问题

17 2002年，阿德勒曼教授应用DNA计算机可以解决具有100万种可能结果的有向哈密尔顿路径问题，阿德勒曼的工作从一个侧面探讨了生命过程就是一种计算的思想。

18 CH02 计算学科中的科学问题 计算学科中的典型问题 及其相关内容

19 哥尼斯堡七桥问题 17世纪的东普鲁士有一座哥尼斯堡城，城中有一座奈佛夫岛，普雷格尔河的两条支流环绕其旁，并将整个城市分成北区、东区、南区和岛区4个区域，全城共有7座桥将4个城区相连起来。 通过这7座桥到各城区游玩，问题：寻找走遍这7座桥的路径，要求过每座桥只许走一次，最后又回到原出发点。

20 问题的抽象 1736年，大数学家列昂纳德·欧拉（L.Euler）发表了关于“哥尼斯堡七桥问题”的论文。
他抽象出问题最本质的东西，忽视问题非本质的东西（如桥的长度等），从而将哥尼斯堡七桥问题抽象为一个数学问题，即经过图中每边一次且仅一次的回路问题了。

21 欧拉给出了哥尼斯堡七桥问题 的证明，还用数学方法给出了三条判定规则： 如果通奇数座桥的地方不止两个，满足要求的路线是找不到的。
欧拉回路 欧拉给出了哥尼斯堡七桥问题 的证明，还用数学方法给出了三条判定规则： 如果通奇数座桥的地方不止两个，满足要求的路线是找不到的。 如果只有两个地方通奇数座桥，可以从这两个地方之一出发，找到所要求的路线。 如果没有一个地方是通奇数座桥的，则无论从哪里出发，所要求的路线都能实现。

22 问题：在某个图G中，能不能找到这样的路径，即从一点出发不重复地走过所有的结点，最后又回到原出发点。
哈密尔顿回路问题 问题：在某个图G中，能不能找到这样的路径，即从一点出发不重复地走过所有的结点，最后又回到原出发点。 “哈密尔顿回路问题”与“欧拉回路问题”的不同点 “哈密尔顿回路问题”是访问每个结点一次，而“欧拉回路问题”是访问每条边一次。 对图G是否存在“欧拉回路”前面已给出充分必要条件，而对图G是否存在“哈密尔顿回路”至今仍未找到满足该问题的充分必要条件。

23 图论的形成和发展 欧拉的论文为图论的形成奠定了基础。 图论已广泛地应用于 计算学科 运筹学 信息论 控制论等学科 图论已成为我们对现实问题进行抽象的一个强有力的数学工具。 图论在计算学科中的作用越来越大，图论本身也得到了充分的发展。

24 梵天塔问题 将64个直径大小不一的金盘子，按照从大到小的顺序依次套放在第一根柱子上，形成一座金塔，天神让庙里的僧侣们将第一根柱子上的64个盘子借助第二根柱子全部移到第三根柱子上，既将整个塔迁移，同时定下3条规则： 每次只能移动一个盘子； 盘子只能在三根柱子上来回移动，不能放在他处； 在移动过程中，三根柱子上的盘子必须始终保持大盘在下，小盘在上。

25

26 算法：C语言描述 hanoi(int n,char left,char middle,char right) { if(n==1) move(1,one,_,three); else hanoi(n-1,left,right,middle); move(1,left,_,right); hanoi(n-1,middle,left,right); }

27 = 2(2h(n-2)+1)+1=22h(n-2)+2+1 = 23h(n-3)+22+2+1 ……
= 2n-1+… =2n-1 需要移动盘子的次数为： 264-1=

28 假定每秒移动一次，一年有31536000秒，则僧侣们一刻不停地来回搬动，也需要花费大约5849亿年的时间。
假定计算机以每秒1000万个盘子的速度进行搬迁，则需要花费大约58490年的时间。 理论上可以计算的问题，实际上并不一定能行，这属于算法复杂性方面的研究内容。

29 算法复杂性中的难解性问题、P类问题和NP类问题
空间复杂性问题] 关于梵天塔问题算法的时间复杂度， 用O(2n)来表示 当算法的时间复杂度的表示函数是一个多项式，如O(n2)时，则可以处理。 一个问题求解算法的时间复杂度大于多项式（如指数函数）时，算法的执行时间将随n的增加而急剧增长， 以致即使是中等规模的问题也不能求解出来，于是在计算复杂性中，将这一类问题称为难解性问题。

30 人工智能领域中的状态图搜索问题（解空间的表示或状态空间搜索问题）就是一类典型的难解性问题。
时间复杂性问题 人工智能领域中的状态图搜索问题（解空间的表示或状态空间搜索问题）就是一类典型的难解性问题。 在计算复杂性理论中，将所有可以在多项式时间内求解的问题称为P类问题，而将所有在多项式时间内可以验证的问题称为NP类问题。由于P类问题采用的是确定性算法，NP类问题采用的是非确定性算法，而确定性算法是非确定性算法的一种特例，因此，可以断定PNP。

31 证比求易算法 艾述国王向邻国秋碧贞楠公主求婚。公主出了一道题： 求出 的一个真因子。若国王能在一天之内求出答案，公主便接受他的求婚。 国王回去后立即开始逐个数地进行计算，他从早到晚，共算了三万多个数，最终还是没有结果。国王向公主求情，公主将答案相告： 是它的一个真因子。国王很快就验证了这个数确能除尽 。

32 公主说：“我再给你一次机会” 国王立即回国，并向时任宰相的大数学家孔唤石求教，大数学家在仔细地思考后认为这个数为17位，则最小的一个真因子不会超过9位， 他给国王出了一个主意：按自然数的顺序给全国的老百姓每人编一个号发下去，等公主给出数目后，立即将它们通报全国，让每个老百姓用自己的编号去除这个数，除尽了立即上报，赏金万两。

33 顺序算法和并行算法 国王最先使用的是一种顺序算法，其复杂性表现在时间方面， 后面由宰相提出的是一种并行算法，其复杂性表现在空间方面。
直觉上，我们认为顺序算法解决不了的问题完全可以用并行算法来解决，甚至会想，并行计算机系统求解问题的速度将随着处理器数目的不断增加而不断提高，从而解决难解性问题，其实这是一种误解。 当将一个问题分解到多个处理器上解决时，由于算法中不可避免地存在必须串行执行的操作，从而大大地限制了并行计算机系统的加速能力。

34 阿达尔定律 设f为求解某个问题的计算存在的必须串行执行的操作占整个计算的百分比，p为处理器的数目，Sp为并行计算机系统最大的加速能力，则
串行执行操作仅占全部操作1%，解题速度最多也只能提高一百倍。 对难解性问题而言，提高计算机系统的速度是远远不够的，而降低算法复杂度的数量级才是最关键的问题。

35 P＝？NP P类问题——存在多项式时间的算法的一类问题； NP类问题——非多项式时间算法解的一类问题。像梵塔问题、推销员旅行问题、（命题表达式）可满足问题这类，至今没有找到多项式时间算法解的一类问题。 P＝NP？如果P=NP，则所有在多项式时间内可验证的问题都将是在多项式时间内可求解（或可判定）的问题。 要证明P≠NP，目前还无法做到这一点 。

36 在P＝?NP问题上，库克（S.A.Cook）等人认为NP类中的某些问题的复杂性与整个类的复杂性有关，当这些问题中的任何一个存在多项式时间算法时，则所有这些NP问题都是多项式时间可解的，这些问题被称为NP完全性问题。 多达数千个的NP完全性问题。有代表性的有：哈密尔顿回路问题、旅行商问题（也称货郎担问题）、划分问题、带优先级次序的处理机调度问题、顶点覆盖问题等。

37 旅行商问题与组合爆炸问题

38 旅行商问题与组合爆炸问题

39 旅行商问题与组合爆炸问题 如果有3个城市A，B和C，互相之间都有往返的飞机，而且起始城市是任意的，则有6种访问每个城市的次序：ABC,ACB,,BAC,BCA,CAB,CBA。如果有4个城市，则有24种次序，可以用阶乘来表示：4！=4×3！=4×3×2×1=24； 若有5个城市，则有5！=5×4！=120，类似的有6！=720等等。即使用计算机来计算，这种急剧增长的可能性的数目也远远超过计算资源的处理能力，  Cook评论：“如果有100个城市，需要求出100！条路线的费用，没有哪一台计算机能够胜任这一任务。打个比方，让太阳系中所有的电子以它旋转的频率来计算，就算太阳烧尽了也算不完。 问题的关键是某些东西在实践中行不通。

40 1998年，科学家们成功地解决了美国13509个城市之间的TSP问题，
解决15112个城市之间的TSP问题，共使用了美国Rice大学和普林斯顿大学之间网络互连的、由速度为500MHz 的Compaq EV6 Alpha 处理器组成的110台计算机，所有计算机花费的时间之和为22.6年。

41 TSP的应用 一个典型的例子就是机器在电路板上钻孔的调度问题（注：在该问题中，钻孔的时间是固定的，只有机器移动时间的总量是可变的），在这里，电路板上要钻的孔相当于TSP中的“城市”，钻头从一个孔移到另一个孔所耗的时间相当于TSP中的“旅行费用”。 运输业、 后勤服务业等 然而，由于TSP会产生组合爆炸的问题，因此寻找切实可行的简化求解方法就成为问题的关键。

42 生产者－消费者问题 一个生产者和一个消费者以及一个硬件资源。
所谓消费者是指使用某一软硬件资源时的进程，而生产者是指提供（或释放）某一软硬件资源时的进程。 一个重要的概念，即信号灯，它借用了火车信号系统中的信号灯来表示进程之间的互斥。

43 “哲学家共餐”问题 5个哲学家围坐在一张圆桌旁，每个人的面前摆有一碗面条，碗的两旁各摆有一只筷子 一个哲学家的生活进程可表示为：
（1）思考问题； （2）饿了停止思考，左手拿一只筷子（拿不到就等）； （3）右手拿一只筷子（拿不到就等） ； （4）进餐；（5）放右手筷子； （6）放左手筷子； （7）重新回到思考问题状态（1）。 问题是：如何协调5个哲学家的生活进程， 使得每一个哲学家最终都可以进餐。

44 按哲学家的活动进程，当所有的哲学家都同时拿起左手筷子时，则所有的哲学家都将拿不到右手的筷子，并处于等待状态，那么哲学家都将无法进餐，最终饿死。
将哲学家的活动进程修改一下，变为当右手的筷子拿不到时，就放下左手的筷子，这种情况是不是就没有问题？不一定，因为可能在一个瞬间，所有的哲学家都同时拿起左手的筷子，则自然拿不到右手的筷子，于是都同时放下左手的筷子，等一会，又同时拿起左手的筷子，如此这样永远重复下去，则所有的哲学家一样都吃不到饭。

45 程序并发执行时进程同步有关的经典问题还有：读－写者问题（Reader－Writer Problem）、理发师睡眠问题（Sleeping Barber Problem）等。

46 GOTO语句的问题以及程序设计方法学 1966年，C.BÖhm和G.Jacopini发表了关于“程序结构”的重要论文《带有两种形成规则的图灵机和语言的流程图》（Flow Diagrams, Turing Machines and Languages with Only Two Formation Rules），给出了任何程序的逻辑结构都可以用3种最基本的结构（如图2.6所示），即顺序结构、选择结构和循环结构来表示的证明。

47

48 GOTO语句 1974年，著名计算机科学家、图灵奖获得者克努特（D.E.Knuth）教授在他发表的有影响力的论文《带有GOTO语句的结构化程序设计》（Structured Programming with Goto Statements）中对这场争论作了较为全面而公正的论述： 滥用GOTO语句是有害的，完全禁止也不明智， 在不破坏程序良好结构的前提下，有控制地使用一些GOTO语句，就有可能使程序更清晰，效率也更高， 关于“GOTO语句”的争论，其焦点应当放在程序的结构上，好的程序应该逻辑正确、结构清晰、朴实无华。

49 关于“GOTO语句”问题的争论直接导致了一个新的学科分支领域，即程序设计方法学的产生。程序设计方法学是对程序的性质及其设计的理论和方法进行研究的学科，它是计算学科发展的必然产物，也是计算机科学与技术方法论中的重要内容。

50 CH02 计算学科中的科学问题 人工智能中的若干哲学问题

51 图灵测试 1950年在英国《 Mind》杂志上发表了 《Computing Machinery and Intelligence》 比赛规则是∶ 让一台计算机与人进行各种话题的文本式聊天，这名参加聊天的人将不知道自己聊天的对象是另外一个人还是一台计算机。 如果这台计算机“足够聪明”，也即它上面运行的程序“足够智能”，能够让与它聊天的对象相信它是一个“人”那么它就 “会思考”———图灵本人更愿意将计算机的这种能力称之为“会摹仿”。 图灵的天才预言终于在IBM的“深蓝”上得到彻底实现。

52 不要求接受测试的思维机器在内部构造上与人脑一样， 只是从功能的角度来判定机器是否能思维，也就是从行为主义这个角度来对“机器思维”进行定义。
图灵测试 不要求接受测试的思维机器在内部构造上与人脑一样， 只是从功能的角度来判定机器是否能思维，也就是从行为主义这个角度来对“机器思维”进行定义。 尽管图灵对“机器思维”的定义是不够严谨的，但他关于“机器思维”定义的开创性工作对后人的研究具有重要意义， 一些学者认为，图灵发表的关于“图灵测试”的论文标志着现代机器思维问题讨论的开始。

53 罗布诺奖 一年一度的“罗布诺奖”计算机与人聊天赛于当地时间9月19日上午10时在美国纽约举行 “罗布诺奖”发起人休·罗布诺挑选了4台计算机参加决赛。 这4台拥有智能程序的计算机将和一个“陪考人”呆在一个房间里，至少一名“主考官”将从隔壁房间内通过电脑打字与4台计算机和“陪考人”自由聊天———他不知道与自己聊天的对象到底是人还是机器， 如果有台计算机能在聊天中让“主考官”相信它是“人”，那么这台计算机和发明它的主人将夺得10万美元的大奖。

54 符号主义者认为认知是一种符号处理过程，人类思维过程也可用某种符号来描述，即思维就是计算（认知就是计算），这种思想构成了人工智能的哲学基础之一。其实，历史上把推理作为人类精神活动的中心，把一切推理都归结于某种计算的想法一直吸引着西方的思想家。然而，由于人们对心理学和生物学的认识还很不成熟，对人脑的结构还没有真正的了解，更无法建立起人脑思维完整的数学模型。因此，到目前为止，人们对人工智能的研究并无实质性的突破。 在未来，如果我们能像图灵揭示计算本质那样揭示人类思维的本质，即“能行”思维，那么制造真正思维机器的日子也就不长了。可惜要对人类思维的本质进行描述，还是相当遥远的事情。

55 西尔勒的“中文屋子” 美国哲学家约翰·西尔勒（J.R.Searle）将有关人工智能的研究划分为强人工智能（Strong Artificial Intelligence，简称强AI）和弱人工智能（Soft Artificial Intelligence，简称弱AI）两个派别。 弱AI认为：计算机的主要价值在于它为我们提供了一个强大的工具； 强AI的观点则是：计算机不仅是一个工具，形式化的计算机是具有意识的。 1980年，西尔勒在《Behavioral and Brain Sciences》杂志上发表了《 Minds、Brains and Programs》的论文，在文中，他以自己为主角设计了一个“中文屋子（Chinese Room）”的假想试验来反驳强AI的观点：

56 电脑博弈传奇 1997年5月11日，人机世纪大战终于降下了帷幕，随着国际象棋世界冠军卡斯帕罗夫败给了IBM公司的一台机器 “深蓝” ,全世界都永远不会忘记那震惊世界的9天的“搏杀”。 卡斯帕罗夫在1988年曾：2000年前电脑绝不会战胜特级象棋大师，虽然卡斯帕罗夫也承认，电脑有可能击败一般的特级大师，但是他斩钉截铁地强调指出：“不包括卡尔波夫和我！”

57

58 卡斯帕罗夫 :阿塞拜疆的首都巴库。 1980年他获得世界少年组冠军， 1981年他并列夺得苏联冠军，随后他又在一系列的国际大赛里频频夺冠。 1984年他一路过关斩将赢得向当时的世界 冠军卡尔波夫挑战的资格。 1985年22岁的卡斯帕罗夫成为历史上最年轻的 国际象棋冠军。 从那以后连续三次击败俄罗斯的卡尔波夫，分别各一次击败英国的肖特和印度的阿南德，捍卫了自己的冠军头衔。

59 棋盘一侧是卡斯帕罗夫，棋盘的另一侧是许峰雄博士
许峰雄将通过另一台带有液晶显示屏的黑色电脑，负责操纵“深蓝”迎战人类世界冠军。 5月3日到5月11日， “深蓝”终以3.5比2.5的总比分将卡斯帕罗夫逼下了世界冠军的王座。 当卡斯帕罗夫的棋局处于不利的时候，他仍然习惯地睁大双眼瞪着许峰雄，似乎认为这个人才是自己的对手，必须用目光给对方造成心理上的压力。

60 许峰雄设计的第一台能下棋的电脑叫“蕊验”。 1987年，他设计的电脑在与其它电脑的角逐中获得冠军，
1988年，他把“蕊验”电脑升级为“深思”，首次战胜了国际象棋特级大师本特·拉尔森，赢得电脑界同行一片喝彩声。 1989年，许峰雄和他的两名助手带着有250多个芯片，每秒能计算750万步棋的“深思”电脑，来到IBM公司设在纽约的电脑研究中心

61 Deep blue 1995年，“学名”为“IBM AS/6000 SP大规模多用途并行处理机”正式诞生，计算速度达到了每秒钟1亿棋步。 最大特点是32个处理器采用“并行处理”的方式解决复杂问题。

62 1996年2月，在美国费城，许峰雄指挥“深蓝”与卡斯帕罗夫再次交锋。
卡斯帕洛夫到底不愧为“有史以来最伟大的棋手”，他稳扎稳打，以3胜2平1负的战绩再次战胜了电脑。 双方作战的过程十分艰难，许峰雄从“深蓝”的进步中看到了曙光。 在以后的一年里，许峰雄和另外四位电脑科学家决心给电脑输入了近两百万局国际象棋程序，再次提高了它的运算速度，使它每秒能分析2亿步棋。由国际象棋特级大师本杰明为它当“陪练”，找出某些棋局的弱点，然后再修改程序。

63 阿兰·图林的“纸上下棋机” 人问： 你下国际象棋吗？ 机答： 是。
人问： 我在我的K1处有棋子K；你仅在K6处有棋子K，在R1处有棋子R。现在轮到你走，你应该下那步棋？ 机答： （在15秒钟后）棋子R走到R8处，将军！ 1953年，图林一篇论文《数字计算机用于竞赛：象棋》中， 初步论述如何编制计算机下棋程序，并详细讲解了机器同一名中等水平棋手实际对局的走法。然而，那时的电脑还不足以用来支持图林的理论，于是，“愚笨”的图林竟然想到去发明“一台”纸上下棋机，以验证自己的设想。

64 把“兵”向前移动一步后，图林就按事先拟定的算法费力地在纸上计算大约半小时，然后才决定是走他的“马”还是走“车”来对付你的“兵”。
“纸机器”实际是一种程序算法 每一步棋都用人工手算后决定实际着法。 把“兵”向前移动一步后，图林就按事先拟定的算法费力地在纸上计算大约半小时，然后才决定是走他的“马”还是走“车”来对付你的“兵”。 有资料记载说，1952年，图林用“纸机器”与一位名叫格伦尼的大学生对弈，开局走得相当精彩，直到第29步时，“纸机器”算出格伦尼似乎没有什么杀着，贪婪地用“后”吃掉了对方的“兵”，结果使自己的门户大开，被格伦尼一着将死。

65 他需要计算双方的棋局优势，在哪些地方布防哪类棋子具有更大的威慑力。
学科诞生 他需要计算双方的兵力优势，为不同种类的棋子赋予一定的分值，例如，“兵”1、“马”3、“士”3.5、“车”5、“后”10，“王”则具有最高分，例如1000，因为它绝对不能被吃掉。 他需要计算双方的棋局优势，在哪些地方布防哪类棋子具有更大的威慑力。 把兵力优势和棋局优势用加权求和的数学式联系起来，构成某种形式的“估值函数”。 用“估值函数”来计算每一可能的合法棋步，寻找函数值最大即对自己最有利的那一步着法，

66 1950年，美国贝尔实验室Shannon的论文《国际象棋与机器》。
要想全部得到一方“马”的所有可能动作以及对方“马”的动作，人工计算决定开局棋步需要的年数是10的95次方，如果用机器运算，仅需要人工时间的百分之一。 1956年， Shannon与麦卡锡、明斯基、罗彻斯特等人发起了具有深远历史意义的“达特莫斯会议”，正式启用“人工智能”这一术语，成为人工智能领域的泰山北斗之一。

67 这个程序可以记住17500张棋谱，实战中能自动分析猜测哪些棋步源于书上推荐的走法，准确率达48％。
塞缪尔 塞缪尔：参加会议的“10大金刚”之一，来自IBM公司的工程师。塞缪选择规则较简单的西洋跳棋作为突破口，成功地研制出世界上第一台电脑“跳棋机”。 塞缪尔的跳棋程序运行于IBM704。 这个程序可以记住17500张棋谱，实战中能自动分析猜测哪些棋步源于书上推荐的走法，准确率达48％。 塞缪尔命令“跳棋机”首先与自己对奕，从而积累经验。1959年，“跳棋机”战胜了塞缪尔本人 IBM704—— 一种用电子管组装的大型通用电子计算机。

68 1962年，一举击败美国一个州保持8年不败记录的跳棋冠军尼亚莱；然而，后来它终于被世界跳棋冠军击败。
塞缪尔的发表了题为《利用跳棋进行机器学习的研究》论文。这台“跳棋机”至今仍是电脑下棋中最杰出的成就之一。 塞缪尔的成就大大鼓舞了人工智能和电脑下棋的研究队伍。参加达特莫斯会议的另一位天才科学家、后来又荣膺图林奖、诺贝尔经济奖和杰出科学贡献奖的赫伯特·西蒙教授，在1957年曾欢欣鼓舞地预测说：“计算机在10年内将成为世界的国际象棋冠军！”

69 “深蓝”战胜卡斯帕罗夫后，以“深蓝”主管谭崇仁（C. J. Tan，美籍华人）、设计师许峰雄（C. B
“深蓝”战胜卡斯帕罗夫后，以“深蓝”主管谭崇仁（C.J.Tan，美籍华人）、设计师许峰雄（C.B.Hsu，美籍华人）、象棋顾问本杰明（GM.J.Benjamin）及其他科学家、工程师加盟的 “深蓝队”获得奖金70万美元，卡斯帕罗夫获40万美元。另外，IBM公司也从中获得了大约5000万美元的广告收益。因此，与其说是“深蓝”战胜了卡斯帕罗夫，还不如说是“深蓝队”战胜了卡斯帕罗夫。

70 3．博弈树搜索 国际象棋、西洋跳棋与围棋、中国象棋一样都属于双人完备博弈。所谓双人完备博弈就是两位选手对垒，轮流走步，其中一方完全知道另一方已经走过的棋步以及未来可能的走步，对弈的结果要么是一方赢（另一方输），要么是和局。 对于任何一种双人完备博弈，都可以用一个博弈树（与或树）来描述，并通过博弈树搜索策略寻找最佳解。

71 博弈树类似于状态图和问题求解搜索中使用的搜索树。搜索树上的第一个结点对应一个棋局，树的分支表示棋的走步，根节点表示棋局的开始，叶节点表示棋局的结束。一个棋局的结果可以是赢、输或者和局。
对于一个思考缜密的棋局来说，其博弈树是非常大的，就国际象棋来说，有10120个结点（棋局总数），而对中国象棋来说，估计有10160个结点，围棋更复杂，盘面状态达10768。计算机要装下如此大的博弈树，并在合理的时间内进行详细的搜索是不可能的。因此，如何将搜索树修改到一个合理的范围，是一个值得研究的问题，“深蓝”就是这类研究的成果之一。

72 4．结论 “深蓝”战胜人类最伟大的棋手卡斯帕罗夫后，在社会上引起了轩然大波。一些人认为，机器的智力已超越人类，甚至还有人认为计算机最终将控制人类。其实人的智力与机器的智力根本就是两回事，因为，人们现在对人的精神和脑的结构的认识还相当缺乏，更不用说对它用严密的数学语言来进行描述了，而电脑是一种用严密的数学语言来描述的计算机器。