从数据到算法 计算机国际象棋漫谈

时间:2008-11-24   来源:   网友评论:0   人气: 438 作者:

第一台弈棋机
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 将杀获胜.


 

文章评论