摘  要：计算机博弈是人工智能的重要分支之一，文章对人工智能算法黑白棋中的应用进行了研究。首先介绍了计算机博弈中的经典黑白棋算法，然后介绍深度强化学习中两种典型的时间差分算法的定义和实现过程，以及两者的区别和联系。最后评测蒙特卡洛树搜索算法、Q学习算法和SARSA算法三种算法在黑白棋实际应用的表现，以及后续改进的方向。

关键词：蒙特卡洛树搜索;深度强化学习;马尔科夫决策过程;Q学习;SARSA

中图分类号：TP181    文献标识码：A 文章编号：2096-4706（2021）17-0073-06

Abstract： Computer game is one of the important branches of artificial intelligence. This paper studies the application of artificial intelligence algorithm in black and white chess. This paper first introduces the classical black and white chess algorithm in computer game， and then introduces the definition and implementation process of two typical time difference algorithms in deep reinforcement learning， as well as their differences and relations. Finally， evaluate the performance of MCTS algorithm， Q learning algorithm and SARSA algorithm in the practical application of black and white chess， as well as the direction of subsequent improvement.

Keywords： MCTS; deep reinforcement learning; Markov decision process; Q learning; SARSA

0  引  言

计算机博弈是人工智能的分支领域之一。它结合了计算机算法与博弈论，成为人工智能算法应用在其他领域前的最佳验证领域，被誉为是人工智能的果蝇[1]。传统的计算机博弈算法一般基于树搜索算法。它是一种穷举算法，采用深度优先的方式搜索整棵多叉树。假定树的分支（也称为宽度）是w，深度是d，那么它的时间复杂度为wd。指数级别的复杂度在实践中由于计算结果的时间可能达到好几天甚至好几个月，很难得到应用。

科学家针对如何在宽度和深度这两方面去减少搜索时间这一问题提出了很多有效的解决方案。第一种是减少搜索宽度。信息论之父香农（Claude shannon）于1950年提出的策略为有选择性地遍历树的分支。它可以显著地减少搜索次数，副作用是会丢失有效的分支路线。

1958年Newell等提出了一种可有效减少搜索宽度的算法：α-β剪枝（alpha-beta pruning）算法。相比香农教授的随机选择分支算法，α-β剪枝算法是一种无损选择算法。……