囲碁の終局図から地を求める

ニューラルネットワークに囲碁を学習させようとしている．前回はとりあえずニューラルネットワークを使ってみるということをしてみた．

学習を始めるには，学習用のデータが必要となる．棋譜はSGFファイル形式でインターネットに転がっているが，人間の棋譜は半端なところで終わっている．どこが自分の地かということにすでに経験的判断が必要になる．とくに日本ルールは終局がwell-definedでないという話がでるほど，終局が難しい．最初のステップとして，終局図から目算できるようにさせたい．

したがって，終局状態の配置と領地の分布の対応のデータが必要なのだが，これを得るのに結構苦労した．

終局しているのだから，モンテカルロ法のプレイアウトのように適当に打っても結果は変わらないのではないかと思ったら全然そんなことはなかった．わざわざプレイアウトをするコード書いたのだけど，意味なかった．

結局，GNU Goで終局状態から更に局面を進めることにした．以下のシェルスクリプトで結果が誰の目にも明らかになるまで局面を進めてくれる．

sgf=`cat $1`
prev=0
while true; do
    sgf=`echo $sgf | gnugo --chinese-rules --play-out-aftermath --capture-all-dead -l - -o - 2> tmp`
    cat tmp 1>&2
    play=`cat tmp | awk '{print $4}'`
    if [ $play = "PASS" ]; then
        if [ $prev -eq 1 ]; then break; fi
        prev=1
    else
        prev=0
    fi
done
echo $sgf

before.sgfに局面が追加されたものafter.sgfに出力される．

$ sh playout.sh before.sgf > after.sgf

左がboforeで右がafter

ここから，さらに地を塗り潰したものが最終的に欲しいものだ．地を塗りつぶすコードも，作りかけで汚いが参考までに貼っておく．モンテカルロ法のプレイアウトの痕跡も残っている．参考にあるモンテカルロ法のサンプルコードをPythonで書きなおしただけだけど．

参考

GNU Goに純碁を打たせる

コンピュータ囲碁 〜 モンテカルロ法の理論と実践 〜 実践編のサンプル一覧

地を埋めるコード

import copy
import random
import sys

EMPTY = 0
BLACK = 1
WHITE = 2
WALL = 3

def flip_color(color):
    return WHITE if color == BLACK else BLACK

class GoError(Exception):
    pass

class SuicidePlayError(GoError):
    pass

class KoError(GoError):
    pass

class EyeBreakingError(GoError):
    pass

class StoneAlreadyExistsError(GoError):
    pass

class Board():
    SIZE = 19
    WIDTH = SIZE + 2
    DIR4 = [+1, -1, +WIDTH, -WIDTH]
    
    def __init__(self):
        self.board = [
        3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
        3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3,
        3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3,
        3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3,
        3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3,
        3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3,
        3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3,
        3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3,
        3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3,
        3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3,
        3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3,
        3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3,
        3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3,
        3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3,
        3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3,
        3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3,
        3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3,
        3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3,
        3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3,
        3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3,
        3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
        ]
        self.teban = BLACK
        self.hama = [0, 0]
        self.ko = 0
        self.komi = 6.5
        
    def get_teban(self):
        return self.teban

    def get_color(self, tz):
        return self.board[tz]
    
    def count_dame(self, tz):
        check_board = []
        color = self.board[tz]
    
        def count_dame_sub(tz_, dame, stone):
            check_board.append(tz_)
            stone += 1
            for direction in self.DIR4:
                z = tz_ + direction
                if z in check_board:
                    continue
                if self.board[z] == 0:
                    check_board.append(z)
                    dame += 1
                if self.board[z] == color:
                    dame, stone = count_dame_sub(z, dame, stone)
            return dame, stone

        return count_dame_sub(tz, 0, 0)
    
    def kesu(self, tz, color):
        self.board[tz] = 0
        for direction in self.DIR4:
            z = tz + direction
            if self.board[z] == color:
                self.kesu(z, color)
    
    def is_eye(self, z, color):
        if self.board[z] != EMPTY:
            return False
        num_friend = 0
        num_wall = 0
        for direction in self.DIR4:
            c = self.board[z + direction]
            if c == color:
                num_friend += 1
            elif c == WALL:
                num_wall += 1
        if num_friend + num_wall == 4:
            return True
        else:
            return False

    def move(self, play, color, allow_eyebreak=True):
        if play == 0:
            self.ko = 0
            self.teban = flip_color(self.teban)
            return
    
        around_dame = [0, 0, 0, 0]
        around_stone = [0, 0, 0, 0]
        around_color = [0, 0, 0, 0]
        
        enemy_color = flip_color(color)
    
        num_empty = 0
        num_wall = 0
        num_safe_friend = 0
        take_sum = 0
    
        for i in range(4):
            z = play + self.DIR4[i]
            c = self.board[z]
            if c == 0:
                num_empty += 1
                continue
            if c == 3:
                num_wall += 1
                continue
            dame, stone = self.count_dame(z)
            around_dame[i] = dame
            around_stone[i] = stone
            around_color[i] = c
            if c == enemy_color and dame == 1:
                take_sum += stone
                ko_kamo = z
            if c == color and dame >= 2:
                num_safe_friend += 1
    
        # Suiside play
        if take_sum == 0 and num_empty == 0 and num_safe_friend == 0:
            raise SuicidePlayError(get_xy(play))
        # Ko
        if play == self.ko:
            raise KoError(get_xy(play))
        # Eye (Not illegal)
        if num_wall + num_safe_friend == 4 and not allow_eyebreak:
            raise EyeBreakingError(get_xy(play))
        # Stone already exists
        if self.board[play] != EMPTY:
            raise StoneAlreadyExistsError(get_xy(play))

        for i in range(4):
            z = play + self.DIR4[i]
            if (around_color[i] == enemy_color and
                around_dame[i] == 1 and
                self.board[z] != EMPTY):  # Stones are takable
                self.kesu(z, enemy_color)
                self.hama[color - 1] += around_stone[i]
        
        # Put a stone
        self.board[play] = color

        # Judge if ko or not
        dame, ishi = self.count_dame(play)
        if take_sum == 1 and ishi == 1 and dame == 1:
            self.ko = ko_kamo
        else:
            self.ko = 0

        self.teban = flip_color(self.teban)

    def print_board(self):
        strs = [". ", "@ ", "O "]
        for y in range(self.SIZE):
            for x in range(self.SIZE):
                z = get_z(x, y)
                s = strs[self.board[z]]
                print s,
            print ""

def get_z(x, y):
    assert 0 <= x < Board.SIZE
    assert 0 <= y < Board.SIZE
    return (y + 1) * Board.WIDTH + (x + 1)

def get_xy(z):
    assert 0 <= z < Board.WIDTH ** 2
    if z == 0:
        return (0, 0)
    y = z / Board.WIDTH
    x = z - y * Board.WIDTH
    return (x, y)

def playout(color, board):
    prev_play = 0  # Previous play
    loop_max = Board.SIZE ** 2
    for _ in range(loop_max):
        # Include all empty points to candidates
        candidates = []
        for y in range(Board.SIZE):
            for x in range(Board.SIZE):
                z = get_z(x, y)
                if board.get_color(z) != EMPTY:
                    continue
                candidates.append(z)

        while True:
            if candidates:
                play = random.choice(candidates)
            else:
                play = 0  # Pass play
            try:
                board.move(play, color, False)
                break
            except StoneAlreadyExistsError:
                # Sanity check
                raise
            except GoError:
                pass
            candidates.remove(play)

        # Continuous pass play
        if play == 0 and prev_play == 0: 
            break
        prev_play = play
        color = flip_color(color)

def fillout_territory(board):
    # Include all empty points to candidates
    candidates = []
    for y in range(Board.SIZE):
        for x in range(Board.SIZE):
            z = get_z(x, y)
            if board.get_color(z) != EMPTY:
                continue
            candidates.append(z)
    while candidates:
        z = random.choice(candidates)
        for direction in Board.DIR4:
            c = board.get_color(z + direction)
            if c == BLACK or c == WHITE:
                board.board[z] = c
                candidates.remove(z)
                break
    
    score_black = 0
    score_white = 0
    for y in range(Board.SIZE):
        for x in range(Board.SIZE):
            z = get_z(x, y)
            c = board.get_color(z)
            if c == BLACK:
                score_black += 1
            elif c == WHITE:
                score_white += 1
    return score_black - score_white - board.komi

class Sgf():
    tesuu_now = 0
    
    def __init__(self, sgf_str): 
        sgf_str = sgf_str.lstrip('(')
        sgf_str = sgf_str.rstrip(')')
        sgfdatas = sgf_str.split(';')[1:]

        header = sgfdatas[0].split(']')[:-1]
        self.props = {}
        header = map(lambda s: s.split('['), header)
        map(lambda l: self.props.update({l[0]:l[1]}), header)
        
        self.plays = sgfdatas[1:]

    def get_result(self):
        result_str = self.props['RE']
        result = float(result_str[1:])
        if result_str[0] == 'W':
            result = - result
        return result

    def get_komi(self):
        return float(self.props['KM'])
    
    def get_tesuu(self):
        return len(self.plays)
    
    def next_play(self):
        if self.tesuu_now >= len(self.plays):
            return '', -1, -1  # When the game is finished
        color_str, play_str = self.plays[self.tesuu_now].split(']')[0].split('[')
        if play_str == '':
            # Pass
            play_x = -1
            play_y = -1
        else:
            play_x = ord(play_str[0]) - ord('a')
            play_y = ord(play_str[1]) - ord('a')
        self.tesuu_now += 1
        return color_str, play_x, play_y

def apply_sgf(board, sgf_str, tesuu=-1):
    s = Sgf(sgf_str)
    b.komi = s.get_komi()
    if tesuu < 0:
        tesuu = s.get_tesuu()
    for _ in range(tesuu):
        color_str, play_x, play_y = s.next_play()
        if color_str == 'B':
            color = BLACK
        elif color_str == 'W':
            color = WHITE
        else:
            raise TypeError('A stone color of a play is imvalid: ' + color_str)
        if play_x >= 0 and play_y >= 0:
            play = get_z(play_x, play_y)
        else:
            play = 0
        board.move(play, color)

def append_sgf(sgf_str, board_old, board_new):
    strs = [sgf_str.strip().rstrip(')')]
    for y in range(Board.SIZE):
        for x in range(Board.SIZE):
            z = get_z(x, y)
            if board_new.board[z] != board_old.board[z]:
                c = 'B' if board_new.board[z] == BLACK else 'W'
                strs.append(';%s[%s%s]C[fillout territory]' % (c, chr(x + ord('a')),
                                           chr(y + ord('a'))))
    strs.append(')')
    return ''.join(strs)

if __name__ == '__main__':
    sgf_str = sys.stdin.read()
    b = Board()
    apply_sgf(b, sgf_str)
    b_copy = copy.deepcopy(b)
    score = fillout_territory(b)
    print append_sgf(sgf_str, b_copy, b)