4/14(日) 足・靴・木型研究会「第2回研究集会」を開催します☆彡

9-3. 遺伝的アルゴリズム(vcopt)でスーパーマリオ1-1をクリアする

本記事の内容は2019年5月13日に更新されました。

やること

動画サイトを探すと「GAでマリオをクリアする」といった動画が見つかります。正直なところ、強化学習でやったほうが良いとは思いますが、どうしてもGAでクリアしたいなら…ということでvcoptを使ってみましょう。

実行環境

Google Colaboratoryが利用可能です。

Google Colaboratory

vcoptの使い方についてはチュートリアルをご参照ください。

vcoptの仕様については最新の仕様書をご参照ください。本記事執筆時とは仕様が異なる場合があります。

pip install

Google Colaboratoryはセッションが切れる度にpip installし直す必要があります。

!pip install gym-super-mario-bros
!pip install vcopt

親玉のgymは最初から入っています。

import

まずは、今回使うパッケージをインポートします。

#マリオ関連のimport
from nes_py.wrappers import BinarySpaceToDiscreteSpaceEnv
import gym_super_mario_bros
from gym_super_mario_bros.actions import SIMPLE_MOVEMENT
env = gym_super_mario_bros.make('SuperMarioBros-1-1-v0')
env = BinarySpaceToDiscreteSpaceEnv(env, SIMPLE_MOVEMENT)

#プロット関連のimport
import matplotlib.pyplot as plt
from matplotlib import animation, rc

#vcopt関連のimport
import numpy as np
import numpy.random as nr
from vcopt import vcopt

マリオの動かし方

こちらのパッケージを使用させていただきます。

gym-super-mario-bros
Super Mario Bros. for OpenAI Gym

こんな感じで、動作確認できました。

#ゲーム環境のリセット
env.reset()

#画像の準備
fig = plt.figure()
ims = []

#繰り返し操作して画面を表示
for i in range(100):
    #0:
    #1:→
    #2:→+ジャンプ
    #3:→→
    #4:→→+ジャンプ
    #5:ジャンプ
    #6:←
    command = nr.randint(1, 7)
    state, reward, done, info = env.step(command)

    plt.imshow(env.render(mode='rgb_array'))
    plt.show()
    
    if done == True:
        break

いろいろ調べてみると、次の仕様が分かりました。

  • 1秒あたり20フレーム(20ステップ)の入力を受け付ける
  • マリオのx座標は取得でき、1-1のゴールのx座標は3161
  • その他、コイン数や残り時間等も取得できる

入力は7種類のようです。

  • 0:(無入力)
  • 1:→
  • 2:→+ジャンプ
  • 3:→→
  • 4:→→+ジャンプ
  • 5:ジャンプ
  • 6:←

動画の表示方法

マリオの画面を1コマ1コマ表示できましたが、見づらいので動画として表示したいです。Google Colaboratoryで動画を表示するため、こちらのサイトを参考にさせていただきました。

これを先ほどのマリオを合体させると、このように表示できました。

#ゲーム環境のリセット
env.reset()

#動画の準備
fig = plt.figure()
ims = []

#繰り返し操作してimsに追加
for i in range(100):
    #0:
    #1:→
    #2:→+ジャンプ
    #3:→→
    #4:→→+ジャンプ
    #5:ジャンプ
    #6:←
    command = nr.randint(1, 7)
    state, reward, done, info = env.step(command)
    
    #imsに追加
    im = plt.imshow(env.render(mode='rgb_array'))
    ims.append([im])
    
    if done == True:
        break
        

#imsを表示
ani = animation.ArtistAnimation(fig, ims, interval=15, blit=True)
rc('animation', html='jshtml')
ani

#保存用
#ani.save('mario.gif', writer='imagemagick')
#ani.save('mario.mp4', writer="ffmpeg")

何を最適化するのか

入力の選択肢。簡単のために、マリオの行動は3(右ダッシュ)と4(右ダッシュジャンプ)の2択しか取れないこととします。入力配列は[3, 3, 4, 3, 4, 4, 3, … , 4, 4]のような感じになり、各入力が各フレームに対応します。走り続けます。

入力配列長。一般に、1-1のクリアタイムは60秒程度なので、20[フレーム/秒]×60[秒]=1200[フレーム]の入力配列を用意したいです。余裕をもって2000[フレーム](100秒)用意しておきたいです。しかし、ちょっと長いですね…。

入力配列長の削減。人間がプレイする際、1秒に20入力もしないと思いますので、1入力を4フレーム継続することにして、入力数を1/4に減らしてみます。よって、500入力で済むことになります。500[入力]×4[フレーム/入力]=2000[フレーム]です。

まとめると、入力配列は[3, 3, 4, 3, 4, 4, 3, … , 4, 4](長さ500個)のような感じで、各入力は4フレーム継続されます。マリオがゴール(x座標=3161)に到達できるように、vcopt().dcGA()で入力配列を最適化します。

(必須)評価関数

入力配列であるparaを受け取り、ゲームオーバーまでプレイします。スコアとして、ゲームオーバー時のx座標をそのまま返しても良いですが、ジャンプ数ができるだけ少なくなるように設計してみます。

#マリオの評価関数
def mario_score(para):
    #ゲーム環境のリセット
    env.reset()
    
    #各paraを4フレームずつ実行し、ゲームオーバーまでプレイ
    end = False
    for p in para:
        #3:→→
        #4:→→+ジャンプ
        for i in range(4):
            state, reward, done, info = env.step(p)
            #ゲームオーバーチェック
            if done == True:
                end = True
                break

        if end == True:
            break
    
    #遠くまで進むほど(x座標)、かつ、ジャンプ割合が少ないほど高スコアとする
    return (info['x_pos']) * (np.sum(para == 3) / len(para))

(任意)poolの可視化関数

poolを受け取って、エリート個体のゲームオーバー時の1コマを見ることにしましょう。pool[best_index ]をparaとして、同様にゲームオーバーまでプレイします。

#poolの可視化(ベストの表示)
def mario_show_pool(pool, **info):
    
    #GA中の諸情報はinfoという辞書に格納されて渡されます
    #これらを受け取って使用することができます
    gen = info['gen']
    best_index = info['best_index']
    best_score = info['best_score']
    mean_score = info['mean_score']
    mean_gap = info['mean_gap']
    time = info['time']
    
    #ゲーム環境のリセット
    env.reset()

    #エリートだけ、各paraを4フレームずつ実行し、ゲームオーバーまでプレイ
    end = False
    for p in pool[best_index]:
        #3:→→
        #4:→→+ジャンプ
        for i in range(4):
            state, reward, done, info = env.step(p)
            #ゲームオーバーチェック
            if done == True:
                end = True
                break

        if end == True:
            break
    
    #情報の表示
    print(gen, mean_score, best_score, info['x_pos'], time)
    print(pool[best_index])
    
    #最後の1コマだけ表示
    plt.imshow(env.render(mode='rgb_array'))
    plt.show()

GAで最適化

para_rangeを用意し、vcopt().dcGA()を実行します。スコアが大きい方向へ最適化しますので、第3引数は大きい数(999999など)にします。また、本来は個体数は自動設定されますが、ここでは時間短縮のためにpool_num=10のコマンドを追加しています。

#パラメータ範囲
para_range = [[3, 4] for j in range(500)]

#GAで最適化
para, score = vcopt().dcGA(para_range,                      #para_range
                           mario_score,                     #score_func
                           999999,                          #aim
                           show_pool_func=mario_show_pool,  #show_para_func=None
                           seed=1,                          #seed=None
                           pool_num=10)
#結果の表示
print(para)
print(score)

0世代目:48%地点で交通事故

0 420.5162 788.448 1528 15.14

20世代目:57%地点で交通事故

20 728.5996 929.316 1801 110.45

30世代目:70%地点で壁にハマってタイムオーバー(最大100秒なので)

30 830.8494 1108.548 2226 182.99

50世代目:87%地点で惜しくも事故死

50 1095.6698 1448.86 2765 343.26

100世代目:ようやくゴール

100 1482.328 1612.11 3161 774.59

700世代目(まだ続けられますが、停止します)

700 2035.0518 2042.006 3161 7818.92

90~100世代目の間に、ゴールに到達したparaが見つかりました。その後は、ジャンプの割合が少なくなるように少しずつ最適化が進みましたが、ほとんど突然変異頼みなので、賢い方法とは言えません。結論、1-1は簡単な問題のため、個体数10でもサクッとゴールに到達できました。

追記

こちらの勉強会では、5種類のアクションでも最適化できました。

AIワークショップ|GA vs 強化学習(DQN) 配管工おじさん、走る (2019/04/24 19:00〜)
## ★オンライン配信を行います★ ~~自宅で参加できるかも!? テスト配信ですので、うまく映らなくても泣かないでください。~~ テスト配信してみました、たぶん大丈夫だと思います! こちらで視聴可能です。 ## 参加方法 抽選や承認はありませんので、好き勝手にお越しください。 ## オンラインコミュニティ ...
  • 0:(無入力)
  • 1:→
  • 2:→+ジャンプ
  • 3:→→
  • 4:→→+ジャンプ

0世代目:56%まで到達

200世代目:64%まで到達

300世代目:78%まで到達

450世代目:87%まで到達

500世代目:ついにゴール

タイトルとURLをコピーしました