技術をかじる猫

適当に気になった技術や言語を流すブログ。

オセロのAIを作成した話2

パート 1 は こっち

github.com

QLerning

QLerning は強化学習という分類のアルゴリズム
平たく言えば、評価基準だけ与えておけば、その評価を満たせるように勝手に学習するというもの。
QLerning では、以下のプロセスを通して学習する。

  • 状況に対して、何の知識もないうちはランダムな行動を起こす。
  • 起こした行動の結果、良い結果が出た(ないしは結果が改善した)場合、その状況と行動に報酬を与える。
  • 報酬を与えられた AI は、報酬に結び付いた行動を取りやすくなる。
    (ただし、その中でもある程度ランダムに行動も交えて、より報酬が高い行動を探る)

というアルゴリズム
学習のやり方を工夫しないと、学習時間がひどいことにはなるが、人の見えていなかった手とかを見つける可能性がある。
因みに、囲碁で人類を打ち倒した AlphaGO は DeepQNetwork で、これのアイディアも引き継いでる。

その辺の話は下記参照。

DQN (コンピュータ) - Wikipedia

いきなり肝の学習機

学習機の実装はこれだけ。
こんなんが複雑な学習をするというのが、理屈ではわかってても変な感じ…。

class Quantity:
    """Q 学習機本体"""
    def __init__(self, alpha, gamma, initial_q=50.0):
        """Q 値、学習係数、伝播係数の設定"""
        self._values = {}
        self._alpha = alpha
        self._gamma = gamma
        self._initial_q = initial_q

    def select_q(self, state, act):
        """状態とアクションをキーに、q 値取得"""
        if (state, act) in self._values:
            return self._values[(state, act)]
        else:
            # Q 値が未学習の状況なら、Q 初期値
            self._values[(state, act)] = self._initial_q
            return self._initial_q

    def save(self):
        with open('qlern.pickle', mode = 'wb') as f:
            pickle.dump(self._values, f)

    def load(self):
        with open('qlern.pickle', mode = 'rb') as f:
            self._values = pickle.load(f)

    def set(self, state, act, q_value):
        """Q 値設定"""
        self._values[(state, act)] = q_value

    def lerning(self, state, act, max_q):
        """Q 値更新"""
        pQ = self.select_q(state, act)
        new_q = pQ + self._alpha * (self._gamma * (max_q - pQ))
        self.set(state, act, new_q)

    def add_fee(self, state, act, fee):
        """報酬を与える"""
        pQ = self.select_q(state, act)
        new_q = pQ + self._alpha * (fee - pQ)
        self.set(state, act, new_q)

__init__ の説明をすると

  • alpha: 学習レート。値が大きいほど極端な学習をするし、小さいと全然覚えない。
  • gamma: 学習の伝播レート。報酬を得るに至る手順を学ぶときの学習レート。報酬に至る手番に通知する点数。
  • initial_q: 学習していない手番に与えるQ値(初期重要度)

これらを踏まえた上で、_values の中に、「(盤面の状況、手番)→Q値」の関係でQ値を保存する。

select_q_values に蓄えた Q 値を取得するメソッドで、実際に学習してるのは lerningadd_fee の二つ。
add_fee は名前の通り報酬を与えるメソッドです。今回は勝った時に呼び出します。 lerning は、決着がつく前の手番に対して学習を行います。

学習の進め方

対戦型のゲームでは、当然相手も存在するので、「自分が一手打ったら、相手の手番を過ぎた後の状況評価がその手の評価」ということになります。
なので、自分の手番では以下の様なフローを行います。

  • 今の盤面を評価して、直前に打った手にQ値を与え(直前の手が無い≒初手ならなにもしない)、学習させる。
    今回なら、今の手番で打てる手の最高値(その手の最高期待値)を学習させる。
  • 一定確率でランダム挙動をするが、そうでなければ最もQ値の高い行動を取る。

こんなモノを書けばよいので、Plaeyer クラス(前回出たやつ)を継承して、put メソッドを継承してそれを行う。

何回もループして学習するので、前回の手番を忘れるための reset とか、学習状況の保存、復帰を行う saveload あとは、一つの Player に白黒立場入れ替えを行うための state 系メソッドを引っこ抜くと、最小セットはこんな感じ。
先手番専用、後手番専用でいいなら、これを交互に回せばOK

class LerningMachine(Player):
    WINNER_SCORE = 1000.0   # 勝利時の褒章スコア
    DEFAULT_ALPHA = 0.1  # 学習レート(スコア変動)は 1 割
    DEFAULT_GAMMA = 0.9  # 続行時のスコア変動レート
    DEFAULT_EPSILON = 0.3 # ランダムで置き場所を決定する確率

    def __init__(self, board, color):
        super().__init__(board, color)
        self._turn = 0
        self._last_board = None
        self._last_attack = None
        self._q = Quantity(LerningMachine.DEFAULT_ALPHA, LerningMachine.DEFAULT_GAMMA)
        self._e = LerningMachine.DEFAULT_EPSILON

    def lerning(self, selectables, latest_board):
        if self._last_board is None:
            return  # 初手は学習対象外
        if self._board.is_game_end():
            # ゲーム終了してるなら、勝利か敗北かでスコア加算
            if self._board.is_win(self._color):
                # 勝利してれば前回の手(状態と着手手)にスコア加算
                self._q.add_fee(self._last_board, self._last_attack, LerningMachine.WINNER_SCORE)
        else:
            # ゲーム継続中
            if len(selectables) == 0:
                # 選択不能って学習できなくね?
                # むしろこの状況は悪手
                max_q = 0
            else:
                # 選択できる手があるならそのまま学習
                qs = []
                for index in selectables:
                    # 一手先の評価値情報を取得
                    qs.append(self._q.select_q(latest_board, index))
                # 評価値の最大値を取得
                max_q = max(qs)
            # 前回の手(状態と着手手)を学習
            self._q.lerning(self._last_board, self._last_attack, max_q)

    def converted_board(self):
        cur = self._color
        enemy = ReversiBoard.STONE_BLACK
        if cur == enemy:
            enemy = ReversiBoard.STONE_WHITE
        board_str = self._board.to_string()
        return board_str.replace(cur, 'S').replace(enemy, 'E')

    def put(self):
        self._turn += 1
        # 既存状態の確認
        current_board = self.converted_board()
        ables = self._board.able_to_puts(self._color)

        # 学習と次の手の準備
        self.lerning(ables, current_board)
        self._last_board = current_board

        # 次が打てないと諦め
        length = len(ables)
        if length == 0:
            return

        # 次の一手
        if random.random() < self._e:
            # 一定確率でランダム行動選択
            if length == 1:
                x, y = ables[0]
                self._last_attack = ables[0]
                self._board.put_stone(self._color, x, y)
            else:
                x, y = ables[random.randint(0, len(ables) - 1)]
                self._last_attack = (x, y)
                self._board.put_stone(self._color, x, y)
        else:
            # さもなくば、評価値の最もいいものを選択
            # 評価値リスト作成
            qs = []
            for index in ables:
                qs.append(self._q.select_q(current_board, index))
            
            # 最高座標を探す
            max_q = max(qs)
            if qs.count(max_q) > 1:
                # 同値 MAX の座標がある場合
                # max_q の座標からランダム決定
                vals = [i for i in range(len(ables)) if qs[i] == max_q]
                i = random.choice(vals)
            else:
                # MAX は一つしかない
                i = qs.index(max_q)
            # 移動先座標確定
            self._last_attack = ables[i]
            x, y = self._last_attack
            self._board.put_stone(self._color, x, y)

盤面の状況を文字列に表す converted_board を使いつつ、「状態+打てる手番→Q値」の組み合わせを学習していきます。

最後に

4x4 位のリバーシなら、2000 回も戦わせればいい感じになります。
しかし、6x6 でやり始めると、一気に手番のパターンが増え始め、学習データが 200,0000 回の対戦で 1.2GB とかいう残念な事態に…なので、学習に関して言えば

  • DB 使わないとメモリが死ぬ
  • 「状況+着手手→Q値」でしか学習してないので、状況や着手手をハッシュで持ってもいいのか?(衝突さえなさげなら)

あと、学習時間短縮のために

  • 上下左右反転した状況は、論理的に一緒なのでまとめて学習
  • 手番の状況を全部記録しておいて、1戦修了時に初手まで強制的に伝播する

なんて工夫とかも必要かもしれない。

オセロのAIを作成した話

自社アドベントカレンダー用に平日2日ででっち上げたAI。 総作成時間は多分6時間位。

github.com

この記事はその解説。

まずはリバーシ

ゲームとしては枯れてるのと、ターン性なので作りやすい。 ボードを定義して初期配置を行う。 再初期化もしたいので、初期化メソッドも用意しておく。

BORAD_LENGTH = 4

class ReversiBoard:
    STONE_WHITE = 'W'
    STONE_BLACK = 'B'
    BLANK = ' '

    def __init__(self):
        self.initialize()

    def initialize(self):
        self.__board_state = [[' ' for i in range(BORAD_LENGTH)] for n in range(BORAD_LENGTH)]
        self.__board_state[1][1] = ReversiBoard.STONE_BLACK
        self.__board_state[2][2] = ReversiBoard.STONE_BLACK
        self.__board_state[1][2] = ReversiBoard.STONE_WHITE
        self.__board_state[2][1] = ReversiBoard.STONE_WHITE

そして置ける場所の検索。 全てのマスを走査(able_to_puts)して、1マス1マス全方向に対して石を取得できるかどうか判定する(__is_able2put)。 判定には移動ベクトルと座標を再起しながら確認していく(vector)。

    def able_to_puts(self, color):
        """
        detect replaceable positions.
        """
        positions = []
        for y in range(len(self.__board_state)):
            for x in range(len(self.__board_state[y])):
                if self.__is_able2put(x, y, color):
                    positions.append((x, y))
        return positions

    def __is_able2put(self, x, y, color):
        if self.__board_state[y][x] != ReversiBoard.BLANK:
            return False
                
        return self.vector(1, 0, x + 1, y, True, color) or \
            self.vector(0, 1, x    , y + 1, True, color) or \
            self.vector(1, 1, x + 1, y + 1, True, color) or \
            self.vector(-1, 0 , x - 1, y    , True, color) or \
            self.vector(0, -1 , x    , y - 1, True, color) or \
            self.vector(-1, -1, x - 1, y - 1, True, color) or \
            self.vector(1, -1, x + 1, y - 1, True, color) or \
            self.vector(-1, 1, x - 1, y + 1, True, color)
    
    def vector(self, vx, vy, cx, cy, is_fst, color):
        if cx < 0 or cy < 0 or cx >= BORAD_LENGTH or cy >= BORAD_LENGTH:
            return False
        if self.__board_state[cy][cx] == ReversiBoard.BLANK:
            return False
        if is_fst:
            if self.__board_state[cy][cx] == color:
                return False
            else:
                return self.vector(vx, vy, cx + vx, cy + vy, False, color)
        else:
            if self.__board_state[cy][cx] == color:
                return True
            else:
                return self.vector(vx, vy, cx + vx, cy + vy, False, color)

これを利用して、石を置いたときにひっくり返す処理も作る。

    def put_stone(self, color, x, y):
        def reverse(vx, vy, cx, cy):
            if cx < 0 or cy < 0 or cx >= 8 or cy >= 8:
                return
            if self.__board_state[cy][cx] == color:
                return
            elif self.__board_state[cy][cx] == ReversiBoard.BLANK:
                return
            self.__board_state[cy][cx] = color
            reverse(vx, vy, cx + vx, cy + vy)
        
        self.__board_state[y][x] = color

        if self.vector(1, 0, x + 1, y, True, color):
            reverse(1, 0, x + 1, y)
        if self.vector(0, 1, x, y + 1, True, color):
            reverse(0, 1, x, y + 1)
        if self.vector(1, 1, x + 1, y + 1, True, color):
            reverse(1, 1, x + 1, y + 1)

        if self.vector(-1, 0, x - 1, y, True, color):
            reverse(-1, 0, x - 1, y)
        if self.vector(0, -1, x, y - 1, True, color):
            reverse(0, -1, x, y - 1)
        if self.vector(-1, -1, x - 1, y - 1, True, color):
            reverse(-1, -1, x - 1, y - 1)

        if self.vector(1, -1, x + 1, y - 1, True, color):
            reverse(1, -1, x + 1, y - 1)
        if self.vector(-1, 1, x - 1, y + 1, True, color):
            reverse(-1, 1, x - 1, y + 1)

デバッグ用に表示メソッドを用意する。

    def show(self):
        """
        Render bord status.
        """
        print(self.to_string())
    
    def to_string(self):
        ylength = len(self.__board_state)
        id_list = zip(range(ylength), self.__board_state)

        rendered_board = "  0 1 2 3 4 5\n"
        rendered_board += "\n".join([f'{n} ' + " ".join(row) for n, row in id_list])
        return rendered_board

勝者判定とか説明不要でしょ?

    def is_game_end(self):
        return len(self.able_to_puts(ReversiBoard.STONE_BLACK)) == 0 and len(self.able_to_puts(ReversiBoard.STONE_WHITE)) == 0
    
    def count_stones(self):
        blacks = 0
        whites = 0
        for r in self.__board_state:
            for c in r:
                if c == ReversiBoard.STONE_BLACK:
                    blacks += 1
                elif c == ReversiBoard.STONE_WHITE:
                    whites += 1
        return (blacks, whites)

    def is_win(self, color):
        if self.is_game_end():
            blacks = 0
            whites = 0
            for r in self.__board_state:
                for c in r:
                    if c == ReversiBoard.STONE_BLACK:
                        blacks += 1
                    elif c == ReversiBoard.STONE_WHITE:
                        whites += 1
            is_black_win = blacks > whites
            is_white_win = whites > blacks
            if is_black_win and color == ReversiBoard.STONE_BLACK:
                return True
            elif is_white_win and color == ReversiBoard.STONE_WHITE:
                return True
        return False
    
    def is_draw(self):
        if self.is_game_end():
            blacks = 0
            whites = 0
            for r in self.__board_state:
                for c in r:
                    if c == ReversiBoard.STONE_BLACK:
                        blacks += 1
                    elif c == ReversiBoard.STONE_WHITE:
                        whites += 1
            return blacks == whites
        return False

あとはそれを使って処理するプレイヤーを定義する。

class Player:
    def __init__(self, board, color):
        self._board = board
        self._color = color

    def set_color(self, color):
        self._color = color

    def put(self):
        ables = self._board.able_to_puts(self._color)
        print(self._board.to_string())
        if len(ables) > 0:
            print([f'{idx}:{v}' for idx, v in zip(range(len(ables)), ables)])
            print(f'Input index({self._color}):')
            position_id = int(input('>>'))
            x, y = ables[position_id]
            self._board.put_stone(self._color, x, y)
        else:
            print('Skip! (can not put)')

あとはこれを人数分作って while で回せばおk

なんかしんどくなったので、明日に続く…

迷路の最短ルートを蟻コロニー最適化で解く

という事でやってみた。
参考書はコレ。

機械学習と深層学習 Pythonによるシミュレーション

機械学習と深層学習 Pythonによるシミュレーション

どこで使おうかと悩んでたら、社内勉強会で「迷路の最短経路を探せ」という問題があったので、応用してみた。
ただし、元のコードは、一定以下に薄いフェロモンを無視しているように見えるが、こちらでは面倒なのでそれをしてない。

https://github.com/Sunao-Yoshii/StudyDocs/blob/master/python/dokaku_ase20181027/ant_colony.py

パット見正しく動いて層には見えるがはてさて?

蟻コロニー最適化法は、迷路でも巡回サラリーマンでもいいのだけど、要するに最も短いルートはどのルートかを計算するアルゴリズム

蟻はフェロモンを地面に塗って、道しるべをつけるけど、これは一定の割合で蒸発して消えてしまう。
その道を参考にしつつ、後続の蟻が少しづつ道を外れたりして、フェロモンの濃いルートが少しづつ短い方によるというもの。

道に元々あったフェロモンは、一定割合で縮小、移動距離の二乗に反比例する形で新しいフェロモンを上塗りするという挙動を繰り返す。
作り自体は単純なので見れ

Q学習で三目並べの評価値テーブルを作らせてみた

機械学習と深層学習 Pythonによるシミュレーション

機械学習と深層学習 Pythonによるシミュレーション

この本で Q 学習のコードまで書いた後、「あー静的な評価値生成に使えるなー」という事で、やってみたのが下記。

StudyDocs/tic_tac_toe.py at master · Sunao-Yoshii/StudyDocs · GitHub

なんで三目並べなのかというと

  • 手数が少なく、試行回数を増やしやすい(というか手数が少ないので、その学習内容が正しいのかどうか評価しやすい)
  • 目が少ないのでランダムでもそれなりに結果が出しやすい
  • 覚えたてのアルゴリズムを試したい

というだけのもの。

現実に対人を想定した評価値となると、相手の手に対して評価をしなければならない事もあるので、単純な Q 学習(静的評価値学習)だけでは判断ができないと思う。
が、三目並べなら参考値位出てきそうかなと思ったのが成り立ち。

そもそも評価値って単純な学習じゃねーよという事に後から気付いて、作り直し。
盤面の状態と、それに対する手、相手の手を踏まえて、Q値の伝播を行った。

やってみたら分かるのだが、正直 5000 回位はランダムとそんな変わらない。
8000 回位強化学習させると、有意差が少しづつ出てくるような感じ。

大体 20,000 回強化学習させれば、ランダムさんに 7 割かた勝てるようになる…ってそんなアホみたいに戦う位なら、人の方がもっと強いわと www

とはいえ、すべての状況に対して次の手、評価…って計算してるから、かなりの無駄は当然あり得るわけで…もう少し考えたいところ。

機械学習と深層学習という本を読みつつ...2

とりあえず第一章を読んだところでの自分の理解。
一応オライリー先生の機械学習本を半分位読んだ前提で…。

基本的な分類として、教師あり学習教師なし学習の二つが基礎としてある。
教師あり学習は教師データを事前に準備することで、学習機にそのパターンを覚えこませる手法。

教師あり学習。このケースで教育した AI はモノや状況の認識を行う。
画像や音声を認識するのはこうした AI。

教師なし学習はおよそ二種類の分岐があり

アルゴリズムによる分類は、クラスタリング等の様に類似したグループにデータを分類するだけで、その分類に名前や意味を与えるのは人間の仕事です。
もう一つの強化学習は、最終目的(結果)から見てその仮説が正しかったと理解を蓄積する学習型です。

クラスタリング等の分類技術は、例えば遺伝子操作の過程で有効な遺伝子を探すために、とりあえず分類を使ってみるとか、商品販売であれば購入顧客の傾向を分類するなどの使い方があります。
どちらかといえば研究向けでしょう。

結果からの学習、これは強化学習に分類します。
例えば将棋やオセロの AI 学習なんかに使います。例としては、一通りの手順で盤を進めて、勝ったらその手順にスコアを割り振る、負けたら手順のスコアを下げる。
そうして評価値を構築するなんて使い方ができます。

機械学習と深層学習という本を読みつつ

github.com

機械学習の基礎とあって、単純ではある。

帰納学習、複数の事象からそのパターンを抽出する学習のことで、今回の方法はその基礎だそうだ。
逆の言い方をすればパターンを見つけるための学習ともいえる。

このケースではランダムで認識パターンを作成、パターンに対して学習データを与えて正答率が良ければ残す。
そんなループを繰り返すことで、精度を上げていくというアルゴリズム

ただ、学習効率のいいものかといえば微妙なパターンではある。
元のコードがあまりにも一筆書き過ぎてもやっとしたので少し変えた。

TestManagementTool探してみた

というのも、テストを管理するのに Excel とか全力でやだ、見づらい、メンテしにくい、同時に更新ですさまじく問題が出る。
ついでにテストの状況をいちいちファイルサーバまで行って開かないと確認できないクソっぷり。

で、老舗で TestLink を久々に弄ってみたのだが、これがやはり死ぬほど使いづらい。

というか UI や言葉の選び方がダメなせいで、ユーザビリティが悪すぎた。
つまり何が言いたいかというと、導入するにあたって学習コストが高すぎる。
その意味で使いたくない

という事で、ほかの使えそうなものを調べてみた。

ざっくり

  • SquahTM
  • TestRail

辺りが人気らしい。

リンクと共にメモだけ。

あとよさげなリンク

モダンなテスト管理プロセスのためにテスト管理ツール3つを比較検討したはなし - Mercari Engineering Blog

妥当なセンは TestRail か。
UI を見る限り、TestLink より絶対使いやすい。