关于棋类软件

3524066572

高水平国际象棋算法的核心技术，是极为精细的“局面评估函数”。而这早在几十年前，就是人工智能博弈算法的核心问题。国际象棋的局面评估函数很好理解，基本想法是对皇后、车、马、象、兵根据战斗力大小给出不同的分值，对王给出一个超级大的分值死了就是最差的局面。一个局面就是棋子的分值和。

但这只是最原始的想法，子力的搭配、兵阵的形状、棋子的位置更为关键，象棋中的弃子攻杀极为常见。这需要国际象棋专业人士进行极为专业细致的估值调整。国际象棋AI的水平高低基本由它的局面评估函数决定。有了好用的局面评估函数以后，再以此为基础，展开一个你一步我一步的指数扩展的博弈搜索树。在这个搜索树上，利用每个局面计算出来的分值，进行一些专业的高效率“剪枝”（如Alpha-Beta剪枝算法）操作，缩小树的规模，用有限的计算资源尽可能地搜索更多的棋步，又不发生漏算。

国际象棋与中国象棋AI发展到水平很高后，棋手们真的感觉到了电脑的深不可测，就是有时电脑会下出人类难于理解的“AI棋”。人类对手互相下，出了招以后，人就会想对手这是想干什么，水平相当的对手仔细思考后总是能发现对手的战术意图，如设个套双吃对手的马和车，如果对手防着了，就能吃个兵。而“AI棋”的特征是，它背后并不是一条或者少数几条战术意图，而是有一个庞大的搜索树支持，人类对手作出任何应对，它都能在几手、十几手后占得优势，整个战略并不能用几句话解释清楚，可能需要写一篇几千字的文章。

这种“AI棋”要思考非常周密深远，人类选手很难下出来。近年来中国象棋成绩最好的是王天一，他的棋艺特点就是主动用软件进行训练，和上一辈高手方法不同。王天一下出来的招有时就象AI，以致于有些高手风言风语影射他用软件作弊引发风波，我认为应该是训练方法不同导致的。国际象棋界对软件的重视与应用比中国象棋界要强得多，重大比赛时，一堆人用软件分析双方的着手好坏，直接作为判据，增加了比赛的可看性。

软件能下出“AI棋”，是因为经过硬件以及算法的持续提升，程序的搜索能力终于突破了人类的脑力限制。经过高效剪枝后，几千万次搜索可以连续推理多步并覆盖各个分枝，在深度与广度方面都超过人类，可以说搜索能力已经超过人类。

其实最初的围棋AI也是用这个思路开发的，也是建立搜索树，在叶子节点上搞局面评估函数计算。但是围棋的评估函数特别难搞，初级的程序一般用黑白子对周边空点的“控制力”之类的原始逻辑进行估值，差错特别大，估值极为离谱，棋力极低。无论怎么人工加调整，也搞不好，各种棋形实在是太复杂。很长时间围棋AI没有实质进步，受限于评估函数极差的能力，搜索能力极差。

实在是没有办法了，才搞出MCTS这种非自然的随机下至终局统计胜率的办法。MCTS部分解决了估值精确性问题，因为下到终局数子是准确的，只要模拟的次数足够多，有理论证明可以逼近最优解。用这种变通的办法绕开了局面评估这个博弈搜索的核心问题。以此为基础，以ZEN为代表的几个程序，在根据棋形走子选点上下了苦功，终于取得了棋力突破，能够战胜一般业余棋手。

接下来自然的发展就是用深度学习对人类高手的选点直觉建模，就是“策略网络”。这次突破引入了机器学习技术，不需要开发者辛苦写代码了，高水平围棋AI的开发变容易了。即使这样，由于评估函数没有取得突破，仍然需要MCTS来进行胜率统计，棋力仍然受限，只相当于业余高手。

“价值网络”横空出世
AlphaGo在局面评估函数上作出了尝试性的创新，用深度学习技术开发出了“价值网络”。它的特点是，局面评分也是胜率，而不是领先多少目这种较为自然的优势计算。但是从《自然》论文以及版本V13与V18的表现来看，这时的价值网络并不是太准确，不能单独使用，应该是一个经常出错的函数。论文中提到，叶子节点胜率评估是把价值网络和MCTS下至终局混合使用，各占0.5权重。

这个意思是说，AlphaGo会象国际象棋搜索算法一样，展开一个叶子节点很多的树。在叶子节点上，用价值网络算出一个胜率，再从叶子节点开始黑白双方一直轮流走子终局得出胜负。两者都要参考，0.5是一个经验性的数据，这样棋力最高。

这其实是一个权宜之计。价值网络会出错，模拟走子终局也并不可靠，通过混合想互相弥补一下，但并不能解决太多问题。最终棋力还是需要靠MCTS海量模拟试错，模拟到新的关键分枝提升棋力。所以版本V18特别需要海量计算，每步需要的时间相对长，需要的CPU与GPU个数也不少，谷歌甚至开发了特别的TPU进行深度神经网络并行计算提高计算速度。

整个《自然》论文给人的感觉是，AlphaGo在围棋AI的工程实施的各个环节都精益求精做到最好，最后的棋力并不能简单地归因于一两个技术突破。算法研发与软件工程硬件开发多个环节都不计成本地投入，需要一个人数不小的精英团队全力支持，也需要大公司的财力与硬件支持。V13与V18更多给人的感觉是工程成就，之前的围棋AI开发者基本是两三个人的小团队小成本开发，提出了各式各样的算法思想，AlphaGo来了个集大成，终于取得了棋力突破。

即使这样，V18在实战中也表现出了明显缺陷，输给李世石一局，也出了一些局部计算错误。如果与国际象棋AI的表现对比，对人并不能说有优势，而是各有所长。人类高手熟悉这类围棋AI的特点后，胜率会上升，正如对腾讯AI刑天与绝艺的表现。

ZEN、刑天、AlphaGo版本V18共同的特点是大局观很好。连ZEN的大局观都超过一些不太注意大局的职业棋手，但是战斗力不足。这是MCTS海量模拟至终局精确数目带来的优势，对于地块的价值估计比人要准。它们共同的弱点也是局部战斗中会出问题，死活搞不清，棋力高的问题少点。这虽然出乎职业棋手的预料，从算法角度看却是自然的。海量终局模拟能体现虚虚的大局观，但是这类围棋AI的“搜索能力”仍然是不足的，局面评估函数水平不高，搜索能力就不足，或者看似搜得深但有漏洞。正是因为搜索能力不足，才需要用MCTS来主打。

但是AlphaGo的价值网络是一个非常重要而且有巨大潜力的技术。它的革命性在于，用机器学习的办法去解决局面评估函数问题，避免了开发者自己去写难度极大甚至是不可能写出来的高水平围棋局面评估函数。国际象棋开发者可以把评估思想写进代码里，围棋是不可能的，过去的经验已经证明了这一点。机器学习的优点是，把人类说不清楚的复杂逻辑放在多达几百M的多层神经网络系数里，通过海量的大数据把这些系数训练出来。

给定一个围棋局面，谁占优是有确定答案的，高手也能讲出一些道理，有内在的逻辑。这是一个标准的人工智能监督学习问题，它的难度在于，由于深度神经网络结构复杂系数极多，需要的训练样本数量极大，而高水平围棋对局的数据更加难于获取。Deepmind是通过机器自我对局，积累了2000万局高质量对局作为训练样本，这个投入是海量的。如果机器数量不多可能要几百年时间，短期生成这么多棋局动用的服务器多达十几万台。但如果真的有了这个条件，那么研究就是开放的。怎么准备海量样本，如何构建价值网络的多层神经网络，如何训练提升评估质量，可以去想办法。

AlphaGo团队算法负责人David Silver在2016年中的一次学术报告会上说，团队又取得了巨大进步，新版本可以让V18四个子了，主要是价值网络取得了巨大进步。这是非常重要的信息。

V25能让V18四个子，如果V18相当于人类最高水平的棋手，这是不可想象的。根据Master对人类60局棋来看，让四子是绝对不可能的，让二子人类高手们都有信心。我猜测，V18是和V25下快棋才四个子还输的。AlphaGo的训练与评估流水线中，机器自我对局是下快棋，每步5秒这样。2016年9月还公布了三局自我对局棋谱，就是这样下出来的。V18的快棋能力差，V25在价值网络取得巨大进步能力后，搜索能力上升极大，只要几秒的时间，搜索质量就足够了。

为什么价值网络的巨大进步带来的好处这么大？

如果有了一个比V18要靠谱得多的价值网络，就等于初步解决了局面评估函数问题。这样，AlphaGo新的prototype就更接近于传统的以局面评估为核心的搜索框架，带有确定性质的搜索就成为算法能力的主要力量，碰运气的MCTS不用主打了。因此，V25对人类高手的实战表现，可以与高水平国际象棋AI相当了。

我可以肯定V25的搜索框架会给价值网络一个很高的权重（如0.9），只给走子至终局数子很低的权重。如果局面平稳双方展开圈地运动，那么各局面的价值网络分值差不多，MCTS模拟至终局的大局观会起作用。如果发生局部战斗，那么价值网络就会起到主导作用，对战斗分枝的多个选择，价值网络都迅速给出明快的判断，通过较为完整的搜索展开，象国际象棋AI一样论证出人类棋手看不懂的“AI棋”。

局面评估函数精确到一定程度突破了临界点，就可以带来搜索能力的巨大进步。因为开发者可以放心地利用局面评估函数进行高效率的剪枝，节省出来的计算能力可以用于更深的推导，表现出来就是算得深算得广。实际人类的剪枝能力是非常强大的，计算速度太慢，如果还要去思考一些明显不行的分枝，根本没办法进行细致的推理。在一个局面人类的推理，其实就是一堆变化图，众多高手可能就取得一致意见了。而Master以及国际象棋AI也是走这个路线了，它们能摆多得多的变化图，足以覆盖人类考虑到的那些变化图，给出靠谱的结论。

但这个路线必须依靠足够精确的价值网络，否则会受到多种干扰。一是估值错了，好局面扔掉坏局面留着选错棋招。二是剪枝不敢做，搜索大量无意义的局面，有意义的局面没时间做或者深度不足。三是要在叶子节点引入快速走子下完的“验证”，这种验证未必靠谱，价值网络正确的估值反而给带歪了。

从实战表现反推，Master的价值网络质量肯定已经突破了临界点，带来了极大的好处，思考时间大幅减少，搜索深度广度增加，战斗力上升。AlphaGo团队新的prototype，架构上可能更简单了，需要的CPU数目也减少了，更接近国际象棋的搜索框架，而不是以MCTS为基础的复杂框架。比起国际象棋AI复杂的人工精心编写的局面评估函数，AlphaGo的价值网络完全由机器学习生成，编码任务更为简单。

理论上来说，如果价值网络的估值足够精确，可以将叶子节点价值网络的权重上升为1.0，就等于在搜索框架中完全去除了MCTS模块，和传统搜索算法完全一样了。这时的围棋AI将从理论上完全战胜人，因为人能做的机器都能做，而且还做得更好更快。而围棋AI的发展过程可以简略为两个阶段。第一阶段局面估值函数能力极弱，被逼引入MCTS以及它的天生弱点。第二阶段价值网络取得突破，再次将MCTS从搜索框架逐渐去除返朴归真，回归传统搜索算法。

由于价值网络是一个机器学习出来的黑箱子，人类很难理解里面是什么，它的能力会到什么程度不好说。这样训练肯定会碰到瓶颈，再也没法提升了，但版本V18那时显然没到瓶颈，之后继续取得了巨大进步。通常机器学习是模仿人的能力，如人脸识别、语音识别的能力超过人。但是围棋局面评估可以说是对人与机器来说都非常困难的任务。

职业棋手们的常识是，直线计算或者计算更周密是可以努力解决的有客观标准的问题，但是局面判断是最难的，说不太清楚，棋手们的意见并不统一。由于人的局面评估能力并不太高，Master的价值网络在几千万对局巧妙训练后超过人类是可以想象的，也带来了棋力与用时表现的巨大进步。但是可以合理推测，AlphaGo团队也不太可能训练无缺陷的价值网络，不太可能训练出国际象棋AI那种几乎完美的局面评估函数。