オセロのAIを作成した話2 - 技術をかじる猫

パート 1 はこっち。

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

学習の進め方

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

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

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

何回もループして学習するので、前回の手番を忘れるための reset とか、学習状況の保存、復帰を行う save や load あとは、一つの 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)