教学参考-31

教学目标

围棋，中国古称“弈”，英文名称“Go”。围棋起源于中国，传说为帝尧所作。围棋使用矩形格状棋盘，纵横19条线，361个落子点。对弈双方执黑白二色棋子交替行棋，以所围占区域多者为胜。
围棋局面千变万化，围棋经典著作《棋经十三篇》中将之称之为 “势”。对于人类棋手，围棋高手们往往把对 “势” 的把握看作是对事物的洞察力和对全局把控力。因此，围棋经常被神秘化，与攻伐、理政、怡情、处世等高级智慧联系起来。 �

1997年IBM的深蓝击败国际象棋冠军卡斯帕罗夫，从此以后机器在各种棋类对弈上鲜有人类对手。那么，为什么不让深蓝来下围棋呢？
我们首先看一看深蓝击败卡斯帕罗夫所用的α-β剪枝算法。这一算法的基本思路是一个极小-极大搜索过程。简单地说，就是从当前棋局往前看几步，努力选择一条“即使对方应对最合理，我依然可以得到高分”的走法，如右图所示。然而，单纯的极小-极大过程速度非常慢（深蓝如果用这一算法，走一步棋要花17年），α-β剪枝算法对此进行了改进，去掉那些不必要的分枝，从而极大提高了搜索效率。
α-β剪枝算法的一个关键问题是需要判断几步之后的棋局形势。在国际象棋中，这一判断还是容易的，但对围棋则困难的多。这是因为围棋太过灵活，即便是人类棋手都只能靠直觉来判断，机器就更困难了。
基于上述原因，在深蓝获胜后的十多年时间里，并没有哪一款计算机围棋程序能击败人类顶尖棋手。因此，直到2016年AlphaGo与李世石交战的前两天，棋圣聂卫平还曾评论说“我认为人百分百会取胜。电脑战胜人脑这种说法完全是忽悠。”他的判断依据是：“围棋中对于几百万种形势哪种最好，人脑可以做出最有利于自己的判断，但电脑面对复杂的情况完全无法判断。”这一评价可谓中肯。

2016年，DeepMind的AlphaGo战胜了韩国顶尖棋手李世石，标志人工智能在对弈领域的完胜。在此之后，AlphaGo以Master为名横扫中日韩顶级棋手，无一败绩。2017年，AlphaGo击败中国柯洁九段，此后再无对手，宣布退役。
蒙特卡洛树（MCT）搜索是AlphaGo取得辉煌胜利的最大功臣。围棋对弈中最大的问题是对棋局的评价。 MCT采用模拟走棋到终局的方式对棋局进行评估。如右图一所示，MCT保持一棵搜索树，经过大量模拟后，每个节点记录的胜率即可作为局面评估的依据。
深度神经网络是AlphaGo取得成功的另一个重要因素。AlphaGo训练了两个卷积神经网络，策略网络用来预测基于当前棋局下每个落子的概率，值网络用来预测棋局本身的胜率。这两个网络与MCT搜索互相配合，一方面用神经网络提高MCT的搜索效率，另一方面用神经网络学习MCT模拟走棋的结果。
最后，自我对弈在AlphaGo的训练和走棋中占有重要分量。自我对弈不仅是MCT模拟走棋的基础，而且可以不断生成新数据，使模型更加强大。