从数据到算法 人对计算机编程的思维模式

csh

好复杂的东西...学数学的人牛叉  .....

zr911

第一台弈棋机
1769年，匈牙利工程师Baron Wolfgang von Kempelen为了取悦于奥地利皇后Maria Theresia而制造了一台国际象棋弈棋机。它只不过是一台纯机械设备，外形很象一个Turk（土耳其人）。当然它的高超的棋艺是由藏在机器内部的一位象棋大师提供的。这台弈棋机是一个骗局。

图灵的“纸上弈棋机”
也许令大家吃惊的是世界上第一个国际象棋弈棋程序诞生于计算机问世之前。这个程序是由一位极富远见的人编写的。他不仅预见到了计算机的问世，而且他还清楚地知道计算机的工作方式，只待计算机一问世，他的程序就可以投入运行。

这个人就是阿兰·图灵（Alan Turing）----世界上最伟大的数学家之一。二战时期，图灵领导的科研小组破解了德国人的"Enigma" 代码，为二战的胜利起了重大的作用。图灵非常爱好国际象棋。但是除了拥有一个聪明的大脑以及在刚学棋时用了点工夫以外，图灵的棋艺水平很一般。二战结束后不久，他就开始编写弈棋程序的代码。在当时世界上并没有可以运行他的程序代码的计算机，图灵就把自己当成人工CPU，一步一步手工演示，每一步棋大约要花上半个多小时。历史上记载了这台纸上弈棋机的一盘对局记录。这盘棋中，纸上弈棋机执白输给了图灵的同事Alick Glennie。以下是棋谱：

图灵纸弈机– Alick Glennie （曼彻斯特 1952年）
1.e4 e5 2.Nc3 Nf6 3.d4 Bb4 4.Nf3 d6 5.Bd2 Nc6 6.d5 Nd4 7.h4 Bg4 8.a4 Nxf3+ 9.gxf3 Bh5 10.Bb5+ c6 11.dxc6 0-0 12.cxb7 Rb8 13.Ba6 Qa5 14.Qe2 Nd7 15.Rg1 Nc5 16.Rg5 Bg6 17.Bb5 Nxb7 18.0-0-0 Nc5 19.Bc6 Rfc8 20.Bd5 Bxc3 21.Bxc3 Qxa4 22.Kd2? [应走22.h5 捉死黑象] 22...Ne6 23.Rg4 Nd4? [23...Rxb2! 24.Bxb2 Rxc2+] 24.Qd3 Nb5 25.Bb3 Qa6 26.Bc4 Bh5 27.Rg3 Qa4 28.Bxb5 Qxb5 29.Qxd6 Rd8 0-1.

香农的战略
大约在与图灵同一时代，另一位在贝尔实验室工作的著名的数学家克劳德·香农（Claude Shannon）也在考虑如何“教会”计算机下棋。他意识到这个问题的难点在于非常巨量的续着分析。他仔细区分了两种策略----α-策略和β-策略。α-策略就是计算所有变着的策略，而β-策略则在计算过程中“砍”掉一些分支。时至今日，我们仍将弈棋程序分成两大类----全搜索型（"brute force"）和选择型（selective"） 程序，尽管绝大多数高水平的程序都或多或少的属于前一类。

国际象棋替代原子计算
在战争期间，美国在位于新墨西哥州沙漠地带的洛斯阿拉莫斯（Los Alamos）建立了一个巨大的实验室。目的是用于研制原子武器。为了正确求出用于引发链式反应的内向爆炸所需的电量科学家们要进行大量的计算。1946年，为了加速这项计算过程，一位美籍匈牙利数学家John von Neumann承担了设计强力计算机的任务。1950年，一台名为MANIAC I的巨型计算机问世。他由成千上万的真空管和开关组成，每秒可执行10,000条指令。当然，它是可编程的。

科学家们并没有把这台计算机立即用于爆炸计算，而是做了一些实验。第一个实验便是编写一个弈棋程序。他们将国际象棋棋盘上的“象”去掉，设计了一个6*6大小的棋盘。尽管如此，每进行4层深度的分析，这个程序便要花上12分钟（如果加上“象”，则需3小时）。

在50年代中期这个程序曾经下过3盘棋。第一盘是程序自己对弈（白方获胜），第二盘是挑战一名大师，对方让一个皇后，经过10个小时的激战，大师获胜。第三盘则是与一位学棋仅一个星期的年轻女士交手，结果程序用了23步获得胜利。这也是人类首次在智力型的游戏中输给计算机。以下是程序获胜的对局记录。

MANIAC 1 – 人类 （洛斯阿拉莫斯, 1956年）
（6*6 棋盘,无“象”,兵第一步不能走两格,不能王车易位）
1.d3 b4 2.Nf3 d4 3.b3 e4 4.Ne1 a4 5.bxa4? [5.Nd2 and 6.Nd2-c4+ Nbcxc4 7.b3xc4 之后，局面占优] 5...Nxa4 6.Kd2? Nc3 7.Nxc3 bxc3+ 8.Kd1 f4 9.a3 Rb6 10.a4 Ra6 11.a5 Kd5 12.Qa3 Qb5 13.Qa2+ Ke5 14.Rb1 Rxa5 15.Rxb5 Rxa2 16.Rb1 [防止16...Ra1 将杀！] 16...Ra5 17.f3 Ra4 18.fxe4 c4 19.Nf3+ Kd6 20.e5+ Kd5 21.exf6Q Nc5 22.Qf6xd4+ Kc6 23.Nf3-e5 将杀获胜.

国际象棋与数学
编写弈棋程序的主要问题在于计算大量的续着。在通常的一个局面中大概有40种合法的变着。如果要为每一步棋计算一个应着，则要分析1600个不同的局面。这就是说2层分析（半个回合）需要分析1600个局面。计算两个回合，则要分析250万个局面，三个回合，41亿个局面。每盘棋大约有40个回合，那么所要分析的局面数为10的128次方个。而这远远超过了宇宙中的原子数量。

显然，没有一台计算机或其它机器可以分析如此之多的局面。然而人类也并非完美无缺，对于计算机来讲，问题在于计算深度为多少时才可以与人类的战略技巧相抗衡？早期的计算机可以每秒评估或分析大约500个局面，或者说是3分钟内分析90,000个局面。而在正式的锦标赛中，每步棋也就是需要大约3分钟。这也就意味着，计算机只能进行3层搜索（1个半回合）----这仅仅是初学者的水平。如要再增加1层搜索深度，则需每秒分析15,000个局面。但即使是4层深度，也还是太浅了。所以看起来，计算机好象不太可能达到大师级水平。

Alpha-beta算法
1958年，位于美国匹兹堡的卡耐基梅隆大学（Carnegie-Mellon university）的三位科学家（Newell, Shaw 和Simon）的重要发现使得这一问题有了重大突破。他们发现：在搜索中，可以“砍掉”搜索树中的大部分分支而不影响最终的分析结果。他们称之为：alpha-beta算法。有一点非常重要值得指出：这个算法是由纯数学理论得来的，没有附加任何的国际象棋知识。

下面非常简略地介绍一下alpha-beta算法的工作原理：假设计算机计算完第一个变着后，正要开始计算第二个变着，如果这一步棋的计算结果数值低于第一着棋，那么计算机可以立即停止继续向下计算。我们没有必要知道到底第二着棋的分值比第一着棋低多少。程序会很自然地选择第一步棋的方案。

Alpha-beta算法与全面搜索算法产生的结果是相同的，而它所需计算的局面数量却是后者的平方根。这样一来，最早期的计算机就可以搜索5层或6层。七十年代最快的计算机（如：CDC-Cyber系列）可以搜索7层深度并且达到相当的水平。然而，即使应用Alpha-beta算法，如果要把搜索深度再增加一层，计算量还是要增加5倍！这种指数式的增加使程序员们大伤脑筋。

“硬”的国际象棋机----Belle（比利）
Ken Thompson是贝尔实验室的一位计算机科学家。他并不想指望一台价值上百万美元，仅仅靠速度快上5倍甚至25倍的超级计算机来提高弈棋水平。他和他的同事们决定制造一台专门下国际象棋的计算机----Belle。它可以在一秒钟内计算大约180,000个局面。（在当时，超级计算机每秒可计算5000个局面）。Belle在正规棋赛的时限内搜索深度可以8到9层，这足以使其达到大师级水平。它不但获得了世界计算机国际象棋锦标赛冠军，而且在1980至1983年间，几乎赢得了所有计算机国际象棋赛。直到价值数千倍于它的Cray X-MPs问世。

国际象棋芯片
80年代中期， 卡耐基梅隆大学（Carnegie-Mellon university）的计算机科学家汉斯.波尔莱纳（Hans Berliner）继续了Ken Thompson的事业。这位曾经获得过国际象棋通讯赛世界冠军的科学家制造了一台硬件驱动的弈棋机----名叫“HiTech”。他和他的学生Carl Ebeling设计了一个硬件棋步生成芯片。装配有64个这样芯片的“HiTech”在1986年以微弱劣势负于Cray获得世界计算机国际象棋锦标赛亚军。

之后不久，Berliner的学生许峰雄（Feng-hsiung Hsu），Murray Campbell等人开发了自己的弈棋机----名为“ChipTest”后来发展为“深思”（Deep Thought），“深思”价值5000美元，它可以每秒计算500,000个局面。许峰雄和Campbell后来脱离了他们的老师加入了IBM。并与Joe Hoane一道合作开发了“深兰”（Deep Blue）。

深兰
在费城和纽约与棋坛巨无霸----卡斯帕洛夫交手的“深兰”包含有一个由大量可以进行快速计算的专用芯片组成的IBM SP/2服务器。每一个专用芯片可以每秒处理二百万到三百万个局面。超过200个这样的芯片组合到一起，运行于其上的程序每秒便可以处理2亿个局面。

搜索深度与棋艺水平
每秒计算2亿个局面对于一台国际象棋计算机意味着什么？Ken Thompson----Belle的制造者（他也是Unix和C语言的创造者）在80年代做了很多有关搜索深度与弈棋水平的很有趣的实验。

Thompson让Belle自己与自己对弈，并把一方的搜索层次不断加深。通常情况下，每一层深度可以换算成200个埃洛分。在4层搜索深度时，Belle的等级分约为1230，当搜索深度为9层时，Belle的等级分达到2328。将实验结果画成曲线，并将曲线平滑延伸，我们可以看到，当搜索深度为14层时，计算机的等级分可以达到世界冠军水平---2800分。

以下是专家的结论：如果想要计算机达到人类国际象棋世界冠军的水平，那么计算机要有每秒计算10亿个局面的能力。深兰接近了这一目标，但还没有达到。

软件方面
当然，弈棋程序的质量同样非常重要。现在，顶级的国际象棋程序例如：Fritz和Junior运行在最快的硬件设备上时，每秒可计算600,000个局面。它们的等级分已经成功地超过了2600分并且可以与世界排名前100名的棋手相对抗。在快棋赛中，大约只有世界前10名的棋手可以与之抗衡，如果在闪电战中，恐怕只有两三名棋手能够“幸存”了。

对局的两端
开局库
开局棋库在提高计算机弈棋能力上起了非常重要的作用。许许多多大师们的开局知识和经验可以很方便的记录在磁盘上并且在开局阶段供程序使用。即使PC机上的程序也可以“通晓”数以千记的开局棋路，并且每一路分支都有详尽的分析（如：棋是如何走的？取得过什么胜绩？棋出自哪位棋手？他的水平如何？等等）。通常情况下，一个程序所弈的前15至20步都来自开局库，然后才真正进入到程序“思考”阶段。如果没有这些人类的开局知识和经验，计算机的水平会显著下降。

通过人类许多年来积累的开局知识，计算机在对弈过程中会占有相当大的优势，同样，计算机也获益于人类对残局知识的研究。

残局库
在残局库的开发方面，Ken Thompson仍然是先导者。80年代期间，他开始制作4子和5子的残局库。一个典型的5子残局如：王双象对王单马，就包含有121,000,000种不同的局面。如果再加一个兵，那么局面数会增加到335,000,000。为此，Thompson专门编写了程序，用于生成所有可能的局面并计算出每一个强制性的变化。然后他又通过某种方式将计算数据压缩，使得一张标准的CD-ROM上可以存放20个不同的残局。

通过这些数据库，计算机可以将残局走得“绝对完美”，就象上帝在下棋。面对满足条件的任何一个局面，计算机可以立即知道该局面是赢棋，和棋还是输棋并且需要下多少步。通常在15步棋之前，计算机就会“看到”将杀并宣布胜利。在输棋的局面中，计算机会以最优的方案进行最顽强的抵抗。“深兰”就采用了Thompson的残局库，就连PC机上的程序Fritz也采用了他的搜索树。

人类对开局和残局的研究还要不断的进行和深入。然而有一点可以指出----开局库和残局库永远不会交叠。因为没有人会见到计算机在弈出第一步棋1.e4之后就宣布在第40步将杀获胜。
　　人们对于棋牌类人机对战的算法的思考，一直没有停止。本文对各棋牌类游戏进行的简单分析，希望能给对此方面感兴趣的人士一些有益信息。
－－－评论
　　　也许你也能创造自己的算法！
　　　或者抛开现在的编程的模式！

＝＝＝＝＝＝＝＝＝＝＝＝
我在网上找到的数据结构