公益网站 速度稍慢 请您谅解

作者: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)%self.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):

返回谈棋论道

Copyright © 2014-2022 daoqi.club
 陕西杆粒生物科技有限公司赞助  GS  GST
道棋对局