人工智能一直是当下发展最具前瞻性并备受人们关注的一个话题，而人工智能的一个长期目标则是建立在具有挑战性的领域里进行学习、决策并逐渐超越人能力的算法。棋类游戏则是人类智力方面最具挑战性的领域之一，因此从人工智能诞生开始，其在棋类游戏领域的探索便一直在进行。最初的人工智能注重算法的计算能力。1997年，IBM的“深蓝”战胜了国际象棋冠军卡斯帕罗夫，“深蓝”通过强大的计算能力穷举所有路数来选择最优策略，做到了可以预判12步。这样的算法依靠强大的计算能力取胜，然而并不是在所有领域中有有效，在围棋方面尽管可以训练到无限接近于人的能力，但始终无法超越，因为围棋不仅仅需要计算能力，还需要思考，因此以人类知识为基础来训练算法的思考能力，即从头开始建立一个可以思考的类似人脑的算法。

因此为对比算法进化的优势和特点，本课题尝试在五子棋领域对经典人工智能的博弈树搜索和后来出现的深度强化学习的算法性能进行比较，从训练速度、计算次数、决策判断、对战胜率等方面对两种算法进行剖析分析，从而得到算法进化的主要思路和方向，为学习深度学习和强化学习提供更好的优化思想。

一、神经网络的国内外发展现状

人工神经网络（Artificial Neural Network，即ANN ），是20世纪80 年代以来人工智能领域兴起的研究热点。它从信息处理角度对人脑神经元网络进行抽象， 建立某种简单模型，按不同的连接方式组成不同的网络。在工程与学术界也常直接简称为神经网络或类神经网络。神经网络是一种运算模型，由大量的节点（或称神经元）之间相互联接构成。每个节点代表一种特定的输出函数，称为激励函数（activation function）。每两个节点间的连接都代表一个对于通过该连接信号的加权值，称之为权重，这相当于人工神经网络的记忆。网络的输出则依网络的连接方式，权重值和激励函数的不同而不同。而网络自身通常都是对自然界某种算法或者函数的逼近，也可能是对一种逻辑策略的表达。最近十多年来，人工神经网络的研究工作不断深入，已经取得了很大的进展，其在模式识别、智能机器人、自动控制、预测估计、生物、医学、经济等领域已成功地解决了许多现代计算机难以解决的实际问题，表现出了良好的智能特性。

1943年，心理学家W.S.McCulloch和数理逻辑学家W.Pitts建立了神经网络和数学模型，称为MP模型。他们通过MP模型提出了神经元的形式化数学描述和网络结构方法，证明了单个神经元能执行逻辑功能，从而开创了人工神经网络研究的时代。1949年，心理学家提出了突触联系强度可变的设想。60年代，人工神经网络得到了进一步发展，更完善的神经网络模型被提出，其中包括感知器和自适应线性元件等。1982年，美国加州工学院物理学家J.J.Hopfield提出了Hopfield神经网格模型，引入了“计算能量”概念，给出了网络稳定性判断。 1984年，他又提出了连续时间Hopfield神经网络模型，为神经计算机的研究做了开拓性的工作，开创了神经网络用于联想记忆和优化计算的新途径，有力地推动了神经网络的研究，1985年，又有学者提出了波耳兹曼模型，在学习中采用统计热力学模拟退火技术，保证整个系统趋于全局稳定点。1986年，Rumelhart, Hinton, Williams发展了BP算法。迄今，BP算法已被用于解决大量实际问题。1988年，Linsker对感知机网络提出了新的自组织理论，并在Shanon信息论的基础上形成了最大互信息理论，从而点燃了基于NN的信息应用理论的光芒。1988年，Broomhead和Lowe用径向基函数(Radial basis function, RBF)提出分层网络的设计方法，从而将NN的设计与数值分析和线性适应滤波相挂钩。90年代初，Vapnik等提出了支持向量机(Support vector machines, SVM)和VC(Vapnik-Chervonenkis)维数的概念。

随着人工神经网络在世界范围内的兴起,国内也逐步掀起了研究热潮。1990年2月由国内自动化学会、中国电子学会、人工智能学会、通信学会、生物物理学会、心理学会和物理学会等八个学会联合在北京召开了中国神经网络首届学术会议。这次大会以“八学会联盟,探智能奥秘"为主题 ,开创了中国人工神经网络及神经计算机方面科学研究的新纪元。2004年8月在中国大连召开的ISNN(International Symposium Neural Networks)2004国际会议，引起了国内外神经网络研究者的广泛关注。经过十几年的发展,中国学术界和工程界在人工神经网络的理论研究和应用方面取得了丰硕成果,学术论文、应用成果和研究人员逐年增加。

二、强化学习的国内外发展现状

强化学习(reinforcement learning)，又称再励学习、评价学习，是一种重要的机器学习方法，在智能控制机器人及分析预测等领域有许多应用。强化学习是智能体（Agent）以“试错”的方式进行学习，通过与环境进行交互获得的奖赏指导行为，目标是使智能体获得最大的奖赏，强化学习不同于连接主义学习中的监督学习，主要表现在强化信号上，强化学习中由环境提供的强化信号是对产生动作的好坏作一种评价(通常为标量信号)，而不是告诉强化学习系统RLS(reinforcement learning system)如何去产生正确的动作。由于外部环境提供的信息很少，RLS必须靠自身的经历进行学习。通过这种方式，RLS在行动-评价的环境中获得知识，改进行动方案以适应环境。

强化学习的思想源于行为心理学（behavioural psychology）的研究。1911年Thorndike提出了效用法则（Law of Effect）：一定情境下让动物感到舒服的行为，就会与此情景加强联系，当此情景再现时，动物的这种行为也更易再现；相反，让动物感觉不舒服的行为，会减弱与此情景的联系，此情景再现时，此行为将很难再现。1954年Minsky首次提出“强化”和“强化学习”的概念和术语。1965年在控制理论中Waltz和傅京孙也提出这一概念，描述通过奖惩的手段进行学习的基本思想。他们都明确了“试错”是强化学习的核心机制。Bellman在1957年提出了求解最优控制问题以及最优控制问题的随机离散版本马尔可夫决策过程（Markov Decision Process，MDP）的动态规划（Dynamic Programming）方法，而该方法的求解采用了类似强化学习试错迭代求解的机制。到1989年，Watkins提出的Q学习进一步拓展了强化学习的应用和完备了强化学习。Q学习使得强化学习不再依赖于问题模型。此外Watkins还证明了当系统是确定性的马尔可夫决策过程，并且回报是有限的情况下，强化学习是收敛的，也即一定可以求出最优解。至今，Q学习已经成为最广泛使用的强化学习方法。

三、模拟方法