コンピュータとオセロ対戦27 ～勝敗予測～

前回

今回の目標

盤面を与えて、そこから最終結果が正確に割り出せるようにしたいです。

ここから本編

なぜ盤面を見てそこから最終結果を割り出したいか説明します。
今までは盤面を見てどちらが有利かを考えていました。なぜなら、自分が石を置いた時に、自分が最も有利になれる場所を知る必要があったからです。そのために戦況を正しく計算できる評価値が必要でした。
しかしこれは最適な方法ではないと考えます。理由は、実際にオセロをプレイする際、そんな固定的な考え方をしないからです。
例えば、評価値では四隅が高得点、そのすぐ隣が低い点となっていますが、実際にはこの限りではありません。すでに相手または自分が隅をとっている場合は、そのすぐ隣をとったとしても、隅を新たに相手にとられるという心配がありませんから気にしなくていいわけです。
しかし戦況に合わせ逐一使用する評価値を変えるというのは現実的ではありません。膨大な量の評価値が必要になると思われるからです。
そのため、「より自分が有利になる位置に置く」のではなく、「盤面から最終結果を予測し、よりよい最終結果になりやすい位置に置く」ことで、様々な状況に対応できるようになるのではないかと考えました。

ちなみに学習はJavaのtribuoで行う予定でしたが、環境構築でハマったのでもうPython使います。

BitBoard

オセロをするためのスーパークラスです。
まず、これを作った時に保留していた、種々の思考方法関数を作りました。

nhand

nhandを指定した際は、評価値すべて1のnhand_customをさせることにしました。
コンストラクタで評価値を作ります。

BitBoard.py

    def nhand(self) -> None:
        self.nhand_custom()

BitBoard.py

    def __init__(self, black_method, white_method,\
                 read_goal=[1, 1], eva=None):
        self.think = [\
            self.human,
            self.random,
            self.nhand,
            self.nhand_custom,
            self.nleast,
            self.nmost
        ]
        if (black_method == osero.PLAY_WAY["nhand_custom"]\
            or white_method == osero.PLAY_WAY["nhand_custom"])\
            and eva is None:
            raise ValueError("designate eva")
        self.black_method = black_method
        self.white_method = white_method
        self.read_goal = read_goal
        self.eva = eva
        if black_method == osero.PLAY_WAY["nhand"]:
            self.eva[0] = [1] * 64
        if white_method == osero.PLAY_WAY["nhand"]:
            self.eva[1] = [1] * 64
        self.setup()

nhand_custom

c++で作ったものとほぼ同じです。

BitBoard.py

    def nhand_custom(self) -> None:
        max_score = -100.0
        line_ans, col_ans = [-1], [-1]
        place_num = 0
        is_d = False

        for i in range(8):
            for j in range(8):
                if self.check(i, j, self.bw, self.turn):
                    board_leaf = deepcopy(self.bw)
                    self.put(i, j, board_leaf, self.turn)
                    score = self.board_add(\
                        board_leaf,
                        not self.turn,
                        1
                    )
                    if score > max_score:
                        max_score = score
                        place_num = 0
                        line_ans = [i]
                        col_ans = [j]
                    elif score == max_score:
                        place_num += 1
                        line_ans.append(i)
                        col_ans.append(j)

        if place_num:
            place = randint(0, place_num)
            line_ans[0] = line_ans[place]
            col_ans[0] = col_ans[place]

        self.put(line_ans[0], col_ans[0], self.bw, self.turn)

    def board_add(self, now: dict, turn: bool, num: int) -> float:
        if num == self.read_goal[self.turn]:
            return self.count(now, self.turn)

        score = 0
        place_num = 0
        for i in range(8):
            for j in range(8):
                if self.check(i, j, now, turn):
                    place_num += 1
                    board_leaf = deepcopy(now)
                    self.put(i, j, board_leaf, turn)
                    score += self.board_add(\
                        board_leaf,
                        not turn,
                        num + 1
                    )

        if place_num:
            return score / place_num
        else:
            return self.count(now, self.turn)

nleast

c++で作ったものとほぼ同じですが、check_place関数にミスがあったので修正しました。
コメント部分が、今まではもし置く場所がなかった際に初期化していない数字place_sumをreturnしていました。

BitBoard.py

    def nleast(self) -> None:
        min_place_num = 100
        line_ans, col_ans = [-1], [-1]
        place_num = 0

        for i in range(8):
            for j in range(8):
                if self.check(i, j, self.bw, self.turn):
                    board_leaf = deepcopy(self.bw)
                    self.put(i, j, board_leaf, self.turn)
                    place = self.check_place(\
                        board_leaf,
                        not self.turn,
                        not self.turn,
                        1
                    )
                    if place < min_place_num:
                        min_place_num = place
                        place_num = 0
                        line_ans = [i]
                        col_ans = [j]
                    elif place == min_place_num:
                        line_ans.append(i)
                        col_ans.append(j)
                        place_num += 1

        if place_num:
            place_num = randint(0, place_num)
            line_ans[0] = line_ans[place_num]
            col_ans[0] = col_ans[place_num]

        self.put(line_ans[0], col_ans[0], self.bw, self.turn)

    def check_place(self, now: dict, turn: bool,\
                    tar_turn: bool, num: int) -> float:
        place_num = 0

        if turn == tar_turn:
            if num == self.read_goal[self.turn]:
                for i in range(8):
                    for j in range(8):
                        if self.check(i, j, now, turn):
                            place_num += 1
                return place_num
            else:
                place_sum = 0
                for i in range(8):
                    for j in range(8):
                        if self.check(i, j, now, turn):
                            board_leaf = deepcopy(now)
                            self.put(i, j, board_leaf, turn)
                            place_sum += self.check_place(\
                                board_leaf,
                                not turn,
                                tar_turn,
                                num + 1
                            )
                            place_num += 1
                if place_num:
                    return place_sum / place_num
                else:
                    return 0
        else:
            place_sum = 0
            for i in range(8):
                for j in range(8):
                    if self.check(i, j, now, turn):
                        board_leaf = deepcopy(now)
                        self.put(i, j, board_leaf, turn)
                        place_sum = self.check_place(\
                            board_leaf,
                            not turn,
                            tar_turn,
                            num
                        )
            if place_sum:
                return place_sum
            else:
                # 修正箇所
                return self.check_place(\
                    deepcopy(now),
                    not turn,
                    tar_turn,
                    num
                )

nmost

特筆することはなし。

BitBoard.py

    def nmost(self) -> None:
        max_place_num = -1
        line_ans, col_ans = [-1], [-1]
        place = 0

        for i in range(8):
            for j in range(8):
                if self.check(i, j, self.bw, self.turn):
                    board_leaf = deepcopy(self.bw)
                    self.put(i, j, board_leaf, self.turn)
                    place = self.check_place(\
                        board_leaf,
                        not self.turn,
                        self.turn,
                        1
                    )
                    if place > max_place_num:
                        max_place_num = place
                        place_num = 0
                        line_ans = [i]
                        col_ans = [j]
                    elif place == max_place_num:
                        place_num += 1
                        line_ans.append(i)
                        col_ans.append(j)

        if place_num:
            place_num = randint(0, place_num)
            line_ans[0] = line_ans[place_num]
            col_ans[0] = col_ans[place_num]
        self.put(line_ans[0], col_ans[0], self.bw, self.turn)

osero_learn

データ集めをするためのクラスです。
play関数は対戦データをDataFrame型で返します。
あとは、play関数で返すデータを作るための関数がいくつかあります。
データは10ターンごとに収集し、その内容はターン数及び盤面状態(黒と白)です。

osero_learn.py

from pandas import DataFrame
from BitBoard import osero

class learn(osero):
    def __init__(self, black_method, white_method,\
                 read_goal=[1, 1], eva=None):
        super().__init__(black_method, white_method, read_goal, eva)

    def play(self) -> DataFrame:
        can, old_can = True, True
        turn_num = 0
        data = {}

        self.first_data_set(data)

        can = self.check_all()
        while can or old_can:
            if can:
                turn_num += 1
                if self.turn:
                    self.think[self.black_method]()
                else:
                    self.think[self.white_method]()
                if turn_num % 10 == 0:
                    self.data_set(data, turn_num)
            self.turn = not self.turn
            old_can = can
            can = self.check_all()

        self.count_last()
        data["last_score"] = [self.score] * (turn_num // 10)
        return DataFrame(data)

    def first_data_set(self, data: DataFrame) -> None:
        data["turn"] = []
        for i in range(64):
            data["b%d" % i] = []
            data["w%d" % i] = []

    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"])

        self.score = black - white

    def data_set(self, data: DataFrame, turn_num: int) -> None:
        data["turn"].append(turn_num)
        for i in range(32):
            data["b%d" % i].append(int((self.bw["b_u"] & (1 << i)) != 0))
            data["w%d" % i].append(int((self.bw["w_u"] & (1 << i)) != 0))
        for i in range(32):
            data["b%d" % (i + 32)].append(int((self.bw["b_d"] & (1 << i)) != 0))
            data["w%d" % (i + 32)].append(int((self.bw["w_d"] & (1 << i)) != 0))

run

データ集め及び学習を行い、結果としてグラフを出すプログラムです。
この記事では拡張子をpyとしていますが、ipynbで書いています。
様々な手法で対戦を行い、評価値は以前作成したものを使いました。

データ集め部分

思考方法が5個、それぞれ黒白10回戦ずつ行います。
5x5x10のたった250試合、さらにビットボードを使用しての実行でしたが平均して2分もかかっていました。
Javaでもやってみたいですね、ちなみにcは昔のデータ集めの時、思考方法randomのみとはいえビットボード使わずとも数秒で1000試合終わっていました。流石。
本来deepcopyする必要はありませんが、ipynbなのでプログラム作成の途中でimport文をできるだけ一番上のセルにまとめようとすると何度もdel文を実行することになりエラーが起きます。それを防ぐためdeepcopyしています。

run.py

from copy import deepcopy

import pandas as pd

from BitBoard import osero
from osero_learn import learn

PLAY_WAY = deepcopy(osero.PLAY_WAY)
del PLAY_WAY["human"]
PLAY_WAY = PLAY_WAY.values()

################################

eva = [[
     1.0, -0.6,  0.6,  0.4,  0.4,  0.6, -0.6,  1.0,
    -0.6, -0.8,  0.0,  0.0,  0.0,  0.0, -0.8, -0.6,
     0.6,  0.0,  0.8,  0.6,  0.6,  0.8,  0.0,  0.6,
     0.4,  0.0,  0.6,  0.0,  0.0,  0.6,  0.0,  0.4,
     0.4,  0.0,  0.6,  0.0,  0.0,  0.6,  0.0,  0.4,
     0.6,  0.0,  0.8,  0.6,  0.6,  0.8,  0.0,  0.6,
    -0.6, -0.8,  0.0,  0.0,  0.0,  0.0, -0.8, -0.6,
     1.0, -0.6,  0.6,  0.4,  0.4,  0.6, -0.6,  1.0
] for i in range(2)]

################################

df = pd.DataFrame({})

for i in range(10):
    print("\r[" + "#" * (i+1) + " " * (10-i+1) + "]", end="")
    for black in PLAY_WAY:
        for white in PLAY_WAY:
            run = learn(\
                black,
                white,
                eva=eva
            )
            data = run.play()
            df = df.append(data, ignore_index=True)

print("\r[" + "#" * 10 + "]")

学習部分

ターン数ごとに学習を行い、それぞれ正解率をグラフ化しました。
学習方法もいろいろ使ってみました。
スコアと平均絶対誤差も調べました。

run.py

import matplotlib.pyplot as plt
import numpy as np

x_data = df.drop("last_score", axis=1)
y_data = df[["turn", "last_score"]]

turn_vari = df["turn"].unique()

################################

from sklearn.model_selection import train_test_split
from sklearn.metrics import mean_absolute_error
from sklearn.linear_model import LinearRegression
from sklearn.linear_model import LogisticRegression
from sklearn.linear_model import Ridge
from sklearn.tree import DecisionTreeClassifier
from sklearn.neighbors import KNeighborsClassifier
from sklearn.svm import LinearSVC

methods = [
    LinearRegression,
    LogisticRegression,
    Ridge,
    DecisionTreeClassifier,
    KNeighborsClassifier,
    LinearSVC
]

methods_str = [
    "LinearRegression",
    "LogisticRegression",
    "Ridge",
    "DecisionTreeClassifier",
    "KNeighborsClassifier",
    "LinearSVC"
]

################################

train_score = []
test_score = []

train_MAE = []
test_MAE = []

for turn_num in turn_vari:
    x_train, x_test, y_train, y_test = train_test_split(\
        x_data.query("turn==%d" % turn_num).drop("turn", axis=1),
        y_data.query("turn==%d" % turn_num).drop("turn", axis=1),
        test_size=0.3
    )

    train_score.append([])
    test_score.append([])

    train_MAE.append([])
    test_MAE.append([])

    for method in methods:
        model = method()
        model.fit(x_train, y_train)

        train_score[-1].append(model.score(x_train, y_train))
        test_score[-1].append(model.score(x_test, y_test))

        train_predict = model.predict(x_train)
        train_MAE[-1].append(mean_absolute_error(train_predict, y_train))
        test_predict = model.predict(x_test)
        test_MAE[-1].append(mean_absolute_error(test_predict, y_test))

################################

width = 0.3
x_axis = np.array([i + 1 for i in range(len(methods_str))])

for i in range(len(turn_vari)):
    fig_name = "score of each models (number of turn is %d)" % turn_vari[i]
    fig = plt.figure(figsize=(10, 10))
    plt.bar(x_axis, train_score[i], label="train score", width=width)
    plt.bar(x_axis + width, test_score[i], label="test score", width=width)
    plt.xticks(x_axis + width/2, labels=methods_str, rotation=15)
    plt.legend()
    plt.title(fig_name)
    plt.xlabel("model name")
    plt.ylabel("score")
    plt.savefig("fig/" + fig_name)
    # plt.show()
    plt.clf()
    plt.close()

    fig_name = "MAE of each models (number of turn is %d)" % turn_vari[i]
    fig = plt.figure(figsize=(10, 10))
    plt.bar(x_axis, train_MAE[i], label="train MAE", width=width)
    plt.bar(x_axis + width, test_MAE[i], label="test MAE", width=width)
    plt.xticks(x_axis + width/2, labels=methods_str, rotation=15)
    plt.legend()
    plt.title(fig_name)
    plt.xlabel("model name")
    plt.ylabel("mean squared error")
    plt.savefig("fig/" + fig_name)
    # plt.show()
    plt.clf()
    plt.close()

################################

x_axis = np.array([i + 1 for i in range(len(turn_vari))])
x_axis_name = [str(i) for i in turn_vari]

train_score_T = np.array(train_score).T
test_score_T = np.array(test_score).T

train_MAE_T = np.array(train_MAE).T
test_MAE_T = np.array(test_MAE).T

for i in range(len(methods_str)):
    fig_name = "score of each turn number (method is %s)" % methods_str[i]
    fig = plt.figure(figsize=(10, 10))
    plt.plot(x_axis_name, train_score_T[i], label="train score")
    plt.plot(x_axis_name, test_score_T[i], label="test score")
    plt.legend()
    plt.title(fig_name)
    plt.xlabel("turn number")
    plt.ylabel("score")
    plt.savefig("fig/" + fig_name)
    # plt.show()
    plt.clf()
    plt.close()

    fig_name = "MAE of each turn number (method is %s)" % methods_str[i]
    fig = plt.figure(figsize=(10, 10))
    plt.plot(x_axis_name, train_MAE_T[i], label="train MAE")
    plt.plot(x_axis_name, test_MAE_T[i], label="test MAE")
    plt.legend()
    plt.title(fig_name)
    plt.xlabel("turn number")
    plt.ylabel("MAE")
    plt.savefig("fig/" + fig_name)
    # plt.show()
    plt.clf()
    plt.close()

実行結果

ターン数ごとの学習方法別のスコアと平均絶対誤差、学習方法ごとのターン数別のスコアと平均絶対誤差をグラフにしました。
棒が消えているように見える箇所がありますが、値を調べると0になっていました。

序盤の正解率ほど低かったのは予想通りでしたが、ターン数が60になるまであまり正解率が上がらなかったのは意外でした。

平均絶対誤差についても、ターン数が進んでもあまり精度は上がっていませんでした。

全体として高い数字を出せていたのはLinearRegressionとRidgeでした。
分類手法の皆さんは総じて低いスコアに。

一方でこちらはRidgeが最優秀という結果に。
しかし序盤だけでなく中盤まで誤差が大きい結果になりました。
オセロの盤面には64か所石が置けるので、単純計算して黒と白の最終結果はそれぞれ30個ずつ程度です。それに対し平均絶対誤差30近くあるということはつまりほぼ予測できていないということになります。50ターン目でやっと20程度の誤差となりました。

フルバージョン

次回は

今回は50ターン以降でないと正確な予測は難しいという結果になりました。
あまり良い結果は得られませんでしたが、改良次第でまだ伸びそうな気がします。
次回はこの方法について掘り下げてみたいと思います。

次回