近年来，随着手机用户数量的急剧增长和手机媒介技术的不断创新，手机的游戏得到了越来越多人的热爱。其中棋类游戏因其休闲益智，可玩性高等特点深受群众欢迎。五子棋游戏更是吸引着各个年龄段的人群。五子棋是一种两人对战的纯策略型棋类游戏，起源于中国古代的传统黑白棋之一,发展于日本，流行于欧美，玩法简单，老少皆宜[1]。目前，很多游戏平台上都有五子棋，如QQ游戏，4399，联众等。

本课题是设计一个安卓平台的五子棋游戏，提供一个人机对弈的功能。目前的很多五子棋程序的对弈策略，一般都采用极大极小搜索、Alpha-Beta剪枝、小窗口搜索等搜索算法[2]。因为棋类游戏巨大的搜索空间，在短时间内，这些搜索算法很难做到同时兼顾搜索的广度和深度。若想得到最优解，必须通过长时间的搜索，无形中磨灭了玩家游戏的耐心和时间。而且这类算法十分依赖估值函数，估值函数优劣直接决定了棋力的强与弱，而估值函数如何确定，本身就是一个相当复杂的问题[3]。本研究旨在实现基于强化学习的五子棋游戏，利用强化学习算法解决短时间内搜索的精度问题，并且使AI的棋力不再受限与估值函数。使得玩家有更好的游戏体验。

强化学习(reinforcement learning)，又称再励学习、评价学习，是一种重要的机器学习方法[4]。强化学习的算法主要有单步更新的Q-learning，Sarsa，升级版Policy Gradients，回合更新的基础版的Policy Gradients、Monte-Carlo Learning等[4]。

强化学习的研究历史：1954年Minsky首次提出“强化”和“强化学习”的概念和术语[5]。1965年在控制理论中Waltz和傅京孙也提出这一概念，描述通过奖惩的手段进行学习的基本思想[6]。他们都明确了“试错”是强化学习的核心机制。Bellman在1957年提出了求解最优控制问题以及最优控制问题的随机离散版本马尔可夫决策过程（MarkovDecision Process，MDP）的动态规划（DynamicProgramming）方法，而该方法的求解采用了类似强化学习试错迭代求解的机制。尽管他只是采用了强化学习的思想求解马尔可夫决策过程，但事实上却导致了马尔可夫决策过程成为定义强化学习问题的最普遍形式，加上其方法的现实操作性，以致后来的很多研究者都认为强化学习起源于Bellman的动态规划，随后Howard提出了求解马尔可夫决策过程的策略迭代方法[7]。

如今，强化学习被广泛应用在自动驾驶[8]，Atari游戏[9]和Markov游戏[10]等领域。打败世界围棋冠军的AlphaGo Zero正是使用了强化学习中的蒙特卡洛方法[11]，展现了强化学习在棋类游戏中的过人之处。

本研究主要实现基于强化学习的五子棋对弈APP, 针对一般五子棋AI搜索算法耗时且结果不精确的缺点，利用强化学习算法，训练出一个速度快且走子精确的模型，并将模型移植到安卓APP上，使玩家在游戏中不再耗费大量时间等待，并且能体验到更智能的AI。

参考文献：

[1] 李露露.图说中国传统玩具与游戏[M]. 世界图书出版公司, 2006.

[2] 李红, 吴粉侠, 刘小豫. 博弈树搜索算法研究[J]. 长春工程学院学报(自然科学版), 2007,8(2):59-62.