作业1: 黑白棋游戏

Modified: 2016/03/04 12:07 by admin - Uncategorized
(Back to course page)

Edit

问题描述

黑白棋,又称反棋(Reversi)、奥赛罗棋(Othello)等,游戏使用围棋的棋盘棋子,在8*8的棋盘上,黑白双方分别落棋,翻动对方的棋子。具体的规则可见:http://www.soongsky.com/strategy/rule.php

点击这里下载一段开源的Othello人机对战源程序,该程序为Java语言编写(如果你没有学习过Java语言,Java的语法跟C++非常接近,但更简单。Java的编译和运行需要安装 JDK )。

NetBeans IDE开发环境为例,首先建立“Java应用”工程,将源代码拷入src目录,即可编译。

Othello Java程序包的构如下
+ othello
|- othello.tests
+ gamePlayer
|- gamePlayer.algorithms

othello包中的Othello.java是主类(即运行该文件来启动游戏),程序入口在该文件中的main函数。其中语句:
Othello frame = new Othello(0, 1000, 2);
包含了3个参数,第一个参数0表示人先手,改为1则电脑先手;第二个1000是在使用MTDDecider作为电脑算法时限定的电脑思考时间;第三个2表示搜索的最大深度。

gamePlayer包下定义了基础类Action(动作), State(棋盘状态),Game(游戏),Decider(决策算法)

gamePlayer.algorithms包下实现了两种搜索算法MiniMaxDecider.java,MTDDecider.java



Edit

作业内容

阅读Othello源代码,了解程序的总体框架,并完成以下任务:
  1. 阅读源代码MiniMaxDecider.java,理解并介绍MiniMax搜索的实现(与课本上分别实现Max和Min函数不同,程序中使用一个开关将两者合并为一个函数)
  2. 请修改MiniMaxDecider类,加入AlphaBeta剪枝,并且比较引入剪枝带来的速度变化(尝试不同的搜索最大深度)
  3. 请理解othello.OthelloState类中的heuristic函数,并尝试改进
  4. 请阅读并尽量理解MTDDecider类,介绍它与MiniMaxDecider类的异同(在Othello.java中,将294行注释掉,将295行去掉注释,即可换用MTDDecider算法)

Edit

作业报告

本次作业不需要提交源码,只需要提交报告。对于以上4个任务,报告需分别详细介绍对代码的理解、对代码做了哪些修改、对比测试的结果。 使用 这个文档模版(点击下载) 撰写实验报告。

Edit

作业提交

作业报告 存储为PDF文件,用学号命名,例如131221001.pdf

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

注意:作业严禁抄袭!

The end