作业1: Bait游戏

Modified: 2018/03/09 14:53 by admin - Uncategorized
(Back to course page)

Edit

理解GVGAI框架

GVG-AI 框架是为了通用人工智能的研究开发的游戏框架,基于VGDL(视觉游戏描述语言),能够构成多种游戏。本次作业使用一种推箱子游戏“Bait”,下面详述。


编程语言为Java(如果你没有学习过Java语言,Java的语法跟C++非常接近,但更简单。Java的编译和运行需要安装 JDK
首先,下载本次作业程序包 gvgai-assignment1.zip (程序包中的代码有所调整)
并在你使用的开发环境中配置好相应的工程,如果配置正确,可以允许 Test.java 启动游戏并可以通过键盘操纵。你可以通过自己玩游戏来了解游戏规则。

Edit

关于Bait游戏

Bait游戏的描述文件在 gvgai-assignment1/examples/gridphysics 目录下
  • bait.txt 为游戏的配置文件
  • bait_lvl0.txt ~ bait_lvl4.txt 为游戏5个关卡的地图描述文件,根据配置文件中定义的符号来设置

下图解释了bait.txt文件的内容


从 bait.txt 文件可以看出游戏规则
  • 精灵要先拿到钥匙,然后走到目标
  • 如果精灵吃了蘑菇,那么额外加1分
  • 精灵不能掉进洞里,否则失败
  • 精灵可以推盒子吧洞填上,洞填上后就可以通过,并且每填一个洞有1分的奖励
  • 只能向前推一个盒子,不能推两个盒子,也不能把盒子推到墙、蘑菇上(盒子可以推到目标上再推开)
  • 箱子可以覆盖钥匙,一旦覆盖,必须推开箱子取得钥匙才能成功
  • 另外,游戏的时间为1000ticket,时间结束即失败

Edit

关于控制程序

在 controllers 目录下,已经有多个样例控制程序了,我们通过最简单的样例:“随机控制” controllers/sampleRandom/Agent.java 来了解基本的控制方法


从上图可以看出
  • act函数是控制程序的关键,需要在给定的时间内返回一个动作
  • stCopy是用来理解游戏变化的“仿真器”,当我们进行搜索时,需要在stCopy上“模拟”动作的执行,从而能够看到状态发生了什么变化



Edit

作业内容

程序包中 Assignment1.java 已经准备好运行本次作业的4个任务

Edit

任务 1

针对第一个关卡,实现深度优先搜索 controllers.DepthFirst.java:
在游戏一开始就使用深度优先搜索找到成功的路径通关,记录下路径,并在之后每一步按照路径执行动作。注意在搜索时避免回路,可使用StateObservation类的equalPosition方法判断状态是否相等。
由于搜索到通关路径所需时间较长,通过CompetitionParameters.ACTION_TIME来设置足够的时间来允许完成搜索。

Edit

任务 2

在任务 1 的基础上,实现深度受限的深度优先搜索 controllers.LimitedDepthFirst.java:
修改为每一步进行一次深度搜索,但这时不需要一定搜索到通关 ,而是搜索到一定的深度,再设计一个启发式函数判断局面好坏。
同时CompetitionParameters.ACTION_TIME设置较小,需要在设置时间内完成一次决策。
针对Bait这个特定的游戏,我们可以利用目标的位置和钥匙的位置构造启发式函数:
ArrayList[] fixedPositions = stateObs.getImmovablePositions();
ArrayList[] movingPositions = stateObs.getMovablePositions();
Vector2d goalpos = fixedPositions[1].get(0).position //目标的坐标
Vector2d keypos = movingPositions[0].get(0).position //钥匙的坐标
该游戏中坐标从 (0,0) 开始,50为一个单元,在第一关中目标的坐标为 (50,50),钥匙的坐标为 (100,200)。

Edit

任务 3

在任务2的基础上,将深度优先搜索换成A*算法 controllers.Astar.java:
并尝试在第二关、第三关中使用A*算法

Edit

任务 4

阅读 controllers.sampleMCTS.Agent.java 控制程序,并介绍其算法。

Edit

作业报告

本次作业需要提交报告和代码。对于以上4个任务,报告需分别详细介绍对代码的实现。 使用这个文档模版(点击下载) 撰写实验报告。

Edit

作业提交

作业报告 存储为PDF文件,用学号命名,例如151221001.pdf,并与的源码打包为 学号命名的.zip文件,例如 151221001.zip

上传到 ftp://lamda.nju.edu.cn/AI/assignment1/ (用户名: ai18, 密码: ai18)
(注意:该ftp不能替换文件,上传一次后,如果需要修改,请在文件名后加上版本号再上传,例如151221001-1.zip)

注意:作业严禁抄袭!

The end