Back
History
作业2: Bait游戏
([course_ai16|Back to course page]) ==理解GVGAI框架== GVG-AI 框架是为了通用人工智能的研究开发的游戏框架，基于VGDL（视觉游戏描述语言），能够构成多种游戏。本次作业使用一种推箱子游戏“Bait”，下面详述。<br/> <img src="http://lamda.nju.edu.cn/yuy/GetFile.aspx?File=course_ai16_hw2/baitgame.png" width="200px"/> 首先，下载本次作业程序包 [{UP}course_ai16_hw2/gvgai-assignment2.zip|gvgai-assignment2.zip] (程序包中的代码有所调整)</br> 并在你使用的开发环境中配置好相应的工程，如果配置正确，可以允许 Test.java 启动游戏并可以通过键盘操纵。你可以通过自己玩游戏来了解游戏规则。 ===关于Bait游戏=== Bait游戏的描述文件在 gvgai-assignment2/examples/gridphysics 目录下 * bait.txt 为游戏的配置文件 * bait_lvl0.txt ~ bait_lvl4.txt 为游戏5个关卡的地图描述文件，根据配置文件中定义的符号来设置 '''下图解释了bait.txt文件的内容'''<br/> <img src="http://lamda.nju.edu.cn/yuy/GetFile.aspx?File=course_ai16_hw2/bait.png" width="700px" style="border: 1px solid black"/> '''从 bait.txt 文件可以看出游戏规则''' * 精灵要先拿到钥匙，然后走到目标 * 如果精灵吃了蘑菇，那么额外加1分 * 精灵不能掉进洞里，否则失败 * 精灵可以推盒子吧洞填上，洞填上后就可以通过，并且每填一个洞有1分的奖励 * 只能向前推一个盒子，不能推两个盒子，也不能把盒子推到墙、蘑菇上（盒子可以推到目标上再推开） * 箱子可以覆盖钥匙，一旦覆盖，必须推开箱子取得钥匙才能成功 * 另外，<font color="blue">游戏的时间为1000ticket</font>，时间结束即失败 ===关于控制程序=== 在 controllers 目录下，已经有多个样例控制程序了，我们通过最简单的样例：“随机控制” controllers/sampleRandom/Agent.java 来了解基本的控制方法<br/> <img src="http://lamda.nju.edu.cn/yuy/GetFile.aspx?File=course_ai16_hw2/random.png" width="800px" style="border: 1px solid black"/> 从上图可以看出 * act函数是控制程序的关键，需要在给定的时间内返回一个动作 * stCopy是用来理解游戏变化的“仿真器”，当我们进行搜索时，需要在stCopy上“模拟”动作的执行，从而能够看到状态发生了什么变化 ==作业内容== 程序包中 Assignment2.java 已经准备好运行本次作业的4个任务 ===任务 1=== 针对第一个关卡，实现深度优先搜索 controllers.DepthFirst.java: <br/> 在游戏一开始就使用深度优先搜索找到成功的路径通关，记录下路径，并在之后每一步按照路径执行动作。注意在搜索时避免回路，可使用'''StateObservation类的equalPosition方法'''判断状态是否相等。<br/> 由于搜索到通关路径所需时间较长，通过CompetitionParameters.ACTION_TIME来设置足够的时间来允许完成搜索。 ===任务 2=== 在任务 1 的基础上，实现深度有限的深度有限搜索 controllers.LimitedDepthFirst.java: </br> 修改为每一步进行一次深度搜索，但这时不需要一定搜索到通关 ，而是搜索到一定的深度，再设计一个启发式函数判断局面好坏。<br/> 同时CompetitionParameters.ACTION_TIME设置较小，需要在设置时间内完成一次决策。<br/> 针对Bait这个特定的游戏，我们可以利用目标的位置和钥匙的位置构造启发式函数： {{{{<nowiki> ArrayList<Observation>[] fixedPositions = stateObs.getImmovablePositions(); ArrayList<Observation>[] movingPositions = stateObs.getMovablePositions(); Vector2d goalpos = fixedPositions[1].get(0).position //目标的坐标 Vector2d keypos = movingPositions[0].get(0).position //钥匙的坐标</nowiki> }}}} 该游戏中坐标从 (0,0) 开始，50为一个单元，在第一关中目标的坐标为 (50,50)，钥匙的坐标为 (100,200)。 ===任务 3=== 在任务2的基础上，将深度优先搜索改为A*算法 controllers.Astar.java:<br/> 并尝试在第二关、第三关中使用A*算法 ===任务 4=== 阅读 controllers.sampleMCTS.Agent.java 控制程序，并介绍其算法。 ==作业报告== 本次作业需要提交报告和代码。对于以上4个任务，报告需分别详细介绍对代码的实现。 使用 [{UP}course_ai15_hw1/template-2.doc|这个文档模版(点击下载)] 撰写实验报告。 ==作业提交== 将 <font color="blue">作业报告</font> 存储为PDF文件，用学号命名，例如131221001.pdf，并与的源码打包为 学号命名的.zip文件，例如 131221001.zip 上传到 {{ftp://lamda.nju.edu.cn/AI/assignment2/}} (用户名: ai16, 密码: ai16)<br/> (注意：该ftp不能替换文件，上传一次后，如果需要修改，请在文件名后加上版本号再上传，例如131221001-1.zip) 注意：<font color="red">作业严禁抄袭！</font>
The end