LoginSignup
34
22

More than 3 years have passed since last update.

@hmarf(hmarf)

機械学習(Q学習,NN&GA)でオセロAIを作って遊ぼう

Last updated at Posted at 2019-03-22

概要

現在、様々な場所で機械学習が使われています。今回は様々な機械学習の理論を用いてオセロAI実装しました。
地獄の卒研の暇な時間に現実逃避として実装してました。

環境

OS
・ macOS
開発環境
・ Python 3.6.0

今回実装したプレイヤー

  1. User: ユーザーがプレイする
  2. Count Stone: 自分の手で多くの石を返せるところに石を置く
  3. Random: ランダムに石を置く
  4. Q_learning: Q学習
  5. NN: 遺伝的アルゴリズム(GA)でニューラルネットワーク(NN)の重みを最適化する

1 ~ 3 のプレイヤーは特に説明することはないので、以下に 4, 5 について説明します。

Q学習

強化学習の一つです。
状態sの状況で、行動aを選択する価値Q(s,a)を学習させる。Q学習はQ（s,a）の値が最大の行動aを選択する。 初期状態ではQ(s,a)の値は最適化されていません。このQ(s,a)の値を最適化していく作業を学習と呼びます。

以下の式に従って学習（Q値の更新）をしていきます。

Q(s_t,a_t) \leftarrow (1-\alpha)Q(s_t,a_t)+\alpha\bigl[r_{t+1}+\gamma max_{a_t+1}Q(s_{t+1},a_{t+1})\bigr] \\
\alpha　(0<\alpha\leqq1) : 学習率 \\
\gamma　(0<\gamma\leqq1) : 割引率 \\

とてもシンプルですね。これで強くなるのか不安になります。
Q学習について私が説明するよりも他の素晴らしい本やサイトを見た方が良いと思うので、そちらをどうぞ。
Q学習＿Q-Learning(Vol.12)
強化学習

コードはそれほど複雑ではないので、リクエストがあったら公開したいと思います。今回は結果だけ記載します。

Q学習の結果

(学習: 1万回) Q学習 vs ランダム
(真剣勝負: 500回) Q学習 vs ランダム

---------学習---------
0) Player1(Q_learning): 0  Player2(Random): 1  Draw: 0
...
500) Player1(Q_learning): 205  Player2(Random): 252  Draw: 44
...
4000) Player1(Q_learning): 1935  Player2(Random): 1689  Draw: 377
...
6800) Player1(Q_learning): 3666  Player2(Random): 2562  Draw: 573
...
9999) Player1(Q_learning): 6110  Player2(Random): 3172  Draw: 718

---------真剣勝負---------
0) Player1(Q_learning): 0  Player2(Random): 1  Draw: 0
...
100) Player1(Q_learning): 64  Player2(Random): 33  Draw: 4
...
250) Player1(Q_learning): 147  Player2(Random): 89  Draw: 15
...
499) Player1(Q_learning): 311  Player2(Random): 156  Draw: 33

　
(学習: 1万回) Q学習 vs Q学習
(真剣勝負: 500回)　Q学習 vs ランダム

---------学習---------
0) Player1(Q_learning): 1  Player2(Q_learning): 0  Draw: 0
...
500) Player1(Q_learning): 234  Player2(Q_learning): 221  Draw: 46
...
4000) Player1(Q_learning): 1762  Player2(Q_learning): 1836  Draw: 403
...
6800) Player1(Q_learning): 3036  Player2(Q_learning): 3116  Draw: 649
...
9999) Player1(Q_learning): 4607  Player2(Q_learning): 4531  Draw: 862
---------真剣勝負---------
0) Player1(Q_learning): 0  Player2(Random): 1  Draw: 0
...
100) Player1(Q_learning): 53  Player2(Random): 41  Draw: 7
...
250) Player1(Q_learning): 168  Player2(Random): 70  Draw: 13
...
499) Player1(Q_learning): 341  Player2(Random): 132  Draw: 27

んー、微妙な勝率。。。
もっと学習させてみます。

(学習: 10万回) Q学習 vs Q学習
(真剣勝負: 500回)　Q学習 vs ランダム

---------真剣勝負---------
0) Player1(Q_learning): 0  Player2(Random): 1  Draw: 0
100) Player1(Q_learning): 99  Player2(Random): 2  Draw: 0
250) Player1(Q_learning): 239  Player2(Random): 12  Draw: 0
499) Player1(Q_learning): 482  Player2(Random): 18  Draw: 0

たまに負けてる。。。
Q学習なら１回も負けないと思ってたのに。。。

NN

ニューラルネットワークを使ってオセロをプレイさせます。

テトリスを学習させてみた(Youtube)

この動画を知っていますか？
動画を見てオセロにも実装してみたくなりました。動画を参考に実装していきます。

NNに入力する特徴量を決定する必要があります。今回は特徴ベクトルを以下の5つにしました。
1. 角の石の数（自分）
2. 角の石の数（相手）
3. （自分の石の数）ー（相手の石の数）
4. 石の置かれていない場所の数
5. 中央2x2にある石の数: （自分の石の数）ー（相手の石の数）
他にも色々な特徴で試すと面白いと思います。（次の手で打つことのできる場所の数とか）

最初にシンプルなニューラルネットワーク(入力層、中間層、出力層それぞれ１層)を実装します。重みの最適化には遺伝的アルゴリズムを用いるので、誤差逆伝播法は必要ありません。隠れ層のニューロン数は10です。

NN.py
import numpy as np

# 入力層・中間層・出力層がそれぞれ１層のニューラルネットワーク
class NN:

    # 活性化関数
    def sigmoid(self, x):
        return 1 / (1 + np.exp(-x))

    # 順伝達
    # vector: 特徴量, w1: 入力層から中間層への重み, w2: 中間層から出力層への重み
    def forward(self, vector, w1, w2):
        layer1 = np.dot(vector, w1)
        layer2 = self.sigmoid(layer1)
        layer3 = np.dot(layer2, w2)
        return layer3

重みを最適化するために遺伝的アルゴリズムを実装していきます。手順としては

  1. 初期個体を乱数で生成
  2. 個体同士で戦わせ、順位付け
  3. 順位付けに応じて次世代へと引き継がれる個体を選択
  4. 個体同士の遺伝子を入れ替え、次世代の個体を生成
  5. 底確率で次世代個体の遺伝子を乱数に置換
  6. 2~5 を繰り返す

個体選択はエリート主義とルーレット方式、交叉は二点交叉を用いました。
詳しくは　遺伝的アルゴリズム(Genetic Algorithm)を始めよう！をご覧ください。とてもわかりやすいです。

Individual.py
class individual:

    def __init__(self,genoms):
    # genoms: 遺伝子
    # score: オセロのスコア
        self.genoms = genoms
        self.score = 0

    def getGenom(self):
        return self.genoms

    def getScore(self):
        return self.score

    def score_reset(self):
        self.score = 0

入力層のニューロン数：５、隠れ層のニューロン数：１０、出力層のニューロン数：１
調整する重みの数は合計で60個です。

各種定数です。適当に決めた数字です。

GA.py
# 世代数
GANERATIONS = 100
# 一世代の個体数
POPULATIONS = 50
# 遺伝子数
GENOMS = 60
# エリート主義で選択される個体数
ELITISM = 2
# ルーレット方式で選択される個体数
ROULETTE = 8
# エリートを交配させ生成される個体数
SON_ELITE = 2
# 現世代の個体をランダムに選び交配させ生成される個体数
SON_CURRENT_ALL = 38
# 突然変異確率
MUTATION = 0.04
# 個体突然変異確率
INDIVIDUAL_MUTATION = 0.2
# 遺伝子突然変異確率
GENOM_MUTATION = 0.2

　
遺伝的アルゴリズムを実装します。
(1) 初期個体を乱数で生成

GA.py
def create(genom_length):
    #　初期個体を乱数で生成
    #　面倒なので入力層から中間層への重みと中間層から出力層への重みを一度に生成
    #　return: 初期状態の一個体（POPULATIONS の数だけ回してください ）
    return np.random.normal(0.0,1.0,(genom_length))

(2) 個体同士を戦わせ、順位付け
(3) 順位付けに応じて次世代へと引き継がれる個体を選択

GA.py
# エリート主義
def select_elite(gas, elite_length):
    # gas: 現世代個体集団
    # elite_length: 選ばれるエリート数(ELITISM)
    # return: ga を elite と other に分けたもの
    sort_individual = sorted(gas, key=lambda u: u.score, reverse=True)
    elite, other = sort_individual[:elite_length], sort_individual[elite_length:]
    return elite, other

# ルーレット方式
def select_roulette(gas, roulette_length):
    # gas: select_elite の other にあたる
    # roulette_length: ルーレット方式で選択される個体数(ROULETTE)
    # return: 選ばれた個体のリスト
    gas_copy = copy.deepcopy(gas)
    total = 0
    select_list = []
    for ga in gas_copy:
        total += ga.score
    for i in range(roulette_length):
        Vsum = 0
        arrow = random.randint(0,total-1)
        for j in gas_copy:
            Vsum += j.score
            if Vsum > arrow:
                select_list.append(j)
                total = total - j.score
                gas_copy.remove(j)
                break
    return select_list

(4)個体同士の遺伝子を入れ替え、次世代の個体を生成

GA.py
def crossover(ga_one,ga_second,genom_length):
    # 二点交叉
    # ga_one: 交叉させる個体１
    # ga_second: 交叉させる個体２
    # genom_length: 遺伝子数(GENOMS)
    # return: 交叉で作成された次世代個体リスト
    new_genom = []
    point_one = random.randint(0,genom_length)
    point_second = random.randint(point_one, genom_length)
    one = ga_one.getGenom()
    second = ga_second.getGenom()
    new_one = np.concatenate([one[:point_one],second[point_one:point_second],one[point_second:]])
    new_second = np.concatenate([second[:point_one],one[point_one:point_second],second[point_second:]])
    new_genom.append(population(new_one))
    new_genom.append(population(new_second))
    return new_genom

(5)底確率で次世代個体の遺伝子を乱数に置換

GA.py
def mutation(gas,mutation,genom_length):
    # gas:　次世代個体集団
    # mutation: 突然変異確率(MUTATION)
    # genom_length: 遺伝子数(GENOMS)
    # return: 次世代個体集団
    for i in gas:
        if mutation > random.random():
            i.genoms[random.randint(0,(genom_length - 1))] = np.random.normal(0.0,1.0)
    return gas

(5)突然変異の方法がしっくりこなかったので、
【初心者向け】Re:ゼロから始める遺伝的アルゴリズム【人工知能】
このサイトを参考に修正しました。

GA.py
def mutation(gas,individual_mutation,genom_mutation):
    # gas:　次世代個体集団
    # individual_mutation: 個体突然変異確率(INDIVIDUAL_MUTATION)
    # genom_mutation: 遺伝子突然変異確率(GENOM_MUTATION)
    # return: 次世代個体集団
    ga_list = []
    for i in gas:
        if individual_mutation > (random.randint(0, 100) / 100.0):
            genom_list = []
            for i_ in i.genoms:
                if genom_mutation > (random.randint(0, 100) / 100.0):
                    genom_list.append(np.random.normal(0.0,1.0))
                else:
                    genom_list.append(i_)
            ga_list.append(population(genom_list))
        else:
            ga_list.append(i)
    return ga_list

　NNの結果

(学習: 100世代) NN vs NN
(真剣勝負: 500回) NN vs ランダム

---------真剣勝負---------
0) Player1(NN): 1  Player2(Random): 0  Draw: 0
100) Player1(NN): 100  Player2(Random): 1  Draw: 0
250) Player1(NN): 248  Player2(Random): 2  Draw: 1
499) Player1(NN): 493  Player2(Random): 4  Draw: 3

めっちゃ強い！！
ニューロン数とか特徴量を変えたらもっと強くなりそう。

Q学習 vs NN

Q学習（10万回学習)　vs　NN(100世代)

---------真剣勝負---------
0) Player1(Q_learning): 0  Player2(NN): 1  Draw: 0
100) Player1(Q_learning): 44  Player2(NN): 56  Draw: 1
250) Player1(Q_learning): 104  Player2(NN): 146  Draw: 1
499) Player1(Q_learning): 226  Player2(NN): 273  Draw: 1

まとめ

NN+GAが想像以上に強い。そして楽しかった。
DQNとかモンテカルロ木探索とか実装したものがあるのでリクエストがあったら記事にしたいと思います。

34
22
3

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
34
22