计算机如何下国际象棋

【美国《科学》周刊２月２日一期文章】题：计算机最终会将死世界冠军吗？
２月１０日，当今世上公认的最优秀国际象棋棋手、世界冠军卡斯帕罗夫开始与１ＢＭ开发的“深蓝”计算机对奕。
卡斯帕罗夫认为，在快棋赛中，机器有可能侥幸取胜。但他又公开宣称：“在严肃、经典的比赛中，计算机在本世纪没有赢棋的机会。”“深蓝”可算１５步棋
与赢过卡斯帕罗夫几盘棋的前辈“深思”相比，“深蓝”采用了新的算法，它可计算到后１５步，国际大师一般可想到１０步或１ｌ步之远。在与卡斯帕罗夫的比赛中，“深蓝”将只计算后１２步的所有可能性，但是，对于利害关系很大的走法将算到３０步以后。
要使计算机具备这一能力，“深蓝”的程序设计者们必须克服人工智能领域的一个关键问题：在组合剧增的情况下进行全盘搜索。当事件数成指数增长时，就会发生组合剧增情况。以下棋为例，棋手每走一步约有３０步不同的走法。那么，要看到１５步之远，计算机必须算遍３０的１５次方种不同走棋过程，并从中作出选择。要选择最佳着法，计算机必须仔细考察这个３０杈的树形图。解决这一问题的基本思想是，计算每种可能的走法，把分数付给树形图的每个端点，分数越高局面越好。然后把分数回送到起始局面。得分最高的树杈对应着计算机的走法。而得分最低的树杈则对应对手的走法。假设对手总是想使计算机的局面最差。使用新算法
但是，由于组合剧增的缘故，如果按照一般的枚举算法，即使是目前最快的计算机完成对每步棋的全部搜索也要花几千年。依靠所谓的“α—β”算法，“深蓝”通过只考察树形图的一小部分避免了组合剧增这一难题。这种算法可以决定忽略哪种选择是安全的。基本思想是：程序确定了一步“好”棋后，一旦算出其他着法会导致较差的局面，就终止考虑这一着法。
为使这种策略达到最大效果，１ＢＭ的研究小组对搜索进行了组织，使“深蓝”能够相对较早地确定好棋。其中的一项技术是先进行“浅”搜索，比如深度只有１０步，以粗略指出哪些步是有希望的，然后对这些走法进行深度较大的搜索。利用有些走法常常导致相同局面这一事实，“深蓝”减掉了对它们的搜索。这些聪明的搜索策略使“深蓝”要处理的局面数减小到１０００亿种左右。即使是这样，在个人计算机上也不能运行“深蓝”程序。深蓝系统包括几百个专为象棋设计的并行芯片，使它每秒平均能够搜索一亿种局面。