ベイズ最適化シリーズ（4）　－ゲームの攻略－

ベイズ最適化シリーズ4回目、今回はゲームを攻略します。

[ベイズ最適化シリーズ（1）　－ベイズ最適化の可視化－](https://qiita.com/shinmura0/items/2b54ab0117727ce007fd)
[ベイズ最適化シリーズ（2）　－アンサンブル学習（Voting）の最適化－](https://qiita.com/shinmura0/items/bcc8c4a06b9a49c943d6)
[ベイズ最適化シリーズ（3）　－XGBoostのハイパーパラメータ探索－](https://qiita.com/shinmura0/items/b2ddd8dfc16a321ec14c)

#ベイズ最適化でゲーム攻略？
ゲームの攻略といえば、強化学習が有名ですが、今回は無謀にもベイズ最適化で
挑みたいと思います。

ベイズ最適化の特長は、以下のとおりです。

・理論が**比較的**簡単（あくまでも、強化学習と比べた場合です。）
・DQNなどと比べて、学習が速い

複雑なゲームになると、強化学習には敵いませんが、簡単なゲームであれば攻略できます。
特に、**覚えゲー**（パターンを記憶すれば簡単に攻略できるゲーム）は得意です。

#弾幕ゲーム
今回は、自作のゲームを題材にします。
内容は、ボールが飛んでくるので、それをかわすゲームです。

![fig.png](https://qiita-image-store.s3.amazonaws.com/0/264781/10def5fc-5013-be46-9e87-13019422f123.png)

プレーヤーは、左右どちらかにカーソルを動かし、ボールに当たらないよう
カーソルを操作するゲームです。ただし、ボールの初期位置は毎回固定です。

こんな感じのゲームです↓

![4_output.gif](https://qiita-image-store.s3.amazonaws.com/0/264781/b8e2d8ea-4617-bc22-bc49-a57794a48455.gif)


・ボールに当たってしまうと、その時点の経過時間がスコアとなります。
　（上の例の場合、スコアは0.85秒です。）
・最長3秒間耐えると、スコア3秒が与えられます。
・スコアを伸ばすために、できるだけボールをかわすことが求められます。

#制御器
カーソルを動かす制御器を以下のように定めます。

```math
F(t)=(t-a)(t-b)(t-c)
```
ただし、tは時間です。そして、Fの符号によってカーソル位置を決めます。

```math
カーソル：右(F(t)>0)\\
カーソル：左(F(t)\leq0)
```

試しに、以下のようにFを決めると、t=0.5秒、1.0秒、1.5秒のときにカーソル位置が
変わります。

```math
F(t)=(t-0.5)(t-1)(t-1.5)
```

動画にすると、以下のようになります。

![test_output.gif](https://qiita-image-store.s3.amazonaws.com/0/264781/a3702670-eacf-b3af-3ae7-6fc6b77b63f0.gif)

#ボールが3つの場合
下のように、ボールが3つのゲームを攻略します。
ただし、ボールの初期位置は固定です。

![2_output.gif](https://qiita-image-store.s3.amazonaws.com/0/264781/ab5bf715-422e-af2e-9295-3ba7c6b02968.gif)

##制御器
制御器は前述したF(t)とします。
お馴染みのGPyOptを使って、ベイズ最適化でa,b,cを探索します。

##結果
a,b,cの探索履歴を表示します。↓
最後の一回で、ようやくベストなパラメータを見つけました。
![Score.png](https://qiita-image-store.s3.amazonaws.com/0/264781/5a203a9a-3637-68ea-f6b7-828bec52b4dc.png)

iteration=7のとき、2.2秒でボールに当たります。
まだまだ良いパラメータとはいえません。
![7_output.gif](https://qiita-image-store.s3.amazonaws.com/0/264781/fb2ad31a-d48e-52f4-2032-1d9217ae7100.gif)

iteration=20のとき、マタドールのようにボールをかわします。
攻略できました。
![best_output.gif](https://qiita-image-store.s3.amazonaws.com/0/264781/f74b2a1b-4225-ba03-106d-ea0dbe289b52.gif)


#ボールが5つの場合
ボールが5つのゲームを攻略します。

##制御器
制御器は以下に定義し、最適なαをベイズ最適化で探索します。

```math
F(t)=(t-\alpha_{1})(t-\alpha_{2})・・・ (t-\alpha_{5})
```

##結果
![best_output.gif](https://qiita-image-store.s3.amazonaws.com/0/264781/a8fc9d61-57bf-69c1-c40c-b32700102114.gif)

当たり判定が微妙ですが、5つのボールを全てかわしています。

#おまけ
ボールが10個でも攻略できちゃいます。
ここまでくると、正に**弾幕ゲーム**ですね！

![best_output.gif](https://qiita-image-store.s3.amazonaws.com/0/264781/c8e3755f-c4d1-ed73-58f0-fbc9adc778f0.gif)


#まとめ
ベイズ最適化を使って、ゲームを攻略しました。
簡単なゲームであれば、ベイズ最適化で攻略できます。

ただし、ランダム性があるものは苦手です。そこは強化学習にお任せしましょう。

#コード
ゲーム環境↓

```py
import numpy as np
import os
import matplotlib.pyplot as plt
import matplotlib.animation as animation
import matplotlib.patches as patches

#gifファイルの保存場所
path = 'movies/'
if not os.path.exists(path):
    os.mkdir(path)
    
#ボールの初期位置
x1 = [1, -1, 1, -1, 1, -0.5, 1.5, -1.8, -1.2, -0.3]
y1 = [73, 79, 31, 23, 67, 61, 43, 53, 37, 18]

#動画の更新周期
cycle_time = 0.1

#ボール位置の更新
def position(y):
  
    y_return = -2.5 + y
    
    return y_return
  
#gifファイルの生成  
def make_gif(frame, iter_, para):
    
    #青玉の初期位置
    x_1 = x1[:]
    y_1 = y1[:]
    
    #グラフの体裁
    fig = plt.figure()
    ax = plt.axes()
        
    #グラフの更新
    def plot(t):
      
        # 現在描写されているグラフを消去
        if t != 0:
            plt.cla()             
        
        #グラフの体裁
        plt.ylim(0,100)
        plt.xlim(-5,5)
        plt.grid(True)
        plt.title('time=' + "%.2f" % (t*cycle_time), fontsize=18)
        
        #ボール位置の更新
        for i in range(len(y_1)):
            y_1[i] = position(y_1[i])
        
        # ボールの位置をグラフにする
        for i in range(len(y_1)):
            plt.scatter(x_1[i],y_1[i], c="b")
        
        #カーソルの位置
        f=1
        for i in range(para.shape[1]):
            f *= (t-para[:,i]/cycle_time)
        
        if f > 0:#右
            e = patches.Rectangle(xy=(0 ,0), width=2, height=0.5, fc='black')
        else:#左
            e = patches.Rectangle(xy=(-2 ,0), width=2, height=0.5, fc='black')
            
        ax.add_patch(e)
        
    #gifの保存
    ani = animation.FuncAnimation(fig, plot, interval = 10, frames=frame)
    ani.save(path + "%s_output.gif"%(str(iter_)), writer="imagemagick")

#gifファイルの保存  
def evaluate_score(para):
    
    #青玉の初期位置
    x_1 = x1[:]
    y_1 = y1[:]
    
    t = 0
    flag = True
    
    #ループを回し、グラフを更新していく
    while(flag):
        before_1 = np.copy(y_1[:])
        
        #ボール位置の更新
        for i in range(len(y_1)):
            y_1[i] = position(y_1[i])
        
        #3秒たったら終了
        if t > 3:
            break
            
        #カーソルの位置
        f=1
        for i in range(para.shape[1]):
            f *= (t-para[:,i])
        
        #ボールと接触しても終了
        for i in range(len(y_1)):
            if before_1[i] * y_1[i] <= 0:#地面に付く瞬間
                if x_1[i]*f > 0:#プレーヤーとボールが同じ側にいる
                    flag = False#ループ終了
                    
        t += cycle_time
        
    return t
```

ベイズ最適化↓

```py
#ベイズ最適化
import GPy
import GPyOpt

try_ = 0

def f(x):
    global try_
    
    score = evaluate_score(x)
    print("iteration:",try_,"score:","%.2f" % (score))
        
    # 3回ごとにgif動画作成
    #if try_%3 == 0:
    #    make_gif(int(score/cycle_time), try_, x)
        
    try_ += 1
    
    return -score

bounds = [{'name': 'a1', 'type': 'continuous', 'domain': (0.1,3)},
          {'name': 'a2', 'type': 'continuous', 'domain': (0.1,3)},
          {'name': 'a3', 'type': 'continuous', 'domain': (0.1,3)},
          {'name': 'a4', 'type': 'continuous', 'domain': (0.1,3)},
          {'name': 'a5', 'type': 'continuous', 'domain': (0.1,3)},
          {'name': 'a6', 'type': 'continuous', 'domain': (0.1,3)},
          {'name': 'a7', 'type': 'continuous', 'domain': (0.1,3)},
          {'name': 'a8', 'type': 'continuous', 'domain': (0.1,3)},
          {'name': 'a9', 'type': 'continuous', 'domain': (0.1,3)},
          {'name': 'a10', 'type': 'continuous', 'domain': (0.1,3)}]

print("Bayesian Optimization")
myBopt = GPyOpt.methods.BayesianOptimization(f=f, domain=bounds, initial_design_numdata=3)
myBopt.run_optimization(max_iter=97)

#探索履歴描画
result_z = myBopt.Y

plt.figure()
plt.plot(-result_z)
plt.xlabel("iteration")
plt.title("Score")
plt.ylabel("Score(time)")
plt.savefig(path + "Score.png")
plt.show()

#最適なパラメータで描画
print("best parameter =")
print(myBopt.x_opt)
para_best = myBopt.x_opt
para_best = para_best.reshape(1,len(y1))
score_test = evaluate_score(para_best)
make_gif(int(score_test/cycle_time), "best", para_best)
```