機械にFizzBuzzのルールを学ばせる話

※追記
既に類似した内容の記事がありました。

こんばんは。りーぜんとです。

この記事をみている方であれば、ほとんどの方が知っているであろうFizzBuzz。プログラマであれば1から100までFizzBuzzのルール通りに出力させたことがあるのではないでしょうか。
今回はそのFizzBuzzを「コードを書かずにAIにやらせる」ということをやってみます。
作成したプログラムはGitHubに公開してあります。

目次

1. FizzBuzzとは
2. ゲームの要素を整理
3. ゲーム環境の構築
4. 学習モデルの構築
5. 学習用メモリの構築
6. 学習エージェントの構築
7. 実際に学習させてみる
8. 結果

FizzBuzzとは

んなもん知っとるわという方は飛ばしてください。

Wikipediaをみてみましょう。

Fizz Buzz（フィズ・バズ、Bizz BuzzやBuzzとも呼ばれる）は英語圏で長距離ドライブ中や飲み会の時に行われる言葉遊びである。

簡単に言うと、数字を順番に挙げていく上で、3の倍数のときは数字の代わりにFizz、5の倍数のときはBuzz、両方の時はFizzBuzzというゲームです。世界のナベアツです。

ゲームの要素を整理

時は2020年、もはや人間がFizzBuzzをするのは時代遅れです。ゲームのルールだけ人間が用意して、あとは機械にプレイをさせてみましょう。

今回使う手法は、強化学習というものです。よくゲームのAIなどに使われている手法で、囲碁や将棋のAIなどにも使われています。

強化学習についてはここで書きません。興味がある方は自分で調べてみてください。

人間がFizzBuzzをプレイする時は、実際には今の数字だけ分かれば答えを出すことができますが、なんかそれだとAI味がないので、今回は過去15ターンの答えを今の状況としてAIに与えます。

ゲーム環境の構築

まずFizzBuzzのゲーム環境を構築します。具体的には以下の機能を実装します。

• 今のゲームの状況、得点の計算
• 次のターンへ遷移

ここでいう得点とは、AIに今の状況に対する各答え(数字、FIzz、Buzz、FizzBuzz)がどれくらいいい答えかを表すものです。
AIはこの得点を取り続けることを目標として成長します。

FizzBuzz.py

from random import randint
from numpy import array

class FizzBuzz:
    def __init__(self, start, end):
        self.start = start # 始まり
        self.end   = end   # 終わり

    def reset(self): # 初期化
        self.turn = self.start # 今の数字
        self.state = []        # 今の状況

        # 初期状況を設定(過去15ターン)
        for i in range(self.turn - 15, self.turn):
            if i % 15 == 0:
                self.state.append(3)
            elif i % 3 == 0:
                self.state.append(1)
            elif i % 5 == 0:
                self.state.append(2)
            else:
                self.state.append(0)

    # 十分学習できたかどうか
    def is_learned(self):
        return self.turn == self.end

    # ターン遷移
    def step(self, action, verbose=False):
        if verbose:
            print(self.turn, [self.turn, 'Fizz', 'Buzz', 'FizzBuzz'][action])

        reward   = 0     # 得点
        terminal = False # ゲーム終了判定

        self.state = self.state[1:] + [action]

        if action == 1:   # Fizz
            if self.turn % 3 == 0 and self.turn % 5 != 0:
                reward   = 1
                terminal = False
            else:
                reward   = -1
                terminal = True
        elif action == 2: # Buzz
            if self.turn % 5 == 0 and self.turn % 3 != 0:
                reward   = 1
                terminal = False
            else:
                reward   = -1
                terminal = True
        elif action == 3: # FizzBuzz
            if self.turn % 15 == 0:
                reward   = 1
                terminal = False
            else:
                reward   = -1
                terminal = True
        else:             # Number
            if self.turn % 3 != 0 and self.turn % 5 != 0:
                reward   = 1
                terminal = False
            else:
                reward   = -1
                terminal = True

        if self.turn == self.end:
            terminal = True

        self.turn += 1

        return array(self.state), reward, terminal

    def random_step(self): # 初期化用
        return array(self.state), 0, False

reset()で初期化したあと、step()で遷移しながら学習を繰り返します。
また、ゲームが最後の数字までいったときに学習を自動で切り上げることができるように、終了判定をするis_learned()を書きました。

学習モデルの構築

次に、実際に学習に使うモデルを作ります。今回は中間層が一層の単純な構成のニューラルネットワークを使用します。

model.py

from keras.models import Sequential
from keras.layers import Dense, Reshape
from keras.optimizers import Adam
import numpy as np

class Model:
    def __init__(self):
        learning_rate = 0.01 # 学習率
        state_size    = 15   # 入力サイズ(今の状態)
        action_size   = 4    # 出力サイズ(0、1、2、3のいずれか)
        hidden_size   = 16   # 隠れ層の大きさ

        self.model = Sequential()
        self.model.add(Dense(hidden_size, activation='relu', input_dim=state_size))
        self.model.add(Dense(action_size, activation='softmax'))
        self.optimizer = Adam(lr=learning_rate)
        self.model.compile(loss='mse', optimizer=self.optimizer)
        self.model.summary()

    # 実際に学習させる関数
    def replay(self, memory, batch_size, gamma, target_model):
        inputs     = np.zeros((batch_size, state_size))
        outputs    = np.zeros((batch_size, action_size))
        mini_batch = memory.sample(batch_size)

        for i, (state, action, reward, next_state) in enumerate(mini_batch):
            inputs[i:i + 1] = state
            target          = reward

            if not (next_state == np.zeros(state.shape)).all():
                q = self.model.predict(next_state.reshape(1, state_size))[0].argmax()
                next_action = np.argmax(q) # 最もQ値が高い行動を次の行動として選択
                target = reward + gamma * target_model.model.predict(
                    next_state.reshape(1, state_size)
                )[0][next_action] # 実際の報酬

            # 現状の予想値を修正して学習させる
            outputs[i] = self.model.predict(state.reshape(1, state_size))
            outputs[i][action.argmax()] = target

        self.model.fit(inputs, outputs, epochs=1, verbose=0)

実際に学習をする時はreplay()を使用します。毎ターン学習させるとデータの時系列にモデルが影響されてしまうので、この後実装するメモリに一定量のデータを蓄積させておいて、その中からランダムで抽出して学習をさせます。

学習用メモリの構築

学習に使うデータをしまっておくメモリを実装します。

memory.py

from collections import deque
import numpy as np

class Memory:
    def __init__(self):
        self.buffer = deque()

    # 現在の状況、どう動いたか、その結果どうなったか、その行動の報酬を格納
    def add(self, exp):
        self.buffer.append(exp)

    # ランダムに格納されているデータを取り出す
    def sample(self, batch_size):
        indice = np.random.choice(np.arange(len(self.buffer)), size=batch_size, replace=False)
        return [self.buffer[i] for i in indice]

学習エージェントの構築

学習時に、実際に行動を決めてその結果に基づいて学習する人(?)をエージェントと呼びます。

agent.py

import numpy as np
from keras.utils.np_utils import to_categorical

class Agent:
    # 行動を選択
    def get_action(self, state, epoch, main_model):
        epsilon = 0.001 + 0.9 / (1.0 + epoch)

        if epsilon < np.random.uniform(0, 1):
            action = main_model.model.predict(state.reshape(1, 15))[0].argmax()
        else: # ある程度の確率でランダム動作をする
            action = np.random.choice([0, 1, 2, 3])

        return to_categorical(action, 4)

get_action()で動作を選択します。基本的にモデルが予想する行動を選択しますが、ある程度の確率でランダムな動作をすることでいわゆる冒険をさせて新たな良い手を発見させることができます。

実際に学習させてみる

上で実装した方々を使って学習を回してみます。

train.py

from fizzbuzz import FizzBuzz
from model import Model
from memory import Memory
from agent import Agent

def evaluate(env):
    env.reset()
    state, _, finished = env.random_step()
    while not finished:
        action = agent.get_action(state, N_EPOCHS, main_model)
        next_state, _, finished = env.step(action.argmax(), verbose=True)
        state = next_state

if __name__ == '__main__':
    N_EPOCHS = 5000 # 最大訓練回数
    S_BATCH  = 4    # バッチサイズ
    GAMMA    = 0.99 # 時間経過による報酬減少率

    env = FizzBuzz(1, 1000) # 学習環境

    main_model   = Model()
    target_model = Model()

    memory = Memory() # メモリ
    agent  = Agent()  # エージェント

    learned_flag = False # 学習が終了したか否か

    for epoch in range(N_EPOCHS):
        if learned_flag:
            break

        print('Epoch: {}'.format(epoch + 1))

        # 初期状態設定
        env.reset()
        state, reward, finished = env.random_step() 
        target_model.model.set_weights(main_model.model.get_weights())

        while not finished:
            action = agent.get_action(state, epoch, main_model)
            learned_flag = env.is_learned()
            next_state, reward, finished = env.step(action.argmax())

            memory.add((state, action, reward, next_state))

            state = next_state

            if len(memory.buffer) > S_BATCH:
                main_model.replay(memory, S_BATCH, GAMMA, target_model)

            target_model.model.set_weights(main_model.model.get_weights())

    env = FizzBuzz(1, 100)
    evaluate(env)

学習終了時に評価するevaluate()も実装しました。実際にFizzBuzzを出力しながら確認できます。

結果

学習結果です。

Epoch: 70
Epoch: 71
Epoch: 72
1 1, 2 2, 3 Fizz, 4 4, 5 Buzz, 6 Fizz, 7 7, 8 8, 9 Fizz, 10 Buzz, 11 11, 12 Fizz, 13 13, 14 14,
15 FizzBuzz, 16 16, 17 17, 18 Fizz, 19 19, 20 Buzz, 21 Fizz, 22 22, 23 23, 24 Fizz, 25 Buzz, 26 26,
27 Fizz, 28 28, 29 29, 30 FizzBuzz, 31 31, 32 32, 33 Fizz, 34 34, 35 Buzz, 36 Fizz, 37 37, 38 38,
39 Fizz, 40 Buzz, 41 41, 42 Fizz, 43 43, 44 44, 45 FizzBuzz, 46 46, 47 47, 48 Fizz, 49 49, 50 Buzz,
51 Fizz, 52 52, 53 53, 54 Fizz, 55 Buzz, 56 56, 57 Fizz, 58 58, 59 59, 60 FizzBuzz, 61 61, 62 62,
63 Fizz, 64 64, 65 Buzz, 66 Fizz, 67 67, 68 68, 69 Fizz, 70 Buzz, 71 71, 72 Fizz, 73 73, 74 74,
75 FizzBuzz, 76 76, 77 77, 78 Fizz, 79 79, 80 Buzz, 81 Fizz, 82 82, 83 83, 84 Fizz, 85 Buzz, 86 86,
87 Fizz, 88 88, 89 89, 90 FizzBuzz, 91 91, 92 92, 93 Fizz, 94 94, 95 Buzz, 96 Fizz, 97 FizzBuzz,
98 98, 99 Fizz, 100 Buzz

学習を72周回したら1から100まで到達できました。

試しに4000からの結果をみてみます。

4000 Buzz, 4001 4001, 4002 Fizz, 4003 4003, 4004 4004, 4005 FizzBuzz, 4006 4006, 4007 4007, 4008 Fizz,
4009 4009, 4010 Buzz, 4011 Fizz, 4012 4012, 4013 4013, 4014 Fizz, 4015 Buzz, 4016 4016, 4017 Fizz,
4018 4018, 4019 4019, 4020 FizzBuzz, 4021 4021, 4022 4022, 4023 Fizz, 4024 4024, 4025 Buzz, 4026 Fizz,
4027 4027, 4028 4028, 4029 Fizz, 4030 Buzz, 4031 4031, 4032 Fizz, 4033 4033, 4034 4034, 4035 FizzBuzz,
4036 4036, 4037 4037, 4038 Fizz, 4039 4039, 4040 Buzz, 4041 Fizz, 4042 4042, 4043 4043, 4044 Fizz,
4045 Buzz, 4046 4046, 4047 Fizz, 4048 4048, 4049 4049, 4050 FizzBuzz, 4051 4051, 4052 4052, 4053 Fizz,
4054 4054, 4055 Buzz, 4056 Fizz, 4057 4057, 4058 4058, 4059 Fizz, 4060 Buzz, 4061 4061, 4062 Fizz,
4063 4063, 4064 4064, 4065 FizzBuzz, 4066 4066, 4067 4067, 4068 Fizz, 4069 4069, 4070 Buzz, 4071 Fizz,
4072 4072, 4073 4073, 4074 Fizz, 4075 Buzz, 4076 4076, 4077 Fizz, 4078 4078, 4079 4079, 4080 FizzBuzz,
4081 4081, 4082 4082, 4083 Fizz, 4084 4084, 4085 Buzz, 4086 Fizz, 4087 4087, 4088 4088, 4089 Fizz,
4090 Buzz, 4091 4091, 4092 Fizz, 4093 4093, 4094 4094, 4095 FizzBuzz, 4096 4096, 4097 4097, 4098 Fizz,
4099 4099, 4100 Buzz, 4101 Fizz, 4102 4102, 4103 4103, 4104 Fizz, 4105 Buzz, 4106 4106, 4107 Fizz,
4108 4108, 4109 4109, 4110 FizzBuzz, 4111 4111, 4112 4112, 4113 Fizz, 4114 4114, 4115 Buzz, 4116 Fizz,
4117 4117, 4118 4118, 4119 Fizz, 4120 Buzz, 4121 4121, 4122 Fizz, 4123 4123, 4124 4124, 4125 FizzBuzz,
4126 4126, 4127 4127, 4128 Fizz, 4129 4129, 4130 Buzz, 4131 Fizz, 4132 4132, 4133 4133, 4134 Fizz,
4135 Buzz, 4136 4136, 4137 Fizz, 4138 4138, 4139 4139, 4140 FizzBuzz, 4141 4141, 4142 4142, 4143 Fizz,
4144 4144, 4145 Buzz, 4146 Fizz, 4147 4147, 4148 4148, 4149 Fizz, 4150 Buzz, 4151 4151, 4152 Fizz,
4153 4153, 4154 4154, 4155 FizzBuzz, 4156 4156, 4157 4157, 4158 Fizz, 4159 4159, 4160 Buzz, 4161 Fizz,
4162 4162, 4163 4163, 4164 Fizz, 4165 Buzz, 4166 4166, 4167 Fizz, 4168 4168, 4169 4169, 4170 FizzBuzz,
4171 4171, 4172 4172, 4173 Fizz, 4174 Fizz

174回目の4174で本来なら4174と出力するところをFizzと間違ってしまいました。
状態の種類は15種類くらいしかないはずなのになんで間違ったんだろう…

ちなみにtrain.pyの43行目のstep()に引数verbose=Trueを追加すると徐々にターン数を伸ばしながら学習していく様子がみられます。かわいいですね。

よければTwitterフォローしてください。じゃあね。