作者：happyfly
2022.03.03
这些天用不同来源的围棋程序改道棋程序，今天终于改成了一个。主要是要实现如下要求：
1、改成道棋规则
在围棋中每个点都要做这样的判断：a. 直线相连的四个点是什么情况；b. 斜角相邻的四个点是什么情况。
直线相连：(x-1, y), (x+1, y), (x, y-1), (x, y+1)
斜角相邻：(x-1, y-1), (x+1, y+1), (x+1, y-1), (x-1, y+1)
围棋程序会有一个检测函数检测这些点是否落在棋盘的范围内，不在棋盘范围内就说明该点处于边角，需要做相应的处理。因为道棋棋盘是循环的，所以不用判断是否在棋盘范围内，而只需要让坐标循环就可以了。具体可以用python取余运算‘%’：
直线相连：((x-1)%size, y), ((x+1)%size, y), (x, (y-1)%size), (x, (y+1)%size)
斜角相邻：((x-1)%size, (y-1)%size), ((x+1)%size, (y+1)%size), ((x+1)%size, (y-1)%size), ((x-1)%size, (y+1)%size)
一般来说，行棋规则只要改这两个部分就可以了。
2、允许自杀
这是为了让道棋规则更加简洁。围棋的核心规则就三条：交替落子、气尽提子、禁止循环，其他都不应该算核心规则，这就包括“禁着点”。目前大部分规则都有禁着点，但应氏规则没有。为了让道棋更有"道"的极简味道，也不设禁着点。事实上，有了禁全同（禁止全局同形再现）规则之后，禁止自杀就是无的放矢了。比如一方“颗子自尽”，等同于棋局没变，只是行棋方发生了改变。这不违反禁全同。如果紧接着下一手另一方又“颗子自尽”，此时棋局还是没变，但却使对方面临曾面临过的局面，违反了禁全同规则，这是不允许了。换个角度看，颗子自尽相当于“虚着”，棋规规定“双方连续使用虚着，为终局”，与前面的情形是自洽的。
3、让棋盘能够平移
这应该是道棋平面化所带来的特点，毕竟现实中我们不能在环面上下棋。而为了观察视野边缘的棋形，平移棋盘的功能是必需的。
程序包含go.py（行棋的所有规则）和play.py（下棋程序）。
go.py:
import numpy as np
WHITE = -1
BLACK = +1
EMPTY = 0
PASS_MOVE = None
board_size = 16
komi = 4
'''
This code is based on 'https://github.com/sanghyunyi/alphago_zero'
'''
class GameState(object):
"""State of a game of Go and some basic functions to interact with it
"""
# Looking up positions adjacent to a given position takes a surprising
# amount of time, hence this shared lookup table {boardsize: {position: [neighbors]}}
__NEIGHBORS_CACHE = {}
def __init__(self, size=board_size, komi=komi, enforce_superko=False):
self.board = np.zeros((size, size))
self.board.fill(EMPTY)
self.size = size
self.current_player = BLACK
self.ko = None
self.komi = komi # Komi is number of extra points WHITE gets for going 2nd
self.history = [] # This is for history of actions
self.board_history = [] # This is for history of boards
for _ in range(8): # Initialize board history with empty boards.
self.board_history.append(self.board)
self.num_black_prisoners = 0
self.num_white_prisoners = 0
self.is_end_of_game = False
# Each pass move by a player subtracts a point
self.passes_white = 0
self.passes_black = 0
# `self.liberty_sets` is a 2D array with the same indexes as `board`
# each entry points to a set of tuples - the liberties of a stone's
# connected block. By caching liberties in this way, we can directly
# optimize update functions (e.g. do_move) and in doing so indirectly
# speed up any function that queries liberties
self._create_neighbors_cache()
self.liberty_sets = [[set() for _ in range(size)] for _ in range(size)]
for x in range(size):
for y in range(size):
self.liberty_sets[x][y] = set(self._neighbors((x, y)))
# separately cache the 2D numpy array of the _size_ of liberty sets
# at each board position
self.liberty_counts = np.zeros((size, size), dtype=np.int)
self.liberty_counts.fill(-1)
# initialize liberty_sets of empty board: the set of neighbors of each position
# similarly to `liberty_sets`, `group_sets[x][y]` points to a set of tuples
# containing all (x',y') pairs in the group connected to (x,y)
self.group_sets = [[set() for _ in range(size)] for _ in range(size)]
# cache of list of legal moves (actually 'sensible' moves, with a
# separate list for eye-moves on request)
self.__legal_move_cache = None
self.__legal_eyes_cache = None
# on-the-fly record of 'age' of each stone
self.stone_ages = np.zeros((size, size), dtype=np.int) - 1
# setup Zobrist hash to keep track of board state
self.enforce_superko = enforce_superko
rng = np.random.RandomState(0)
self.hash_lookup = {
WHITE: rng.randint(np.iinfo(np.uint64).max, size=(size, size), dtype='uint64'),
BLACK: rng.randint(np.iinfo(np.uint64).max, size=(size, size), dtype='uint64')}
self.current_hash = np.uint64(0)
self.previous_hashes = set()
def _create_neighbors_cache(self):
if self.size not in GameState.__NEIGHBORS_CACHE:
GameState.__NEIGHBORS_CACHE[self.size] = {}
for x in range(self.size):
for y in range(self.size):
neighbors = [((x - 1) % self.size, y), ((x + 1) % self.size, y), (x, (y - 1) % self.size), (x, (y + 1) % self.size )]
GameState.__NEIGHBORS_CACHE[self.size][(x, y)] = neighbors
def _neighbors(self, position):
"""A private helper function that simply returns a list of positions neighboring
the given (x,y) position.
"""
return GameState.__NEIGHBORS_CACHE[self.size][position]
def _diagonals(self, position):
"""Like _neighbors but for diagonal positions
"""
(x, y) = position
return [((x - 1) % self.size, (y - 1) % self.size), ((x + 1) % self.size, (y + 1) % self.size),
((x + 1) % self.size, (y - 1) % self.size), ((x - 1) % self.size, (y + 1) % self.size)]
def _update_neighbors(self, position):
"""A private helper function to update self.group_sets and self.liberty_sets
given that a stone was just played at `position`
"""
(x, y) = position
merged_group = set()
merged_group.add(position)
merged_libs = self.liberty_sets[x][y]
for (nx, ny) in self._neighbors(position):
# remove (x,y) from liberties of neighboring positions
self.liberty_sets[nx][ny] -= set([position])
# if neighbor was opponent, update group's liberties count
# (current_player's groups will be updated below regardless)
if self.board[nx][ny] == -self.current_player:
new_liberty_count = len(self.liberty_sets[nx][ny])
for (gx, gy) in self.group_sets[nx][ny]:
self.liberty_counts[gx][gy] = new_liberty_count
# MERGE group/liberty sets if neighbor is the same color
# note: this automatically takes care of merging two separate
# groups that just became connected through (x,y)
elif self.board[x][y] == self.board[nx][ny]:
merged_group |= self.group_sets[nx][ny]
merged_libs |= self.liberty_sets[nx][ny]
# now that we have one big 'merged' set for groups and liberties, loop
# over every member of the same-color group to update them
# Note: neighboring opponent groups are already updated in the previous loop
count_merged_libs = len(merged_libs)
for (gx, gy) in merged_group:
self.group_sets[gx][gy] = merged_group
self.liberty_sets[gx][gy] = merged_libs
self.liberty_counts[gx][gy] = count_merged_libs
def _update_hash(self, action, color):
(x, y) = action
self.current_hash = np.bitwise_xor(self.current_hash, self.hash_lookup[color][x][y])
def _remove_group(self, group):
"""A private helper function to take a group off the board (due to capture),
updating group sets and liberties along the way
"""
for (x, y) in group:
self._update_hash((x, y), self.board[x, y])
self.board[x, y] = EMPTY
for (x, y) in group:
# clear group_sets for all positions in 'group'
self.group_sets[x][y] = set()
self.liberty_sets[x][y] = set()
self.liberty_counts[x][y] = -1
self.stone_ages[x][y] = -1
for (nx, ny) in self._neighbors((x, y)):
if self.board[nx, ny] == EMPTY:
# add empty neighbors of (x,y) to its liberties
self.liberty_sets[x][y].add((nx, ny))
else:
# add (x,y) to the liberties of its nonempty neighbors
self.liberty_sets[nx][ny].add((x, y))
for (gx, gy) in self.group_sets[nx][ny]:
self.liberty_counts[gx][gy] = len(self.liberty_sets[nx][ny])
def copy(self):
"""get a copy of this Game state
"""
other = GameState(self.size, self.komi)
other.board = self.board.copy()
other.current_player = self.current_player
other.ko = self.ko
other.history = list(self.history)
other.board_history = list(self.board_history)
other.num_black_prisoners = self.num_black_prisoners
other.num_white_prisoners = self.num_white_prisoners
other.enforce_superko = self.enforce_superko
other.current_hash = self.current_hash.copy()
other.previous_hashes = self.previous_hashes.copy()
# update liberty and group sets.
#
# group_sets and liberty_sets are shared between stones in the same
# group. We need to make sure this is the case in the copy, as well.
#
# we store set copies indexed by original id() in set_copies
def get_copy(s, set_copies={}):
if id(s) not in set_copies:
set_copies[id(s)] = set(s) # makes a copy of s
return set_copies[id(s)]
for x in range(self.size):
for y in range(self.size):
other.group_sets[x][y] = get_copy(self.group_sets[x][y])
other.liberty_sets[x][y] = get_copy(self.liberty_sets[x][y])
other.liberty_counts = self.liberty_counts.copy()
return other
def is_positional_superko(self, action):
"""Find all actions that the current_player has done in the past, taking into
account the fact that history starts with BLACK.
"""
if self.current_player == BLACK:
player_history = self.history[0::2]
else:
player_history = self.history[1::2]
if action not in player_history:
return False
state_copy = self.copy()
state_copy.enforce_superko = False
state_copy.do_move(action)
if state_copy.current_hash in self.previous_hashes:
return True
else:
return False
def is_legal(self, action):
"""determine if the given action (x,y tuple) is a legal move
note: we only check ko, not superko at this point (TODO?)
"""
# passing is always legal
if action is PASS_MOVE:
return True
(x, y) = action
if self.board[x][y] != EMPTY:
#print("not empty")
return False
if action == self.ko:
#print("ko")
return False
if self.enforce_superko and self.is_positional_superko(action):
#print("lala")
return False
return True
def is_eyeish(self, position, owner):
"""returns whether the position is empty and is surrounded by all stones of 'owner'
"""
(x, y) = position
if self.board[x, y] != EMPTY:
return False
for (nx, ny) in self._neighbors(position):
if self.board[nx, ny] != owner:
return False
return True
def get_score_of_empty(self):
"""Calculate score for empty positions of board state using Tromp-Taylor scoring.
Returns BLACK_score, WHITE_score
"""
empties = zip(*np.where(self.board == EMPTY))
empty_neighbors = {}
reachability = {}
for empty in empties:
reachability[empty] = (False, False) # reachability of the empty postion from BLACK, WHITE.
empty_neighbors[empty] = []
for empty in empties:
for (nx, ny) in self._neighbors(empty):
if self.board[nx, ny] == BLACK:
reachability[empty] = (reachability[empty][0]|True, reachability[empty][1])
elif self.board[nx, ny] == WHITE:
reachability[empty] = (reachability[empty][0], reachability[empty][1]|True)
else :
empty_neighbors[empty].append((nx, ny))
# propagate reachability
reachability_old = reachability.copy()
while True:
for empty in empties:
for (nx, ny) in empty_neighbors[empty]:
black_reach, white_reach = reachability[(nx, ny)]
reachability[empty] = (reachability[empty][0]|black_reach,reachability[empty][1]|white_reach)
if reachability_old == reachability:
break
else :
reachability_old = reachability.copy()
BLACK_score = 0
WHITE_score = 0
for empty, (br, wr) in reachability.items():
if (br, wr) == (True, False):
BLACK_score += 1
elif (br, wr) == (False, True):
WHITE_score += 1
else:
pass
return BLACK_score, WHITE_score
def get_winner(self, tromp=True):
"""Calculate score of board state and return player ID (1, -1)
corresponding to winner. Uses 'Tromp-Taylor scoring' or 'Area scoring'.
"""
# Count number of positions filled by each player, plus 1 for each eye-ish space owned
score_white = np.sum(self.board == WHITE)
score_black = np.sum(self.board == BLACK)
if tromp:
black_reach, white_reach = self.get_score_of_empty()
score_white += white_reach
score_black += black_reach
else:
empties = zip(*np.where(self.board == EMPTY))
for empty in empties:
# Check that all surrounding points are of one color
if self.is_eyeish(empty, BLACK):
score_black += 1
elif self.is_eyeish(empty, WHITE):
score_white += 1
score_white -= self.passes_white
score_black -= self.passes_black
score_white += self.komi
if score_black > score_white:
winner = BLACK
else:
winner = WHITE
return winner
def get_current_player(self):
"""Returns the color of the player who will make the next move.
"""
return self.current_player
def do_move(self, action, color=None):
"""Play stone at action=(x,y). If color is not specified, current_player is used
If it is a legal move, current_player switches to the opposite color
If not, an IllegalMove exception is raised
"""
color = color or self.current_player
reset_player = self.current_player
self.current_player = color
if self.is_legal(action):
# reset ko
self.ko = None
# increment age of stones by 1
self.stone_ages[self.stone_ages >= 0] += 1
if action is not PASS_MOVE:
(x, y) = action
self.board[x][y] = color
self._update_hash(action, color)
self._update_neighbors(action)
self.stone_ages[x][y] = 0
if len(self.liberty_sets[x][y]) == 0:
suicide = True
# no liberties here 'immediately'
# but this may still connect to another group of the same color
for (nx, ny) in self._neighbors(action):
if self.board[nx, ny] == -color and len(self.liberty_sets[nx][ny]) == 0:
suicide = False
if suicide:
# suicide
captured_group = self.group_sets[x][y]
num_captured = len(captured_group)
self._remove_group(captured_group)
if color == BLACK:
self.num_black_prisoners += num_captured
else:
self.num_white_prisoners += num_captured
# check neighboring groups' liberties for captures
for (nx, ny) in self._neighbors(action):
if self.board[nx, ny] == -color and len(self.liberty_sets[nx][ny]) == 0:
# capture occurred!
captured_group = self.group_sets[nx][ny]
num_captured = len(captured_group)
self._remove_group(captured_group)
if color == BLACK:
self.num_white_prisoners += num_captured
else:
self.num_black_prisoners += num_captured
# check for ko
if num_captured == 1:
# it is a ko iff, were the opponent to play at the captured position,
# it would recapture (x,y) only
# (a bigger group containing xy may be captured - this is 'snapback')
would_recapture = len(self.liberty_sets[x][y]) == 1
recapture_size_is_1 = len(self.group_sets[x][y]) == 1
if would_recapture and recapture_size_is_1:
# note: (nx,ny) is the stone that was captured
self.ko = (nx, ny)
# _remove_group has finished updating the hash
self.previous_hashes.add(self.current_hash)
else:
if color == BLACK:
self.passes_black += 1
if color == WHITE:
self.passes_white += 1
# next turn
self.current_player = -color
self.history.append(action)
self.board_history.append(self.board)
self.board_history.pop(0)
self.__legal_move_cache = None
else:
self.current_player = reset_player
raise IllegalMove(str(action))
# Check for end of game
if len(self.history) > 1:
if self.history[-1] is PASS_MOVE and self.history[-2] is PASS_MOVE:
self.is_end_of_game = True
else :
pass
return self.is_end_of_game
class IllegalMove(Exception):
pass
play.py
import numpy as np
import re
import go
# 定义一个玩家的类
class Player(object):
def __init__(self, color):
self.color = color
# 下棋程序
def run_a_game(black, white):
global h_shift
global v_shift
v_shift = 0
h_shift = 0
# 实例化一局棋
state = go.GameState(size=go.board_size, komi=go.komi)
current = black
other = white
# 打印空白棋盘
print_board(state.board)
# 棋局循环
while not state.is_end_of_game:
query = input(current.color + " move (Enter for PSAA, 0 for shift): ")
# 直接回车代表虚着，两虚棋终
if len(query)==0:
state.do_move(go.PASS_MOVE)
current, other = other, current
continue
# 如果需要平移棋盘的话，需要先输入“0”，改到平移状态
if query == '0':
query = input("For board shift, input L/R/U/D0~16: ")
try:
alphabet, number = re.match(r"([a-z]+)([0-9]+)", query, re.I).groups()
if alphabet.upper() == 'L':
h_shift -= int(number)
if alphabet.upper() == 'R':
h_shift += int(number)
if alphabet.upper() == 'U':
v_shift -= int(number)
if alphabet.upper() == 'D':
v_shift += int(number)
print_board(state.board)
continue
except:
print("Input format error!")
continue
# 既不是虚着也不是平移，此时判断输入格式后调用go.py中的do_move行棋
try:
alphabet, number = re.match(r"([a-z]+)([0-9]+)", query, re.I).groups()
y = ord(alphabet.upper()) - ord('A')
x = go.board_size - int(number)
x = (x - v_shift) % go.board_size
y = (y - h_shift) % go.board_size
try:
state.do_move((x,y))
except:
print("Illegal move!")
continue
current, other = other, current
print_board(state.board)
except:
print("The input should have the form like 'a1' or 'A1'.")
continue
# 最后调用go.py中的get_winner判断赢家（Tromp-Taylor计分法）
print('Black' if state.get_winner() == 1 else 'White', "won the game.")
# 棋盘平移
def boardshift(matrix, v_shift, h_shift):
v, h = matrix.shape
matrix=np.vstack((matrix[(v - v_shift % v):,:],matrix[:(v - v_shift % v),:]))
matrix=np.hstack((matrix[:,(h - h_shift % h):],matrix[:,:(h - h_shift % h)]))
return matrix
# 在终端打印棋盘
def print_board(board):
out0 = ' '
for j in range(go.board_size):
out0 += chr(65+j) +' '
print(out0)
for j in range(go.board_size):
if go.board_size-j < 10:
out = ' ' + str(go.board_size-j) + ' '
else :
out = str(go.board_size-j) + ' '
# 根据横纵坐标位移参数打印平移后的棋盘（程序中实际的棋盘一直不变）
line = list(boardshift(board, v_shift, h_shift)[j])
for pt in line:
if pt == go.EMPTY:
out += '. '
elif pt == go.BLACK:
out += 'X '
else:
out += 'O '
out += str(go.board_size-j)
print(out)
print(out0)
if __name__ == '__main__':
# 实例化两个玩家
black = Player(color='Black')
white = Player(color='White')
# 开始一个棋局
run_a_game(black, white)
程序需要python3，没用到太特殊的库。我试过3.5、3.6和3.10，都可以运行。
目前只有字符界面，也只能左右互搏。在终端字符界面下程序运行看起来是这样的：
White move (Enter for PSAA, 0 for shift): i2 A B C D E F G H I J K L M N O P 16 . . . . . . . . . . . . . . . . 16 15 . . . . . . . . . . . . . . . . 15 14 . . . . . . . . . . . . . . . . 14 13 . . . . . . . . . . . . . . . . 13 12 . . O . . . . . . . . . . . . . 12 11 O X . . . . . . . . . . . . . . 11 10 X O X . . . . . . . . . . . . . 10 9 X O O X . . . . . . . . . . . . 9 8 . X O O X . . . . . . . . . . . 8 7 . . X O O X . . . . . . . . . . 7 6 . . . X O O X . . . . . . . . . 6 5 . . . . X O O X . . . . . . . . 5 4 . . . . . X O O X . . . . . . . 4 3 . . . . . . X O O X . . . . . . 3 2 . . . . . . . X O . . . . . . . 2 1 . . . . . . . . . . . . . . . . 1 A B C D E F G H I J K L M N O P Black move (Enter for PSAA, 0 for shift): 0 For board shift, input L/R/U/D0~16: u6 A B C D E F G H I J K L M N O P 16 X O X . . . . . . . . . . . . . 16 15 X O O X . . . . . . . . . . . . 15 14 . X O O X . . . . . . . . . . . 14 13 . . X O O X . . . . . . . . . . 13 12 . . . X O O X . . . . . . . . . 12 11 . . . . X O O X . . . . . . . . 11 10 . . . . . X O O X . . . . . . . 10 9 . . . . . . X O O X . . . . . . 9 8 . . . . . . . X O . . . . . . . 8 7 . . . . . . . . . . . . . . . . 7 6 . . . . . . . . . . . . . . . . 6 5 . . . . . . . . . . . . . . . . 5 4 . . . . . . . . . . . . . . . . 4 3 . . . . . . . . . . . . . . . . 3 2 . . O . . . . . . . . . . . . . 2 1 O X . . . . . . . . . . . . . . 1 A B C D E F G H I J K L M N O P Black move (Enter for PSAA, 0 for shift):
