Python Miniproject: Making the Game of Go from Scratch in PyGame | by Thomas Hikaru Clark
- Nelly
- February 1, 2023
- Board Games
The traditional game of Go has been performed for hundreds of years. With extra board configurations than there are atoms within the universe, Go is a sport of nice complexity and abstraction that emerges from a set of straightforward guidelines. DeepMind’s AlphaGo program made headlines when it beat high Go skilled Lee Sedol in a match of 5 video games in 2016. After watching an important documentary concerning the AlphaGo-Lee match, I assumed it could be enjoyable to strive coding a fundamental Go sport from scratch in Python. Doing enjoyable, bite-size tasks like this was an enormous a part of my very own growth as a programmer, so I hope you take pleasure in following alongside and really feel impressed to sort out your personal tasks, too!
On this article, we are going to discover tips on how to create Go from scratch utilizing Python and PyGame. Alongside the way in which, we are going to see how we are able to use instruments from knowledge science to assist us code this sport extra simply. By the top of the article, you’ll perceive:
- Tips on how to arrange a fundamental sport GUI with PyGame
- Tips on how to use collections and itertools to jot down concise, elegant code
- Tips on how to use NumPy operators for quick matrix operations
- Tips on how to use the Networkx graph library to interrupt down advanced issues
Fast Overview of Go Guidelines
The principles of Go are literally fairly easy. Black and White take turns putting stones on a 19×19 board (different sizes are potential too, however that is the usual dimension). A set of stones that type a contiguous chain (related by gridlines) kinds a gaggle. If a stone or group of stones is totally surrounded by the opposite colour, then these video games are captured and faraway from the board. On the finish of the sport, the participant whose stones encompass extra territory wins. I’m deliberately glossing over some particulars right here, however that is the fundamental gist. Our aim is now to design a program that enables two gamers to put stones on the board whereas implementing the foundations of Go, reminiscent of forbidding unlawful strikes and implementing captures.
Design Course of
When engaged on a posh undertaking, it’s useful to interrupt the issue down into digestible chunks. I attempt to create applications which are encapsulated and modular, with totally different capabilities for dealing with the assorted sub-parts of an issue. Within the case of Go, I made a decision I would want capabilities to do the next:
- Draw the board utilizing PyGame
- Convert between the (x,y) coordinates of PyGame and the discrete board positions of the 19×19 grid
- Replace the sport state primarily based on consumer actions (e.g. mouse clicks)
- Examine if an tried transfer is legitimate
As a lot as potential, I attempt to separate the enter/output of the sport from the interior sport state. I create a Sport class which shops all knowledge a couple of given sport, such because the state of the board and the variety of captured stones or ‘prisoners’ for every participant. The Sport class has a draw() operate to deal with rendering the board state to a PyGame GUI, and has an replace() operate to test for consumer actions reminiscent of mouse clicks and key presses.
The Code
The GitHub repository beneath accommodates the total code for the Go sport. Notice that that is solely a fundamental, bare-bones implementation missing most of the options you could find in Go apps and web sites, however I selected to maintain the undertaking easy to concentrate on the necessities. You may check out the code after which proceed studying for my explanations of a number of the code highlights. Be at liberty to fork the code on GitHub, mess around with it, and go away any feedback or questions.
Making a Primary Sport with PyGame
PyGame is a Python library for creating fundamental GUI video games. It supplies help for drawing shapes to a display, monitoring mouse clicks and key presses, taking part in sounds, and different operations that you’d anticipate in a sport. After importing PyGame, you should use pygame.init() to initialize a PyGame GUI. Different helpful capabilities embody pygame.mouse.get_pos() to get the present mouse place, blit() to ship textual content to the display, and flip() to replace the display with new shapes. Please see the above code for examples of how these PyGame capabilities work in follow.
The Magic of NumPy Operations
The Go sport board is, as you possibly can most likely inform, a 2-dimensional matrix. The NumPy library has a whole lot of very handy capabilities for coping with arrays and matrices.
To generate evenly spaced gridlines, I used the np.linspace() and np.full() capabilities. The primary operate, np.linspace(), creates an inventory of evenly spaced values between a given begin and finish worth. In the meantime, np.full() creates an array of an identical values of a desired form. This enables me to shortly generate a set of begin and finish factors for the road segments the shape the Go board’s grid, which I then feed into the pygame.draw.line() operate.
One other extraordinarily helpful NumPy operate is the np.the place() operate, which returns indices in an array the place a sure situation is true. For instance, the road np.the place(self.board == 1) returns board positions storing the worth 1 (which within the conventions of my sport point out the presence of a black stone).
Itertools and Collections
I used itertools.product() to exchange nested for loops. For instance, to shortly create an inventory of all grid factors on the Go board (e.g. (0,0) by way of (18,18)), I can use itertools.product(vary(19), vary(19)).
In the meantime, I used collections.defaultdict() to create a rating counter that gracefully handles being incremented even when empty. The road self.prisoners = collections.defaultdict(int) creates an information construction just like a Python dictionary, besides that when a key’s to entry the dictionary for the primary time, it’s given a corresponding worth of 0. I like to make use of defaultdicts to make my code extra strong to KeyErrors with out having to jot down a bunch of particular edge case checks.
Figuring out Stone Teams Utilizing Graph Principle
A elementary unit of Go gameplay is the stone group. A gaggle of stones lives or dies collectively. When a gaggle of stones is totally surrounded, all might be captured directly. However so long as one stone in a gaggle has at the least a single liberty (unoccupied neighboring board area), the complete group remains to be alive.
For the needs of our sport program, we now have the next mathematical downside: Given a N x N matrix populated with three totally different values (0 for empty, 1 for black stone, 2 for white stone), produce an inventory of stone teams of every colour, the place every stone group is an inventory of stones such that every one stones within the group type a contiguous block. This description could also be a bit onerous to know, so please check with the picture beneath, and see in case you can work out what number of stone teams of every colour there are.
The proper reply is that there are 6 black stone teams and a couple of white stone teams. Don’t be misled by the three black stones positioned in a diagonal orientation — they aren’t contiguous with one another as a result of they aren’t instantly related by grid strains, so every stone is its personal stone group. I shortly realized that writing a program to take a sport board and routinely discover all of the stone teams was not trivial, so I started to marvel if the issue might be decreased to an present downside for which an algorithm already exists.
I discovered that utilizing graph idea and the Networkx graph library led to a surprisingly elegant resolution to stone-group counting downside. Let’s say we need to discover all black stone teams. The fundamental instinct is that we begin with a “grid graph”, which appears to be like precisely just like the grid of the Go board: every vertex related to the vertices above, beneath, to the left, and to the proper of it. We then take away all vertices which would not have a black stone on them. This leaves us with a graph during which related parts correspond on to stone teams! We are able to merely use the built-in connected_components() operate in Networkx to return the reply! Utilizing this operate, I may now implement the code for detecting captures within the sport. This implies the sport will routinely detect when a stone group is surrounded, will take away them from the board, and increment the variety of prisoners accordingly.
Subsequent Steps
Severe Go gamers who tried out the code might have observed that the sport isn’t 100% full. The sport doesn’t implement the rule of Ko, which doesn’t enable gamers to repeat a earlier sport place. It might even be good to have computerized rating counting on the finish of a sport, in addition to comfort options like “undo”. Lastly (and it is a massive problem), it could be nice to have an AI that may play in opposition to a solo human participant, since proper now the sport requires having two human gamers.
I hope you loved studying about my expertise constructing a Go sport in Python, and that you simply discovered a number of new issues alongside the way in which. You probably have every other solutions or suggestions, go away a remark beneath!
References
[1] PyGame Documentation: https://www.pygame.org/docs/
[2] Networkx Documentation: https://networkx.org/documentation/stable/reference/index.html
[3] Try this wonderful documentary on AlphaGo’s match in opposition to Lee Sedol:
Related Posts
