2020幻影圍棋 第三天圍棋規則子產品（一）

圍棋規則其實很簡單，首先每個棋子會有氣，相連的一片棋子共用氣，那麼基于這個規則我們可以構造這樣一個Group類：

class Group(namedtuple(
    'Group',
    ['id', 'stones', 'liberties', 'color']
)):
    """

    ++++++
    ++..++
    ++..++
    +*++++
    上面那些點就構成了一個群
    群: 一個群就是一大片連着的相同顔色的棋子
    :stones 群内棋子的集合
    :liberties 群周圍相鄰且沒有棋子的點的集合
    :color 群内棋子的顔色
    """

    def __eq__(self, other):
        return self.stones == other.stones and self.liberties == other.liberties and self.color == other.color

           

這個群是一個命名元組類，Group是這個命名元組的名稱，後面接了他的四個屬性。

基于這個資料結構我們可以構造一個氣追蹤器類，用于記錄和更新棋盤上棋子的氣。

class LibertyTracker(object):
    @staticmethod
    def newTrackerFromBaseBoard(board=gf.Board.getStaticBaseBoard())
    def __init__(self, groupIndexMap=None, groups=None, librtyCacheMap=None, maxGroupId=1)
    def __deepcopy__(self, memodict={})
    def addStone(self, color, point, phantom=True)
    def _handleCaptures(self, capturedStones)
    def _createGroup(self, color, point, liberties)
    def _delGroup(self, groupId)
    def _captureGroup(self, groupId, phantom)
    def _mergeGroup(self, group1Id, group2Id)
    def _updateLiberties(self, groupId, add=None, remove=None)
           

首先來看這個靜态方法，這個靜态方法用于根據目前棋面生産出LibertyTrakcer:

@staticmethod
    def newTrackerFromBaseBoard(board=gf.Board.getStaticBaseBoard()):
        """
        :param board 預設為基礎棋盤。
        從基礎棋盤上建立自由度追蹤器
        :return: LibertyTracker
        """
        baseBoard = np.copy(board)
        curGroupId = 0
        libTracker = LibertyTracker()
        for color in (WHITE, BLACK):
            while color in baseBoard:
                curGroupId += 1
                foundColor = np.where(baseBoard == color)
                # point的值為第一個點
                point = foundColor[0][0], foundColor[1][0]
                chain, reached = findReached(point=point, baseBoard=baseBoard)
                # 相鄰且為EMPTY的點的集合
                liberties = set(r for r in reached if baseBoard[r] == EMPTY)
                newGroup = Group(curGroupId, chain, liberties, color)
                libTracker.groups[curGroupId] = newGroup
                for c in chain:
                    libTracker.groupIndexMap[c] = curGroupId
                #在另一張圖上标注這裡已經有棋子了
                placeStones(baseBoard, FILL, chain)
        libTracker.maxGroupId = curGroupId

        libertyCounts = np.zeros([SIZE, SIZE], dtype=np.uint8)
        for group in libTracker.groups.values():
            # 一個群的自由度
            libNum = len(group.liberties)
            for s in group.stones:
                libertyCounts[s] = libNum
        libTracker.libertyCacheMap = libertyCounts

        return libTracker
           

該方法會周遊棋盤上的棋子，用findReached方法:

def findReached(point, baseBoard=gf.Board.baseBoard):
    """
    深搜
     傳回目前點相同顔色(WHITE,BLACK,EMPTY)所連成的鍊以及相鄰不同顔色的集合(WHITE,BLACK,EMPTY)
    :param baseBoard:基礎棋盤(二維數組)
    :param point:目前點(元組對象)
    :return: sameColorChain: 相同顔色連成的一片點的集合 diffColorReached: 相鄰不同顔色的點的集合
    """
    if isinstance(point, gf.Point):
        point = point.toTuple()
    color = baseBoard[point]
    sameColorChain = set([point])
    diffColorReached = set()
    frontier = [point]
    while frontier:
        cur = frontier.pop()
        sameColorChain.add(cur)
        for p in NEIGHBORS[cur]:
            if baseBoard[p] == color and not p in sameColorChain:
                frontier.append(p)
            elif baseBoard[p] != color:
                diffColorReached.add(p)
    return sameColorChain, diffColorReached

           

findReached方法用深搜的方法得到一個群的集合，以及群周圍一圈位置的集合。

LibertyTrakcer的構造函數：

def __init__(self, groupIndexMap=None, groups=None, librtyCacheMap=None, maxGroupId=1):
        """
        一個"自由度追蹤器"類,
        :param groupIndexMap: 一個棋盤(群的索引, 二維數組)，上面用不同的數字(ID)标明不同的群 例如
                                1 1 1 1
                                1 2 2 1
                                1 2 1 1
        :param groups: 一個字典, 根據群的ID傳回群
        :param librtyCacheMap: 記錄每個群的自由度(周圍相鄰且為EMPTY的點的數量, 二維數組)
        :param maxGroupId: 記錄ID最大的群的ID
        """
        self.groupIndexMap = groupIndexMap if groupIndexMap is not None else -np.ones([SIZE, SIZE], dtype=np.int16)
        self.groups = groups or {}
        self.libertyCacheMap = librtyCacheMap if librtyCacheMap is not None else np.zeros([SIZE, SIZE], dtype=np.uint8)
        self.maxGroupId = maxGroupId