7
\$\begingroup\$

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/

\$\endgroup\$
  • \$\begingroup\$ You say unbearably slow, but have your profiled it? What part is slow? \$\endgroup\$ – juvian Apr 4 '18 at 14:41
  • \$\begingroup\$ floodfilltakes up around 80% of the time. I drawing moves from a pool of replays essentially "simulating" (in apostrophes, because it's not a full simulator yet) Go games and profiling the result. I will post numbers once my current profiling finishes. \$\endgroup\$ – FirefoxMetzger Apr 4 '18 at 17:40
  • \$\begingroup\$ @juvian Progressing through a single replay takes about 1.08s out of which 1.005s are spend inside floodfill. Second biggest is capture_stones` with a few ms per run. The remainder is spend on auxiliary stuff (which is likely not relevant). Results are over 1000 runs. \$\endgroup\$ – FirefoxMetzger Apr 4 '18 at 18:03
  • \$\begingroup\$ is the information of the last move available? \$\endgroup\$ – juvian Apr 4 '18 at 18:28
  • 1
    \$\begingroup\$ I would try using en.wikipedia.org/wiki/Disjoint-set_data_structure \$\endgroup\$ – juvian Apr 5 '18 at 6:51
8
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ Nice answer. As for the performance part, even though he "starts" a new floodfill, he does not perform adding neighbors from a cell twice over different calls as the condition for entering is if its still unknown \$\endgroup\$ – juvian Apr 4 '18 at 17:46
  • \$\begingroup\$ The reason I start with two arrays is mainly memory constraints. 2 bool arrays are 93% smaller then 1 float32 and still 75% smaller then 1 int8. I have a lot of replays I want to keep in memory (in the 1e5) and I have to keep a full history over all board states. Further, I report the board state in a certain way (aggregating those black/white stone arrays in a certain way) and keeping actual arrays is convenient. Similarly I want to output two arrays again. What happens in between I don't care (it's non-persistent) \$\endgroup\$ – FirefoxMetzger Apr 4 '18 at 18:20
  • \$\begingroup\$ Why do you need to keep full history over all board states? if you want to simulate a replay, the list of moves made is enough \$\endgroup\$ – juvian Apr 4 '18 at 18:35
  • \$\begingroup\$ @juvian :D This is starting to breach the "MWE" style I am used from SE. The scenario is a small machine learning project. I want to build a GO AI from human data. I need the history as input for the network, because the current board state alone is not Markov (repeated moves are prohibited). \$\endgroup\$ – FirefoxMetzger Apr 4 '18 at 19:09
  • \$\begingroup\$ I am actually not too surprised by your convolution results. FFT is only faster for large arrays, because it has quite a big constant overhead. The rule of thumb is 500 elements in 1D conv. What could be interesting is to unroll the convolution into a matrix multiplication and see how that performs. \$\endgroup\$ – FirefoxMetzger Apr 5 '18 at 5:39
3
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ nice solution. Instead of returning a list of neighbours, I would make this into a generator. You can also cache this result with functools.lru_chache, or even precompute it for a give boardsize, since this function is likely to be called a lot. PS, you keep hard-coding (19,19) as the board shape \$\endgroup\$ – Maarten Fabré Apr 6 '18 at 10:09
  • \$\begingroup\$ @MaartenFabré Good pointers. I will have to do some refactoring before I can put this into a decent simulator. My main goal here was to quickly sketch the idea and see if it is any good. I'm not clear about the generator though, how would that benefit me? \$\endgroup\$ – FirefoxMetzger Apr 6 '18 at 10:57
  • \$\begingroup\$ Very nice, my implementation used this same idea, although I kept at all times the group of stones that were related for calculating liberties. However keeping those groups is unnecessary as you can calculate them by the flood fill. My approach takes about same time as this, but more code and still has a few bugs, so will refrain from posting it. My approach would only be faster than this one is I could keep information of liberties for each group and then know if a group has liberties or not without iterating it, but haven't thought of a way for that to be possible. Anyway, good job ^^ \$\endgroup\$ – juvian Apr 7 '18 at 23:29
  • \$\begingroup\$ @juvian you can do that, but it will cost some memory. I would maintain a dict that maps positions to groups. Whenever a stone is captured it increases the liberties of adjacent stones that remain once the group is removed. Whenever a stone is placed, it decreases the liberties of adjacent stones, merges groups and then increases the current group's liberties by it's liberties. You'd probably want an ordered list of groups as well to quickly find captured groups... \$\endgroup\$ – FirefoxMetzger Apr 8 '18 at 7:34
  • \$\begingroup\$ instead of a dict mapping positions, you could use an array with the groupnumber, and then just a dict with the number of liberties per groupnumber \$\endgroup\$ – Maarten Fabré Apr 9 '18 at 8:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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