按照这两个等级分的两个棋手对弈，李世乭每盘的胜算为89%（\frac{1}{(1+10^{(()/400))} )} ，公式见：How to Guide: Converting Elo Differences To Winning Probabilities : chess）。如果对弈一盘，AlphaGo尚有11%的获胜的可能性，而整个比赛五盘胜出三盘或更多，AlphaGo就只有1.1%的可能性了。（当然，这是几个月前的AlphaGo，也许今天已经超越了：见下面第三点）。　　AlphaGo不是打败了欧洲冠军吗？有些人认为AlphaGo去年底击败了欧洲冠军樊麾，所以挑战（前）世界冠军应有希望。但是，樊麾只是职业二段（Elo 3000左右），而李世乭是职业九段（ELO 3532）。这两位的差别是巨大的，完全不能混为一谈。就比如说一个人乒乓球打败了非洲冠军，并不代表他就可以成功挑战中国冠军。　　AlphaGo有可能在这几个月突飞猛进，进而击败李世乭吗？AlphaGo的负责人说：”外界不知道我们这几个月进步了非常多“。（来自：Odds favor machine over human in big Go showdown ）。这点确实有可能。AlphaGo进步的方法有两个：（1）增加硬件：我们从Nature的文章可以看到：从1202个CPU到1920个CPU，AlphaGo的ELO只增加了28，而且线性地增加CPU，不会看到线性的ELO成长。若要达到364 ELO积分的提升，需要的CPU将达到天文数字（有篇文章估计至少要10万个CPU：AlphaGo and AI Progress）。当然，谷歌有钱有机器，但是纯粹加机器将会碰到并行计算互相协调的瓶颈（就是说假设有十万万台机器，它们的总计算能力很强，但是彼此的协调将成为瓶颈）。在几个月之内增加两个数量级的CPU并调节算法，降低瓶颈，应该不容易。（2）增加学习功能：AlphaGo有两种学习功能，第一种是根据高手棋谱的学习，第二种是自我对弈，自我学习。前者已经使用了16万次高手比赛，而后者也在巨大机组上训练了8天。这方面肯定会有进步，但是要超越世界冠军可能不容易。最后，换一种分析方式：如果从过去深蓝击败世界冠军的“成长过程”来看，深蓝大约1993年达到职业大师水平，4年后才在一场六盘的比赛中击败世界冠军（大约500Elo积分点的提升）。今天的AlphaGo应该和1993年的深蓝相似，刚进入职业大师水平。若要击败世界冠军，虽然未必需要4年的时间，但是几个月似乎不够。　　还有什么以上未考虑的因素，导致AlphaGo获胜吗？如果谷歌刻意未出全力和樊麾对抗，或者有其它学习或并行计算方面超越了Nature里面的描述，那AlphaGo完全有可能获胜。　　既然写了这么多，就对这个题目再发表一些看法：　　AlphaGo 是什么？在今年一月的Nature (/nature/journal/v529/n7587/full/nature16961.html )有AlphaGo的详细介绍，AlphaGo是一套为了围棋优化的设计周密的深度学习引擎，使用了神经网路加上MCTS (Monte Carlo tree search），并且用上了巨大的谷歌云计算资源，结合CPU+GPU，加上从高手棋谱和自我学习的功能。这套系统比以前的围棋系统提高了接近1000分的Elo，从业余5段提升到可以击败职业2段的水平，超越了前人对围棋领域的预测，更达到了人工智能领域的重大里程碑。　　AlphaGo 是科学的创新突破吗？AlphaGo是一套设计精密的卓越工程，也达到了历史性的业界里程碑，不过Nature文章中并没有新的“发明”，AlphaGo的特点在于：不同机器学习技术的整合（例如：reinforcement learning, deep neural network, policy+value network, MCTS的整合可谓创新）、棋谱学习和自我学习的整合、相对非常可扩张的architecture（让其充分利用谷歌的计算资源）、CPU+GPU并行发挥优势的整合。这套“工程”不但有世界顶级的机器学习技术，也有非常高效的代码，并且充分发挥了谷歌世界最宏伟的计算资源（不仅仅是比赛使用，训练AlphaGo时也同样关键）。　　AlphaGo的跳跃式成长来自几个因素：1）15-20名世界顶级的计算机科学家和机器学习专家（这是围棋领域从未有的豪华团队：也许你觉得这不算什么，但是要考虑到这类专家的稀缺性），2）前面一点提到的技术、创新、整合和优化。3）全世界最浩大的谷歌后台计算平台，供给团队使用，4）整合CPU+GPU的计算能力。　　AlphaGo是个通用的大脑，可以用在任何领域吗？AlphaGo里面的深度学习、神经网络、MCTS，和AlphaGo的扩张能力计算能力都是通用的技术。AlphaGo的成功也验证了这些技术的可扩展性。但是，AlphaGo其实做了相当多的围棋领域的优化；除了上述的系统调整整合之外，里面甚至还有人工设定和调节的一些参数。AlphaGo的团队在Nature上也说：AlphaGo不是完全自我对弈end-to-end的学习（如之前同一个团队做Atari AI，用end-to-end，没有任何人工干预学习打电动游戏）。如果AlphaGo今天要进入一个新的应用领域，用AlphaGo的底层技术和AlphaGo的团队，应该可以更快更有效地开发出解决方案。这也就是AlphaGo真正优于深蓝的地方。但是上述的开发也要相当的时间，并且要世界上非常稀缺的深度计算科学家（现在年待遇行情已达250万美金）。所以，AlphaGo还不能算是一个通用技术平台，不是一个工程师可以经过调动API可以使用的，而且还距离比较远。　　如果这次AlphaGo没有打败李世乭，那还要多久呢？IBM深蓝从进入大师级别到比赛击败世界冠军花了四年。AlphaGo应该会比深蓝更快提升自己，因为深蓝需要新版本的硬件，和针对Kasparov的人工调节优化，而AlphaGo是基于谷歌的硬件计算平台，和相对通用的深度学习算法。所以，几个月太短，4年太长，就预计1-2年之间吧。　　从国际象棋到围棋，到底是不是巨大的突破呢？肯定是的，在这篇文章里面（在国际象棋领域，电脑已经可以战胜人脑，那么围棋领域电脑还差多远？ - 计算机 ），第一位回答者分析了围棋的复杂度为10^{172}
而国际象棋则只有10^{46}
。在1997年深蓝击败世界冠军时，大家都认为：深蓝使用的是人工调整的评估函数，而且是用特殊设计的硬件和”暴力“的搜索 (brute-force) 地征服了国际象棋级别的复杂度，但是围棋是不能靠穷举的，因为它的搜索太广（每步的选择有几百而非几十）也太深（一盘棋有几百步而非几十步）。而AlphaGo的发展让我们看到了，过去二十年的发展，机器学习+并行计算+海量数据是可以克服这些数字上的挑战的，至少足以超越最顶尖的人类。　　AlphaGo 若打败了世界冠军，就意味着计算机超越人脑？或者可以思考了吗？我的回答：　　在可以凭逻辑分析推算的问题上，机器即将远远把人类抛在后面。机器速度会越来越快，学习能力会越来越强，数据会越来越多。当年，大家讨论“国际象棋输给机器不算什么，围棋才是真正的智慧”只是我们人类维护自己尊严但是不实际的幻想！今天，我们该面对现实了！　　在大数据+机器学习+大规模并行计算的时代，我们将看到无数的商机和产品，能够在预测、分析、推荐等方面，产生巨大的商业和用户价值。不过，这些解决方案和人类相比，其实没有什么意义，因为人差太远了（比如说：推荐引擎将能推荐你最可能会买的产品、想吃的菜，想认识的人；自动交易能得到更高的投资回报和风险比例。。。）。　　在感知方面，人类也将会被机器超越。今天的语音识别，人脸识别，未来的自动驾驶，都是例子。　　但是，以上都还是冷冰冰的技术，机器打败了世界冠军也没有感到高兴（甚至说不出为什么）。对于那些科幻片的粉丝们：机器人是否会人性化？这还是未知的。毕竟，在情感、喜怒哀乐、七情六欲、人文艺术、美和爱、价值观等方面，机器离人还差的很远，甚至连基础都没有。对人工智能的研究者，这是下一个挑战。对我们人类，在下个突破之前，我们还是多发展右脑吧！　　P.S. - 也许有人好奇，为什么这个话题我说了这么多，因为在1986年，我在读书时，曾经开发了一套黑白棋系统（复杂度10^{28} ），击败了黑白棋的世界团体冠军，而当年的那套系统也有（非常粗浅的）自我学习的能力。有兴趣的网友可以在这里看到我当年的文章：A pattern classification approach to evaluation function learning ) 。　　编辑于 　　著作权归作者所有
楼主发言：1次 发图：0张 | 更多
　　计算机出错少而已
　　别逗了，现在围棋界最强的是中国的柯洁。阿法狗还没战胜柯洁就不算终结了人类。　　
　　才下了一盘了就完爆，你好意思说这种话？
　　我下象棋只赢过简单的电脑。咋的？还不是我让它咋的就咋的。我让它看A片，它就不敢看B片。
　　输赢的只是人和机！围棋永远都还是围棋！
　　今天又输了
　　只是输给程序员
　　棒子能代表人类？
　　谁知道电脑后面是不是柯洁啊
　　真相是，人脑和现在的电脑，在原理上越来越接近了。　　也需有一天，人类会被淘汰吧
　　李世乭过气了　　且有不许打劫的秘密协依，实在不堪
　　且看第三盘打不打劫吧，再吹不迟
　　那个棒子是世界排名第一吗？
　　无劫无转换，AlphaGo差评
　　李世石连输5局气急败坏地砸开电脑，发现柯洁趴在机箱里。
　　几个劫下来准保那台机器漏电
　　这个，，，只是 优化的比较好的 “剪枝搜索”算法而已。 如果规则改为99线，或者199线围棋，估计这阿法狗就要算爆了。。。。　　这个，，，只是 优化的比较好的 “剪枝搜索”算法而已。 如果规则改为99线，或者199线围棋，估计这阿法狗就要算爆了。。。。　　这个，，，只是 优化的比较好的 “剪枝搜索”算法而已。 如果规则改为99线，或者199线围棋，估计这阿法狗就要算爆了。。。。　　这个，，，只是 优化的比较好的 “剪枝搜索”算法而已。 如果规则改为99线，或者199线围棋，估计这阿法狗就要算爆了。。。。　　这个，，，只是 优化的比较好的 “剪枝搜索”算法而已。 如果规则改为99线，或者199线围棋，估计这阿法狗就要算爆了。。。。　　这个，，，只是 优化的比较好的 “剪枝搜索”算法而已。 如果规则改为99线，或者199线围棋，估计这阿法狗就要算爆了。。。。　　这个，，，只是 优化的比较好的 “剪枝搜索”算法而已。 如果规则改为99线，或者199线围棋，估计这阿法狗就要算爆了。。。。　　这个，，，只是 优化的比较好的 “剪枝搜索”算法而已。 如果规则改为99线，或者199线围棋，估计这阿法狗就要算爆了。。。。　　这个，，，只是 优化的比较好的 “剪枝搜索”算法而已。 如果规则改为99线，或者199线围棋，估计这阿法狗就要算爆了。。。。　　这个，，，只是 优化的比较好的 “剪枝搜索”算法而已。 如果规则改为99线，或者199线围棋，估计这阿法狗就要算爆了。。。。　　这个，，，只是 优化的比较好的 “剪枝搜索”算法而已。 如果规则改为99线，或者199线围棋，估计这阿法狗就要算爆了。。。。　　这个，，，只是 优化的比较好的 “剪枝搜索”算法而已。 如果规则改为99线，或者199线围棋，估计这阿法狗就要算爆了。。。。　　这个，，，只是 优化的比较好的 “剪枝搜索”算法而已。 如果规则改为99线，或者199线围棋，估计这阿法狗就要算爆了。。。。　　这个，，，只是 优化的比较好的 “剪枝搜索”算法而已。 如果规则改为99线，或者199线围棋，估计这阿法狗就要算爆了。。。。　　这个，，，只是 优化的比较好的 “剪枝搜索”算法而已。 如果规则改为99线，或者199线围棋，估计这阿法狗就要算爆了。。。。　　这个，，，只是 优化的比较好的 “剪枝搜索”算法而已。 如果规则改为99线，或者199线围棋，估计这阿法狗就要算爆了。。。。　　这个，，，只是 优化的比较好的 “剪枝搜索”算法而已。 如果规则改为99线，或者199线围棋，估计这阿法狗就要算爆了。。。。　　这个，，，只是 优化的比较好的 “剪枝搜索”算法而已。 如果规则改为99线，或者199线围棋，估计这阿法狗就要算爆了。。。。　　这个，，，只是 优化的比较好的 “剪枝搜索”算法而已。 如果规则改为99线，或者199线围棋，估计这阿法狗就要算爆了。。。。　　这个，，，只是 优化的比较好的 “剪枝搜索”算法而已。 如果规则改为99线，或者199线围棋，估计这阿法狗就要算爆了。。。。　　这个，，，只是 优化的比较好的 “剪枝搜索”算法而已。 如果规则改为99线，或者199线围棋，估计这阿法狗就要算爆了。。。。　　这个，，，只是 优化的比较好的 “剪枝搜索”算法而已。 如果规则改为99线，或者199线围棋，估计这阿法狗就要算爆了。。。。　　这个，，，只是 优化的比较好的 “剪枝搜索”算法而已。 如果规则改为99线，或者199线围棋，估计这阿法狗就要算爆了。。。。　　这个，，，只是 优化的比较好的 “剪枝搜索”算法而已。 如果规则改为99线，或者199线围棋，估计这阿法狗就要算爆了。。。。　　这个，，，只是 优化的比较好的 “剪枝搜索”算法而已。 如果规则改为99线，或者199线围棋，估计这阿法狗就要算爆了。。。。　　这个，，，只是 优化的比较好的 “剪枝搜索”算法而已。 如果规则改为99线，或者199线围棋，估计这阿法狗就要算爆了。。。。　　这个，，，只是 优化的比较好的 “剪枝搜索”算法而已。 如果规则改为99线，或者199线围棋，估计这阿法狗就要算爆了。。。。　　这个，，，只是 优化的比较好的 “剪枝搜索”算法而已。 如果规则改为99线，或者199线围棋，估计这阿法狗就要算爆了。。。。　　这个，，，只是 优化的比较好的 “剪枝搜索”算法而已。 如果规则改为99线，或者199线围棋，估计这阿法狗就要算爆了。。。。　　这个，，，只是 优化的比较好的 “剪枝搜索”算法而已。 如果规则改为99线，或者199线围棋，估计这阿法狗就要算爆了。。。。　　这个，，，只是 优化的比较好的 “剪枝搜索”算法而已。 如果规则改为99线，或者199线围棋，估计这阿法狗就要算爆了。。。。　　这个，，，只是 优化的比较好的 “剪枝搜索”算法而已。 如果规则改为99线，或者199线围棋，估计这阿法狗就要算爆了。。。。　　这个，，，只是 优化的比较好的 “剪枝搜索”算法而已。 如果规则改为99线，或者199线围棋，估计这阿法狗就要算爆了。。。。　　这个，，，只是 优化的比较好的 “剪枝搜索”算法而已。 如果规则改为99线，或者199线围棋，估计这阿法狗就要算爆了。。。。　　这个，，，只是 优化的比较好的 “剪枝搜索”算法而已。 如果规则改为99线，或者199线围棋，估计这阿法狗就要算爆了。。。。　　这个，，，只是 优化的比较好的 “剪枝搜索”算法而已。 如果规则改为99线，或者199线围棋，估计这阿法狗就要算爆了。。。。　　这个，，，只是 优化的比较好的 “剪枝搜索”算法而已。 如果规则改为99线，或者199线围棋，估计这阿法狗就要算爆了。。。。　　这个，，，只是 优化的比较好的 “剪枝搜索”算法而已。 如果规则改为99线，或者199线围棋，估计这阿法狗就要算爆了。。。。　　这个，，，只是 优化的比较好的 “剪枝搜索”算法而已。 如果规则改为99线，或者199线围棋，估计这阿法狗就要算爆了。。。。　　这个，，，只是 优化的比较好的 “剪枝搜索”算法而已。 如果规则改为99线，或者199线围棋，估计这阿法狗就要算爆了。。。。　　这个，，，只是 优化的比较好的 “剪枝搜索”算法而已。 如果规则改为99线，或者199线围棋，估计这阿法狗就要算爆了。。。。　　这个，，，只是 优化的比较好的 “剪枝搜索”算法而已。 如果规则改为99线，或者199线围棋，估计这阿法狗就要算爆了。。。。　　这个，，，只是 优化的比较好的 “剪枝搜索”算法而已。 如果规则改为99线，或者199线围棋，估计这阿法狗就要算爆了。。。。　　这个，，，只是 优化的比较好的 “剪枝搜索”算法而已。 如果规则改为99线，或者199线围棋，估计这阿法狗就要算爆了。。。。
　　左下角那个断子一接 黑棋必输 走的太重 一盘赢棋被小李搞砸了 就攻击连接的三个和虚攻右边的三个 白棋很厚实的 当时有40多目 黑棋上边是虚空算30目 左下7目 右下外实算10目 白优
　　@精神方面有问题 　　
　　尽吹牛逼！　　
　　你懂围棋的精髓吗　　
　　楼主的标题是：人类战胜人类吗？怪怪的。
　　人类还是有希望的，麻将将最终捍卫人类的尊严。　　别跟我说你用手机打脱衣麻将输给电脑了，那是因为洗牌码牌发牌的都是电脑。　　换成实物麻将，电脑绝对不是人类的对手。　　不要小看中国人狡猾的智慧。
　　@又矮又黑怎么办
17:30:00　　这个，，，只是 优化的比较好的 “剪枝搜索”算法而已。 如果规则改为99线，或者199线围棋，估计这阿法狗就要算爆了。。。。　　这个，，，只是 优化的比较好的 “剪枝搜索”算法而已。 如果规则改为99线，或者199线围棋，估计这阿法狗就要算爆了。。。。　　这个，，，只是 优化的比较好的 “剪枝搜索”算法而已。 如果规则改为99线，或者199线围棋，估计这阿法狗就要算爆了。。。。　　这个，，，只是 优化的比较好......　　-----------------------------　　审局函数不一样了
　　李世石又不是最强的。而且这孙子压根不打劫。白送阿发狗。尤其到最后了，还特么不打劫。
　　事实上，电脑永远也不能战胜人类，毕竟人类还有最后一招：耍赖。。。
　　棒子不能代表人类，只能代表棒子
　　一停电看它还拽个球！
　　李世石被柯洁虐成狗了，人类还没出动，机器狗只赢了高丽狗罢了。
　　然后又怎么样？人类制作工具不就是因为工具比人的能力强才制作的吗？要是制作出来的工具比人还废，制作出来自慰啊?
<span class="count" title="
<span class="count" title="
请遵守言论规则，不得违反国家法律法规回复(Ctrl+Enter)科普贴：扒一扒人工智能到底有多厉害
用微信扫描二维码分享至好友和朋友圈
在刚刚结束的围棋人机大战中，AlphaGo机器人在与韩国顶尖高手李世石之间的五番棋第一战中取胜，总比分1-0落后。可以预见，这场世纪大战之后，人类被计算机碾压、人工智能时代来临、人类治理骄傲即将崩塌……这些说法充斥着朋友圈与各大新闻频道。
中新网3月9日电在刚刚结束的围棋人机大战中，AlphaGo机器人在与韩国顶尖高手李世石之间的五番棋第一战中取胜，总比分1-0落后。这是AlphaGo机器人去年战胜欧洲围棋冠军后在人机大战中的又一次胜利。 可以预见，这场世纪大战之后，人类被计算机碾压、人工智能时代来临、人类治理骄傲即将崩塌&&这些说法充斥着朋友圈与各大新闻频道。
资料图 多年以来，人机大战从来没停止过，人工智能一直在各个领域不停地向人类发起挑战。1997年，IBM的超级电脑&深蓝&击败国际象棋世界冠军卡斯帕罗夫，深蓝也成为击败人类的最知名的人工智能。不过马上就不是了，因为AlphaGo准备在更难的围棋领域，击败人类！ 众所周知，围棋的规则与胜负条件足够复杂，其估值函数非常不平滑，差一个子盘面就可能天翻地覆，同时状态空间大，也没有全局的结构。 说的再简单一些，我们都知道国际象棋有着明确的兑子价值： 后&&10分 车&&5分 象&&3分 马&&3分 兵&&1分
图：国际象棋算法的搜索树
图：围棋算法的搜索树 围棋复杂度超过宇宙原子总数：围棋棋盘横竖各有19条线，共有361个落子点，双方交替落子，这意味着围棋总共可能有10^171(1后面有171个零)种可能性。这个数字到底有多大，你可能没有感觉。我们可以告诉你，宇宙中的原子总数是10^80(1后面80个零)，即使穷尽整个宇宙的物质也不能存下围棋的所有可能性。 而且在围棋中，我们很难量化每一子的价值；遑论对弈过程中还需要符合&打劫&的游戏规则，并通过挤、拆、逼、封等手段获取优势，其难度远高于其它项目。因此，棋类游戏中，围棋成为了计算机唯一一道未能攻破的防线。
那么守护人类智力的重任，就交给你了！ 不过围棋与IT界似乎都相信，即便这次AlphaGo跪了，电脑也迟早是会在围棋等全部博弈类游戏上赢过顶尖的人类选手。 因为人工智能技术已经迎来了一个新的突破&&深度学习技术。 AlphaGo比此前国际象棋人工智能复杂的点在于：它基于深度学习进行估值和走棋。而近几年深度学习最大的突破之处，就是深度学习不需要人来设计算法&找特征&；只通过大量原始数据和标签的对比，程序便可以自动找特征，并且并不比人差。 那这和下围棋有什么关系？！先别急，围棋虽说是&千古无同局&，但在局部及开局还是有很多相似或者相同的模式会反复出现，人工智能需要寻找并记录的，就是这其中的特征、以及每一步之间的规律。之后，人工智能将深度学习的找特征，与蒙特卡洛搜索树相结合&& 等等，蒙特卡洛搜索树(MCTS)又是什么鬼？科幻爱好者对这个应该词语并不陌生，老刘的《三体》里也曾出现过。说得简单一些，就是一种通过大量采样获取最优解的方法；体现在围棋中，就是运用了蒙特卡洛搜索树的人工智能，能够看到更多步以后的局势，不会为了眼前的利益而舍弃大局。对于机器来说，这几乎是智的飞跃。 但《三体》里也曾表示，在样本过多的情况下，蒙特卡洛搜索树耗时过长，往往需要以年作为时间单位。因此，快速、精准发现特征的深度学习技术，成为其最好拍档。于是，蒙特卡洛搜索树搭配深度学习&&利用前者枚举棋路、利用后者发现特征加以分析的人工智能AlphaGo，成为了人类棋坛荣耀的最大威胁。 不只是围棋，自从人工智能不断趋向成熟，越来越多的传统领域受到了挑战。 人工智能VS专业医师
图：沃森电脑已向医疗领域进军 例如11年在综艺节目上狂虐人类选手的超级电脑&沃森&。在面对主持人提出的各类新奇古怪的问题时，沃森不仅能在第一时间给出正确答案，还能主动忽略自己不擅长的问题。据说，沃森储存了数百万的文档资料，包括字典、百科全书、新闻、文学等，其硬件配置可以使它每秒处理500GB的数据，相当于每秒阅读100万本书。 如今沃森被运用于医疗服务、咨询等领域，能够给患者提供最合适的治疗方案。不论从效率还是诊断准确率来讲，人工智能都远胜过人工咨询，足以媲美专业医师。 人工智能VS顶级黑客
图：360天眼团队在BlackHat大会上演讲 对于人工智能来说，达到专业医师的程度还不够。采用深度学习技术的360天眼系统，已经和世界最顶尖的黑客开始了博弈。去年8月，全球信息安全行业的最高盛会&&世界黑帽大会BlackHat在召开。期间，该人工智能系统被搬上大会讲台，为在场的1.5万余名专业安全人士以及顶级黑客，展示深度学习与流量识别的综合应用。 虽然出现在黑客的最大party上，但天眼系统的目标却是防止黑客的攻击：基于多GPU的并行计算，建立一个模拟人类大脑的深度学习神经网络，通过网络流量识别协议及应用程序，找出云端海量数据中的APT攻击、免杀木马、新型木马等未知威胁。 人工智能VS男/女朋友
图：呆萌的随身人工智能&&Siri 如果说这些人工智能只让一些职业感到危机的话，那么Siri、小冰等这些语音助手的出现，就可能让男票女票面临失业了&&早期的Siri相当于语音识别+搜索引擎，而如今，Siri不仅能够知道语言所代表的含义，还能给出一个或有趣或靠谱的回答，像人多过于机器。 还记得电影《Her》吗？男主人公爱上了电脑操作系统里的女声&萨曼莎&&&有着一把略微沙哑的性感嗓音，并且风趣幽默、善解人意的人工智能。按照现在小冰以及Siri这些语音助手的发展速度，恐怕人工智能成为人类心灵伴侣的一天，并不会遥远了&& 还有Google的无人驾驶、美联社一周能写百万篇新闻的Wordsmith、facebook的虚拟助手M&&各行各业的人工智能科技不胜枚举。按照比尔盖茨、霍金这些大佬的说法，我们正处于人工智能爆发的节点，接下来，将会有更多智能系数更高的系统、程序被研发出来。 &世界最好的人类棋手在压力下崩溃了。&1997年，卡斯帕罗夫被深蓝击败后如是表示。
也许世界冠军卡斯帕罗夫最后都没能明白，击败他的并非是心理压力，而是进击的人工智能。
[责任编辑：周超]
用微信扫描二维码分享至好友和朋友圈电脑围棋中的人工智能技术
电脑围棋中的人工智能技术
本文通过研究几个最出色的电脑围棋程序，从认知科学的角度介绍了电脑围棋，并特别针对电脑围棋编程人员（或有意投身
于此的程序员）揭示围棋作为一个认知科学研究领域的日益增长的重要性。对手谈，Go4++，Many Faces of Go，Go
和Explorer几个目前最优秀的电脑围棋程序，我们概括了它们用到的人工智能技术，必须面对的关键性挑战和博弈树搜索中牵涉的问题，以此揭示为什么计
算机国际象棋技术不能被很好的移植到围棋领域。
1． 挑战围棋的程序
作为正规游戏之一的围棋领域，过去即便是应付一般的人类棋手计算机也难以有所作为。几个一年一度的电脑围棋赛事，如FOST杯赛为第一名提供2，000，000日元奖金，台湾的应氏基金为第一个能在分先七番棋中击败顶尖职业棋手的围棋程序许诺40万美元的奖金。
早以围棋为对象把电脑围棋纳入研究工作是在1962年，尽管第一次由程序下一盘完整的棋是发生在1968年（Zobrist，1970）。随着电脑围棋赛
事的举行和第一个商业程序的发放，电脑围棋作为一个领域于80年代被正式创立，并在90年代变得兴旺起来。目前活跃在电脑围棋竞赛中的顶尖程序有
Explorer，Go Intellect，Go4++，手谈和The Many Faces of
Go，它们的水平大致在4-8级之间。
2． 围棋中的博弈树搜索
二人完美信息博弈中典型的人工智能方法是搜索博弈树以决定走哪一步。标准博弈树搜索由四部分组成：1．状态表示，2．候选走法产生，3．确定目标状态，以及4．一个确定相对优势状态的静态评估函数。有效的博弈树剪枝方法（比如α-β）增强了程序的表现。
博弈树这条途径很成功，如我们在国际象棋程序中所看到的，基于典型的完全广度α-β剪枝博弈树搜索的程序甚至击败了世界冠军。这一节我们从透视电脑围棋的角度检查博弈树搜索的四个构件。
2.1 状态表示
完全信息的角度看，围棋盘面有19X19的3次方格，每个交叉点要么空要么被黑子或白子占据。状态空间的大小（例如可能的位置数）是3的361次方（或
10的172次方），相比之下国际象棋大致为10的50次方而Othello棋为10的30次方（Allis，1994）。另外，博弈树的大小（例如可能
的博弈数）在10的575次方和10的620次方之间，对比国际象棋的10的123次方和Othello棋的10的55次方（Allis，1994）。
于空间的组合尺寸，用19X19格的形式严格表示状态空间对人或机器来说都层次太低而不能有效使用。接下来的层面的描述是把正交的邻接棋子组成串（或
链）。所有的程序把串搜集到更大的单元，然而没有通用的处理方法——即便是对专业棋手来说——把串组合到更大的单元中。依靠他们的围棋理论，程序员开发了
他们自己的启发式，当串有效的连接在一起时用做评估之用（叫做模糊组或块）。
另外，恰当层次的表示能改变对运行时子任务的依赖，例如，战术分析，死活分析，或实地评估。
手在禁止自杀和同型反复（劫）的规则限制下轮流把棋子投放在空的交叉点（包括角和边）。象国际象棋一样，围棋在给定位置的上下文中只有所有合法走法中的一
部分是有效的。围棋的平均分枝因子是很大的，大约是国际象棋的六倍（200对35，Burmeister &
Wiles，1995）。
注意这个分枝因子在全盘中的考虑。而在某些情形下只有局部的考虑是重要的。例如，直接目标搜索被用来判断通常只有一两种可能走法却可以多达60手深度的征子。
实际的走子是个复杂的问题：参见3.4部分。
2.3 目标状态
棋的最终目标是获得比对手更多的实地。有两种方法用来争取实地：建棋子城墙围空以及用棋子包围并吃掉敌方的棋串。实际上很难确定目标状态，因为实地的获得
是靠慢慢积累起来的（不象国际象棋那样将军的最终的目标是突然死亡并且集中在一个子上）。由于在接近终局前很难精确地计算实地，故启发式估计用的较多。这
样的启发方式通常要归并组件和指示领地安全潜力的（例如死活组和影响）次要目标（例如国际象棋里的材料优势）。
当对局双方依次弃权时结束。棋手通
常在没有走法能增加所得和/或无论怎么走都会减少所得时选择弃权。实际上，要确定对局结束（即何时弃权）是相当困难的。人们下棋，计算结果时如果遇到有关
死活的争执要通过继续下直到最终结果出现。在电脑围棋比赛中，如果程序出现算法不能解决的得分争执，计分就由组织比赛的人员来做。
2.4 评估函数
判断盘面的形势优劣时棋块的死活是个重要的考虑点。死活判断是很费时间的，并且是典型的通过战术搜索（参见3.5部分）或死活搜索（参见3.6部分）来获
得的。有意思的是，另一评估棋块死活的复杂之处在于它可能需要评估全盘的形势：如果要一个棋块在劫争中是可活的（即它必须赢得打劫来使自己活下来），就必
须估算所有和对手相比用来决定棋块死活的劫材的数量和大小。如果出现双重或三重劫的形势，打劫分析会变得更复杂。
评估的结果有时不确定，因为明确的死活定义在受限的战术搜索里也许是不可能的，即一个绝对的死活回答可能超出了战术或死活搜索的范围。
从 复杂的类型分析看，由一个绝对位置来确定赢家是P空间难题（Lichtenstein &
Sipser，1980），决定一个棋手能否左右输赢需指数时间来完成（Robson，1983），由此也就不奇怪要用到启发式了。这些理论结果显示不存
在从一个绝对局势出发决定领地结果的多项式时间算法。
3． 参赛程序里的博弈树搜索和人工智能技术
当前活跃在各电脑围棋赛事里的程序有 Martin
Muller（1995）的Explorer（EX），陈恳（陈，；1992）的Go
Intellect（GI），Michael Reiss 的Go4++（Go4），陈志行的HandTalk（HT）以及David
Fotland 的Many Faces of
Go（MFG）。针对第2节讨论的博弈树搜索和围棋专用的人工智能技术：战术搜索，死活搜索和势函数，我们报告这些程序的细节。
3.1 位置表示
所有的程序都有子、串、块的表示，确认串属于某个组的典型方式是采用基于模式的启发来确定串与串之间的关联性。敌方（或块）表示也被用在EX和GI
中，启发式用来确定敌方的影响（GI）和领地区域（EX）。
盘面（例如棋块、敌方）表示的对象属性包括它们的死活状态（也指安全性或生命力）、实地数、眼数和势。某些情况下这些属性值由战术搜索决定。
MFG的表示方式中一些组件由评估函数控制（例如块、联接、眼、实地和势）。Go4的盘面只是简单的由评估函数（例如块、眼、安全性、实地）来表示。
3.2 候选走法
通常，由模式或更常见的是由基于规则的专家系统产生候选走法。走子产生过程最后是通过（线性的或加权求和的）相加棋盘上所有点的参考值为合适的走法给出一个分值。全盘评估一般选最高得分点作为下一手的落子点。
同程序由全局水平变量估值得出的候选走法数也有所不同：GI（陈，1997）有12手，MFG有10手，而Go4至少有50手。程序变量保持的规则
数：EX大约100，MFG大约200。GI含有约20个走子算法，它们或者基于模式库，或者基于面向目标的搜索，或者基于启发式规则（可能含有大量的规
模式通常既包含低级信息也包含高级信息。低级信息与黑白子的位置有关，那些点必须是空着的，已经被子占据的点不在此列。高级信息则是关于气
的数量、安全性、眼位和领地的信息。模式匹配不仅与子的配置匹配，而且跟包含在子或串里的任何高级需求有关。大量的模式匹配计算是很耗时的，并且由于棋盘
上的对称性而变得更复杂。这已经导致了发展特殊算法来克服与模式匹配有关的问题（比如MFG的哈希函数，EX的串匹配）。
知识以不同的方式组合到
程序当中：一些程序几乎完全依据第一原则工作，另一些根据存储的模式匹配当前位置。不同的程序其模式数量相差很大：Go4约有15个；MFG大约2000
个；而EX则在3000个左右。有些程序也包含开放的走法模式数据库（定式）（例如，MFG含有约45，000个定式模式）。
数情况下，大量的实地比起少量的实地加相应的外势更合乎需要。尽管有时也存在着实地和外势间地转化（特别是在布局和中盘阶段）。然而，虽然实地的启发式评
估是可能的，实地依然不总是形势优劣最好的指示明灯。在对局的早期阶段，占有大量的实地可能表明一种过于集中的形势，从实地安全的角度看，这样的形对对局
的后面阶段或许是有害的。开局造就最大可能的势而不是实地通常导致局末对更多实地的追求。外势是可能用来确定形势优劣的子目标的一个例子。
定形势优劣的大量子目标的相对优先度在电脑围棋中看来没有一致性可言。典型的块和实地的死活状态（安全性）被包含在目标和子目标中。在手谈中，战术手段是
重点，而MFG集中在联接性、眼和块的生命力。Go4则好像完全贯注于联接性上，几乎任何东西都是从联接概率图上派生（直接或间接地）出来。
3.4 评估过程
估围棋的形势是个很慢的过程（例如，比起国际象棋程序的每秒10,000-100,000次评估，MFG是以低于每秒10次的速度完成对整局棋不超过
10,000种全盘形势的评估）。由于比赛时间的限制，程序执行的全局评估数通常是有限的（例如，MFG在选择下一步时全局的评估数不超过100）。
的50种候选走法中每一个都通过一个六步的过程来评估：1.启用一个联接概率图。对于盘面上的每一个黑子和白子，计算它与32个（实际的或假定的）友好点
的联接概率（要处理大量的数据）。确定联接性还要用到战术搜索；2.棋块由联接图和战术搜索来确定；3.眼位（利用模式）由联接性和棋块数据确定；4.眼
位的数量确定了棋块的安全性；5.每个子的安全性按联接概率图的比率辐射并在所有棋子上相加；6.黑白领地由辐射值估计。黑白领地的差别作为一个给定走法
的评估结果返回。
MFG的评估是个多步过程，并且在很大程度上依赖于战术搜索。战术搜索检查所有少于四口和一部分有四口气的串以确定是不是死串。
战术搜索也被用来鉴别联接性和眼位。在这一环节，串组成了棋块。棋块的生命力由基于死活的考虑（例如，联接、眼位等）决定，并且用来确定黑白子在盘面每个
点（在-50至+50的范围之间）行使控制的总量统计。在总和每个点的值的基础上确定领地，给出最终的估计值。多达6轮的静态搜索可以被执行，有时用一个
特殊的模式集找出能使形势稳定下来的局部走法。
GI的评估用在做全局搜索时。如果所有候选走法中有一种走法的得分要明显高于其它的走法，它就被选
为要走的下一步。如果候选走法中有些走法的得分大致相等，靠评估带来方便的全局搜索决定选择走哪一步。评估时，敌子的安全性是为盘上每个点指定一个在
-64到+64之间的黑白控度的基础，所有点的分值加起来返回一个评估值。全局搜索检查的步数不多于6到7步，搜索的深度不超过6层。
3.5 战术搜索
术搜索是有选择的、面向目标的搜索，并且为一大堆目的而使用，包括确定串是死是活（Go4，MFG，EX，GI）、联接是安全的还是可被切断的
（Go4，MFG）、是否可以形成眼位（MFG）、产生候选走法（GI）和确定棋块的死活（EX）。就是在全局的水平，战术搜索也要用来做棋步产生和评
估。战术评估和全盘评估有区别，这跟搜索的目标（例如，一个串的气的数量）有关。由于时间上的制约，战术搜索通常在节点数、枝因子和层的深度上受到限制。
因此，尽管象死活这类的问题通常被认为是战术性的，棋子却可以在战略上就死去了，即使它们可能不能通过战术手段被抓获。由此，从围棋评估的方方面面看，战
术搜索只是一种启发式装备而已。
MFG提供了一个战术搜索操作的很好的例证（通过“战术家”）：每个有三口或更少的气的串和许多有四口气的串被
“战术家”检查过。每个串检查两次，一次白先走一次黑先走。“战术家”决定一个串是否被抓（比如，即使它先走也不能活）、被威胁（比如，如果它先走则活，
后走则死），或者是牢固的。“战术家”依靠简单的启发式（例如，气数和联接性）。
“战术家”有两个分离的走子器；一个执行攻击走法，一个执行防卫
走法。走子器建议的走法按一些规则分类，这些规则包括二次气（气的气）、切点和简单的眼形。一旦分类，根据依赖走法分类的质量的搜索的表现，一种α-β深
度优先搜索被派上用场。走子和分类解释了多数时间依靠战术搜索的原因。
战术搜索直接针对目标并被限制一个最大节点数。抓子时这个限制是大约
100，然而当只有一步可走时就不考虑这个限制。采用这种方式，可以毫不费力地确定征子的胜方。根据第一层走子产生赋予走法的分值，一次搜索的节点数分配
到树枝中，因此不同的树枝可能在不同的深度结束。每一成功的层的枝因子被“战术家”逐步强化；枝因子从第一层5降到第五层的1或2。
对局过程中，MFG作大约100,000-150,000次战术搜索，以每秒2,000-2,500个节点的速度遍历1.5-2百万个节点。平均起来每次战术搜索访问约10-20个节点，尽管由于一些搜索因节点限制而终止，许多搜索访问过节点数要少于5个。
3.6 死活搜索
不是所有的程序都做明确的死活分析，很多程序对此使用了战术搜索。MFG用与它的战术搜索过程类似的方式作死活分析，除了它是在块上作死活分析而不是分析串。
一个静态死活评估器在多步过程中确定每个块的死活状态，而没有以从简单的结构中进一步产生复杂结构的方式向前搜索。静态死活评估器使用“战术家”并且为棋块中的每个合适的串至少调用两次。
活搜索是直接面向目标的（例如，拯救或杀死一个棋块）。如果在一个特定点没有获得搜索目标，合适走法由死活搜索引擎自身的走法器产生，并继续搜索。为了在
一次死活搜索期间确定目标是否已经达到，静态死活评估器在每个点被调用。死活搜索引擎使用深度优先α、β搜索，每一个特定的枝的搜索深度由启发式决定。搜
索树的大小是强制性的，通常可以达到7层的深度和20个节点的大小。死活搜索是很慢的，整棵树要装到缓存里以减少花在重复搜索上的开销。死活搜索的缓慢也
意味着它不会被用在全盘评估中。
3.7 势函数
势是一种围棋概念，它表明了每一方棋子对空点的最大可能的控制潜力。通过确保开局时子力投放不过于集中，棋手在后面的对局中将取得最大限度获得领地的机会。
通过势函数建立可计算模型（Zobrist，1969；Ryder，1971；Chen，1989）。通常，子力以盘上每个点的辐射影响值的和（黑白子辐
射正负相反的值）对周边的点施加辐射影响（MFG的黑白子的势是分离的）。子力辐射按距离函数递减：GI是2的距离次方分之一，MFG是距离分之一。但过
于依赖势函数的程序表现不佳（EX和Go4不再使用势函数，尽管Go4的辐射函数很象一个势函数，EX采取另一些措施，象同色点或可联接点的距离）。
应用势的启发包括确定联接性和敌子（GI），以及确定领地（MFG）。MFG的块势初始值依赖于块的强度等，强壮的块比弱块或将死的块辐射更大的影响。这也意味着死块辐射负影响等，因为它对敌方有利。在MFG和GI中势都没有通过子辐射；MFG也没有通过敌链辐射影响。
前的围棋程序都使用了一定量的“知识”。由于建立在设计者下棋成功经验的启发之上，每个程序都可被看作一种（可能是含蓄的）围棋理论的一次以经验为依据的
实验。围棋理论成立的关键要靠数据结构的选择，因为它们决定了编码不同类型知识的难易和应用这些知识的计算开销。随着程序员同时在围棋和电脑围棋方面获得
技能，程序会有发展（例如，在过去的十五年中随着 Fotland
的棋力从15级发展到2段，MFG也增长了棋力并且代码长度增加到目前的4万行）。程序的性能由它最弱的部件决定，而向程序增加新知识的难易是提高程序性
能的重要部分。
由此可见，电脑围棋领域在关于怎样构筑一个围棋程序或者指配不同围棋知识的优先性（例如，Go4注重联接性而MFG注重死活）方面
还没有一致性可言。必须提到的一点是：关于人类是怎样下围棋的至今也没个一致的说法，这是目前认知科学研究的一个课题（见Saito
Yoshikawa，1977，作为回顾）。这个领域的任何进展都会对围棋理论有个直接的促进，并可能导致电脑围棋程序算法的改进。
本文对目前比
较成功的几个程序作了比较。通过这项工作，我们在博弈树搜索的框架内分析了围棋，并通过对示例电脑围棋编程的观察把有关的问题暴露出来。这种困难在电脑围
棋领域是常识，但在更为广泛的人工智能范畴却很少被人们认识和接受。围棋全盘评估需要确定棋块的死活状态，不管是通过死活搜索还是战术搜索，评估是非常消
耗计算资源的。缺乏快速有效的评估函数是电脑围棋遭遇的一个基本问题，并且和巨大的树枝因素、用户和电脑比赛的实时需求（一般来说，相对于国际象棋的每秒
180步围棋每秒只有24步）等搅和在一起。因此，计算机国际象棋通常要用到的完全广度博弈树搜索在电脑围棋里是行不通的。
除了所列出的围棋领域
固有的问题外，本文还探讨当前的程序怎样地处理这些问题，由此为未来的围棋程序员提供一个跳板。请注意电脑围棋是个商业的领域，程序本身（不是学术论文）
就是它的主要产品。跟其它的参考不同的是，这里报告的细节都已经通过个人交流征询了（慷慨贡献自己的知识的）程序作者本人的意见，并且有相关的电脑围棋邮
件列表&[email]computer-go@anu.edu.au[/email]&和FTP站点&[url]ftp:
//igs.nuri.net/Go/comp/[/url]&的信息为依据。
电脑围棋的挑战性在于要扩展当前的围棋理论或发展新理论——
特别是与评估有关的，针对实时限制设计合适的数据结构和算法，解决知识瓶颈。目前还没有一个有力的程序使用学习技术，尽管有过几次这样的尝试
（如，Pell，1991；Schraudolph, Dayan & Sejnowski，1994；Donnelly, Corr
Crookes，1994）。回顾这些程序已经超出了本文的范围，但我们推测这些程序也没有成功，因为它们的设计者的含蓄的围棋理论缺乏对围棋复杂性的必
要理解。怎样把学习能力赋予现有的程序（或者它们暗示的围棋理论）是个等待解决的问题。
电脑棋手的“思维”
1. 博弈与计算科学
现在的世界上有各种各样电脑棋手。能够在普通计算机上运行的国际象棋程序已经达到了职业棋手的水平，就黑白棋而言，人类已经不是计算机的对手。但是就围棋而言，计算机与人进行抗衡的路还很遥远。
如果电脑棋手战胜了人类棋手，那么是否就可以说它和人一样具有智能？这个问题，将放到最后进行讨论。我首先将向大家展示，电脑棋手是如何下棋的。
2. 择优而行
电脑棋手下棋的原理，简单地说，就是选出它所认为最有利的下法。
|...4 3 -1
们来看上面这个图。假设在某一个时刻，摆在电脑棋手面前的是一个局面A。当然，电脑棋手懂下棋的规则，于是它发现一共有三种符合规则的下法（为了画图方
便，所以少了一些，事实上，在国际象棋和中国象棋中，符合规则的下法一般为数十种，围棋则多达两三百种）。这三种下法将分别形成局面B、C、D。现在，我
们假设电脑棋手能够判断局面的优劣，为每一个局面都计算一个分数，比如局面B的得分为4，局面C的得分为3，局面D的得分为-1。当然，我们可以作一些规
定：分数越高局面越好，分数越低局面越差；当分数为0时表示双方均势，则正分表示电脑棋手方优势，负分表示电脑棋手处于劣势。于是，电脑棋手就选择对它最
有利的下法，即第一种下法，最后形成了局面B。此时，在这种情况下，作为一个副产品，那就是局面A被认为是4分，因为后面两种下法对计算机而言是没有意义
的，所以B的分数也就是A的分数。
接下来的问题是计算机如何做到为每一个局面评出一个得分。这在下棋中被称为形势判断。
现在以中国象
棋或国际象棋为例（这个问题对围棋而言是很复杂的），最简单的形势判断就是评价以下棋局中双方的子力对比。例如，在中国象棋中，每个车记8分，每个马或炮
记3.5分，每个兵、士、相都记1分，将帅无价，姑且记1000分，那么很容易就可以计算出双方的兵力，两者的差就形成了一种最简单的形势判断。当然，这
种形势判断是十分粗糙的。
稍稍复杂一些的形势判断，除了考虑子力优势之外，还要考虑局面优势。比如一方的马处于十分积极的盘河位置，而另一方的
马则还留在原位没有跳出，两者之间显然存在着差距。这时，需要将这些差距折算成分数，加到形势判断中去。在计算机中，这是最通俗、或者说最常用的形势判断
一般说，对局面的形势判断可以用一个数学式子计算得出。举一个简单的例子：
设在形势中一共考虑n个因素（或特征）。用xi表示
第i个因素是否在当前的局面G中出现，如果出现则取1，没有出现则取0，比如第6个因素是指一方的第1个车，那么当这个车还存在时，x6=1，这个车不存
在时，x6=0。用wi表示第i个因素在形势判断中所计算的分数，这被称为权重，例如一个车的分数为8，则w6=8。那么对局面G的形势判断为：
| f(G)=W1*X1+W2*X2+...Wi*Xi=S(i=1 to i)WiXi
符号S被称为累加符，如果读者以前不知道这个符号，只要看着上面的等式，将它想像为在for循环中套了一个加法的命令，就很容易理解了。这是为了书写方便而引入的符号。
3. 搜索的魔术
果形势判断十分准确，故事就简单地结束了。可惜的是，问题没有这么简单。我们（无论是计算机还是人类）永远不可能得到一个准确的形势判断。这是因为，形势
判断是静态的，而棋局是动态的，要从静态的特征中获取动态的信息，这并非易事。当然，如果需要做到万无一失，那么在形势判断中，必须包括所有可以想到的对
局面产生影响的因素，但这时，因素的数量是一个天文数字，我们既不可能对所有的因素都赋一个权重，也不可能在有限的时间内计算出局面的形势判断。
我们回过来看，人在下棋时也不能一眼就对静态的局势作出准确的判断，笼统地说，他们往往需要向后面计算几步，看看在走了几步棋之后，局面的形势如何。这被称为“多算胜”，也就是说，谁看得越深远，谁就可以获胜。这个思维方式立刻被用到了计算机上。
3.1 最小最大树
以第2部分中出现过的图为例，假设向后再多考虑一步，得到下图
|...........A
|........./ | /
|........B C D
|......./ | / / | /
|.......E F G H I J
|.......5 3 2.5 2 -2 10
是一棵树。从图中看到，假设在三个局面B、C、D下，都恰好有两种符合规则的下法，可以形成局面E、F、G、H、I、J，而这些局面的形势判断已经得到
了。电脑棋手的任务是利用这些已知条件，选择局面B、C、D的中对它最有利的一个局面。我们可以发现，局面J的得分最大，那么是不是应该选择局面D，以便
形成对电脑棋手最有利的局面J呢？
假设电脑棋手的对手（可能是人，也可能是一个计算机程序，现在为了便于说明问题时不产生混淆，假设对手是人）
面对的是局面B，那么他一定会选择对自己最有利的下法。由于是零和博弈，对人最有利的下法就是计算机最不利的下法，那么在E和F之中，他会选择F。这时，
如果电脑棋手选择局面B，那么对方就会选择F，最后电脑棋手得到的结果是3，也就是说，B的形势判断结果应该为3。同样道理，如果人处于C中，他会选择
H，于是f(C) = f(H) = 2。同理，f(D) = -2。最后，发现是B的得分最高，因此电脑会选择B，此时f(A) =
f(B) = 3。
按前面的猜测，如果因为f(J)=10而计算机选择了局面D，那么对手就会选择I，最后计算机得到了最差的结果-2。
从这里我们
可以看出，在电脑棋手下棋的局面中，它总是选择下一个层次中由该局面衍生出的局面中得分最高的，而在对手下棋的局面中，它总是选择下一个层次中由该局面衍
生出的局面中得分最低的。用数据结构中的术语，假设对于某一个局面，已经将在几步棋之后的所有可能形成的局面的得分都计算了出来，那么从这棵树的最底层一
层层向上推，在对手下棋的层次中，每一个结点取其子结点的最小值，在电脑下棋的层次中，每一个结点取子结点的最大值。这就被称为最小最大树。
后，问题转化为对某一局面下衍生出的最小最大树的遍历。这种遍历用一个深度优先搜索就很可以处理了。在搜索的过程中，当前路径上的每一个结点上都保存着搜
索到目前为止的当前最优值。搜索用一个递归函数实现，该函数的功能是计算某个结点的最优值。每当一个结点得到子结点的返回值时，就从当前最优值和返回值中
选取一个更优的值作为当前最优值。当一个结点的子结点都搜索完毕之时，其当前最优值就是该结点的实际最优值，也就是这个结点的得分，这时，将这个值返回其
父结点。下面给出最大最小搜索的伪码：
…………………………………………
需要注意的是，在搜索过程中，我们不仅仅关心每个局面的得分是
多少，我们同样关心是如何得到这个得分的，也就是说，在这个局面下，电脑棋手或是对手应选择什么下法，才能得到这个得分。这个功能没有包括在上面的伪码
中。不过只要读者理解了上面的伪码，就一定能够自己将相应的代码加进去。
进一步，由于是零和博弈，假设从对手角度考虑形式判断函数为g，则有g =
-f。这样，在深度优先搜索中，电脑下棋的结点时考虑取子结点中f最大的，而对手下棋的结点中取f最小的，也就是g最大的，这样两者就完全统一成取最大
值。而在返回值时，只需要把符号改变一下，就可以把f和g值相互转换了。例如在前面的例子中，当位于对手下棋的局面B时，有g(E)=
-f(E)= -5，g(F)= -f(F)= -3，g(B)取最大值，则g(B)=
-3，随后返回到电脑下棋的局面A时，改变符号，使用f(B)= -g(B)=
3，在A点取f的最大值。这被称为负最大搜索，它比最小最大搜索来得简单。下面给出负最大搜索的伪码，相信有一定基础的读者看了之后就会明白。
……………………………………………………..
3.2 a-b裁剪(alphabeta裁剪)
的问题又出现了，假设我们考虑的是中国象棋或国际象棋，现在希望每次都可以搜索到5个回合之后。5个回合就相当于双方一共下10步棋，每一次都有几十种下
法可以选择，姑且算每次有30种选择，于是最小最大树的叶结点个数总共多达30^10，这是一个非常庞大的数字。搜索的结点越多就相当于在搜索中花费的时
间更多，我们总不能忍受电脑棋手一年才下一步棋。减少搜索结点的最简单的方法是减小搜索深度，但这大大影响了电脑棋手的棋力。是否有办法在不减小搜索深度
的前提下将需要搜索的结点减小一些？
|......A 3
|......B 2
|..../ | /
|....C D E
|....4 ? ?
设上图是在深度优先搜索过程中的一个局部，用fnow表示搜索到当前状态结点的当前最优值。B是电脑下棋的结点，A和C则是对手下棋的结点，当前正处于结
点C所属的子树已经搜索完毕，从结点C返回至结点B的时刻，方框中的结点表示搜索到目前为止的当前最优值，即
fnow(A)=3，fnow(B)=2，fnow(C)=f(C)=4。我们知道，由于B是电脑下棋的结点，因此当f(C)&fnow(B)时，
应当更新结点B的当前最优值，即令fnow (B)=f
(C)=4。此时，虽然结点E、F尚未搜索，但由于结点B处为电脑下棋，应取子结点中最大值，其当前最优值随着搜索的进行只会增加而不会减小，因此有
f(B)&=fnow(B)=4。而结点A是对手下棋，应取子结点的最小值，而f(B)&=4&3=fnow(A)，其当前值必然小于
结点B的实际最优值，因此对手处于结点A时必然不会选择到结点B的下法，也就是说，结点B不会对结点A的最优值产生影响。因此，不必再进行结点E和结点F
的搜索，结点B就可以直接返回其父结点A。
在搜索过程中，电脑下棋结点的当前最优值被称为a值（即前面的例子中局面B的最大值），对手下棋结点
的当前最优值被称为b值（即例子中A的最小值）。在搜索过程中，a值递增，b值递减，两者构成了一个区间。这个区间被称为窗口，而对手下棋的结点最终的最
优值将落在这个窗口中。一旦在电脑下棋的结点得到其子结点的返回值大于b值，则发生剪枝。
同样，a-b裁剪也有简洁的负最大的版本，这时对手的a值即负的电脑的b值，对手的a值即负的电脑的b值。a-b裁剪的伪码如下：
…………………………………………………….
3.3 NegaScout搜索
常情况下，在搜索树的根结点，也就是电脑棋手需要决策的局面，我们可以调用3.2中给出的函数alphabeta来得到根结点的分值，同时也可以得到应该
走哪一步棋的结论。这时，调用该函数时，我们应使参数alpha=-1000，beta=1000，这里1000是一个足够大的数。这是因为在根结点时，
我们需要把窗口初始化成最大，在搜索过程中，随着信息的获得，这个窗口会渐渐地减小，最后收敛到根结点的最优值上。
现在我们来看一个有趣的现象：如果我们调用alphabeta( d, b & 0.1, b, p
)会产生什么结果？这里0.1是一个较小的常数，而b是某一个数值。
接从程序中分析，现在形式参数beta就等于b。如果函数的返回值大于b（也就是beta），说明对于局面p，至少有一个子结点的返回值比b大，所以其最
优值必然大于b。这时，我们知道b是局面p最优值的下界。注意，在这种情况下，后面也许还有子结点根本来不及搜索就被裁剪了，所以这时的返回值并不代表局
面p的实际最优值，可能比实际最优值小。如果函数的返回值小于b，说明没有一个子结点的最优值比b大，于是局面p的最优值必然小于b（事实行，由于初始的
窗口在函数递归过程中被反复传递下去，所有的返回值都只体现了是否比b大的信息，所以返回值不是局面p的实际最优值）。此时，b是局面p最优值的上界。于
是，我们得到结论，运用这种类型的alphabeta函数调用，根据返回值是否比b大，可以得出局面p的最优值是否比b大的结论。
注意到在函数调用过程中，alpha和beta很接近，因此窗口很小，在窗口很小的情况下，搜索树的各个层次中，得到的返回值比beta大的可能性就大大增加了，这样剪枝的可能性也变大了。
种类型的alphabeta函数调用被称为零窗口a-b搜索，由于产生了大量的剪枝，它的时间消耗比正规的a-b裁剪少。但正规的a-b裁剪可以得到一个
局面的实际最优值，而零窗口a-b调用只能得到实际最优值和某一个特定值b比大小的结果，也就是说，一个上界或下界的信息。
于是，我们可以对
a-b裁剪作一个改进：在每次向下搜索之前，首先先用零窗口a-b调用判断一下，这个搜索是否能够改善当前的最优值，即局面p某一个子结点的实际最优值是
否比alpha大。如果比alpha小，则跳过这个子结点。进一步，当该子结点的返回值大于alpha时，从前面的分析中已经知道，它的实际最优值大于这
个值，所以当返回值大于beta时，其实际最优值也超过了beta，这时就应该进行剪枝。这就是NegaScout搜索。在这个新算法中，增加的时间消耗
是零窗口a-b调用，而如果零窗口a-b调用的返回值比alpha小，那么就可以节约一个较大窗口的a-b调用花费的时间，当零窗口a-b调用的返回值比
beta大时，则直接产生了进一步的剪枝。实践证明，由于零窗口a-b裁剪中产生了大量的剪枝，所以其实践消耗相对于大窗口a-b调用而言是很小的。总的
说，NegaScout搜索较a-b裁剪有效。下面依照前述的思想，给出一个不算太规范的NegaScout算法的伪码（这里也使用了负最大搜索）：
…………………………………………………..
关于NegaScout的细节及其进一步的优化，读者可以查阅文献[1]。
3.4 魔术所在
按理说，搜索技术发展到这个地步，似乎已经很完善了。而事实上，这只是一个开始而已。
先出现的是一些改进的技术。例如，在前面讨论的各种搜索中，除了保存当前的搜索路径（搜索树的一个分支）的堆栈之外，不需要其它的内存消耗。这种做法并没
有充分利用资源。在实际的计算机博弈程序中，需要建立散列，用以保存在以前的搜索过程中所遇到的局面。这样，一旦在搜索过程中再次遇到相同的局面（这很常
见，如几种不同的行棋次序可能导致相同的局面），就可以利用以前计算的结果。关于这方面的细节，有兴趣的读者可以参阅文献[2]。
然而，真正的革命在于搜索算法全新的变化。
MTD(f) （全称是Memory-enhanced Test
Driver）就是其中一个相当优秀的新方法。它的思想非常简单：既然零窗口的a-b调用可以判断局面的最优值是否大于或小于一个固定的值，那么就反复运
用这个调用。假设已知局面的最优值f的范围是min &= f &=
max（例如在最初，min=-1000，max=1000），那么就在这个范围选一个值g，然后用这个值进行零窗口a-b调用。如果调用结果比g大，那
么说明g是f的下界，就得到min=g，反之max=g，这样，范围就缩小了。以上过程反复进行，直到上下界收敛到相同的一个值为止。
MTD(f)算法中，虽然也利用了a-b裁剪，但其仅仅作为一个辅助工具出现。其思想却非常有趣，完全跳出了前面的思维，以全新的方式出现在了我们的面前。
如果在搜索过程中能够使用散列保存已经搜索过的局面的特性，那么这个算法的效率将优于NegaScout。关于MTD(f)的细节，请有兴趣的读者查阅文献[3]。在此，我只简单地给出算法的伪码：
……………………………………………………………….
需 要注意的是，既然算法的名称中有Memory-enhanced，在这里使用的a-b裁剪应使用散列保存以前的搜索结果（这里使用了函数
alphabetawithmemory，以区分于原先的不使用散列的a-b裁剪）。在MTD(f)中，被重复搜索的相同局面大大增加，当以前的结果被保
留下来时，才可能提高效率。在国际象棋的实验中，该算法使效率提高了15%。
此外，还有其它的一些搜索算法，如SSS*[4]、B*[5]、Probcut[6]，这些算法和我们讨论的算法多少有些不同（或在局面的评价上、或在剪枝上、或在搜索的次序上），在这里就不再论述，有兴趣的读者可以自行参阅文献，进行研究。
4. 电脑棋手的学习
机器学习技术的发展为电脑下棋水平的提高带来了新的希望。各种各样的学习技术都被试图应用于博弈的某一个部分。文献[7]综述了机器学习在计算机象棋对弈中的应用。
在此，我将展示一个典型的方案：对形势判断函数进行学习。
4.1 监督学习
回顾一下第2部分中的内容，一个一般的形势判断函数（或称估价函数）具有如下的形式：
| f(G)=W1*X1+W2*X2+...+WiXi=S(i=0 to n)WiXi
中，xi表示局面的某一个因素（或特征），而wi是这个特征在形势判断中所起的重要程度（即相应的分值），通常被称为权重。如果当这个因素是子力时，在中
国象棋或国际象棋中，还是比较容易给出一个相对准确的值，而当这个因素是某些局面性的优势时，如何准确地估价这些优势，可能令有经验的大师都会感到烦恼。
虽然大师们很难对于一个孤立的局面因素给出具有普遍性的估计，例如在中国象棋中，一个处于巡河位置的车具有多大的分值，但对于一些特定的局面，大师们还是可以较为准确地给出综合评价。这为学习形势判断函数提供了可能。
一个很简单的方法就是找出许多局面，然后请大师为每一个局面作出自己的形势判断。然后把大师们给出的形势判断作为标准答案，训练形势判断函数。这种学习方式被称为监督学习（或称有师学习），因为这种学习就如在老师的监督指导下进行。
例 如现在有k个局面G1, G2, …,
Gk。第j个局面Gj的n个特征用X1j,X2j,...,Xnj表示。对这k个局面，大师给出的形势判断为h1, h2, …,
hk。现在的任务是找出合适的权重w1, w2, …, wn，使得以下的方程组尽可能地得到满足：
| j=1 W1X1j+W2X2j+...+WnXnj=h1
| j=2 W1X1j+W2X2j+...+WnXnj=h2
| j= ... M
| j=k W1X1j+W2X2j+...+WnXnj=hk
注意，之所以说是尽可能得到满足，是因为以上关于w1, w2, …, wn的方程组不一定有解，我们所希望的是实际形势判断结果f1,
f2, …, fk与大师给出的结果h1, h2, …, hk尽可能接近。
形势判断函数非常复杂时，这个问题实际上是一个优化问题。解决这个问题的通用方法是梯度下降法（有兴趣的读者可以参阅有关最优化的书籍）。由于现在的形势
判断函数非常简单，也可以应用许多其它方法（如最小二乘）。下面仅仅给出梯度下降方法在这个简单的实际问题上的应用。
首先对所有的权重w1, w2, …, wn赋以随机的数值。然后反复进行以下的迭代：在时刻t，对局面G1, G2, …,
Gk计算形势判断结果f1, f2, …, fk，依照下式得到下一时刻（即t +1时刻）的权重为
| wi(t+1)=wi(t)+H*S(j=1 to k)(hj-fj)*xij
以上对权重的更新过程反复进行，直到形势判断的结果不能再改善为止。式子中的H被称为学习速率，当取值较大时，学习速度较快（即需要迭代的次数变少），但学习的精度较低（准确地说，在最后阶段会产生振荡），当取值较小时精度提高，但学习速度变慢。
如果哪位读者对人工神经网络有一定的了解，也可以将以上的过程看作是一个连续型感知器的学习过程。
4.2 强化学习
监督学习并不是一个令人满意的学习方法（虽然在某些情况下是不可替代的）。毕竟，当这样的“老师”也是很累的，很难想像去请一个大师对数百个甚至数千个局面给出自己的形势判断。
化学习是监督学习的一个特例。这时，“老师”不再每次都给出准确的答案，他（她、它）只是对电脑的计算结果给出一个好或不好的评价，或者是告诉电脑究竟好
到何种程度，作为一个带有模糊性的判断。在下棋中，这种“老师”是随处可得的。电脑棋手和每一个对手的对局都有可能成为这种“老师”，对局的胜负就可以看
作是“老师”对电脑棋手的评价。当然，如何有效地利用这种评价是学习技术的关键。
以中国象棋或国际象棋为例，在一局棋的进行过程中，一个形势判 断函数的结果往往时好时差。这是因为在形势判断函数中的权重w1, w2,
wn中，有些比较准确（比如子力因素的权重），而其它的一些并不准确（如一些表示局面优势因素的权重）。在棋局的进行中，经常出现的状况是一方首先取得了
局面优势，随后转化成了子力的优势，最后取胜，或者更一般地说，一方首先取得了一些潜在的优势，随后将这些潜在的优势转化为实在的优势。一般地说，电脑棋
手对潜在的优势往往不能给出准确的判断，而对较为实在的优势（例如子力优势或者直接构成的杀局）则判断正确。于是我们可以得到一个基本准确的结论，电脑棋
手在其对局的后期（更特殊的状况是对局结束的时刻），得到的形势判断往往是比较正确的。同时，我们可以设想，在对局的前面的一些时刻，正确的形势判断应该
和对局后期的形势判断较为接近。如果计算机能够有效地参考对局后期正确的形势判断，就有可能自行给出对局前期的一些局面的相对准确的形势判断，作为在前一
节所提到的监督训练中的标准答案h1, h2, …, hk。
TD( )就是一个实用的强化学习技术。TD（Temporal
Difference）即瞬时差异，就是指在一个对局中相邻两个时刻的局面的形势判断之差。如果这个形势判断函数比较准确，则这个差（即瞬时差异）应该接
近于0。假设G1, G2, …, Gk,
Gk+1是在一个对局中，从某一时刻到对局结束的连续的k+1个局面。这时根据前面的假设，在对局结束时的形势判断是准确的，即对于第k+1个局面，形势
判断的标准答案hk+1=f(Gk+1)。现在我们利用这个值来形成前k个局面的形势判断标准答案：从对局结束开始，向前一步步倒退，在每一个时刻，其形
势判断标准答案为
|.......h =(1-y)f(G )+y*k
|........i i+1 i+1
从这个式子中
可以看到，当y=0时，第i个局面的形势判断标准答案应该接近于在此之后的局面的形势判断；当y=1时，所有局面的形势判断标准答案都接近于hk+1，即
对局结束时刻的形势判断。于是，当y取介于0和1之间的某一个数值时，形势判断的标准答案将成为以上两者的折中。经过了学习之后的形势判断函数将在对局中
的一系列连续的局面中，相邻局面的判断结果相似，并逐渐逼近终局时的结果。
)被应用于多个计算机博弈程序之中。在文献[8]中，一个应用了该技术（稍作了一些改变，有兴趣的读者请自行查阅文献）的国际象棋程序在国际互联网上进行了300多局对局后，其等级分从1650分（一般水平）上涨到了2110分（美国大师水平）。
以上网友发言只代表其个人观点，不代表新浪网的观点或立场。