资源下载地址:/download/sheziqiong/85819561
一、题目(二选一)
选题一:使用 Minimax 算法及 α-β 优化剪枝,实现可进行人机对弈的五子棋 AI 程序。
选题二:使用马尔科夫决策过程方法,训练迷宫寻路 AI 程序。
二、说明
2.1 选题一:人机对弈的五子棋 AI 程序
2.1.1 问题描述
实现可进行人机对弈的五子棋 AI 程序。在大小为 15×15 的棋盘上,黑子先行,轮流下于棋盘空点处,先把五枚或以上己棋相连成任何横纵斜方向为胜。
2.1.2 作业要求
搜索:采用 Minimax 算法及 α-β 剪枝的方法,实现每一步 AI 落子位置的搜索过程。
局面评估函数:对于五子棋来说,很难每一步都能返回胜负结果,需要设计评估函数,给出局面评估值,可参考资料:
张明亮, 吴俊, 李凡长. 五子棋机器博弈系统评估函数的设计[J].计算机应用, 32(07):1969-1972.
裴博文. 五子棋人工智能权重估值算法[J]. 电脑编程技巧与维护, (6):69-75.
五子棋估值算法,
代码框架:作业包中提供 C++ 的代码框架,包含部分数据结构及 UI 实现。补充实现其它功能(包括搜索、局面评估、胜负判断、落子合法性判断等),提交完整项目代码。框架代码可以修改。要求代码可读性良好,有必要的注释。www.biyezuopin.vip
2.1.3 提交要求
实验报告:至少包括算法描述、程序设计及重要实现、实验结果及评价、实验收获与体会等。
源代码:用 C++ 实现,可正常编译执行,实验结果能够复现。
可执行程序
使用说明
2.1.4 评分标准
实验报告:清晰简洁,重点突出,重点介绍搜索部分实现的策略及方法,使用提供的模板,中文撰写,导出为 pdf,长度不超过 6 页,此部分占本次作业总分的 30%。
报告至少应包括以下重点:
数据结构及变量设计说明
creatmoves、gameover 模块实现方法说明 searchmove 模块实现方法说明。(如用到 α-β 剪枝以外的优化方法,需要单独进行说明并进行优化前后效果对比)
实验结果,展示加入不同优化策略前后的运行效果对比
程序实现:此部分占本次作业总分的 70%,至少应实现以下内容
程序逻辑
createmoves 模块
gameover 模块
searchmove 模块
额外加分项:不超过本次作业总分的 10%,以下列出一些可以拓展的点供参考
加 入 散 列 表 优 化 方 法 , 避 免 重 复 搜 索 相 同 局 面
加 入 迭 代 加 深 方 法 , 优 化 初 试 搜 索 顺 序
使用 α-β 剪枝外其它优化方法加深搜索层数
完善程序功能,如加入悔棋、复盘功能等
2.2 选题二:迷宫寻路 AI
2.2.1 问题描述
给出任意大小规模的迷宫,包含入口、出口、障碍及陷阱等元素,使用马尔科夫决策过程,使程序经过多次迭代计算后找到从入口到出口的最优策略(Policy)。
示例:
AI 从蓝色的起点出发,找到一条到达红色终点的路,灰色格子为陷阱(走到陷阱立刻回到起点),黑色格子为障碍(障碍同边界相同,走到障碍或边界返回上一步所在位置)
AI 的动作包括向上、向下、向左、向右,其中向上有 1/5 概率向左上方移动一格,有 1/5 概率向右上方移动一格,有 3/5 概率向正上方移动一格,向下向左向右同理到达终点获得回报值 1,到达陷阱回报值-1。到达其它格子状态可自行设置回报值,如下图所示:
2.2.2 作业要求
问题描述中给出了一个迷宫地图中的基本元素和迷宫游戏规则,需自行完善迷宫地图,具体地图可自行设计,地图中包含的陷阱、障碍等元素也可自行设计,在提交的文档中要说明地图中不同元素的含义和功能运行程序可动态展示 AI 寻路的迭代计算过程,并展示地图中每个格子的状态值变化过程,如下所示,其中格子中的数字表示状态值:
N=1 时
N=5 时
N=10 时
2.2.3 提交要求
实验报告:至少包括算法描述、程序设计及重要实现、实验结果及评价、实验收获与体会等。
源代码:程序可采用 Java、C/C++、 C#或 python 实现,可正常编译执行,实验结果能够复现。
可执行程序
使用说明
2.2.4 评分标准
实验报告:实验报告要求清晰简洁,重点突出,重点介绍马尔科夫过程实现的策略方法,使用提供的模板,中文撰写,导出为 pdf,长度不超过 6 页,此部分占本次作业总分的 30%。报告至少应包以下重点:
数据结构及变量设计说明
地图元素设计说明、地图不同格子回报值设计说明
马尔科夫决策过程实现方法说明
实验结果展示及说明
程序实现:此部分占本次作业总分的 70%,至少应实现以下内容
地图设计、回报值设计及逻辑实现部分
马尔科夫决策过程实现部分
程序迭代结果可视化展示部分
额外加分项:不超过本次作业总分的 10%,以下列出一些可以拓展的点供参考
使用强化学习的方法学习动作选择概率,并对比强化学习方法(如:Q-Learning、
SARSA)与马尔科夫决策过程之间实现效果的异同
使用其它创新性方法优化搜索过程
资源下载地址:/download/sheziqiong/85819561