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:
- A group of connected, similarly colored stones is captured if it is surrounded by opposite colored stones.
- 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/
floodfill
takes 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\$1.08s
out of which1.005
s are spend insidefloodfill. 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\$