みっつめ

ゾブリストハッシュを使うことによるコードの変更

『囲碁ディープラーニングプログラミング』の続きである。

goboard_slow.py をコピーして goboard.py とし、以下の部分を変更する。

GoString

最初のコード goboard_slow.py では、”set” を使って連を管理していた。

goboard.py
クラス GoString ( self, color, stones, liberties )
  プロパティ: self.color     = color
              self.stones    = set(stones)                 -- <1>
              self.liberties = set(liberties)              -- <2>

  メソッド: remove_liberty( self, point ) -- remove        -- <3>
            add_liberty( self, point )    -- add           -- <4>
            merged_with( self, go_string) -- | (論理和)    -- <5>
            num_liberties( self )         -- len
            __eq__( self, other )         -- isinstance 他

連を石と呼吸点の集合と捉え、その集合に対し、追加や削除をおこなっている。
<1> -- 石の集合をつくる。
<2> -- 呼吸点の集合をつくる。
<3> -- 石を集合から削除する。
<4> -- 呼吸点を集合から削除する。
<5> -- 2つの連を合体する。

今後はゾブリストハッシュを使って盤の状態ならびに石の状態を管理するので、
GoStringをそれに適応させる。

<1><2> — まず、連をsetによる追加削除可能な集合ではなくすため、frozensetを使う。
<3><4> — 削除と追加をハッシュを使ったものに変更する。
<5> — 変更の必要はない。

goboard.py(つづき)
# 石の連 GoString
#   color -- 石の色
#   stones -- 石の集合 setを使っている。集合をあらわすデータ型だそうだ。
#   liberties -- 呼吸点の集合
# (例)
#   ren1 = GoString(white, 3, 8) -- ren1は白で、3つの石があり、呼吸点は8個である。
#   ren1.wighout_liberty(point) -- 呼吸点を1つ削除する。
class GoString():
    def __init__( self, color, stones, liberties ):
        self.color = color
        self.stones = frozenset(stones)                    # <1>
        self.liberties = frozenset(liberties)
    # <1> frozenset -- 一度作成すると、追加削除はできない。

    # 呼吸点を削除
    # removeは集合型のメソッドなので使えない。変更する。
    def without_liberty( self, point ):
        new_liberties = self.liberties - set([point])                # <1>
        return GoString( self.color, self.stones, new_liberties )    # <2>
    # <1> 呼吸点の集合と、削除する要素の集合との、差集合をとる。
    # <2> 新しい呼吸点を使った連を作成する。

    # 呼吸点を追加
    # with_liberty -- 集合に要素を追加する
    def with_liberty( self, point ):
        new_liberties = sel.liberties | set([point])                 # <1>
        return GoString( self.color, self.stones, new_liberties )
    # <1> 今までの連と加えたい要素の集合との論理和

Board

Boardクラスは盤情報を管理する。
Boardクラスをハッシュを使ったものに変更する。

goboard.py(つづき)
# ゾブリストハッシュを使う
from dlgo import zobrist

# 盤面
# num_rows, num_cols -- 格子線の数
# _grid -- 盤面の情報を辞書リストでもっている。
#          keyは、Point(row=2, col=3)などのPoint。
#          値は、オブジェクトで、GoString情報をもっている
class Board():
    def __init__( self, num_rows, num_cols ):
        self.num_rows = num_rows
        self.num_cols = num_cols
        self._grid = {}                    # 辞書 -- {キー: 値, ...}
        self._hash = zobrist.EMPTY_BOARD         # <1>
    # _grid -- Pointをkeyとした辞書である。
    #          value には、GoStringが入っている。
    # <1> zobrist.py の中で EMPTY_BOARD は 0に設定されている。

place_stone は、石を置いて連を再構成するメソッドである。
石を置くということは、ハッシュを適用するということなので、それに合うように変更する。

goboard.py(つづき)
    # player -- (ex) Player.black
    # point -- (ex) Point(row=1, col=1)
    def place_stone( self, player, point ):
        assert self.is_on_grid(point)         # pointが盤上にあるかどうか
        assert self._grid.get(point) is None  # pointがまだ打たれていないかどうか
        adjacent_same_color = []              # 同じ色のリスト
        adjacent_opposite_color = []          # 相手の色のリスト
        liberties = []                        # 呼吸点のリスト
        # print( Point(3, 5).neighbors() )
        # [ Point(row=15, col=6), Point(row=17, col=6), Point(row=16, col=5), Point(row=16, col=7) ]
        for neighbor in point.neighbors():
            if not self.is_on_grid( neighbor ):                # <1>
                continue
            neighbor_string = self._grid.get( neighbor )       # <2>
            if neighbor_string is None:                        # <3>
                liberties.append( neighbor )
            elif neighbor_string.color == player:               # <4>
                if neighbor_string not in adjacent_same_color:
                    adjacent_same_color.append( neighbor_string )
                else:
                    if neighbor_string not in adjacent_opposite_color:
                        adjacent_opposite_color.append( neighbor_string )
        new_string = GoString( player, [point], liberties )      # <5>
        # <1> neighborが盤上の点ではなかったら、パス
        # <2> _grid.get( key ) -- 指定されたkeyがあれば、その連情報を返す。
        #                         なければ、Noneを返す。
        #       値は、GoStringである。
        # <3> もしneighbor_stringがNoneであれば、呼吸点のリストに追加
        # <4> もしneighbor_stringの色がプレイヤーと同じであれば
        #     adjacent_sama_color, adjacent_oppsite_colorにいれる
        # <5> 新しい連をつくる
        #
        for same_color_string in adjacent_same_color:                  # <6>
            new_string = new_string.merged_with( same_color_string )
        for new_string_point in new_string.stones:                     # <7>
            self._grid[ new_string_point ] = new_string

        self._hash ^= zobrist.HASH_CODE[ point, player ]               # <8>
        
        for other_color_string in adjacent_opposite_color:             # <9>
            replacement = other_color_string.without_liberty( point )
            if replacement.num_liberties:                              # <10>
                self._replace_string( other_color_string.without_liberty( point ))
            else:
                self._remove_string( other_color_string )
        # <6> 同じ色の隣接する連をマージする
        # <7> 新しくできた連のそれぞれのポイントに、連の情報をそれぞれセットする。
        # <8> この点とプレーヤーのハッシュコードを適用
        #     a ^= b -- 排他的論理和をとって、それを a に代入する。
        # <9> 敵の色の隣接する連の呼吸点を減らし、それを replacement とする。
        # <10> 敵の色の連の呼吸点があれば、それを減らし、敵の色の連の
        #     呼吸点が 0 ならば、その連をとりのぞく。

上記の中で、<8><9><10>が今回の変更である。
<8> — このハッシュを 排他的論理和することで、盤の状況を表現できる。
<9> — 石を置くことで、隣接点の相手の石は呼吸点を失う。
GoStringの without_libertyメソッドを使用。
<10> — _replace_string、_remove_string は、ハッシュを使ったメソッドで、
_replace_string は、新しいメソッドである。

goboard.py(つづき)
    # 連を更新する
    def _replace_string( self, new_string ):
        for point in new_string.stones:
            self._grid[ point ] = new_string

    # 連を取り除く
    # 連を取り除くと、相手の石が呼吸点を得ることができる
    # string -- 取られる連
    def _remove_string( self, string ):
        for point in string.stones:                             # <1>
            for neighbor in point.neighbors():                  # <2>
                neighbor_string = self._grid.get( neighbor )    # <3>
                if neighbor_string is None:
                    continue
                if neighbor_string is not string:               # <4>
                    self._replace_string( neighbor_string.with_liberty( point ))
            self._grid[ point ] = None                          # <5>

            self._hash ^= zobrist.HASH_CODE[ point, string.color ]  # <6>
    # <1> string.stones --- stonesはpointの集合
    # <2> point.neighbors() --- 隣の点のリスト
    # <3> neighbor_string -- 隣の連の情報
    # <4> neighbor_string が 取られる連でなかったら、相手の連の呼吸点の集合に追加する。
    # <5> 石を取り除いたので、そのポイントは None になる
    # <6> そのポイントにハッシュ値を XOR することで、そのポイントの石を
    #     取り除いた盤面を得ることができる。

現在のゾブリストハッシュを返すメソッドを追加。

goboard.py(つづき)
    # 盤の現在のゾブリストハッシュを返す
    def zobrist_hash( self ):
        return self._hash

GameState

GameState はゲームの状態を管理するクラスである。

goboard.py(つづき)
class GameState():
    def __init__( self, board, next_player, previous, move ):
        self.board = board                      # 盤面の情報
        self.next_player = next_player          # 次のプレーヤー
        self.previous_state = previous          # 前のゲーム状態
        self.last_move = move                   # 最後に行われた着手
        if self.previous_state is None:
            self.previous_states = frozenset()
        else:
            self.previous_states = frozenset(
                previous.previous_states |
                {( previous.next_player, previous.board.zobrist_hash())})  # <1>
    # <1> 盤が空の場合、self.previous_statesは空のイミュータブルなfrozensetです。
    #     それ以外の場合は、次のプレーヤーの色と直前のゲーム状態のゾブリストハッシュ
    #     を追加します。(p81)

この <1> の部分については、別項で詳しく述べる。

あと、変更部分は、「コウ」の部分である。

goboard.py(つづき)
    # player -- Player.black / Player.white
    # move -- Move.play(row, col)
    def does_move_violate_ko( self, player, move ):
        if not move.is_play:
            return False
        next_board = copy.deepcopy( self.board )           # <1>
        next_board.place_stone( player, move.point )       # <2>
        next_situation = ( player.other, next_board.zobrist_hash()) # <3>
        return next_situation in self.previous_states      # <4>
    # <1> 現在の盤をdeepcopyして、next_boardとする。
    # <2> next_boardに次の指し手を実行(石を置く)。
    # <3> next_board のハッシュと player.other をタプルにして
    #     next_situation とする。
    # <4> self.previous_states の中に next_situation が含まれていれば、
    #     True、そうでなければ False を返す。
    #     ハッシュ値が同じであるということは、二つが同じ配置であるということ。

あとは、この変更されたプログラムと人間が対戦できるようにする。

Utils.py に以下のコードを追加する。

utils.py
# 人間の入力をBoardのための座標に変換する
# coords -- C3 とか E7 などの文字列
def point_from_coords( coords ):
    col = COLS.index( coords[0] ) + 1
    row = int( coords[ 1: ])
    return gotypes.Point( row=row, col=col )

ボットと対局するためのプログラムは、以下。

human_v_bot.py
# human_v_bot.py
# 人間対ボットの対局プログラム(9路盤)

from dlgo import agent
from dlgo import goboard
from dlgo import gotypes
from dlgo.utils import print_board, print_move, point_from_coords
from six.moves import input

def main():
    board_size = 9
    game = goboard.GameState.new_game( board_size )
    bot = agent.RandomBot()

    while not game.is_over():
        print( chr(27) + "[2J")
        print_board( game.board )
        if game.next_player == gotypes.Player.black:          # <1>
            human_move = input('-- ')                         # <2>
            point = point_from_coords( human_move.strip() )   # <3>
            move = goboard.Move.play( point )
        else:
            move = bot.select_move( game )                    # <4>
        print_move( game.next_player, move )                  # <5>
        game = game.apply_move( move )
# <1> 黒は人間の手番
# <2> 標準入力から文字列を受け取る
# <3> strip() -- 空白や改行を削除する
# <4> bot の手番
# <5> print_move -- utils.py の中にある関数。指し手を表示する。

if __name__ == '__main__':
    main()

対戦する。

$ python3 human_v_bot.py

以下は、xが黒(人間)、oが白(ボット)で、6手すすんだ局面である。

 9 ..o......
 8 .........
 7 ......x..
 6 .....o...
 5 .........
 4 ..x......
 3 ...x.....
 2 .........
 1 .......o.
   ABCDEFGHJ
-- 

ボットはランダムに指し手を選んでいる。

『囲碁ディープラーニングプログラミング』

Max Pumperia、Kevin Ferguson 著
山岡忠夫 訳
マイナビ出版
2019年4月22日 初版第1刷