基于强化学习的围棋对弈算法设计与实现开题报告

全文总字数：7114字

1. 研究目的与意义（文献综述）

近些年来，人工智能与强化学习^[1]发展越来越快，涉及的领域越来越广泛，而对于普通开发者的门槛却在逐年降低，以tensorflow^[2]、mxnet^[3]为代表的强化学习框架与以谷歌云、亚马逊云为代表的云平台服务，极大程度的降低了普通开发者进行机器学习开发的学习成本。围棋是一种双人对战的策略性棋类，使用的是方形棋盘加上黑白色棋子进行对弈。在19路围棋中，每个交叉点都有黑白空三种不同的状态，那么博弈的复杂度在10的300次方左右。因此，围棋有着巨大搜索空间，难以预测的走棋和围棋盘面的价值估计，在之前普遍被认为是计算机最难以打败职业棋手的棋类运动。但是在2016年3月，deepmind团队的人工智能程序alphago^[4]以4:1的成绩打败韩国棋手李世石九段，引发了各界尤其是人工智能界的广泛关注，这对于计算机围棋来说具有划时代的意义。alphago使用的深度学习技术也成为了人们关注和讨论的热点。deepmind团队的alphago主要由蒙特卡洛搜索树、策略神经网络、快速走子网络、价值神经网络^[5]组成。依托于以上部分，alphago实现了预测下一步棋盘上每个点的价值、在适当牺牲下子质量的情况下来进行比策略神经网络走子快千倍的速度进行瞎子、评估整盘棋双方胜率的功能的完整计算机围棋程序。标志着使用强化学习算法训练的计算机围棋程序的水平已经达到了战胜围棋世界冠军的水平。

国内由腾讯微信翻译团队开发的人工智能围棋程序phoenixgo基于alphago zero论文实现，同时做了若干提高训练效率的创新，利用微信服务器的闲事计算资源进行自我对弈，成功缓解了zero版本对资源的巨额需求。于2018年初，phoenixgo以bensondarr等账号在腾讯野狐围棋上进行实战，战胜200多位棋手，并于当年以2：1的比分击败自家另一人工智能围棋程序绝艺，赢得世界人工智能围棋大赛冠军。

然而，传统的围棋机器学习是建立在完全信息的基础上，这就引出了一个致命的缺点：他不能理解人类的欺诈，会因为被人类欺诈而陷入错误的行进路线而不自知，最为明显著名的例子便是李世石于2016年3月13日大战alphago的被称为“神之一手”的78手。随着alphago大量的进行职业九段（最顶级的围棋选手）的棋谱学习与自我博弈^[6]，使得其水平短时间内突飞猛进。但正因为学习的是大量顶级职业选手的棋谱，使得alphago对围棋的理解仅仅局限于高端对局。而低端选手下出来的不合理的走法，对于人来说，这是职业选手在高端局绝不会去思考、展现出来的一个思路，所以在学习过程中alphago并没有处理这种的对弈，因此李世石的欺诈成功的成为了“假妙手”，使得alphago在数十步之后才意识到了对决胜率急转直下进而输掉比赛。对于围棋这种完全信息的对弈来说，人类很被对手不合理的决策所迷惑，但未经训练的机器，就很容易被不合理的决策所迷惑。与此相对应的，就是以德州扑克为首的不完全信息对弈的机器学习^[7]，大大改善了机器对不完美博弈决策的应对策略，甚至达到了领先于职业玩家的地步。由此受到的启发，对于围棋这类完全信息的机器学习，也非常有必要进行一些非完全信息模式的机器学习。而纳什均衡^[8]则是这种模式下的主要思想策略，即在对抗条件下，双方可以通过向对方提出威胁和要求，找到双方能够接受的解决方案而不至于因为各自追求自我利益而无法达到妥协，甚至两败俱伤。稳定的均衡点建立在找到各自的“占优策略”(dominant strategy)^[9]，即无论对方作何选择，这一策略优于其他策略。主要通过具有记忆的神经网络为基础，然后运用进化算法加机器学习（强化 监督学习）^[10]，把一个最外层的代系间的进化过程，和内层的持续不断的强化学习结合起来。内层的学习会反馈给外层从而影响外层的进化。与此同时，引入了不同参数网络^[11]之间的博弈，当一轮结束之后，胜者将改写败者的网络，但败者不会消失。这样，本文的研究就得到一个纳什均衡状态下多样化的解空间。也就是说，最后的最优解不是一个网络，而是一个策略集群。从而把非完全信息的对弈思想贯彻到了复杂的围棋对弈之中：整个围棋局势都在迅速的变化，之前处于劣势的对手，可能就在下一个拐点处处于优势。这也是之前版本围棋机器学习得薄弱之处。

2. 研究的基本内容与方案

一、基本内容

1. 基于围棋文本协议开发一个能对围棋棋盘进行估值、快速走子的计算机围棋程序。

2.制作价值神经网络数据集，把围棋棋谱信息文件引入作为训练用的特征矩阵。设计价值神经网络并进行优化，使用蒙特卡洛树方法进行自我博弈，将博弈的结果用于训练网络策略输出和价值输出，得到更为优化的网络，重复这一过程，直到棋力达到预期的目标。

3. 研究计划与安排

第一阶段（第1周——第3周）：查阅相关的参考论文和书籍资料并完成开题报告；翻译英文论文（不少于5000汉字），并交予指导教师检查。

第二阶段（第4周——第9周）：了解室强化学习的各个过程，广泛查围棋机器学习的项目，了解各个项目的优缺点，并且开始构建自己的开发计划。同时对比现有的各个机器学习框架，学会正确的使用框架进行训练。

第三阶段（第10周——第13周）：实现自己程序，开始训练，与其他算法程序进行对弈，与人对弈，记录训练的成果，分析对弈数据。

4. 参考文献（12篇以上）

[1] hardt m, price e, srebro n. equality of opportunity in supervised learning[c]advances in neural information processing systems. 2016: 3315-3323.

[2] schmidhuber j. deep learning in neural networks: an overview[j]. neural networks, 2015, 61: 85-117.

[3] ren s, he k, girshick r, et al. faster r-cnn: towards real-time object detection with region proposal networks[c]advances in neural information processing systems. 2015: 91-99.