Permalink
Find file
89783fd Oct 30, 2016
390 lines (332 sloc) 14 KB
'''
A board is a NxN numpy array.
A Coordinate is a tuple index into the board.
A Move is a (Coordinate c | None).
(0, 0) is considered to be the upper left corner of the board, and (18, 0) is the lower left.
'''
from collections import namedtuple
import copy
import itertools
import numpy as np
# Represent a board as a numpy array, with 0 empty, 1 is black, -1 is white.
# This means that swapping colors is as simple as multiplying array by -1.
WHITE, EMPTY, BLACK, FILL, KO, UNKNOWN = range(-1, 5)
# Represents "group not found" in the LibertyTracker object
MISSING_GROUP_ID = -1
class IllegalMove(Exception): pass
# these are initialized by set_board_size
N = None
ALL_COORDS = []
EMPTY_BOARD = None
NEIGHBORS = {}
DIAGONALS = {}
def set_board_size(n):
'''
Hopefully nobody tries to run both 9x9 and 19x19 game instances at once.
Also, never do "from go import N, W, ALL_COORDS, EMPTY_BOARD".
'''
global N, ALL_COORDS, EMPTY_BOARD, NEIGHBORS, DIAGONALS
if N == n: return
N = n
ALL_COORDS = [(i, j) for i in range(n) for j in range(n)]
EMPTY_BOARD = np.zeros([n, n], dtype=np.int8)
def check_bounds(c):
return c[0] % n == c[0] and c[1] % n == c[1]
NEIGHBORS = {(x, y): list(filter(check_bounds, [(x+1, y), (x-1, y), (x, y+1), (x, y-1)])) for x, y in ALL_COORDS}
DIAGONALS = {(x, y): list(filter(check_bounds, [(x+1, y+1), (x+1, y-1), (x-1, y+1), (x-1, y-1)])) for x, y in ALL_COORDS}
def place_stones(board, color, stones):
for s in stones:
board[s] = color
def find_reached(board, c):
color = board[c]
chain = set([c])
reached = set()
frontier = [c]
while frontier:
current = frontier.pop()
chain.add(current)
for n in NEIGHBORS[current]:
if board[n] == color and not n in chain:
frontier.append(n)
elif board[n] != color:
reached.add(n)
return chain, reached
def is_koish(board, c):
'Check if c is surrounded on all sides by 1 color, and return that color'
if board[c] != EMPTY: return None
neighbors = {board[n] for n in NEIGHBORS[c]}
if len(neighbors) == 1 and not EMPTY in neighbors:
return list(neighbors)[0]
else:
return None
def is_eyeish(board, c):
'Check if c is an eye, for the purpose of restricting MC rollouts.'
color = is_koish(board, c)
if color is None:
return None
diagonal_faults = 0
diagonals = DIAGONALS[c]
if len(diagonals) < 4:
diagonal_faults += 1
for d in diagonals:
if not board[d] in (color, EMPTY):
diagonal_faults += 1
if diagonal_faults > 1:
return None
else:
return color
class Group(namedtuple('Group', ['id', 'stones', 'liberties', 'color'])):
'''
stones: a set of Coordinates belonging to this group
liberties: a set of Coordinates that are empty and adjacent to this group.
color: color of this group
'''
def __eq__(self, other):
return self.stones == other.stones and self.liberties == other.liberties and self.color == other.color
class LibertyTracker():
@staticmethod
def from_board(board):
board = np.copy(board)
curr_group_id = 0
lib_tracker = LibertyTracker()
for color in (WHITE, BLACK):
while color in board:
curr_group_id += 1
found_color = np.where(board == color)
coord = found_color[0][0], found_color[1][0]
chain, reached = find_reached(board, coord)
liberties = set(r for r in reached if board[r] == EMPTY)
new_group = Group(curr_group_id, chain, liberties, color)
lib_tracker.groups[curr_group_id] = new_group
for s in chain:
lib_tracker.group_index[s] = curr_group_id
place_stones(board, FILL, chain)
lib_tracker.max_group_id = curr_group_id
liberty_counts = np.zeros([N, N], dtype=np.uint8)
for group in lib_tracker.groups.values():
num_libs = len(group.liberties)
for s in group.stones:
liberty_counts[s] = num_libs
lib_tracker.liberty_cache = liberty_counts
return lib_tracker
def __init__(self, group_index=None, groups=None, liberty_cache=None, max_group_id=1):
# group_index: a NxN numpy array of group_ids. -1 means no group
# groups: a dict of group_id to groups
# liberty_cache: a NxN numpy array of liberty counts
self.group_index = group_index if group_index is not None else -np.ones([N, N], dtype=np.int16)
self.groups = groups or {}
self.liberty_cache = liberty_cache if liberty_cache is not None else np.zeros([N, N], dtype=np.uint8)
self.max_group_id = max_group_id
def __deepcopy__(self, memodict={}):
new_group_index = np.copy(self.group_index)
new_lib_cache = np.copy(self.liberty_cache)
new_groups = {
group.id: Group(group.id, set(group.stones), set(group.liberties), group.color)
for group in self.groups.values()
}
return LibertyTracker(new_group_index, new_groups, liberty_cache=new_lib_cache, max_group_id=self.max_group_id)
def add_stone(self, color, c):
assert self.group_index[c] == MISSING_GROUP_ID
captured_stones = set()
opponent_neighboring_group_ids = set()
friendly_neighboring_group_ids = set()
empty_neighbors = set()
for n in NEIGHBORS[c]:
neighbor_group_id = self.group_index[n]
if neighbor_group_id != MISSING_GROUP_ID:
neighbor_group = self.groups[neighbor_group_id]
if neighbor_group.color == color:
friendly_neighboring_group_ids.add(neighbor_group_id)
else:
opponent_neighboring_group_ids.add(neighbor_group_id)
else:
empty_neighbors.add(n)
new_group = self._create_group(color, c, empty_neighbors)
for group_id in friendly_neighboring_group_ids:
new_group = self._merge_groups(group_id, new_group.id)
for group_id in opponent_neighboring_group_ids:
neighbor_group = self.groups[group_id]
if len(neighbor_group.liberties) == 1:
captured = self._capture_group(group_id)
captured_stones.update(captured)
else:
self._update_liberties(group_id, remove={c})
self._handle_captures(captured_stones)
# suicide is illegal
if len(new_group.liberties) == 0:
raise IllegalMove
return captured_stones
def _create_group(self, color, c, liberties):
self.max_group_id += 1
new_group = Group(self.max_group_id, set([c]), liberties, color)
self.groups[new_group.id] = new_group
self.group_index[c] = new_group.id
self.liberty_cache[c] = len(liberties)
return new_group
def _merge_groups(self, group1_id, group2_id):
group1 = self.groups[group1_id]
group2 = self.groups[group2_id]
group1.stones.update(group2.stones)
del self.groups[group2_id]
for s in group2.stones:
self.group_index[s] = group1_id
self._update_liberties(group1_id, add=group2.liberties, remove=(group2.stones | group1.stones))
return group1
def _capture_group(self, group_id):
dead_group = self.groups[group_id]
del self.groups[group_id]
for s in dead_group.stones:
self.group_index[s] = MISSING_GROUP_ID
self.liberty_cache[s] = 0
return dead_group.stones
def _update_liberties(self, group_id, add=None, remove=None):
group = self.groups[group_id]
if add:
group.liberties.update(add)
if remove:
group.liberties.difference_update(remove)
new_lib_count = len(group.liberties)
for s in group.stones:
self.liberty_cache[s] = new_lib_count
def _handle_captures(self, captured_stones):
for s in captured_stones:
for n in NEIGHBORS[s]:
group_id = self.group_index[n]
if group_id != MISSING_GROUP_ID:
self._update_liberties(group_id, add={s})
class Position():
def __init__(self, board=None, n=0, komi=7.5, caps=(0, 0), lib_tracker=None, ko=None, recent=tuple(), to_play=BLACK):
'''
board: a numpy array
n: an int representing moves played so far
komi: a float, representing points given to the second player.
caps: a (int, int) tuple of captures for B, W.
lib_tracker: a LibertyTracker object
ko: a Move
recent: a tuple of Moves, such that recent[-1] is the last move. (Would be nicely implemented as a linked list in lower level languages!)
to_play: BLACK or WHITE
'''
self.board = board if board is not None else np.copy(EMPTY_BOARD)
self.n = n
self.komi = komi
self.caps = caps
self.lib_tracker = lib_tracker or LibertyTracker.from_board(self.board)
self.ko = ko
self.recent = recent
self.to_play = to_play
def __deepcopy__(self, memodict={}):
new_board = np.copy(self.board)
new_lib_tracker = copy.deepcopy(self.lib_tracker)
return Position(new_board, self.n, self.komi, self.caps, new_lib_tracker, self.ko, self.recent, self.to_play)
def __str__(self):
pretty_print_map = {
WHITE: 'O',
EMPTY: '.',
BLACK: 'X',
FILL: '#',
KO: '*',
}
board = np.copy(self.board)
captures = self.caps
if self.ko is not None:
place_stones(board, KO, [self.ko])
raw_board_contents = []
for i in range(N):
row = []
for j in range(N):
appended = '<' if (self.recent and (i, j) == self.recent[-1]) else ' '
row.append(pretty_print_map[board[i,j]] + appended)
raw_board_contents.append(''.join(row))
row_labels = ['%2d ' % i for i in range(N, 0, -1)]
annotated_board_contents = [''.join(r) for r in zip(row_labels, raw_board_contents, row_labels)]
header_footer_rows = [' ' + ' '.join('ABCDEFGHJKLMNOPQRST'[:N]) + ' ']
annotated_board = '\n'.join(itertools.chain(header_footer_rows, annotated_board_contents, header_footer_rows))
details = "\nMove: {}. Captures X: {} O: {}\n".format(self.n, *captures)
return annotated_board + details
def is_move_suicidal(self, move):
potential_libs = set()
for n in NEIGHBORS[move]:
neighbor_group_id = self.lib_tracker.group_index[n]
if neighbor_group_id == MISSING_GROUP_ID:
# at least one liberty after playing here, so not a suicide
return False
neighbor_group = self.lib_tracker.groups[neighbor_group_id]
if neighbor_group.color == self.to_play:
potential_libs |= neighbor_group.liberties
elif len(neighbor_group.liberties) == 1:
# would capture an opponent group if they only had one lib.
return False
# it's possible to suicide by connecting several friendly groups
# each of which had one liberty.
potential_libs -= set([move])
return not potential_libs
def is_move_legal(self, move):
'Checks that a move is on an empty space, not on ko, and not suicide'
if self.board[move] != EMPTY:
return False
if move == self.ko:
return False
if self.is_move_suicidal(move):
return False
return True
def pass_move(self, mutate=False):
pos = self if mutate else copy.deepcopy(self)
pos.n += 1
pos.to_play *= -1
pos.ko = None
pos.recent += (None,)
return pos
def flip_playerturn(self, mutate=False):
pos = self if mutate else copy.deepcopy(self)
pos.ko = None
pos.to_play *= -1
return pos
def get_liberties(self):
return self.lib_tracker.liberty_cache
def play_move(self, color, c, mutate=False):
# Obeys CGOS Rules of Play. In short:
# No suicides
# Chinese/area scoring
# Positional superko (this is very crudely approximate at the moment.)
pos = self if mutate else copy.deepcopy(self)
if not self.is_move_legal(c):
raise IllegalMove()
if c is None:
pos = pos.pass_move(mutate=mutate)
return pos
place_stones(pos.board, color, [c])
captured_stones = pos.lib_tracker.add_stone(color, c)
place_stones(pos.board, EMPTY, captured_stones)
opp_color = color * -1
if len(captured_stones) == 1 and is_koish(self.board, c) == opp_color:
new_ko = list(captured_stones)[0]
else:
new_ko = None
if pos.to_play == BLACK:
new_caps = (pos.caps[0] + len(captured_stones), pos.caps[1])
else:
new_caps = (pos.caps[0], pos.caps[1] + len(captured_stones))
pos.n += 1
pos.caps = new_caps
pos.ko = new_ko
pos.recent += (c,)
pos.to_play *= -1
return pos
def score(self):
working_board = np.copy(self.board)
while EMPTY in working_board:
unassigned_spaces = np.where(working_board == EMPTY)
c = unassigned_spaces[0][0], unassigned_spaces[1][0]
territory, borders = find_reached(working_board, c)
border_colors = set(working_board[b] for b in borders)
X_border = BLACK in border_colors
O_border = WHITE in border_colors
if X_border and not O_border:
territory_color = BLACK
elif O_border and not X_border:
territory_color = WHITE
else:
territory_color = UNKNOWN # dame, or seki
place_stones(working_board, territory_color, territory)
return np.count_nonzero(working_board == BLACK) - np.count_nonzero(working_board == WHITE) - self.komi
set_board_size(19)