如今移动智能终端的普及，人们有许多碎片时间都在手机上度过，其中手机游戏占比例非常大，这其中有一部分迷宫寻宝系列的益智游戏广受群众欢迎。经网上搜索，如国内寻宝游戏多为网页游戏或单机游戏如“夺宝奇兵”，手机游戏“不思议迷宫”等，国外的迷宫寻宝游戏有“密道寻宝之海盗行动”，“东方大菠萝寻宝者”等，受众广泛，能在空闲片段中完成一个迷宫，体验解谜乐趣。

本课题是对寻宝游戏设计的Android端游戏设计，该类游戏一般为进入迷宫后，操作角色去寻找迷宫中的一个或多个宝藏并找到出口完成迷宫。有些迷宫的设计与玩法可能非常困难或非常耗时，玩家在面临困难时，游戏并没有帮助玩家去完成通关。为了去设计帮助玩家通关的AI，目前人工智能完成游戏采取的策略一般为A*算法[1]或BFS算法[1]。这两种算法都是不断地盲目搜索，并不能很好地高效地通关游戏。而强化学习是一个根据环境以及自身状态来制定行动决策和规划的算法，可以很好地解决寻找迷宫的解决路径，帮助玩家解决迷宫难题，同时观看AI去完成迷宫是一件非常有趣味的事情。本实验旨在实现基于强化学习的人工智能完成迷宫寻宝游戏，并对比多种强化学习的效果，选择最佳的强化学习方法去走出迷宫。

强化学习(reinforcement learning)[2]，又称再励学习、评价学习，是一种重要的机器学习方法。近年来,基于Q-learning的强化学习[3]有许多改进,如同样是基于价值的Sarsa算法[4]，基于准则的[5],把二者结合起来的Actor-Critic算法[6]基于解决高维度输入与深度学习结合起来的深度强化学习[7]等,如今广泛应用在自动驾驶[8]和Atari游戏[9]等领域。

强化学习的研究历史：1954年Minsky首次提出“强化”和“强化学习”的概念和术语[10]。1965年在控制理论中Waltz和傅京孙也提出这一概念，描述通过奖惩的手段进行学习的基本思想。[2][11]他们都明确了“试错”是强化学习的核心机制。Bellman在1957年提出了求解最优控制问题以及最优控制问题的随机离散版本马尔可夫决策过程（MarkovDecision Process，MDP）的动态规划（DynamicProgramming）方法，而该方法的求解采用了类似强化学习试错迭代求解的机制。尽管他只是采用了强化学习的思想求解马尔可夫决策过程，但事实上却导致了马尔可夫决策过程成为定义强化学习问题的最普遍形式，加上其方法的现实操作性，以致后来的很多研究者都认为强化学习起源于Bellman的动态规划，随后Howard提出了求解马尔可夫决策过程的策略迭代方法[12]。到1989年，Watkins提出的Q学习进一步拓展了强化学习的应用和完备了强化学习[3]。Q学习使得在缺乏立即回报函数（仍然需要知道最终回报或者目标状态）和状态转换函数的知识下依然可以求出最优动作策略，换句话说，Q学习使得强化学习不再依赖于问题模型。此外Watkins还证明了当系统是确定性的马尔可夫决策过程，并且回报是有限的情况下，强化学习是收敛的，也即一定可以求出最优解。至今，Q学习已经成为最广泛使用的强化学习方法。

如今，为解决高维度连续输入问题，结合深度学习，深度强化学习把Q-Table的更新问题变成一个函数拟合问题，相近的状态得到相近的输出动作。如下式，通过更新参数 θ 使Q函数逼近最优Q值 。近年来，深度强化学习在多个领域应用，如在围棋上击败顶级选手的ALPHA GO，deep mind在atari游戏[9]上的应用，以及openAI在DOTA2游戏上击败人类半职业队伍的深度强化学习AI。

本研究主要实现基于深度强化学习的迷宫寻宝策略，对于寻找迷宫，学习解决迷宫寻宝问题，将在安卓移动平台上实现不同迷宫的Agent训练以及测试，开发出迷宫寻宝游戏App，给用户进行游戏，操纵角色避开陷阱寻找宝藏。当玩家需要帮助或者提示时，运用强化学习，让小人自动寻找出最优的寻宝路线，走出迷宫完成游戏。

参考文献：

[1]樊质军,杨朋英,孙玉霞.基于A星算法的游戏路径优化的仿真分析[J].电脑知识与技术,2018,14(01):195-196.

[2]WaltzM D amp; Fu K S, A heuristic approach to reinforcement learning controlsystems[J],IEEE Trans Automatic Control, 1965,10(3):390-398

[3] WatkinsC J C H, Dayan P. Q-learning[J]. Machine learning, 1992, 8(3-4): 279-292.