前回

今回の目標

今までの機械学習は、まず実行速度の速いc/c++でデータを作成し、ライブラリの豊富なPythonで学習を行うといった方法をとっていました。しかしそれでは学習に必要なデータをパソコン上に保存しなければならず、これが無視できない容量になりそうなのでこの際データ集めもPythonで行うことにしました。
Pythonでのオセロは10で行っていますが、BitBoardを使用していないこと、またクラスでないためデータづくりがしづらそうだと考え作り直しました。

ここから本編

まず、盤面を記録しておくデータ型としてPythonはint型しか選べませんが、自分の環境ではintは32ビットでしたのでnumpyのint64を使おうと考えました。
しかしnumpyのint64はビットシフトに対応していなかったため、やむなく組込み32ビットint2つx黒と白の2つの、計4つの整数で盤面を記録することにしました。
また今回、かなりデータ型を意識したためいちいち注記しています。Pythonでデータ型を意識するのは新鮮で楽しかったです。

使用ライブラリ

組込みのrandomのみです。

osero.py

from random import randint

クラス変数及びコンストラクタ

PLAY_WAYがc++でも使っていたように思考方法を指定します。Pythonには列挙型がないため人力列挙しました。
think配列内に思考方法の関数を入れ、この配列番号をPLAY_WAYで指定します。その番号がblack_methodおよびwhite_methodに格納されます。
setup関数は最初の盤面状態を作っているだけです。黒が二個と白が二個中央に置かれているあの状態です。
b_uが黒の上側(盤面1～4行の1～8列)、b_dが黒の下側(盤面5～8行の1～8列)、w_uが白の上側、w_dが白の下側です。

osero.py

class osero:
    PLAY_WAY = {\
        "human": 0,
        "random": 1,
        "nhand": 2,
        "nhand_custom": 3,
        "nleast": 4,
        "nmost": 5
    }
    
    def __init__(self, black_method, white_method,\
                 goal_n=[1, 1]):
        self.think = [\
            self.human,
            self.random,
            self.nhand,
            self.nhand_custom,
            self.nleast,
            self.nmost
        ]
        self.black_method = black_method
        self.whtie_method = white_method
        self.setup()
    
    def setup(self) -> None:
        self.turn = True
        self.bw = {"b_u": 0x10000000,
                   "b_d": 0x8,
                   "w_u": 0x8000000,
                   "w_d": 0x10}

printb

盤面表示関数。
デバッグ用ですので実行効率は無視し、とにかく分かりやすく作りました。
最初に上側をプリントし、その後下側をプリントしています。

osero.py

    def printb(self) -> None:
        print(end="  ")
        for i in range(8):
            print(" %d " % (i + 1), end="")
        print("\n -------------------------")
        
        num = 1
        for i in range(32):
            if i % 8 == 0:
                print("%d" % ((i >> 3) + 1), end="")
            if self.bw["b_u"] & num:
                print("|〇", end="")
            elif self.bw["w_u"] & num:
                print("|●", end="")
            else:
                print("|  ", end="")
            if i % 8 == 7:
                print("|\n -------------------------")
            num = num << 1
        
        num = 1
        for i in range(32):
            if i % 8 == 0:
                print("%d" % ((i >> 3) + 5), end="")
            if self.bw["b_d"] & num:
                print("|〇", end="")
            elif self.bw["w_d"] & num:
                print("|●", end="")
            else:
                print("|  ", end="")
            if i % 8 == 7:
                print("|\n -------------------------")
            num = num << 1

popcount

c言語丸写しです。
32ビットver。

osero.py

    def popcount(self, now: int) -> int:
        now = now - ((now >> 1) & 0x55555555)
        now = (now & 0x33333333) + ((now >> 2) & 0x33333333)
        now = (now + (now >> 4)) & 0x0f0f0f0f
        now = now + (now >> 8)
        now = now + (now >> 16)
        
        return now & 0x7f

check_all

置ける箇所が一か所でもあるかどうか調べる関数。
今までとほぼ同じ。

osero.py

    def check_all(self) -> bool:
        for i in range(8):
            for j in range(8):
                if self.check(i, j, self.bw, self.turn):
                    return True
        
        return False

human

置く場所を人間が指定する関数。
こちらも今までとほぼ同じ。

osero.py

    def human(self) -> None:
        while True:
            line = input("line:\t")
            col = input("col:\t")
            try:
                line = int(line)
                col = int(col)
            except:
                line, col = -1, -1
            if self.check(line - 1, col - 1, self.bw, self.turn):
                break
            print("can't put that place.once input.")
        self.put(line - 1, col - 1, self.bw, self.turn)

random

ランダムに置く関数。
特筆することはなし。

osero.py

    def random(self) -> None:
        while True:
            line = randint(0, 8)
            col = randint(0, 8)
            if self.check(line, col, self.bw):
                break
        self.put(line, col, self.bw, self.turn)

count_last

最後に試合結果を表示する関数。
どうせ継承先で上書きするので適当。

osero.py

    def count_last(self) -> None:
        black = self.popcount(self.bw["b_u"])\
                + self.popcount(self.bw["b_d"])
        white = self.popcount(self.bw["w_u"])\
                + self.popcount(self.bw["w_d"])
        
        print("black: %d\nwhite: %d" % (black, white))
        if black > white:
            print("black win!")
        elif black < white:
            print("white win!")
        else:
            print("draw!")

その他の思考方法

まだ作っていませんが、必要があれば作ります。

osero.py

    def nhand(self) -> None:
        pass
    
    def nhand_custom(self) -> None:
        pass
    
    def nleast(self) -> None:
        pass
    
    def nmost(self) -> None:
        pass

check

指定した場所に置けるかどうか調べる関数。
今回(というより毎回)最も苦戦したのがcheck関数とput関数です。
置ける場所があるかどうかは、例えば5行13列の次は5行4列のように、一か所ずつ見ながら調べます。しかし盤面が二つに割かれているため、今までのような方法で調べることはできず、上下を移動する必要があります。

そのアルゴリズムは以下の通り。

調べたい行と列の番号、そして調べたい盤面とターンを受け取る。
行番号または列番号が盤面範囲外の場合はFalseを返す。
指定した場所に既に石が置かれていないか調べる。
指定したターンから、自分と相手の色を決める。
指定した場所から八方向について、ひっくりかえせる石があるか調べる。
一つもひっくりかえせる場所がなかった場合、Falseを返す。

5の、「ひっくりかえせる石があるかどうか調べる」についてその手順を詳しく説明します。

八方向調べるため、縦と横にそれぞれ-1方向、0方向、1方向と場所を移しながら調べる。なお、どちらも0方向の場合は調べない。
調べる位置を指定するためのローカル変数line_xとcol_yを定義する。中身はそれぞれline + xとcol + y。
もしline_xまたはcol_yの値が即座に盤面範囲外に出た場合、調べたいと指定した場所は盤面の外周部であり、その外に行こうとしていると判断しcontinueする。
line_xが4未満の場合は盤面上部を調べるため、盤面下部かどうかを格納する変数is_dにFalseを代入する(つまりこれから上部を調べることを明確にしておく)。
逆にline_xが4以上の際はline_xの値から4を引いた後、is_dにTrueを代入し、下部を調べることを明確にしておく。
もしline_x行col_y列(つまり、指定した座標の隣)に相手の石があった場合、while文の中に入る。以下、12番までwhile文の中身。
もしline_x + xが4以上で、なおかつis_dがFalseなら(つまり今まで調べていたのが上側で、ここから下側に移る場合は)、line_xを0にしis_dをTrueにする(次は下側の1行目、つまり盤面全体の5行目を調べると設定する)。
もしline_x + xが0未満で、なおかつis_dがTrueなら(つまり今まで調べていたのが下側で、ここから上側に移る場合は)、line_xを3にしis_dをFalseにする(次は上側の4行目、つまり盤面全体の4行目を調べると設定する)。
もし上記の状況以外でline_xが4以上または0未満となった場合、全体の8行目のさらに下、または1行目のさらに上を調べようとしていると判断できるのでbreakする。
それ以外の場合は普通にline_xにxを足す。
col_yにyを足す。
もしその先に自分の石があった場合、ひっくりかえせる石があると判定できるのでTrueを返す。
ひっくりかえせる石が一つもなかったらFalseを返す。

osero.py

    def check(self, line: int, col: int, now: dict, turn: bool) -> bool:
        # 範囲内か調べる
        if line >= 8 or line < 0\
           or col >= 8 or col < 0:
            return False
        
        # 既に石が置かれていないか調べる
        place = (line << 3) + col
        if line < 4:
            if now["b_u"] & 1 << place\
               or now["w_u"] & 1 << place:
                return False
        else:
            if self.bw["b_d"] & 1 << (place - 32)\
               or now["w_d"] & 1 << (place - 32):
                return False
        
        # ターンから自分と相手の色決め
        if turn:
            my = ["b_u", "b_d"]
            opp = ["w_u", "w_d"]
        else:
            my = ["w_u", "w_d"]
            opp = ["b_u", "b_d"]
        
        # ひっくり返せる石があるか調べる
        for x in range(-1, 2):
            for y in range(-1, 2):
                if x == 0 and y == 0:
                    continue
                line_x = line + x
                col_y = col + y
                if line_x < 0 or col_y < 0\
                   or line_x >= 8 or col_y >= 8:
                    continue
                if line_x < 4:
                    is_d = False
                else:
                    line_x = line_x - 4
                    is_d = True
                while now[opp[is_d]] & 1 << (line_x << 3) + col_y\
                      and 0 <= y + col_y and y + col_y < 8:
                    if line_x + x >= 4 and not is_d:
                        line_x = 0
                        is_d = True
                    elif line_x + x < 0 and is_d:
                        line_x = 3
                        is_d = False
                    elif line_x + x >= 4 or line_x + x < 0:
                        break
                    else:
                        line_x += x
                    col_y += y
                    if now[my[is_d]] & 1 << ((line_x << 3) + col_y):
                        return True
                
        return False

put

指定した場所に石を置く関数。
なおこの関数は従来通り、check関数で「この場所に置ける！」ということを確認したうえで呼び出されることを想定しています。

アルゴリズムは以下の通り。

置きたい行と列の番号、そして置きたい盤面とターンを受け取る。
指定したターンから、自分と相手の色を決める。
指定した場所に置く。
八方向について、ひっくり返せる石を調べひっくり返す。

ひっくり返すアルゴリズムについて説明します。check関数ではひっくりかえせる場所が一か所でもあればその時点で終了しますが、put関数はひっくりかえせる場所をすべてひっくり返すまで止まりません。なお、盤面の上下移動に関してはcheck関数で説明したので省きます。

八方向調べるため、縦と横にそれぞれ-1方向、0方向、1方向と場所を移しながら調べる。なお、どちらも0方向の場合は調べない。
ひっくり返す場所を記録しておくための配列inverを定義する。なお0番目が上側の、1番目が下側のひっくりかえせる場所。
調べる位置を指定するためのローカル変数line_xとcol_yを定義する。中身はそれぞれline + xとcol + y。
もしline_xまたはcol_yの値が即座に盤面範囲外に出た場合、調べたいと指定した場所は盤面の外周部であり、その外に行こうとしていると判断しcontinueする。
place変数にこれから調べる場所を代入する。
調べる場所に相手の石があった場合、while文に入る。以下、8番までwhile文内の動作。
inverにplaceを足す。
次の位置を調べるため、line_x及びcol_yを次の位置に更新。
もし相手の石の先が自分の石だった場合、間にあった相手の石はひっくりかえせるので、inverに保存しておいた位置で足したり引いたりして盤面を更新する。

osero.py

    def put(self, line: int, col: int, now: dict, turn: bool) -> None:
        # ターンから自分と相手の色決め
        if turn:
            my = ["b_u", "b_d"]
            opp = ["w_u", "w_d"]
        else:
            my = ["w_u", "w_d"]
            opp = ["b_u", "b_d"]
            
        # 指定した場所に置く
        if line < 4:
            is_d = False
            now[my[is_d]] += 1 << (line << 3) + col
        else:
            is_d = True
            now[my[is_d]] += 1 << ((line - 4) << 3) + col
        
        # ひっくりかえせる石をひっくり返す
        for x in range(-1, 2):
            for y in range(-1, 2):
                if x == 0 and y == 0:
                    continue
                inver = [0, 0]
                line_x = line + x
                col_y = col + y
                if line_x < 0 or line_x >= 8\
                   or col_y < 0 or col_y>= 8:
                    continue
                if line_x < 4:
                    is_d = False
                else:
                    line_x = line_x - 4
                    is_d = True
                place = 1 << (line_x << 3) + col_y
                while now[opp[is_d]] & place\
                      and 0 <= y + col_y and y + col_y < 8:
                    inver[is_d] = inver[is_d] | place
                    if line_x + x >= 4 and not is_d:
                        line_x = 0
                        is_d = True
                    elif line_x + x < 0 and is_d:
                        line_x = 3
                        is_d = False
                    elif line_x + x > 4 or line_x + x < 0:
                        break
                    else:
                        line_x += x
                    col_y += y
                    place = 1 << (line_x << 3) + col_y
                if now[my[is_d]] & place:
                    now[my[is_d]] += inver[is_d]
                    now[my[not is_d]] += inver[not is_d]
                    now[opp[is_d]] -= inver[is_d]
                    now[opp[not is_d]] -= inver[not is_d]

play

試合を実行する関数。
こちらもcount_last同様、どうせ継承先で上書きするので適当です。

osero.py

    def play(self) -> None:
        can, old_can = True, True
        
        self.printb()
        
        can = self.check_all()
        while can or old_can:
            if can:
                if self.turn:
                    print("black turn")
                    self.think[self.black_method]()
                else:
                    print("white turn")
                    self.think[self.whtie_method]()
                self.printb()
            else:
                print("not place. once ", end="")
            self.turn = not self.turn
            old_can = can
            can = self.check_all()
            
        self.count_last()

実際にやってみた

デバッグ作業は面倒なので何度か自動対戦させて不自然な動作がないか調べました。

osero.py

o = osero(osero.PLAY_WAY["random"], osero.PLAY_WAY["random"])
o.play()

フルバージョン

次回は

機械学習を進めたいと思います。

次回