Given a board state in the game of Go (
19x19 grid with entries
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.
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 - 1: floodfill(liberties,y+1,x) if x > 0: floodfill(liberties,y,x-1) if x < liberties.shape - 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): for x in range(has_stone.shape): 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 - 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: 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/