Project 2: 五子棋AI

Due: 10.09（国庆节后第一天）

Pacman in a maze

本次实验中, 你将要实现一个基于搜索的五子棋AI, 并且能够在提供的环境中进行对弈.

本次作业所需的文件为：Lab2.zip

本次实验中包含以下几个文件:

lab2-stu/
├── gomoku.py  # 包含五子棋的环境
├── agent.py   # 所有五子棋AI的基类, 实现了一个随机下棋的算法
├── STU_ID.py  # 你需要创建的文件, 在其中实现你的算法
└── human.py   # 实现了一个由人类下棋的接口

实验环境

在 gomoku.py 中实现了一个五子棋的游戏逻辑, 实现了游戏胜利的判断, 棋盘(11×11)的维护等简单功能. 你实现的搜索算法的 make_move 方法会在这个文件中被调用, 返回下一步下棋的位置 (x, y).

注意：在本次实验中, 你不应该修改该文件中的内容, 除了替换游戏中使用的AI.

运行游戏环境

本次实验中的游戏环境在 gomoku.py 中, 运行方式:

python gomoku.py -m human # 这样可以和你实现的Agent对战

运行测试程序可以使用以下命令行参数:

  • method: 与默认搜索算法对战的算法. 这里需要写文件的名称, 比如 -m human 就会使用 human.py 中实现的算法与 gomoku.py 中设置的默认算法对战. 默认算法的修改方式在后文中会提到.
  • size: 棋盘的尺寸, 默认是11. 一般情况下不需要设置.

gomoku.py 中默认使用 Agent 作为AI, 在你实现好你的算法后, 只需要修改 gomoku.py 的 main 函数中的

def main():
    ...
    from agent import Agent as A1  # TODO: fill in the name of your file
    ...

修改为你实现的算法即可.

实现要求

在本次实验中, 你需要实现一个基于搜索的五子棋AI算法, 并且有以下要求:

  • 你需要实现一个叫做 Search 的类, 并在其中实现你的搜索算法
  • 你实现是 Search 类必须继承自 Agent 类(在 agent.py 中)
  • 你需要重写 Search 类的 make_move 方法, 其接受一个棋盘作为输入, 输出一个元组 (x, y) 代表下棋的位置.
  • 你的算法不应该调用除了 numpy 之外的任何库
  • 你的算法每一步搜索时间不应该长于一分钟
  • 不要做并行搜索(毕竟写并发代码挺麻烦的, 且并不是这门课的重点)

思路提示

五子棋AI的设计应该分为两部分, 搜索算法的设计以及评估函数的设计:

  • 五子棋本质是一个零和博弈游戏, 而五子棋AI则是一个决策树搜索问题. 显然, 遍历整个决策树不切实际的, 因此, 如何搜索, 搜索多深就是这次作业中同学们需要解决的核心问题.
  • 在搜索出某个局面时, 如何判断这个局面的价值是一个值得研究的问题. 同学们最直观的想法通常已经足够有效, 但也有一些更加复杂的评估函数值得去探索.

提交要求

你只需要创建 STU_ID.py 并在其中完成你的算法实现, 提交时也只需提交这个文件. 不要修改 gomoku.py 中的内容, 除了设置 gomoku.py 中的默认算法.

例如学号为240000001的同学只需要完成 240000001.py 并提交即可.

请各位同学将第二次实践作业上传至NJU_box_Project2, 命名为"学号.py".

Bonus: 本次作业提供一个额外的五子棋对战平台, 不强制提交. 该平台采用打擂台的方式计算排名, 最后前10名有适当加分. 该平台主要用途是娱乐, 不必太过认真, 加分也只有一点点啦~

学术诚信

我们会将你的代码与课堂上其他提交的代码进行逻辑查重. 如果你拷贝了别人的代码, 并做一些微小的修改, 我们会很容易发现, 请不要尝试. 我们相信你们会独立完成作业.