"""Go board representation."""
from gomill.common import *
class _Group(object):
"""Represent a solidly-connected group.
Public attributes:
colour
points
is_surrounded
Points are coordinate pairs (row, col).
"""
class _Region(object):
"""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(object):
"""A legal Go position.
Supports playing stones with captures, and area scoring.
Public attributes:
side -- board size (eg 9)
board_points -- list of coordinates of all points on the board
Behaviour is unspecified if methods are passed out-of-range coordinates.
"""
def __init__(self, side):
self.side = side
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 xrange(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):
"""Find 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):
"""Say 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.
"""
return self.board[row][col]
[docs] def play(self, row, col, colour):
"""Play a move on the board.
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 self.board[row][col] is not None:
raise ValueError
self.board[row][col] = colour
surrounded = self._find_surrounded_groups()
simple_ko_point = None
if surrounded:
if len(surrounded) == 1:
to_capture = surrounded
else:
to_capture = [group for group in surrounded
if group.colour == opponent_of(colour)]
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 = iter(to_capture[0].points).next()
for group in to_capture:
for r, c in group.points:
self.board[r][c] = None
self._is_empty = False
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.
"""
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_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']