Source code for sgfmill.boards

"""Go board representation."""

from itertools import chain

from .common import opponent_of

class _Group:
    """Represent a solidly-connected group.

    Public attributes:
      colour
      points
      is_surrounded

    Points are coordinate pairs (row, col).

    """

class _Region:
    """Represent an empty region.

    Public attributes:
      points
      neighbouring_colours

    Points are coordinate pairs (row, col).

    """
    def __init__(self):
        self.points = set()
        self.neighbouring_colours = set()

[docs]class Board: """A legal Go position. Supports playing stones with captures, and area scoring. Public attributes: side -- board size (int >= 2) board_points -- list of coordinates of all points on the board """ def __init__(self, side): self.side = side if side < 2: raise ValueError self.board_points = [(_row, _col) for _row in range(side) for _col in range(side)] self.board = [] for row in range(side): self.board.append([None] * side) self._is_empty = True
[docs] def copy(self): """Return an independent copy of this Board.""" b = Board(self.side) b.board = [self.board[i][:] for i in range(self.side)] b._is_empty = self._is_empty return b
def _make_group(self, row, col, colour): points = set() is_surrounded = True to_handle = set() to_handle.add((row, col)) while to_handle: point = to_handle.pop() points.add(point) r, c = point for neighbour in [(r-1, c), (r+1, c), (r, c-1), (r, c+1)]: (r1, c1) = neighbour if not ((0 <= r1 < self.side) and (0 <= c1 < self.side)): continue neigh_colour = self.board[r1][c1] if neigh_colour is None: is_surrounded = False elif neigh_colour == colour: if neighbour not in points: to_handle.add(neighbour) group = _Group() group.colour = colour group.points = points group.is_surrounded = is_surrounded return group def _make_empty_region(self, row, col): points = set() neighbouring_colours = set() to_handle = set() to_handle.add((row, col)) while to_handle: point = to_handle.pop() points.add(point) r, c = point for neighbour in [(r-1, c), (r+1, c), (r, c-1), (r, c+1)]: (r1, c1) = neighbour if not ((0 <= r1 < self.side) and (0 <= c1 < self.side)): continue neigh_colour = self.board[r1][c1] if neigh_colour is None: if neighbour not in points: to_handle.add(neighbour) else: neighbouring_colours.add(neigh_colour) region = _Region() region.points = points region.neighbouring_colours = neighbouring_colours return region def _find_surrounded_groups(self, r, c): """Find solidly-connected groups with 0 liberties adjacent to r,c. Returns a list of _Groups. """ surrounded = [] handled = set() for (row, col) in [(r, c), (r-1, c), (r+1, c), (r, c-1), (r, c+1)]: if not ((0 <= row < self.side) and (0 <= col < self.side)): continue colour = self.board[row][col] if colour is None: continue point = (row, col) if point in handled: continue group = self._make_group(row, col, colour) if group.is_surrounded: surrounded.append(group) handled.update(group.points) return surrounded def _find_all_surrounded_groups(self): """Find all solidly-connected groups with 0 liberties. Returns a list of _Groups. """ surrounded = [] handled = set() for (row, col) in self.board_points: colour = self.board[row][col] if colour is None: continue point = (row, col) if point in handled: continue group = self._make_group(row, col, colour) if group.is_surrounded: surrounded.append(group) handled.update(group.points) return surrounded
[docs] def is_empty(self): """Return a boolean indicating whether the board is empty.""" return self._is_empty
[docs] def get(self, row, col): """Return the state of the specified point. Returns a colour, or None for an empty point. Raises IndexError if the coordinates are out of range. """ if row < 0 or col < 0: raise IndexError return self.board[row][col]
[docs] def play(self, row, col, colour): """Play a move on the board. Raises IndexError if the coordinates are out of range. Raises ValueError if the specified point isn't empty. Performs any necessary captures. Allows self-captures. Doesn't enforce any ko rule. Returns the point forbidden by simple ko, or None """ if row < 0 or col < 0: raise IndexError opponent = opponent_of(colour) if self.board[row][col] is not None: raise ValueError self.board[row][col] = colour self._is_empty = False surrounded = self._find_surrounded_groups(row, col) simple_ko_point = None if surrounded: if len(surrounded) == 1: to_capture = surrounded if len(to_capture[0].points) == self.side*self.side: self._is_empty = True else: to_capture = [group for group in surrounded if group.colour == opponent] if len(to_capture) == 1 and len(to_capture[0].points) == 1: self_capture = [group for group in surrounded if group.colour == colour] if len(self_capture[0].points) == 1: (simple_ko_point,) = to_capture[0].points for group in to_capture: for r, c in group.points: self.board[r][c] = None return simple_ko_point
[docs] def apply_setup(self, black_points, white_points, empty_points): """Add setup stones or removals to the position. This is intended to support SGF AB/AW/AE commands. Each parameter is an iterable of coordinate pairs (row, col). Applies all the setup specifications, then removes any groups with no liberties (so the resulting position is always legal). If the same point is specified in more than one list, the order in which they're applied is undefined. Returns a boolean saying whether the position was legal as specified. Raises IndexError if any coordinates are out of range. """ for (row, col) in chain(black_points, white_points, empty_points): if row < 0 or col < 0 or row >= self.side or col >= self.side: raise IndexError for (row, col) in black_points: self.board[row][col] = 'b' for (row, col) in white_points: self.board[row][col] = 'w' for (row, col) in empty_points: self.board[row][col] = None captured = self._find_all_surrounded_groups() for group in captured: for row, col in group.points: self.board[row][col] = None self._is_empty = True for (row, col) in self.board_points: if self.board[row][col] is not None: self._is_empty = False break return not(captured)
[docs] def list_occupied_points(self): """List all nonempty points. Returns a list of pairs (colour, (row, col)) """ result = [] for (row, col) in self.board_points: colour = self.board[row][col] if colour is not None: result.append((colour, (row, col))) return result
[docs] def area_score(self): """Calculate the area score of a position. Assumes all stones are alive. Returns black score minus white score. Doesn't take komi into account. """ scores = {'b' : 0, 'w' : 0} handled = set() for (row, col) in self.board_points: colour = self.board[row][col] if colour is not None: scores[colour] += 1 continue point = (row, col) if point in handled: continue region = self._make_empty_region(row, col) region_size = len(region.points) for colour in ('b', 'w'): if colour in region.neighbouring_colours: scores[colour] += region_size handled.update(region.points) return scores['b'] - scores['w']