The process of creating a Go program

Introduction#

This is one of the assignments for my freshman computer introduction course. Last year, the seniors wrote a Gomoku program, but I don't know why it changed to Go this year. It seems that neither the teacher nor the teaching assistant knows how to play Go... They even added creating a Go AI as an extra credit question, which I think is quite unreasonable for first-year students.

Let's start with a link to the project...#

yy4382/StupidGo | GitHub

Assignment Requirements#

Please choose any programming language and design and implement a small Go game that can automatically handle capturing stones and determine the winner.
Extra credit:

Timing function and timeout judgment.

Human vs. AI function (the AI should only compete with other students' AIs, not humans).

Submission requirements: Provide the code and a description document. The document should mainly describe the design ideas and how to use your code (note: the document is an important criterion for grading).

My Evaluation:

Although we were allowed to choose any programming language, the teacher actually wanted us to use Python's tkinter. And we have only learned C++, and it seems that writing GUI programs in C++ is more difficult (I mean Qt, as seen in the C++ Qt project I wrote last semester, it was quite torturous), and it's not like we would write something like JavaScript, so tkinter should be the only choice.
As for the other requirements, the timing function is just a bonus point, easy to implement; automatic capturing stones is a bit more complicated, but still can be done in one night; the most annoying part is determining the winner, not to mention the confusion caused by various rules, just capturing dead stones alone actually requires machine learning: in the end, I couldn't make it fully automatic, so I manually captured dead stones and automatically determined the winner.

Writing Process#

I wrote a document describing the specific rules and implementation methods, which can be found in the readme of the GitHub repository.

The program consists of 4 classes:

GoBasicAttributes: Used to record the attributes of the current board, including the size of the board, the size of the board in pixels, the type of stone at a certain position on the board, and the previous states of the board, etc.
GoCore: The main logic processing class, where most of the core logic is implemented. It provides an API for AI in human vs. AI mode, although I didn't end up implementing the AI.
GoBoard: A tkinter.frame used to draw the board.
GoControl: Coordinates GoCore and GoBoard, and also handles the controls outside the board.

Originally, I wanted to decouple GoCore and GoBoard as much as possible, but as I was writing, they became mixed together and I didn't care anymore. They can influence each other, and I didn't pay attention to maintainability. After all, I only wrote it for a few days, and I won't look at it again after submitting the assignment. Who cares about maintainability?

Writing the GUI was quite convenient. For this kind of hierarchical structure, I just opened GitHub Copilot and wrote a comment, and it helped me complete the code. But when it came to writing the logic, Copilot was just a waste of time, so I turned it off and wrote the code faster.

The first feature I implemented was automatic capturing stones, which automatically removes stones without liberties after a move is made. This feature only took me one night to implement. The knowledge involved mainly includes abstracting the rules of Go into logic that computers can understand, and then using BFS. In fact, breadth-first search is involved in every aspect of Go, because both stones and empty spaces are represented by connected groups, and BFS is used to traverse these connected components. For the specific implementation, please refer to Implementation Details - StupidGo.

The second feature is determining the winner. This can be said to be the most complex feature in the entire project, and it took me several days to research. I chose the Chinese rules for scoring. It can be divided into two steps: capturing dead stones and counting the score. Here, dead stones do not refer to stones without liberties at the moment, but stones that will never form two eyes regardless of future moves. After searching for a while, I couldn't find any algorithm that I could grasp to determine dead stones, so I made a semi-automatic version: you can click on a dead stone, and it will automatically remove all the dead stones related to it. Usually, it only takes 2-3 clicks to remove all the dead stones. After capturing dead stones, each block of empty spaces will only be adjacent to stones of one color, making it easy to count the score.

After that, I mainly did some optimizations for the user experience and added a chess clock, but I couldn't understand the rules for counting seconds, so I just made a convenient package timing system.

As for why I named the project StupidGo, it was because I originally wanted to implement human vs. AI mode, and if I had to write the logic for the AI moves, it would definitely be stupid, so I called it Stupid. But in the end, although I still had several days before the deadline, I didn't continue working on it.

Result#

I think the final result is okay. Let's not worry about beautifying the interface, because I won't be using it anyway.

There is actually no need to use any advanced algorithm or technique in the entire project. The most difficult algorithm is probably BFS, but it still meets the requirement of using a computer to solve practical problems, so it is quite in line with the positioning of this computer introduction course.