6
\$\begingroup\$

The Game

Go or weiqi is an amazingly simple yet complex board game. This game is typically played on a 19x19 grid, and pieces are played on the intersections of lines. Pieces are removed when they are surrounded by opposing stones on all orthogonally adjacent points, in which case the stone or group is captured and removed from the board.

The game ends when both players pass a turn, such as beliving that nothing can be accomplished from further play.

Score is calculated by adding the amount of your pieces on the board and the amount of empty spaces on the board completely encircled and surrounded by your pieces ONLY.

An complete description of the game can be found here: https://en.wikipedia.org/wiki/Go_(game)

My attempt

My code is an attempt to clone this game, trying to keep things accurate, playable, and enjoyable.

An algorithm for detecting pieces that should be removed has been inspired by FirefoxMetzger.

Further notes

Komi, which can be found at the bottom of my code, is well described here: https://en.wikipedia.org/wiki/Go_(game)#Komi. To summarize it, komi is added to white (black goes first) to compensate for the disadvantage of going second. Also, komi is sometimes also a decimal number (such as 4.5) to prevent any ties.

Some questions

Would like speed improvements, removal of unnessacary code, and code style improvements.

I have implemented a function to scale up the fontsize of the widgets as the window grows. However, it is extremely laggy (maybe because of the 19x19 board?) and have disabled it. If anybody has any suggestions for this, I would greatly appreciate it.

Additionally, right now, passing a turn is only avaliable through Command+P or the menubar. I would like a button below (have tried using frames) but when I use the frame, scaling up and keeping the widgets square is not working well.

Lastly, I would like to improve on my question-asking skills. Please criticise me in all ways,

The code

import tkinter as tk
import tkinter.messagebox as msg

import numpy as np
from pprint import pprint

class Main:
    def __init__(self, komi=4.5, theme=['gray', 'dark gray']):
        self.komi = komi

        self.theme = theme[:-1]
        self.dimensions = 19

        self.window = tk.Tk()
        self.window.aspect(1, 1, 1, 1)
        self.window.resizable(True, True)
        self.window.geometry('700x700')
        self.window.config(bg=theme[-1])
        self.window.title('Go Chess | It\'s Black\'s turn!') 

        #self.window.bind('<Configure>', self.windowResized)
        self.window.bind('<Meta_L>p', self.passMove)

        self.board_array = np.array([[_ for _ in range(self.dimensions)] for _ in range(self.dimensions)], dtype=object)

        self.move = -1
        self.white_move = False
        self.passed_in_a_row = 0
        self.gameover = False

    def run(self):   
        for rows in range(self.dimensions):
            tk.Grid.rowconfigure(self.window, rows, weight=1)
            tk.Grid.columnconfigure(self.window, rows, weight=1)

        self.window.protocol('WM_DELETE_WINDOW', self.onClosing)
        self.setupMenus()
        self.createGrid()
        #self.window.after(250, self.windowResized)
        self.window.mainloop()
    
    def showAbout(self):
        text = '\nGo Chess (Chinese Chess)\nCloned by Colin Ding\n\nAlgorithimic improvements by Sebastian Wallkötter\n'
        msg.showinfo(title='Go Chess', message=text)

    def showHowToPlay(self):
        text = '\nThis is Go, a variant of Chess originating from China.\nTo play, place a piece on any spot.\n\nPlayers can place pieces on any spot, except spots\
which have no liberties (explained below).\n\nA liberty is a spot next to a piece, including left, right, up and down. Diagonals do not count.\nWhen a \
piece has no empty liberties, it is captured and removed from the board.\n\nHowever, if a piece\'s liberties include another piece of a same color, this formes a formation.\n\n\
A formation is a group of pieces all sharing sides. This formation cannot be captured unless surrounded entirely.\n\nThe game ends when both players pass a turn. (TO PASS: cmd+p)\n\n\
A good guide is avalible here: https://en.wikipedia.org/wiki/Go_(game)\n'
        
        msg.showinfo(title='Go Chess', message=text)

    def setupMenus(self):
        def donothing():
            return

        menubar = tk.Menu(self.window)
        filemenu = tk.Menu(menubar, tearoff=0)
        filemenu.add_command(label="New", command=donothing, accelerator='Command-n', state=tk.DISABLED)
        filemenu.add_command(label="Open", command=donothing, accelerator='Command-o', state=tk.DISABLED)
        filemenu.add_command(label="Save", command=donothing, accelerator='Command-s', state=tk.DISABLED)
        filemenu.add_command(label="Save as...", command=donothing, accelerator='command-shift-s', state=tk.DISABLED)
        filemenu.add_command(label="Close", command=self.window.destroy, accelerator='cmd-w')

        filemenu.add_separator()

        filemenu.add_command(label="Exit", command=self.window.destroy, accelerator='cmd-q')
        menubar.add_cascade(label="File", menu=filemenu)
        editmenu = tk.Menu(menubar, tearoff=0)
        editmenu.add_command(label="Undo", command=donothing, accelerator='command-z', state=tk.DISABLED) #add undo commmand

        editmenu.add_separator()

        editmenu.add_command(label="Cut", command=donothing, accelerator='command-x', state=tk.DISABLED)
        editmenu.add_command(label="Copy", command=donothing, accelerator='command-c', state=tk.DISABLED)
        editmenu.add_command(label="Paste", command=donothing, accelerator='command-v', state=tk.DISABLED)
        editmenu.add_command(label="Select All", command=donothing, accelerator='command-a', state=tk.DISABLED)
        editmenu.add_command(label="Delete", command=donothing, accelerator='Delete', state=tk.DISABLED)

        menubar.add_cascade(label="Edit", menu=editmenu)

        viewmenu = tk.Menu(menubar, tearoff=0)

        menubar.add_cascade(label='View', menu=viewmenu)

        gamemenu = tk.Menu(menubar, tearoff=0)
        gamemenu.add_command(label="Pass", command=self.passMove, accelerator='command-p')
        
        menubar.add_cascade(label='Game', menu=gamemenu)

        helpmenu = tk.Menu(menubar, tearoff=0)
        helpmenu.add_command(label="Help Index", command=donothing, state=tk.DISABLED)
        helpmenu.add_command(label='How To Play', command=self.showHowToPlay)
        helpmenu.add_command(label="About...", command=self.showAbout)
        menubar.add_cascade(label="Help", menu=helpmenu)

        self.window.config(menu=menubar)
    
    def findPiecesOnBoard(self):
        white_count = 0
        black_count = 0

        for row in self.board_array:
            for item in row:
                text = item.cget('text')
                if '*' not in text:
                    continue
                color = item.cget('fg')

                if color == 'white':
                    white_count += 1
                else:
                    black_count += 1

        return (white_count, black_count)

    def calculateSurroundedSpots(self):
        white_count = 0
        black_count = 0
        
        self.empty_groups = []
        self.empty_counts = []
        self.empty_colors = []

        self.visited = []        

        for y, row in enumerate(self.board_array):
            for x, widget in enumerate(row):
                if '*' in widget.cget('text'):
                    continue
                
                self.findEmptyLocations(y, x)

        for index in range(len(self.empty_colors)):
            empty_count = self.empty_counts[index]
            empty_colors = self.empty_colors[index]

            if 'black' not in empty_colors and 'white' in empty_colors:
                white_count += empty_count
            if 'white' not in empty_colors and 'black' in empty_colors:
                black_count += empty_count
        
        return (white_count, black_count)

    def getNonEmptyColorsOfNeighbors(self, y, x):
        colors = []

        neighbors = self.getNeighbors(y, x, (19, 19))
        for location in neighbors:
            widget = self.board_array[location[0]][location[1]]
            if '*' not in widget.cget('text'):
                continue
            colors.append(widget.cget('fg'))
        
        return colors

    def findEmptyLocations(self, y, x, adding=False):
        if not adding:
            self.empty_groups.append([])
            self.empty_counts.append(0)
            self.empty_colors.append([])

        neighbors = self.getNeighbors(y, x, (19, 19))
        neighbors.append((y, x))

        for location in neighbors:
            widget = self.board_array[location[0]][location[1]]
        
            if '*' in widget.cget('text') or widget in self.visited:
                continue

            self.visited.append(widget)
            self.empty_groups[-1].append(location)
            self.empty_counts[-1] += 1
            self.empty_colors[-1] += self.getNonEmptyColorsOfNeighbors(y, x)

            self.findEmptyLocations(location[0], location[1], adding=True)

    def calculateWhoWon(self):
        white_score = self.komi
        black_score = 0

        white_on_board, black_on_board = self.findPiecesOnBoard()
        white_surrounded, black_surrounded = self.calculateSurroundedSpots()

        white_score += white_on_board
        black_score += black_on_board

        white_score += white_surrounded
        black_score += black_surrounded
        
        print()
        print('ENDING SCORES:')
        print(f'{white_surrounded=}, {black_surrounded=}')
        print(f'{white_on_board=}, {black_on_board=}')
        print(f'{white_score=}, {black_score=}')
        print()

        if white_score > black_score:
            return 'White'
        else:
            return 'Black'

    def gameOver(self):
        person_won = self.calculateWhoWon()
        won_string = f'Go Chess | {person_won} won!'

        self.window.title(won_string)
        
        self.window.unbind_all('<Button-1>')
        for child in self.window.winfo_children():
            child.unbind('<Button-1>')

        self.gameover = True
        return
    
    def passMove(self, event=None):
        self.passed_in_a_row += 1
        if self.passed_in_a_row == 2:
            self.gameOver()
            return

        self.move += 1
        self.white_move = True if not self.white_move else False

        person = 'Black' if self.move % 2 else 'White'
        self.window.title(f'Go Chess | It\'s {person}\'s turn!')

    def handleClick(self, event=None):
        if self.gameover:
            return

        self.passed_in_a_row = 0
        location = [0, 0]

        done = False
        for row_index, row in enumerate(self.board_array):
            for item_index, item in enumerate(row):
                if item == event.widget:
                    location = [row_index, item_index]
                    done = True
                    break
                if done:
                    break

        if event.widget.cget('text') != '   ':
            return
        
        if not self.move % 2:
            fg = 'white'
        else:
            fg = 'black'

        location.reverse()
        event.widget.config(text=' * ', fg=fg)

        self.move += 1
        self.capturePieces(location[0], location[1])

        if '*' not in self.board_array[location[1]][location[0]].cget('text'):
            self.move -= 1
            self.white_move = True if not self.white_move else False
            return
        
        person = 'Black' if self.move % 2 else 'White'
        self.window.title(f'Go Chess | It\'s {person}\'s turn!')

    def windowResized(self, event=None):
        if not event:
            for widget in self.window.winfo_children():
                widget.config(font = ('Courier', 18))
            return

        for widget in self.window.winfo_children():
            widget.config(font = ('Courier', int((event.width/700)*18)))

    def onClosing(self):
        if not self.gameover:
            self.window.destroy()
            return

        if not msg.askyesno(title='Go Chess', message='Play again?'):
            self.window.destroy()
        else:
            app = Main(theme=self.theme)
            self.window.after(100, app.run)
            self.window.destroy()        
            
    def createGrid(self):
        colors = self.theme
        index = 0
        
        for row in range(self.dimensions):
            for col in range(self.dimensions):
                button_widget = tk.Label(self.window, text='   ', font=('Courier', 18), bg = colors[index % 2], fg = 'blue')
                button_widget.bind('<Button-1>', self.handleClick)
                button_widget.grid(row=row, column=col, padx=2, pady=2, sticky='nsew')
                self.board_array[row][col] = button_widget
                    
                index += 1

    def testGroup(self, board, opponent_board, y, x, current_group):
        """ Assume the current group is captured. Find it via flood fill
        and if an empty neighboor is encountered, break (group is alive).

        board - 19x19 array of player's stones
        opponent_board - 19x19 array of opponent's stones
        x,y - position to test
        current_group - tested stones in player's color

        """

        pos = (y,x)

        if current_group[pos]:
            # already tested stones are no liberties
            return False

        if opponent_board[pos]:
            current_group[pos] = True
            neighbors = self.getNeighbors(y,x,board.shape)

            for yn, xn in neighbors:
                has_liberties = self.testGroup(board, opponent_board, yn, xn, current_group)
                if has_liberties:
                    return True
            return False

        return not board[pos]

    def floodfill(self, liberties, y, x):
        """
        flood fill a region that is now known to have liberties. 1.0 signals a liberty, 0.0 signals
        undecided and -1.0 a known non-liberty (black stone)
        liberties is an np.array of currently known liberties and non-liberties
        """
        
        #"hidden" stop clause - not reinvoking for "liberty" or "non-liberty", only for "unknown".
        if not liberties[y][x]:
            liberties[y][x] = 1.0 
            if y > 0:
                self.floodfill(liberties, y-1, x)
            if y < liberties.shape[0] - 1:
                self.floodfill(liberties, y+1, x)
            if x > 0:
                self.floodfill(liberties, y, x-1)
            if x < liberties.shape[1] - 1:
                self.floodfill(liberties, y, x+1)

    def fastCapturePieces(self, black_board_, white_board_, turn_white, y,x):
        """Remove all pieces from the board that have no liberties.
        black_board is a 19x19 np.array with value 1.0 if a black stone is
        present and 0.0 otherwise.

        white_board is a 19x19 np.array similar to black_board.

        active_player - the player that made a move
        (x,y) - position of the move

        """

        black_board, white_board = black_board_.copy(), white_board_.copy()

        # only test neighbors of current move (other's will have unchanged
        # liberties)
        neighbors = self.getNeighbors(y, x, black_board.shape)

        board = white_board if turn_white else black_board
        opponent_board = black_board if turn_white else white_board

        # to test suicidal moves
        original_pos = (y, x)
        original_pos = original_pos[::-1]

        # testing suicides

        current_group = np.zeros((19,19), dtype=bool)
        has_liberties = self.testGroup(opponent_board, board, *original_pos, current_group)
        if not has_liberties:
            board[current_group] = False
            # output
            out_board = [[i for i in range(19)] for v in range(19)]
            for i in range(19):
                for v in range(19):
                    if white_board[i][v]:
                        out_board[i][v] = 1
                    elif black_board[i][v]:
                        out_board[i][v] = -1
                    else:
                        out_board[i][v] = 0

            return out_board

        # only test adjacent stones in opponent's color
        for pos in neighbors:
            pos = pos[::-1]

            if not opponent_board[pos]:
                continue

            current_group = np.zeros((19,19), dtype=bool)
            has_liberties = self.testGroup(board, opponent_board, *pos, current_group)

            if not has_liberties:

                opponent_board[current_group] = False

        # output
        out_board = [[i for i in range(19)] for v in range(19)]
        for i in range(19):
            for v in range(19):
                if white_board[i][v]:
                    out_board[i][v] = 1
                elif black_board[i][v]:
                    out_board[i][v] = -1
                else:
                    out_board[i][v] = 0

        return out_board

    def getNeighbors(self, y, x, board_shape):
        neighbors = list()

        if y > 0:
            neighbors.append((y-1,x))
        if y < board_shape[0] - 1:
            neighbors.append((y+1,x))
        if x > 0:
            neighbors.append((y,x-1))
        if x < board_shape[1] - 1:
            neighbors.append((y,x+1))

        return neighbors

    def capturePieces(self, y, x):
        white_board = np.array([[1.0 if item.cget('fg') == 'white' and '*' in item.cget('text') else 0.0 for item in row] for row in self.board_array], dtype=int)
        black_board = np.array([[1.0 if item.cget('fg') == 'black' and '*' in item.cget('text') else 0.0 for item in row] for row in self.board_array], dtype=int)

        white_move = self.white_move
        self.white_move = True if not self.white_move else False

        resulting_board = self.fastCapturePieces(black_board, white_board, white_move, y, x)

        for index1, row in enumerate(resulting_board):
            for index2, item in enumerate(row):

                text = ' * ' if item != 0 else '   '
                fg = 'white' if item == 1 else 'black'

                self.board_array[index1][index2].config(text=text, fg=fg)  



if __name__ == '__main__':
    themes = \
           {
               'theme1': ['gray', 'dark gray', 'black'],
               'theme2': ['blue', 'red', 'yellow'],
               'theme3': ['dark yellow', 'dark yellow', 'black']
            }
    
    app = Main(komi=2.5, theme=themes['theme1'])
    app.run()
\$\endgroup\$
4
  • \$\begingroup\$ code improvements? use 80 or 120 length lines to start. and don't use tkinter for non-trivial applications. \$\endgroup\$
    – qwr
    Aug 15, 2022 at 20:10
  • \$\begingroup\$ my experience is that tkinter is ancient and has some weird behavior with what you mention (widgets). but I acknowledge rewriting in like pyQt is a huge task. \$\endgroup\$
    – qwr
    Aug 15, 2022 at 21:27
  • \$\begingroup\$ So you would recommend pyQt for a GUI alternative? I am considering learning a newer GUI library. \$\endgroup\$
    – cold10
    Aug 15, 2022 at 21:29
  • 1
    \$\begingroup\$ I'm also biased because I think tkinter is really dated and ugly looking, and the code patterns are a little dated. So if you want a new GUI library that will scale up to more complex tasks, pyQt would be the way to go. \$\endgroup\$
    – qwr
    Aug 15, 2022 at 21:37

1 Answer 1

2
\$\begingroup\$

Wow, nice project!


... and code style improvements.

Here's some trivial effort that improves technical communication with collaborators. After a pair of pip installs, run

$ isort . ; black -S .

review the diffs, and commit.

Consider asking your IDE to do some rename refactors. PEP-8 asks for identifiers like def show_how_to_play, even if libraries like Tk use other conventions. No biggie, it's just a python culture thing. I do thank you for correctly spelling things like class Main.


    def __init__(self, komi=4.5, theme=['gray', 'dark gray']):

Komi is self descriptive. But please spell out the meaning of theme in a """docstring""".

Consider doing an assert len(theme) == 3. Or 2. The usage is inconsistent. Or document the current usage. Consider breaking out three kw parameters for it. Or bury it in a small class Theme, perhaps a dataclass,

BTW, pythonic code usually prefers a tuple for situations where number of elements is constant and position affects meaning -- think of it like an immutable C struct. In contrast, prefer a list for arbitrary number of elements which are all "same kind of thing".


small spelling nit:

        self.dimensions = 19

Maybe not plural? Yeah, yeah, it's a square, I get it, whatever.


        self.window = tk.Tk()

I am slightly sad to see this in the ctor. That is, we can only instantiate if we have a display canvas.

That seems inconvenient for writing tiny unit tests that don't need such a canvas. I am suggesting we might assign self.window = None here, and then caller can invoke a "gimme a canvas!" method if desired.


In showHowToPlay, consider using """ triple quote notation for long string constants.


        filemenu.add_command(label="New", command=donothing, accelerator='Command-n', state=tk.DISABLED)

Hmmm, I guess I'm slightly surprised the Tk bindings won't accept command=None, or let you omit it.

Or perhaps the bindings allow that, and you invented the donothing method as a convenient place for debugging print() statements. If so, and you choose to retain it, then mentioning the motivation in a """docstring""" would be appropriate.

You might find it convenient to define a little

disabled = dict(command=donothing, state=tk.DISABLED)

dictionary, and use it with ... , accelerator='command-x', **disabled)


The findPiecesOnBoard identifier is literally true. But consider using a name that mentions "counts", since that's what we return.


        self.empty_groups = []
        self.empty_counts = []
        self.empty_colors = []

Style objection: Please initialize these in the __init__ ctor, even if it is just to assign None to them. That way we have a directory of object attributes in one convenient spot, rather than having surprises like this scattered around the codebase.

Maybe we need e.g. empty_colors as an object attribute. But maybe it would make sense to define an object which calculateSurroundedSpots and findEmptyLocations use to communicate with each other? I'm just keeping an eye on coupling, is all.


I wonder if iterating through widgets is on the slow side, and you might prefer to make a numpy array the "source of truth", occasionally copying from it out to the canvas as needed. We read cell locations much much more often than we alter them, so for speed purposes we'd want to focus on reading.

(And cProfile output should be reviewed before attempting any such refactors, so we know where the cycles actually get consumed.)


While the 'black' / 'white' thing works fine, consider using Enum. Then some future maintainer will never have to wonder if 'White' works the same.

Also, the business of asking "is black present and white absent?" is a little odd. Perhaps the representation could be cleaned up a bit.


        neighbors = self.getNeighbors(y, x, (19, 19))

Hey, wait a minute! Didn't we define self.dimensions for exactly that purpose?

        for location in neighbors:
            widget = self.board_array[location[0]][location[1]]

The 0 / 1 subscripts are inconvenient. Prefer tuple unpack:

        for y, x in neighbors:
            widget = self.board_array[y][x]

        if white_score > black_score:

I understand why we don't even consider equality -- because we expect a 0.5 offet in komi. But the codebase never verified that, which seems Bad.

Recommend you code a "tied" clause, or you verify that ties are impossible.


    def gameOver(self):
        ...
        self.gameover = True
        return

Those are ill-chosen identifiers. Yes, they are distinct. No, I would not expect humans to always interact correctly with them. Maybe throw a verb into the method name?

Please delete the superfluous return, as we are just falling off the end of the method that was evaluated for side effects. We only write that for an early exit, as seen e.g. in the middle of passMove().

Is there maybe an opportunity to define a @property, obviating the need for maintenance of a separate variable?


    def handleClick(self, event=None):

We unconditionally dereference event attributes in several places. It is definitely not optional, so don't write that in the signature.

It is curious that we generate location backwards, and subsequently .reverse() it.

                    done = True
                    break
                if done:
                    break

That's just too ugly. Let's clean it up. Define a _get_location() helper which can return location the moment it's found.

Any chance we could just tack on a location to each widget? Then instead of a search we'd have a simple dereference.

        if not self.move % 2:
            fg = 'white'
        else:
            fg = 'black'

Nit: that seems gratuitously complicated, though I'm sure there was some "first player" motivation that went into it. Prefer to examine modulo without a not, and swap the clauses.

Consider defining black_white = ['black', 'white'] and then we'd have fg = black_white[self.move % 2]. Recycle it a few lines further down when assigning person.

Consider renaming it to move_num -- in another method I may have thought that move would reference a location.

        self.capturePieces(location[0], location[1])

Prefer

        self.capturePieces(*location)
            self.white_move = True if not self.white_move else False

Argghh, no! Just assign ... = not self.white_move.

Also, that decrement is making me nervous. I guess we just undid a move? But we unconditionally zeroed passed_in_a_row. Should we undo that, too?


During a resize the int((event.width/700)*18) expression warrants a # comment or """explanation""", perhaps even a tiny named helper function.

Also, the parentheses are kind of crazy -- please delete the redundant pair. I started to read it as "oh, we're multiplying an int by eighteen", and then realized the author was trying to trick me.


            self.window.after(100, app.run)

That magic number 100 I think just means "soon". I don't think it is about human psychology or perception. Consider changing it to 1, or defining a MANIFEST_CONSTANT.


In the createGrid expression colors[index % 2], consider using colors[row * col % 2] and dispensing with the index temp var.


I feel this is a helpful comment. But please fix up its grammar.

            # already tested stones are no liberties

I am reading the flood fill docstring.

        liberties is an np.array of currently known liberties and non-liberties

Very nice. But consider pushing the type annotation (numpy array) up into the signature instead.

In the text "a known non-liberty (black stone)", I found the trailing parenthetical confusing. Is that remark maybe valid from just one player's perspective?

            liberties[y][x] = 1.0 

That has a very specific meaning, which the docstring helpfully told us about. Instead of assigning 1.0, maybe assign a MANIFEST_CONSTANT or even an Enum?

Similarly, instead of not liberties[y][x] we might test for equality with UNDECIDED.


    def fastCapturePieces(self, black_board_, white_board_, turn_white, y,x):

I don't understand what's going on with the trailing _ underscore on those board identifiers. Usually we only do that when we're trying to avoid shadowing a builtin, e.g. id_, dir_, max_, that sort of thing.

        black_board, white_board = black_board_.copy(), white_board_.copy()

Oh. There's nothing wrong with using same identifier. It's not like it can mess up caller or anything. Revise the signature and then prefer

        black_board, white_board = black_board.copy(), white_board.copy()
        board = white_board if turn_white else black_board

I have seen several distinct idioms for this common concept. Recommend you pick one and stick with it. Also, consider using a list of two boards and then asking for the 0th or 1st board.


getNeighbors is lovely. It returns a container, a list.

You might possibly find it convenient to make it a generator, which yields locations. Whatever.


DRY. In capturePieces you have an opportunity to introduce a tiny helper method for those list comprehensions.


Overall?

This is a large project, and it is great code. It is clear some careful thought went into its design.

I would be happy to accept or delegate maintenance tasks on this codebase. Though adding the occasional unit test wouldn't hurt!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.