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

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

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

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

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

基本内容：

1）研究基于android平台，实现在android手机端一款迷宫寻宝策略游戏，迷宫中有陷阱和宝藏，玩家需要操纵角色躲避陷阱，找到宝藏；

2）对于每一个游戏关卡，使用强化学习来训练出一条帮助玩家完成游戏关卡的路径，在玩家需要帮助时点击提示即可自动去寻找通关路径；

3. 研究计划与安排

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

第二阶段（第4周—第9周）：了解基本的强化学习算法：重点掌握q-learning，sarsa算法，sarsa-lambda算法，deep-q-learning算法。研究现有强化学习方法，同时总结各种算法的优缺点以及使用范围。

第三阶段（第10周—第13周）：实现基于强化学习的android端迷宫寻宝策略游戏，完成游戏逻辑功能以及用强化学习实现的提示自动寻路。

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

[1] 郭霖. 第一行代码——android[m]. 人民邮电出版社, 2016.

[2] sutton r s, barto a g. reinforcementlearning: an introduction[m]. mit press, 2018.

[3]watkins c j c h, dayan p. q-learning[j]. machine learning, 1992, 8(3-4):279-292.