记一个围棋程序的编写过程

2023-06-30

这是我大一计算机导论课的大作业之一,去年的学长还是写的五子棋,不知道为什么今年开始变成围棋了,而且无论老师还是助教好像都和我一样是不会下围棋的。。。甚至把写出围棋 AI 作为附加题加分项,我觉得对于大一学生是挺离谱的。

先贴个项目的链接吧。。。

yy4382/StupidGo | GitHub

作业要求

请任意选择一种编程语言, 设计并实现一个围棋小游戏, 要求能够自动实现提子, 判定胜负等功能。 附加题:

  1. 计时功能, 超时判负功能。
  2. 人机对战功能(机器人不和人比, 仅与其他同学实现的机器人之间横向比较。)

作业提交要求: 最后给出代码和描述文档, 文档主要描述设计思路、 以及你的代码要如何使用(注意: 文档是判定成绩的重要指标)

我的评价:

  1. 虽然要求是任选一种编程语言,但是其实课堂上老师是希望我们用 Python 的 tkinter 来实现的。而且我们其实只学过 C++,而 C++ 的 GUI 程序似乎比较难写(我指 Qt,可见我上个学期写的 这个 C++ Qt 项目,当时写的可折磨了),又不至于去写 js 之类的,所以 tkinter 应该是唯一的选择了。
  2. 其他的要求,计时功能就是送分功能,轻松解决;自动提子略复杂,但是依旧可以一个晚上写完;最烦的是判定胜负,且不谈各种规则在这方面的混乱,光是提死子这一点实际上就要用到机器学习:最后还是没能做成全自动的,手动提死子 + 自动判胜负。

编写过程

具体使用的规则和实现方式我写了文档,在 GitHub 仓库的 readme 里有链接。

整个程序有 4 个类:

  1. GoBasicAttributes:用来记录当前棋盘的属性,包括棋盘是几乘几的,棋盘的(像素)大小,棋盘上某个地方是什么子,棋盘曾经的状态等等。
  2. GoCore:最主要的逻辑处理类,绝大部分的核心逻辑是在这个类里完成的。预留了给人机对战的 ai 提供的 api,虽然最终没写 ai。
  3. GoBoard:是一个 tkinter.frame,画棋盘用的。
  4. GoControl:统筹 GoCoreGoBoard,同时画除了棋盘之外的控件。

原本是希望可以做到 GoCoreGoBoard 尽量解耦的,但是后来写着写着就又混一起了,然后摆烂不管了,互相影响就互相影响吧,反正我就写几天,作业交了我也不会再去看了,要什么可维护性(

写 GUI 的时候其实很方便,这种层次的东西直接打开 GitHub Copilot 写个注释它就帮你写完了,但是写逻辑的时候 Copilot 就是纯纯浪费时间的智障,直接关了写的更快。

我第一个实现的功能是自动提子,就是在下子之后自动去除无气的棋子。这个功能只花了我一个晚上,涉及的知识主要是学会把围棋规则抽象为计算机可以理解的逻辑,其次是 BFS:其实广度优先搜索涉及到了围棋的每一个逻辑中,因为无论是棋子还是空白,都是以连接在一起的块为单位的,需要 BFS 把这个连通图遍历一下。具体实现见 具体实现 - StupidGo

第二个功能是判定胜负。这可以说是整个项目中最复杂的功能,花了我好几天研究。这玩意我选用的是中国规则的数子法,其实分为两步:提死子和数子。此处的死子不是指此时没有气的子,而是无论之后如何下都一定不会形成两眼的子。搜了半天,没找到什么我可以掌握的算法可以判断死子,所以干脆做了一个半自动版的:可以点一个死子,会自动把与它相关的死子都提掉,一般点 2-3 次就提完了。提完死子之后,每一个空白点组成的块只会和一种颜色的棋子接壤,这样数子就很好做了。

之后就主要做了一些体验上的优化,同时把棋钟加上了,但是数秒制我规则都没看懂,最后还是搞了个方便的包干计时制。

至于为什么我把项目起名为 StupidGo,是因为原本想做人机对战的,如果要写机器落子逻辑的话一定很傻,所以叫 Stupid。但是最后虽然我写完的时候离 deadline 还有好几天,但是直接开摆不写了。

效果

效果图

最终的效果我觉得还行,美化界面的事就不管了吧,反正我又不用(

整个其实没有用到什么高深的算法技巧,最难的算法可能也就是 BFS 了,但是对于把实际问题用计算机解决的要求还是有一点的,所以还挺符合计算机导论这门课的定位?(

评论
  • 按正序
  • 按倒序
  • 按热度
Powered by Waline v3.1.3