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 Go game that can automatically handle capturing stones, determine the winner, and other functions.
Extra credit:

Timing function and timeout judgment.

Human vs. AI function (the AI does not compete with humans, only horizontally compares with other students' implemented AIs).

Assignment 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 can choose any programming language, the teacher actually wants 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). I didn't want to write something like JavaScript, so tkinter should be the only choice.
As for the other requirements, the timing function is an easy way to get extra points; automatic capturing of stones is a bit more complicated, but can still be completed in one night; the most annoying part is determining the winner, not to mention the confusion caused by various rules. Just the capturing of dead stones alone requires the use of machine learning. In the end, I couldn't make it fully automatic, so I manually captured the dead stones and automatically determined the winner.

Writing Process#

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

The program consists of four classes:

GoBasicAttributes: Used to record the attributes of the current Go board, including the size of the board, the size 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 Go board.
GoControl: Coordinates GoCore and GoBoard, and also handles the drawing of controls other than the Go board.

Originally, I wanted to decouple GoCore and GoBoard as much as possible, but as I continued writing, they became mixed together, and I didn't care anymore. They can influence each other, and I didn't prioritize maintainability since I only had a few days to write it, and I won't look at it again after submitting the assignment.

Writing the GUI was quite convenient. I could just open GitHub Copilot and write a comment to let it complete the code for me. But when it came to writing the logic, Copilot was just a waste of time, so I turned it off and wrote it faster on my own.

The first feature I implemented was automatic capturing of stones, which removes stones without liberties after a move is made. This feature only took me one night to complete. The knowledge involved mainly includes abstracting the rules of Go into logic that can be understood by computers, and using breadth-first search (BFS). BFS is used in every aspect of Go, as both stones and empty spaces are considered as connected groups, and it is necessary to traverse this connected graph using BFS. 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, which can be divided into two steps: capturing dead stones and counting territory. 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 the dead stones, each block of empty spaces will only be adjacent to stones of one color, making it easy to count territory.

After that, I mainly made some optimizations for the user experience and added a chess clock. However, I couldn't understand the rules for counting seconds, so I made a convenient package-based 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, it would definitely be quite stupid, so I named it Stupid. But in the end, although I still had several days before the deadline, I didn't continue working on it.

Results#

I think the final result is okay. I didn't bother beautifying the interface since I won't be using it anyway.

The entire project didn't involve any advanced algorithm techniques. The most difficult algorithm was probably BFS, but it still meets the requirement of using computers to solve real problems, so it is quite suitable for a computer introduction course.