原创论文网 原创论文网

原创论文网电话
免费咨询热线电话
15871151735
首页 > 论文 > 计算机 >

基于强化学习的迷宫寻宝游戏设计与实现

论文库:计算机 时间:2022-01-22 15:03:03 点击:

摘  要wI4原创论文网_专业的研究生论文网站

随着科学技术的不断发展,人工智能作为计算机科学的一个分支,理论和技术日益成熟,应用领域不断扩大,强化学习是一种重要的无监督人工智能算法,能够控制个体在某个环境下自主行动,并透过和环境之间的互动,个体可以不断改进自身的行为。wI4原创论文网_专业的研究生论文网站
wI4原创论文网_专业的研究生论文网站
现如今,游戏作为一种休闲娱乐活动已经深入人们的生活,游戏 AI 作为各类游戏不可缺少的一部分,如何最少的资源,提高游戏的趣味性与品质,就成了目前游戏开发的一个钟难点。wI4原创论文网_专业的研究生论文网站
wI4原创论文网_专业的研究生论文网站
因此,本文基于强化学习相关理论实现了迷宫寻宝游戏的设计与开发,基本的思想就是先绘制地图,显示路径,然后通过强化学习的机制,可以让玩家更有兴趣更深入的去了解这个游戏,把游戏分成一个个小的模块,小的结构,让玩家有更好的体验效果,满足玩家的需求,达到我们学习目的,同时也可以让玩家有更好的体现效果。经过测试,使用强化学习算法在博弈训练后可以获得更长的存活时间和更好的得分,大大的提高了训练的稳定性和效率。wI4原创论文网_专业的研究生论文网站
  wI4原创论文网_专业的研究生论文网站
关键词: 强化学习;迷宫寻宝;游戏博弈 ;Q-learning;人工智能wI4原创论文网_专业的研究生论文网站
 wI4原创论文网_专业的研究生论文网站
 wI4原创论文网_专业的研究生论文网站

 wI4原创论文网_专业的研究生论文网站

AbstractwI4原创论文网_专业的研究生论文网站

With the continuous development of science and technology, as a branch of computer science, artificial intelligence is becoming more and more mature in theory and technology, and its application field is expanding. Reinforcement learning is an important unsupervised artificial intelligence algorithm, which can control individuals to act independently in a certain environment, and through the interaction with the environment, individuals can continuously improve their own behavior.wI4原创论文网_专业的研究生论文网站
Nowadays, as a kind of leisure and entertainment activities, game AI has gone deep into people's life. As an indispensable part of all kinds of games, how to improve the interest and quality of the game with the least resources has become a difficult point in the current game development.Therefore, based on the theory of reinforcement learning, this paper realizes the design and development of maze treasure hunt game. The basic idea is to draw a map and show the path first, and then through the mechanism of reinforcement learning, players can be more interested in understanding the game in depth, and the game can be divided into small modules and structures, so that players can have better experience effect and meet the needs of players To achieve our learning goal, we can also make players have better effect. After testing, using reinforcement learning algorithm in the game training can get longer survival time and better scores, greatly improving the stability and efficiency of training.wI4原创论文网_专业的研究生论文网站
  wI4原创论文网_专业的研究生论文网站
Key words: Strengthen learning; Maze treasure hunt;Game game; Q-learning;artificial intelligencewI4原创论文网_专业的研究生论文网站

wI4原创论文网_专业的研究生论文网站
wI4原创论文网_专业的研究生论文网站
wI4原创论文网_专业的研究生论文网站
第一章  绪  论wI4原创论文网_专业的研究生论文网站

1.1 研究背景及意义wI4原创论文网_专业的研究生论文网站
 wI4原创论文网_专业的研究生论文网站

强化学习是机器学习的一个领域,强调如何根据环境采取行动,以最大限度地实现预期效益。它的灵感来源于心理学中的行为理论,即像有机体一样,在环境给予的奖惩刺激下,对刺激的期待逐渐形成并产生能够获得最大利益的习惯性行为。这种方法具有普遍性,因此在博弈论、控制论、运筹学、信息论、仿真优化、多智能体系统学习、群体智能、统计学和遗传算法等许多领域都得到了研究。在外科研究和控制理论的背景下,增加的学习被称为“近似动态规划”(ADP)。在经济学和博弈论中,强化学习被用来解释在有限理性条件下如何平衡。强化学习通过agent感知外部环境状态作出不同的尝试,通过不断的尝试留下相对好的动作,抛弃相对差的动作,从而来提高自己的行为表现。它具有对环境的先验知识低的特点,可以在实时环境中在线学习,因此在人工智能领域得到广泛的研究和使用。wI4原创论文网_专业的研究生论文网站

wI4原创论文网_专业的研究生论文网站
在以往的游戏当中,有角色扮演类等等很多类型的游戏,本文设计开发的这一款迷宫类的游戏基于了强化学习这一个理念,通过学习Q-learning的基本原理,更深度的去优化这个算法,对控制游戏开发复杂性、降低开发门槛有着重要意义,同时对于开发更通用的人工智能也有着一定的帮助。wI4原创论文网_专业的研究生论文网站

wI4原创论文网_专业的研究生论文网站
1.2 国内外研究现状wI4原创论文网_专业的研究生论文网站

wI4原创论文网_专业的研究生论文网站
强化学习是机器学习的一个分支,与机器学习经典的有监督学习和无监督学习不同,强化学习最大的特点是在与环境的交互中进行学习。在与环境的互动中,智能体根据他们获得的奖励和惩罚不断学习以更好的适应环境。强化学习范式与人类学习知识的过程非常相似,在未知采取何种行为的情况下,智能体必须通过不断尝试,才能发现采取哪种行为能够产生最大回报。因此,强化学习被视为实现通用人工智能的重要途径。最早应用强化学习的案例可以追溯到1956年Bellman提出来动态规划方法;wI4原创论文网_专业的研究生论文网站
wI4原创论文网_专业的研究生论文网站
1992 年 Wathins 提出的 Q-learning 算法,Q-learning 算法是现在最常用的强化学习算法之一;同年,Tesauro 等人将强化学习应用于西洋双陆棋并达到了大师级的水准[6] [7];2015 年,Google-deepmind 团队提出的 Deep-Q-Network 算法,应用于 Atari 游戏,取得了超过人类玩家水平的成绩[8];2016,将深度学习与强化学习相结合而产生的 AlphaGo,再一次掀起深度强化学习的热潮,走上高峰。强化学习算法与深度学习的结合会更加紧密,机器学习算法常被分为监督学习、非监督学习和强化学习,强化学习算法其中一个趋势便是三类机器学习方法在逐渐走向统一的道路,谁结合得好,谁就会有更好的突破,该方向的代表作如基于深度强化学习的对话生成等。wI4原创论文网_专业的研究生论文网站

wI4原创论文网_专业的研究生论文网站
1.3 论文主要工作wI4原创论文网_专业的研究生论文网站

wI4原创论文网_专业的研究生论文网站
本文介绍了强化学习的相关理论与知识,在此基础上整体设计并实现了了迷宫游戏,利用强化学习的机制,对整体进行了优化与训练,游戏让玩家有更好的体验效果,满足玩家的需求。经过测试,使用强化学习算法在博弈训练后可以获得更长的存活时间和更好的得分,大大的提高了游戏的趣味性。wI4原创论文网_专业的研究生论文网站

wI4原创论文网_专业的研究生论文网站
1.4 论文组织结构wI4原创论文网_专业的研究生论文网站
 wI4原创论文网_专业的研究生论文网站

本文的文章结构分为五章,具体阐述基于强化学习的迷宫寻宝游戏研究与设计实现,各章节安排为:wI4原创论文网_专业的研究生论文网站

wI4原创论文网_专业的研究生论文网站
绪论。说明本文的研究背景及意义,简要介绍强化学习的发展历程、概念背景等,阐述了本文的主要工作,最后说明本文的组织结构。wI4原创论文网_专业的研究生论文网站

wI4原创论文网_专业的研究生论文网站
相关理论与技术基础。介绍了游戏博弈策略,简单介绍了强化学习和TensorFlow的概念wI4原创论文网_专业的研究生论文网站

wI4原创论文网_专业的研究生论文网站
基于强化学习的迷宫寻宝游戏框架。wI4原创论文网_专业的研究生论文网站

第四章,深度Q-learning网络的设计。wI4原创论文网_专业的研究生论文网站
第五章,模型训练与结果分析。wI4原创论文网_专业的研究生论文网站
第六章,结论。总结本论文的主要内容与成果,并对未来的工作内容提wI4原创论文网_专业的研究生论文网站
出展望。wI4原创论文网_专业的研究生论文网站
 wI4原创论文网_专业的研究生论文网站
wI4原创论文网_专业的研究生论文网站
 wI4原创论文网_专业的研究生论文网站

第二章相关理论与技术基础wI4原创论文网_专业的研究生论文网站

2. 1博弈策略wI4原创论文网_专业的研究生论文网站
 wI4原创论文网_专业的研究生论文网站

在人工智能的发展历史中,游戏扮演着不可或缺的角色。本文将深度学习和强化学习结合起来应用于游戏中,训练智能体学习制定最佳游戏博弈策略[9]。在 1989 年到 2007 年之间,加拿大阿尔伯坦大学的团队,做了一个跳棋的人工智能——Chinook。把 Chinook 喻为跳棋之神毫不为过,因为它在真正意义上破解了跳棋。换言之,就是不论你用什么策略,Chinook 永远不会输。这是可以在数学上被验证的。根据 Chinook 的分析,在跳棋中不论你是先手或是后手,只要有一个完美的策略,永远双方都会打成平手。也就是说,跳棋被证明是一个真正意义上的游戏博弈。下一位出场的,是 IBM 的研究员 Gerald Tesauro。他最著名的成就,就是写了一个能够超越人类 Backgammon世界冠军的人工智能。Backgammon 是一个有一定随机性的掷骰子的概率游戏。2016 年 3 月谷歌 deepmind 团队的围棋 AI“AlphaGo”以 4:1 的大比分战胜了世界顶级围棋选手李世石,称为一个里程碑似的成就。但是 AlphaGo并没有停止它的进化,经过 AlphaGo Fan、AlphaGo Lee、AlphaGo Master 之后,AlphaGoZero 在极短的时间内诞生,并成功打败了战胜李世石的 AlphaGo,它第一次让AI 完全脱离人类历史棋谱,只通过围棋规则和“自我对弈”,在 2900 万次自我对弈后成长为世界上最强大的围棋大师。除此之外,在其他游戏中,深度强化学习也发挥了强大的功能。在 2016 年九月份的基于第一人称射击游戏毁灭战士 DOOM 的 AI 挑战赛“Visual Doom AICompetition@CIG 2016”中[10],获得第二名的卡耐基梅隆大学[11]The Terminators团队的机器人 Arnold,在他们的模型使用了DQN 和DRQN。wI4原创论文网_专业的研究生论文网站

wI4原创论文网_专业的研究生论文网站
2.2强化学习简介wI4原创论文网_专业的研究生论文网站
 wI4原创论文网_专业的研究生论文网站

强化学习(Reinforcement learning)是一个由行为心理学启发的机器学习领域,是机器学习里面的一个分支,指的是面向目标的算法,这种算法学习如何在一些具的步骤中达到一个目标或者最大化,例如,最大化一个游戏中通过些行动而获得的得分。它们可以从一个空白状态开始,然后在合适的条件下达到超越人类水平的性能。就像被糖果和体罚刺激的小孩子一样,当它们做出错的预测时,这些算法会受到惩罚,当它们做出正确的预测时,它们会得到奖励—这便是强化的意义所在。wI4原创论文网_专业的研究生论文网站
wI4原创论文网_专业的研究生论文网站
强化学习主要包括以下几部分:wI4原创论文网_专业的研究生论文网站
wI4原创论文网_专业的研究生论文网站
●智能体(Agent):可以采取行动的智能个体。例如,可以完成投递的无人机,或者在视频游戏中朝目标行动的超级马里奥。强化学习算法就是一个智能体。而在现实生活中,那个智能体就是你。wI4原创论文网_专业的研究生论文网站
wI4原创论文网_专业的研究生论文网站
●行动(Action):A 是智能体可以采取的行动的集合。一个行动(action)几乎是一目了然的,但是应该注意的是智能体是在从可能的行动列表中进行选择。在电子游戏中,这个行动列表可能包括向右奔跑或者向左奔跑,向高处跳或者向低处跳,下蹲或者站住不动。在股市中,这个行动列表可能包括买入,卖出或者持有任何有价证券或者它们的变体。在处理空中飞行的无人机时,行动选项包含三维空间中的很多速度和加速度。wI4原创论文网_专业的研究生论文网站
wI4原创论文网_专业的研究生论文网站
●环境(Environment):指的就是智能体行走于其中的世界。这个环境将智能体当前的状态和行动作为输入,输出是智能体的奖励和下一步的状态。如果你是一个智能体,那么你所处的环境就是能够处理行动和决定你一系列行动的结果的物理规律和社会规则。wI4原创论文网_专业的研究生论文网站
wI4原创论文网_专业的研究生论文网站
●状态(State,S):一个状态就是智能体所处的具体即时状态,也就是说,一个具体的地方和时刻,这是一个具体的即时配置,它能够将智能体和其他重要的失事物关联起来,例如工具、敌人和或者奖励。它是由环境返回的当前形势。wI4原创论文网_专业的研究生论文网站
wI4原创论文网_专业的研究生论文网站
●奖励(Reward,R):奖励是本文衡量某个智能体的行动成败的反馈。例如,在视频游戏中,当马里奥碰到金币的时候,它就会赢得分数。面对任何既定的状态,智能体要以行动的形式向环境输出,然后环境会返回这个智能体的一个新状态(这个新状态会受到基于之前状态的行动的影响)和奖励(如果有任何奖励的话)。奖励可能是即时的,也可能是迟滞的。它们可以有效地评估该智能体的行动。wI4原创论文网_专业的研究生论文网站
wI4原创论文网_专业的研究生论文网站
●策略(policy,π):policy 是智能体基于当前的状态做出下一步行动所wI4原创论文网_专业的研究生论文网站
用的策略。wI4原创论文网_专业的研究生论文网站
wI4原创论文网_专业的研究生论文网站
●价值(value,V):期望的具有折扣的长期收益,而不是短期回报 R。Q 价值或者行动价值(Q):Q 价值(Q-Value)和上述的价值类似,不同的是它还使用了另一个参数--当前的行动 a。wI4原创论文网_专业的研究生论文网站
所以,环境就是能够将当前状态下采取的动作转换成下一个状态和奖励的函数;智能体是将新的状态和奖励转换成下一个行动的函数。可以知悉智能体的函数,但是无法知悉环境的函数。环境是一个只能看到输入输出的黑盒子。强化学习相当于智能体在尝试逼近这个环境的函数,这样就能够向黑盒子环境发送最大化奖励的行动了。wI4原创论文网_专业的研究生论文网站
wI4原创论文网_专业的研究生论文网站
在上图 3.1 的反馈回路中,每一个代表时间步骤的下标 t 和 t+1 都指的是一个不同的状态:在 t 时刻和 t+1 时刻的状态。与其他诸如监督学习和非监督学习形式不同—强化学习仅可以被认为是一系列先后发生的状态-行动(state-action)对。强化学习通过行动产生的结果来判断行动。它是面向目标的,它的目标是习得能够让智能体达到目标的一些行动序列。例如,在电子游戏中,这个目标是以最高的分数完成游戏,所以游戏过程中每一次得到的额外分数都会影响智能体随后的行动;也就是说,智能体可能学会:为了最大化它的得分,他应该射击战舰,触碰硬币或者躲避流星。可以通过对输入的解释将强化学习与监督学习和非监督学习区分开来。本文通过描述它们学习的“东西”来说明它们的不同之处。wI4原创论文网_专业的研究生论文网站
wI4原创论文网_专业的研究生论文网站
l 无监督学习:那东西就是这个样子的。无监督学习算法学到了没有名字的事物之间的相似性,通过进一步的扩展,它们可以通过识别不寻常或者不相似的实例来发现相反或者执行异常检测。wI4原创论文网_专业的研究生论文网站
l 监督学习:那个东西是一块“双层吉士汉堡”。监督学习算法学到了数据实体实例和它们的标签之间的关联。也就是说,监督学习算法需要有一个有标签的数据集。那些标签被用来“监督”和矫正算法,因为算法在预测标签的时候可能会做出错误的猜测。wI4原创论文网_专业的研究生论文网站
l 强化学习:基于短期和回报和长期回报的奖励,强化学习可以被看做是在一个具有稀疏反馈的环境中的监督学习。wI4原创论文网_专业的研究生论文网站
wI4原创论文网_专业的研究生论文网站
2.3TensorFlow系统介绍wI4原创论文网_专业的研究生论文网站
wI4原创论文网_专业的研究生论文网站
TensorFlow简介wI4原创论文网_专业的研究生论文网站
wI4原创论文网_专业的研究生论文网站
TensorFlow 是由 Google 大脑小组开发的用于数值计算的开源软件库。wI4原创论文网_专业的研究生论文网站
wI4原创论文网_专业的研究生论文网站
TensorFlow 采用数据流图(data flow graphs)的形式进行数值计算,数据用 tensor来表示,通过session对图进行计算,使用 variable 来保持状态信息,使用 feeds和 fetches 来填充数据和抓取任意的操作结果。TensorFlow 架构灵活,可以在一个或者多个平台上进行计算,如 CPU、GPU、移动设备等。TensorFlow 被广泛应用于机器学习及其他计算机领域。wI4原创论文网_专业的研究生论文网站
wI4原创论文网_专业的研究生论文网站
图 3.4 TensorFlow 运算流程(略)wI4原创论文网_专业的研究生论文网站

wI4原创论文网_专业的研究生论文网站
wI4原创论文网_专业的研究生论文网站
第三章 总体功能wI4原创论文网_专业的研究生论文网站

3.1 迷宫算法形成wI4原创论文网_专业的研究生论文网站

对迷宫生成算法进行具体阐述之前,有两个概念首先要明确定义一下:迷宫单元和墙。迷宫单元可以映射到无权连通图中的点,而墙壁则可以映射到无权连通图中两点之间的边。如果墙壁是打通的,则记为无权连通图中的墙壁两侧的点间有边;如果墙壁是没有打通的,则记为无权连通图中的墙壁两侧的点间没有边。要生成一个随机的迷宫,就需要做到迷宫中任意两个迷宫单元之间都有一条路径。wI4原创论文网_专业的研究生论文网站
 wI4原创论文网_专业的研究生论文网站

我们用二维数组表示一个迷宫,每个迷宫单元表示为一个二维数组元素,由于生成算法的限制,迷宫的行数和列数均需设置为奇数,在了解了相关算法原理后,就能明白其中原因。在下列迷宫生成算法执行之前,假设位于奇数行奇数列的点为迷宫单元,位于偶数行或者偶数列的点为墙壁,且所有的点均初始化为未访问状态、不可通过状态。wI4原创论文网_专业的研究生论文网站
 wI4原创论文网_专业的研究生论文网站

3.2 算法描述wI4原创论文网_专业的研究生论文网站

wI4原创论文网_专业的研究生论文网站
Depth First Search Algorithm(深度优先搜索算法)wI4原创论文网_专业的研究生论文网站

将起点作为当前迷宫单元并标记为已访问。wI4原创论文网_专业的研究生论文网站

当还存在未标记的迷宫单元,进行循环。wI4原创论文网_专业的研究生论文网站

wI4原创论文网_专业的研究生论文网站
Ⅰ如果当前迷宫单元有未被访问过的的相邻的迷宫单元。wI4原创论文网_专业的研究生论文网站

a随机选择一个未访问的相邻迷宫单元。wI4原创论文网_专业的研究生论文网站

b将当前迷宫单元入栈。wI4原创论文网_专业的研究生论文网站

c移除当前迷宫单元与相邻迷宫单元的墙。wI4原创论文网_专业的研究生论文网站

d标记相邻迷宫单元并用它作为当前迷宫单元。wI4原创论文网_专业的研究生论文网站

wI4原创论文网_专业的研究生论文网站
Ⅱ如果当前迷宫单元不存在未访问的相邻迷宫单元,并且栈不空。wI4原创论文网_专业的研究生论文网站

a栈顶的迷宫单元出栈。wI4原创论文网_专业的研究生论文网站

b令其成为当前迷宫单元。wI4原创论文网_专业的研究生论文网站

wI4原创论文网_专业的研究生论文网站
生成迷宫特点图5-2 所示。wI4原创论文网_专业的研究生论文网站

 图5-2 生成迷宫特点图(略)wI4原创论文网_专业的研究生论文网站

wI4原创论文网_专业的研究生论文网站
wI4原创论文网_专业的研究生论文网站
第四章 软件系统设计wI4原创论文网_专业的研究生论文网站

4.1 项目结构设计wI4原创论文网_专业的研究生论文网站
 wI4原创论文网_专业的研究生论文网站

在强化学习的5个主要的因素有环境,智能体,状态,动作,奖励,这五个部分的结构来组成,首先我们需要的是生成环境,迷宫矩阵的形成其代码部分如。wI4原创论文网_专业的研究生论文网站
wI4原创论文网_专业的研究生论文网站
from maze_env import MazewI4原创论文网_专业的研究生论文网站
env = Maze() #迷宫可以自定义。wI4原创论文网_专业的研究生论文网站
env.mainloop()wI4原创论文网_专业的研究生论文网站

wI4原创论文网_专业的研究生论文网站
4.2 动作定义wI4原创论文网_专业的研究生论文网站

wI4原创论文网_专业的研究生论文网站
定义机器人的动作,我们所用到的就是强化学习当中的epsilon greedy的概念。因为在初始阶段, 随机的探索环境, 往往比固定的行为模式要好, 所以这也是累积经验的阶段, 我们希望探索者不会那么贪婪(greedy)。说说我的理解,上图迷宫中,当机器人第一次找到黄金后,如果不控制他的贪婪程度,那么很可能他每次都会直奔去,加入地图中还有第二个黄金,则很有可能被忽略(即缺少对地图的完全搜索)。wI4原创论文网_专业的研究生论文网站
  wI4原创论文网_专业的研究生论文网站
所以epsilon就是用来控制贪婪程度的值。epsilon可以随着探索时间不断提升(越来越贪婪), 不过在这个例子中, 我们就固定成 epsilon = 0.9, 90% 的时间是选择最优策略, 10% 的时间来探索,其代码如下。wI4原创论文网_专业的研究生论文网站
wI4原创论文网_专业的研究生论文网站
Def choose_action(self,observation):wI4原创论文网_专业的研究生论文网站
Self.check_state_exist(observation) # 检查这个state(状态)下的所有action值wI4原创论文网_专业的研究生论文网站
# action selectionwI4原创论文网_专业的研究生论文网站
If np.random,uniform() < self.epsilon: # 非贪婪模式wI4原创论文网_专业的研究生论文网站
# choose best actionwI4原创论文网_专业的研究生论文网站
state_action = self.q_table.loc[observation, :]wI4原创论文网_专业的研究生论文网站
#some actions may have the same value,randomly choose on in the actionswI4原创论文网_专业的研究生论文网站
Action = np.random.choice(state_action[state_action == np.max(state_action)].index)wI4原创论文网_专业的研究生论文网站
else:wI4原创论文网_专业的研究生论文网站
# choose random actionwI4原创论文网_专业的研究生论文网站
action = np.random.choice(self.actions) # 贪婪模式wI4原创论文网_专业的研究生论文网站
return actionwI4原创论文网_专业的研究生论文网站
ActionwI4原创论文网_专业的研究生论文网站
 wI4原创论文网_专业的研究生论文网站
4.3环境反馈wI4原创论文网_专业的研究生论文网站
wI4原创论文网_专业的研究生论文网站
在动作和环境定义好了之后,当机器人做出动作之后,其环境也要相对应的给出一些反馈,其中就包括我之前提到的奖励和惩罚,这也是强化学习的主要部分环境需要反馈出下个 state(S_ ) 和上个 **state(S)**已经做出 action(A) 所获得的 reward(R) 当机器人撞到则惩罚 ,踩到陷阱则惩罚,进入终点则奖励。代码如下。wI4原创论文网_专业的研究生论文网站
wI4原创论文网_专业的研究生论文网站
def step(self, action):wI4原创论文网_专业的研究生论文网站
s = self.canvas.coords(self.rect)wI4原创论文网_专业的研究生论文网站
base_action = np.array([0, 0])wI4原创论文网_专业的研究生论文网站
if action == 0:   # upwI4原创论文网_专业的研究生论文网站
if s[1] > UNIT:wI4原创论文网_专业的研究生论文网站
base_action[1] -= UNITwI4原创论文网_专业的研究生论文网站
elif action == 1:   # downwI4原创论文网_专业的研究生论文网站
if s[1] < (MAZE_H - 1) * UNIT:wI4原创论文网_专业的研究生论文网站
base_action[1] += UNITwI4原创论文网_专业的研究生论文网站
elif action == 2:   # rightwI4原创论文网_专业的研究生论文网站
if s[0] < (MAZE_W - 1) * UNIT:wI4原创论文网_专业的研究生论文网站
base_action[0] += UNITwI4原创论文网_专业的研究生论文网站
elif action == 3:   # leftwI4原创论文网_专业的研究生论文网站
if s[0] > UNIT:wI4原创论文网_专业的研究生论文网站
base_action[0] -= UNITwI4原创论文网_专业的研究生论文网站
 wI4原创论文网_专业的研究生论文网站
self.canvas.move(self.rect, base_action[0], base_action[1])  # move agentwI4原创论文网_专业的研究生论文网站
 wI4原创论文网_专业的研究生论文网站
s_ = self.canvas.coords(self.rect)  # next statewI4原创论文网_专业的研究生论文网站
 wI4原创论文网_专业的研究生论文网站
# reward functionwI4原创论文网_专业的研究生论文网站
if s_ == self.canvas.coords(self.oval):wI4原创论文网_专业的研究生论文网站
reward = 1wI4原创论文网_专业的研究生论文网站
done = TruewI4原创论文网_专业的研究生论文网站
s_ = 'terminal'wI4原创论文网_专业的研究生论文网站
elif s_ in [self.canvas.coords(self.barrier1),wI4原创论文网_专业的研究生论文网站
self.canvas.coords(self.barrier2),wI4原创论文网_专业的研究生论文网站
self.canvas.coords(self.barrier3),wI4原创论文网_专业的研究生论文网站
self.canvas.coords(self.barrier4),wI4原创论文网_专业的研究生论文网站
self.canvas.coords(self.barrier5),wI4原创论文网_专业的研究生论文网站
self.canvas.coords(self.barrier6)]:wI4原创论文网_专业的研究生论文网站
reward = -1wI4原创论文网_专业的研究生论文网站
done = TruewI4原创论文网_专业的研究生论文网站
s_ = 'terminal'wI4原创论文网_专业的研究生论文网站
else:wI4原创论文网_专业的研究生论文网站
reward = 0wI4原创论文网_专业的研究生论文网站
done = FalsewI4原创论文网_专业的研究生论文网站
 wI4原创论文网_专业的研究生论文网站
return s_, reward, donewI4原创论文网_专业的研究生论文网站

wI4原创论文网_专业的研究生论文网站
4.4 Q-learning算法的应用wI4原创论文网_专业的研究生论文网站
 wI4原创论文网_专业的研究生论文网站

Q学习的思想完全基于价值迭代。价值迭代每次都对所有的Q值更新一次,也就是将所有的状态和动作更新一遍,但是实际情况没有办法遍历所有的状态和动作,只能通过有限的样本进行更新,更新方法如公式:wI4原创论文网_专业的研究生论文网站
 wI4原创论文网_专业的研究生论文网站
公式略wI4原创论文网_专业的研究生论文网站
wI4原创论文网_专业的研究生论文网站
虽然目标Q值是基于价值迭代计算的,但它不会直接将计算出的Q值分配给新Q,而是使用渐进的方法,如梯度下降,逐渐收敛到最优Q值。wI4原创论文网_专业的研究生论文网站
 wI4原创论文网_专业的研究生论文网站
算法如下图:(略)wI4原创论文网_专业的研究生论文网站
 wI4原创论文网_专业的研究生论文网站
在整个的系统当中,其中最主要的就是利用到Q-learning算法,在系统中实现Q-learning算法其实就是不断的更新其中的Q table的值,然后再根据新的值来判断要在某个 state 采取怎样的 action. Q-learning 是一个 off-policy 的算法, 因为里面的 max action 让 Q table 的更新可以不基于正在经历的经验。其中就体现了强化学习和Q-learning算法,其代码如下所示。wI4原创论文网_专业的研究生论文网站
wI4原创论文网_专业的研究生论文网站
This part of code is the Q learning brain, which is a brain of the agent.wI4原创论文网_专业的研究生论文网站
All decisions are made in here.wI4原创论文网_专业的研究生论文网站
View more on my tutorial page: https://morvanzhou.github.io/tutorials/wI4原创论文网_专业的研究生论文网站
"""wI4原创论文网_专业的研究生论文网站
import numpy as npwI4原创论文网_专业的研究生论文网站
import pandas as pdwI4原创论文网_专业的研究生论文网站
class QLearningTable:wI4原创论文网_专业的研究生论文网站
def __init__(self, actions, learning_rate=0.01, reward_decay=0.9, e_greedy=0.9):wI4原创论文网_专业的研究生论文网站
self.actions = actions  # a listwI4原创论文网_专业的研究生论文网站
self.lr = learning_ratewI4原创论文网_专业的研究生论文网站
self.gamma = reward_decaywI4原创论文网_专业的研究生论文网站
self.epsilon = e_greedywI4原创论文网_专业的研究生论文网站
self.q_table = pd.DataFrame(columns=self.actions, dtype=np.float64)wI4原创论文网_专业的研究生论文网站
def choose_action(self, observation):wI4原创论文网_专业的研究生论文网站
self.check_state_exist(observation)wI4原创论文网_专业的研究生论文网站
# action selectionwI4原创论文网_专业的研究生论文网站
if np.random.uniform() < self.epsilon:wI4原创论文网_专业的研究生论文网站
# choose best actionwI4原创论文网_专业的研究生论文网站
state_action = self.q_table.loc[observation, :]wI4原创论文网_专业的研究生论文网站
state_action = state_action.reindex(np.random.permutation(state_action.index))     # some actions have same valuewI4原创论文网_专业的研究生论文网站
action = state_action.idxmax()wI4原创论文网_专业的研究生论文网站
else:wI4原创论文网_专业的研究生论文网站
# choose random actionwI4原创论文网_专业的研究生论文网站
action = np.random.choice(self.actions)wI4原创论文网_专业的研究生论文网站
return actionwI4原创论文网_专业的研究生论文网站
def learn(self, s, a, r, s_):wI4原创论文网_专业的研究生论文网站
self.check_state_exist(s_)wI4原创论文网_专业的研究生论文网站
q_predict = self.q_table.loc[s, a]wI4原创论文网_专业的研究生论文网站
if s_ != 'terminal':wI4原创论文网_专业的研究生论文网站
q_target = r + self.gamma * self.q_table.loc[s_, :].max()  # next state is not terminalwI4原创论文网_专业的研究生论文网站
else:wI4原创论文网_专业的研究生论文网站
q_target = r  # next state is terminalwI4原创论文网_专业的研究生论文网站
self.q_table.loc[s, a] += self.lr * (q_target - q_predict)  # updatewI4原创论文网_专业的研究生论文网站
 wI4原创论文网_专业的研究生论文网站
def check_state_exist(self, state):wI4原创论文网_专业的研究生论文网站
if state not in self.q_table.index:wI4原创论文网_专业的研究生论文网站
# append new state to q tablewI4原创论文网_专业的研究生论文网站
self.q_table = self.q_table.append(wI4原创论文网_专业的研究生论文网站
pd.Series(wI4原创论文网_专业的研究生论文网站
[0]*len(self.actions),wI4原创论文网_专业的研究生论文网站
index=self.q_table.columns,wI4原创论文网_专业的研究生论文网站
name=state,wI4原创论文网_专业的研究生论文网站
)wI4原创论文网_专业的研究生论文网站

wI4原创论文网_专业的研究生论文网站
wI4原创论文网_专业的研究生论文网站
第五章 系统分析与调试wI4原创论文网_专业的研究生论文网站

5.1 测试原理wI4原创论文网_专业的研究生论文网站

测试是软件开发过程中不可或缺的过程。对于已经实现系统基本功能的项目,必须对其功能进行测试。在验证系统功能正确、修改已存在错误之后才可以发布,并且在后期要进行长期的维护。对系统进行测试可以检测系统的各功能模块,对未达到预期要求的功能进行完善,之后反复对其进行迭代测试,直至测试所得数据能够完成系统预期所需各项功能和用户需求为止。现实中,人无完人,技术产品亦是如此,但对于技术类的产品来说有些错误如果不能被及时发现并改正,有可能就会造成系统的崩溃,同时给使用系统的用户或企业带来不必要的损失。因此,进行系统测试是保证系统稳定性、功能正确性非常重要的过程。我们主要对系统进行以下四个方向测试。wI4原创论文网_专业的研究生论文网站

wI4原创论文网_专业的研究生论文网站
5.2 程序运行结果wI4原创论文网_专业的研究生论文网站

进行单元测试、集成测试、功能测试。运行效果图如下:wI4原创论文网_专业的研究生论文网站

wI4原创论文网_专业的研究生论文网站
5.3 功能测试用例wI4原创论文网_专业的研究生论文网站

完整性测试是系统测试最常见的一种形式,采用功能测试用例来检查系统各项功能的正确性和完整性。可以检测系统能否完全正常的使用,看是否符合用户的需要,各个模块的功能能否实现,在我的运行过程当中,其所有的功能已经在我的需求下完成,所涉及到的强化学习和Q-learning算法也已经实现。wI4原创论文网_专业的研究生论文网站
 wI4原创论文网_专业的研究生论文网站
 wI4原创论文网_专业的研究生论文网站

wI4原创论文网_专业的研究生论文网站
第六章  结  论wI4原创论文网_专业的研究生论文网站

当今电脑游戏是很多人都会去接触和娱乐的项目,我所开发的这个迷宫寻宝的这个游戏,利用到了强化学习的思想,也是目前不管是企业还是我们在平时生活还是教育当中都会使用到的一种思想,在迷宫的创建和设计当中,我从中又加深了最短路径和优先级的算法。其中我们在生活和学习中更加要认识到强化学习所带给我们的好处,以后无论遇到什么先行动起来,如果方向正确那么就继续前行,如果错了,子曰:过则勿惮改。吸取经验,好好改正,失败乃成功之母,从头再来就是。总之要行动,胡适先生说:怕什么真理无穷,进一寸有一寸的欢喜。wI4原创论文网_专业的研究生论文网站
wI4原创论文网_专业的研究生论文网站
即想要理解信息,获得输入到输出的映射,就需要从自身的以往经验中去不断学习来获取知识,从而不需要大量已标记的确定标签,只需要一个评价行为好坏的奖惩机制进行反馈,强化学习通过这样的反馈自己进行“学习”。(当前行为“好”以后就多往这个方向发展,如果“坏”就尽量避免这样的行为,即不是直接得到了标签,而是自己在实际中总结得到的),所以来说这次的论文对我的帮助十分大。wI4原创论文网_专业的研究生论文网站
 wI4原创论文网_专业的研究生论文网站

wI4原创论文网_专业的研究生论文网站
 wI4原创论文网_专业的研究生论文网站

参考文献wI4原创论文网_专业的研究生论文网站

[1]  王桂平,孟宪虎.多因素制约的迷宫问题最优解的求解算法[J].计算机应用与软件,2012,29(3):171-174. wI4原创论文网_专业的研究生论文网站
[2]  遇娜,简广宁.回溯法求解迷宫问题[J].天津职业院校联合学报,2011,13(8):46-49.wI4原创论文网_专业的研究生论文网站
[3]  李少保,赵春晓.基于多 Agent 遗传算法求解迷宫游戏[J].北京建筑工程学院学报,2011,27(3):39-43.wI4原创论文网_专业的研究生论文网站
[4]  胡正红.一种寻路算法在游戏中的应用[J].山西电子技术,2009(6):53-54.wI4原创论文网_专业的研究生论文网站
[5]  徐洪智,李仁发,颜一鸣.分支限界法在游戏地图寻径中的应用[J].计算机工程与应用,2007,43(1):104-106.wI4原创论文网_专业的研究生论文网站
[6]  邱仲潘. Java 游戏编程[M].北京:科学出版社,2009.wI4原创论文网_专业的研究生论文网站
[7]  田翠华.  算法设计与分析[M].北京:冶金工业出版社,2007.wI4原创论文网_专业的研究生论文网站
[8]Wikipedia.Regularmap(graphtheory)[P/OL].http://en.wikipedia.org/wiki/Regular_map_(graph_theory).wI4原创论文网_专业的研究生论文网站
[9] GB3100-3102  0001—1994,中华人民共和国国家标准[S].wI4原创论文网_专业的研究生论文网站
[13]黄志强. 卷积神经网络研究及其在基音检测中的应用[D].内蒙古大学,2015.wI4原创论文网_专业的研究生论文网站
[14]LeCun Y, Bottou L, Bengio Y, et al. Gradient-based learning applied to document recognition[J]. Proceedings of the IEEE, 1998, 86(11): 2278-2324wI4原创论文网_专业的研究生论文网站
[15]Bengio Y, Louradour J, Collobert R, et al. Curriculum learning[J]. Journal of the American Podiatry Association, 2009, 60(60):6.wI4原创论文网_专业的研究生论文网站
[16]肖锋. 基于强化学习的库位优化算法在物料拉动系统中的研究与应用[D].西wI4原创论文网_专业的研究生论文网站
南交通大学,2015.wI4原创论文网_专业的研究生论文网站
[17]王新. 基于强化学习的自适应城市交通信号控制方法研究[D].浙江师范大wI4原创论文网_专业的研究生论文网站
学,2015.wI4原创论文网_专业的研究生论文网站
[18]Jianyong Liu,Ke Liu. Markov decision programming with constraints[J]. ActawI4原创论文网_专业的研究生论文网站
Mathematicae Applicatae Sinica,1994,10(1).wI4原创论文网_专业的研究生论文网站
[19]VAN H H, GUEZ A, SILVER D. Deep reinforcement learning with double Q-learning [C] //Proceedings of the 30th AAAI Conference on Artificial Intelligence. Phoenix: AAAI, 2016: 1813 – 1819.wI4原创论文网_专业的研究生论文网站
[20]Richard Maclin,Jude W. Shavlik. Recent Advances in ReinforcementwI4原创论文网_专业的研究生论文网站
Learning[M].Springer US:1995-10-04.wI4原创论文网_专业的研究生论文网站
[21]Yifan Shen,Ning Zhao,Mengjue Xia,Xueqiang Du. A Deep Q-Learning Network for Ship Stowage Planning Problem[J]. Polish Maritime Research,2017,24(s1).wI4原创论文网_专业的研究生论文网站
[22]Schaul T, Quan J, Antonoglou I, et al. Prioritized Experience Replay[J]. Computer Science, 2015.wI4原创论文网_专业的研究生论文网站
[23]Wang Z, Schaul T, Hessel M, et al. Dueling network architectures for deep reinforcement learning[J]. 2015:1995-2003.wI4原创论文网_专业的研究生论文网站
[24]Mnih V, Kavukcuoglu K, Silver D, et al. Human-level control through deep reinforcement learning[J]. Nature, 2015, 518(7540):529.wI4原创论文网_专业的研究生论文网站
[25]Lillicrap T P, Hunt J J, Pritzel A, et al. Continuous control with deep reinforcement learning[J]. Computer Science, 2015, 8(6):A187.wI4原创论文网_专业的研究生论文网站
[26]Mnih V, Kavukcuoglu K, Silver D, et al. Playing Atari with Deep Reinforcement Learning[J]. Computer Science, 2013.[11]Lample G, Chaplot D S. Playing FPS Games with Deep Reinforcement Learning[J]. 2016.wI4原创论文网_专业的研究生论文网站

上一篇:俄罗斯方块游戏的设计与实现
下一篇:关于网上书城的分析与实现

| 论文推荐

更多 更多论文
在线客服系统