Go (board game) check for removed stones

Question

Given a board state in the game of Go (19x19 grid with entries white, black, empty) I want to write an algorithm that, for each stone, determines if it is captured or not. [And thus removes it if needed.]

A stone is captured if it has no more liberties. A stone is considered to have liberties if it is connected to an empty field or to a stone of the same color that has liberties. Here connection is specified as the four cardinal directions (up, down, left, right); edges and corners only have 3 or 2 connections respectively.

Two other ways of thinking about this:

1. A group of connected, similarly colored stones is captured if it is surrounded by opposite colored stones.
2. A stone has liberties if there is a path (may be empty) of similarly colored stones between it and an empty field.

Here is my implementation based on floodfill. My question is if this is a good, readable way to tackle this problem. A problem I am having is that it is unbearably slow. I am looking for ways to optimize this implementation.

For brevity I only show the two relevant functions because they don't depend on any class variables or functions.

Floodfill:

def floodfill(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 liberties[y][x] == 0.0:  
        liberties[y][x] = 1.0 
        if y > 0:
            floodfill(liberties,y-1,x)
        if y < liberties.shape[0] - 1:
            floodfill(liberties,y+1,x)
        if x > 0:
            floodfill(liberties,y,x-1)
        if x < liberties.shape[1] - 1:
            floodfill(liberties,y,x+1)

The (quasi static) class function to capture pieces:

def capture_pieces(self, black_board, white_board):
    """Remove all pieces from the board that have 
    no liberties. This function modifies the input variables in place.

    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.

    """

    has_stone = np.logical_or(black_board,white_board)
    white_liberties = np.zeros((19,19))
    black_liberties = np.zeros((19,19))

    # stones in opposite color have no liberties
    white_liberties[black_board] = -1.0
    black_liberties[white_board] = -1.0

    for y in range(has_stone.shape[0]):
        for x in range(has_stone.shape[1]):
            if not has_stone[y,x]:
                floodfill(white_board,y,x)
                floodfill(black_board,y,x)

    white_liberties[white_liberties == 0.0] = -1.0
    black_liberties[black_liberties == 0.0] = -1.0

    white_board[white_liberties == -1.0] = 0.0
    black_board[black_liberties == -1.0] = 0.0

Update: This is the result of cProfile when executing moves from 1000 replays from strong players (so the distribution of moves is more realistic):

ncalls  tottime percall cumtime percall filename:lineno(function)
714846699/149091622 1005    6.741e-06   1005    6.741e-06   go.py:7(floodfill)
207082  37.22   0.0001797   1043    0.005036    go.py:244(capture_pieces)

The total time was 1080s. The remaining time was spend in auxiliary methods which I don't think are too relevant at the moment. I can't profile the inside of floodfill, because numpy runs in C and isn't reached by cProfile.

Update 2: I have profiling results for the function floodfill. There doesn't seem to be much room for improvement other then changing the entire algorithm.

Line   Hits       Time     Per Hit   % Time     Line Contents
============================================================== 
18 333929022 1872910206.0      5.6     50.8      if liberties[y][x] == 0.0:
19  69744678  154694113.0      2.2      4.2          liberties[y][x] = 1.0
20  69744678   97583648.0      1.4      2.6          if y > 0:
21  66071000  421815655.0      6.4     11.4              floodfill(liberties,y-1,x)
22  69744555  136365909.0      2.0      3.7          if y < liberties.shape[0] - 1:
23  66070955  262426237.0      4.0      7.1              floodfill(liberties,y+1,x)
24  69744429  106364662.0      1.5      2.9          if x > 0:
25  66070883  250659691.0      3.8      6.8              floodfill(liberties,y,x-1)
26  69744429  134409204.0      1.9      3.6          if x < liberties.shape[1] - 1:
27  66070778  250329742.0      3.8      6.8              floodfill(liberties,y,x+1)

Update 3: I found one optimization. Changing liberties[y][x] == 0.0 to not liberties[y][x] reduces the needed time by ~66%.

I set up a new replay dataset (I found that I was testing more then 1k replays). Here is the profile of the two versions in comparison:

liberties[y][x] == 0.0
650412346/135653278 892.6   6.58e-06    892.6   6.58e-06    go.py:7(floodfill)

not liberties[y][x]
650412346/135653278 300.6   2.216e-06   300.6   2.216e-06   go.py:7(floodfill)

Update 4: I've written a small replay "parser" to make it easier to test ideas and to compare. It builds on top of an existing .sgf parser and adds a bit of game logic and console visalization: https://gist.github.com/FirefoxMetzger/e98dc6a52deed5130a9d35df401a14d8

Tons of replay data in .sgf is available at https://u-go.net/gamerecords/

Answer 1

Performance

I think the main reason why the algorithm is slow, is because you start a new flood fill for every empty place on the board. It would be smarter to keep a collection of the positions that need to be checked

Enum

One thing I would change first, is instead of working with the magical values 0, 1, -1, is working with two IntEnums

from enum import IntEnum
class Position(IntEnum):
    black = -1
    empty = 0
    white = 1
class Liberty(IntEnum):
    taken = -9
    opponent = -1
    unknown = 0
    free = 1

This will make your code a lot more clear.

The board

Instead of 2 boards with the stones of one colour, I would change to 1 board, something like this:

board = np.array([
    [ 1, -1,  0,  0, -1,  1,  0],
    [-1,  0,  0,  0, -1,  1,  1],
    [ 0,  0,  0,  1, -1,  1,  1],
    [ 0,  0,  1, -1,  1, -1, -1],
    [ 0,  0,  0,  1,  0,  0, -1],
    [ 0,  0,  0,  0,  0, -1,  1],
    [ 0,  0,  0,  0,  0,  0,  1],
])

Repetition

A lot of the code is repeated for the 2 colours. I would make a 1 method, and then call it for the 2 colours

def capture_coloured_pieces(board: np.array, colour: Position):
    '''
    takes a `board` and returns the captured stones of `colour`
    '''

First you prime the liberties. Here, instead of hard-coding 19x19 as board size, use the shape of board. instead of the arbitrary values, I use the Enum

    liberties = np.ones_like(board) * Liberty.unknown
    liberties[board == -colour] = Liberty.opponent
    liberties[board == Position.empty] = Liberty.free

Instead of iterating over every position, and checking whether it has a stone, I would make a collection of the empty positions, and of the stones that are still unknown

    empty = set(zip(*np.where(board == Position.empty)))
    stones = set(zip(*np.where(board == colour)))

and then pick an empty position as a seed, and start the flood fill

    while empty:
        start = empty.pop()
        # print(f'starting at {start}')
        floodfill_set(liberties, start, empty, stones)

Then, if you want to, you can mark those positions on a copy of the board

    b1 = board.copy()
    for x, y in stones:
        b1[x, y] = Liberty.taken

    return stones, liberties, b1

The floodfill:

This function assumes the coord is a valid coordinate and needs to be set to Free

def floodfill_set(liberties, coord, empty, stones):
    x, y = coord
#     print(f'test {coord},{ liberties[x, y]}')
    empty.discard(coord)
    stones.discard(coord)
    liberties[x, y] = Liberty.free

Instead of the long list of if-statements, I would use a list of coordinates that can be checked

    coords = ((x, y-1), (x, y+1), (x-1, y), (x+1, y))

and then for each of those coordinates, see whether it still needs to be checked. If so, continue the floodfill

    for coord in coords:
        if coord in (empty | stones):
            floodfill_set(liberties, coord, empty, stones)

calling this:

colour = Position.black
capture_coloured_pieces(board, colour)

captured black stones

{(3, 3)}, 

liberties for black

array([[-1,  1,  1,  1,  1, -1,  1],
         [ 1,  1,  1,  1,  1, -1, -1],
         [ 1,  1,  1, -1,  1, -1, -1],
         [ 1,  1, -1,  0, -1,  1,  1],
         [ 1,  1,  1, -1,  1,  1,  1],
         [ 1,  1,  1,  1,  1,  1, -1],
         [ 1,  1,  1,  1,  1,  1, -1]
]), 

the captured stones marked on the board

array([[ 1, -1,  0,  0, -1,  1,  0],
         [-1,  0,  0,  0, -1,  1,  1],
         [ 0,  0,  0,  1, -1,  1,  1],
         [ 0,  0,  1, -9,  1, -1, -1],
         [ 0,  0,  0,  1,  0,  0, -1],
         [ 0,  0,  0,  0,  0, -1,  1],
         [ 0,  0,  0,  0,  0,  0,  1]
])
)

Liberties

In all this, you can make it even simpler, and not use the liberties array

convolution

You can also expand the liberties via convolution. I have an attempt with that method on my github repo, but it is slower than my other attempt

timings

on my 7x7 test board

original

on the slightly adapted original code

white_board = (board== Position.white)
black_board = (board== Position.black)
%timeit  capture_pieces(black_board, white_board)

2.77 ms ± 302 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

My original attempt

%timeit capture_coloured_pieces(board, Position.black), capture_coloured_pieces(board, Position.white)

443 µs ± 17.7 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

using only the set, dropping the liberties

%timeit capture_coloured_pieces2(board, Position.black), capture_coloured_pieces2(board, Position.white)

385 µs ± 31.3 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

So a 7* speed up

using convolution

%timeit capture_all(board, Position.white), capture_all(board, Position.black)

1.39 ms ± 58.3 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

'only' double the speed

Answer 2

I've found a method that is a lot faster.

Fast capture 1000 runs: 2.17
Slow capture 1000 runs: 208.35
Relative gain: 96.11

I now average over 1000 runs for a single game for both versions (compared to 1000 different games in my original post), using the method posted in Update 4.

The other answer is very efficient in cutting down on the constant overhead and rightfully points out that the number of calls (even if it's doing no modifications to the board) adds unnecessary bloat. Juvian also pointed out that I do have access to the current move, which inspired this idea.

For each adjacent field I use floodfill to find the group of enemy stones (if any). While doing so, if I encounter a border which is free the group has liberties and I stop the floodfill. If I manage to fill the entire region without encountering an empty border field the group has no liberties and is thus captured.

Another advantage of this approach is that it conforms with the rules (See this Boardgames SE question), because I remove all stones in the opposite color first.

Here are the two relevant functions:

def test_group(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

        neighboors = get_neighboors(y,x,board.shape)
        for yn, xn in neighboors:
            has_liberties = test_group(board,opponent_board,yn,xn,current_group)
            if has_liberties:
                return True
        return False

    return not board[pos]

def fast_capture_pieces(black_board, white_board, turn_white, y,x):
    """Remove all pieces from the board that have 
    no liberties. This function modifies the input variables in place.

    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

    """

    # only test neighboors of current move (other's will have unchanged
    # liberties)
    neighboors = get_neighboors(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)

    # only test adjacent stones in opponent's color
    for pos in neighboors:
        if not opponent_board[pos]:
            continue

        current_group = np.zeros((19,19), dtype=bool)
        has_liberties = test_group(board, opponent_board, *pos, current_group)
        if not has_liberties:
            opponent_board[current_group] = False

    current_group = np.zeros((19,19), dtype=bool)
    has_liberties = test_group(opponent_board, board, *original_pos, current_group)
    if not has_liberties:
        board[current_group] = False

I introduced a utility function to get the neighborhood:

def get_neighboors(y,x,board_shape):
    neighboors = list()

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

    return neighboors

This avoids duplicates for corners and edges and I could cache the results for even faster computation (though this is not very expensive to compute).

Here is the full example as a gist: https://gist.github.com/FirefoxMetzger/bbc7e14a777dd529942d3e68ba919a9c