はじめに

こんにちは。今回は遺伝アルゴリズムでスーパーマリオブラザーズの1-1をクリアしてみましたので、プロセスとコードを備忘録を兼ねて記事にしました。

また、なるべく理論に沿った実装にしたかったので、ライブラリはほとんど利用していません。おそらく配列処理などはもっと良い方法があると思いまが、大目に見てやってください。

遺伝アルゴリズムに関しては、このスライドが死ぬほどわかりやすいのでぜひ見てみてください（笑）

実装に関して

遺伝子長は300

マリオの1-1をクリアするには、最速ではないモデルでおよそ2700フレームが必要です。
皆さんがTASではない限り、フレームごとに入力を変えることはないですし、遺伝子長が長くなると生成や交配などで重くなったり多くのメモリを占有するのでこのようにしました。
10フレームごとに行動を選択することとしました。

遺伝子パターンは0と1

なるべく早くゴールしたかったので、ただ右に走る０と、走りながらジャンプする１の２つに絞りました。

個体数は20

特に理由はありませんが、あまり多くしても結果が変わらないことが多くあったので、私はいつもこのくらいの数にしています。

評価方法：たどり着いた距離

今回はゴールが目標なので、死ぬまで、もしくは時間切れまでに進んだ距離にしました。
移動する床もありませんし、右にしか進まないので、ステップが増えるごとに到達距離が減少することはありません。

交叉方法：1点交叉

今回は遺伝子長も短めで、時系列での配列になるので、これがベストだと思い選びました。
2点交叉でもよかったんですが、1点交叉の方が収束が早かったです。

遺伝子の突然変異率：5％

収束までを早めたかったので少し高めに設定しました。最速モデルを目指す場合はもう少し落とした方がいいと思います。

世代交代手法：最良の2個体はそのまま、残り18個体は上位10個体からランダムに選別し交配

いつも使ってる手法なのであまり考えたことはありませんが、最良個体をそのまま残すことで極端に低い世代が生まれにくくなりますし、個人的に気に入っている設定です。

実装(関数)

適当に実装していきます。普段はパラメータとか遺伝子クラスを継承したりして丁寧に作りますが、今回はわかりやすくマリオに遺伝子を組み込みたいので省略します。
気になる方は多くの先輩方がQiitaで実装を記事にしてくださっているので参考にしてみてください。

遺伝子の作成

def create_gene():
    generation = []
    for x in range(20):
        gene = []
        for y in range(300):
            gene.append(random.choice([0, 1]))
        generation.append(gene)

    return generation

遺伝子の交配

def cross(gene1, gene2):
    cross_point = random.choice(range(len(gene1)))
    new_gene1 = gene1[:cross_point] + gene2[cross_point:]
    new_gene2 = gene2[:cross_point] + gene1[cross_point:]
    return new_gene1, new_gene2

遺伝子の突然変異

def mutation(genes):
    new_genes = []
    for move in genes:
        if random.random() < 0.05:
            if move == 1:
                new_genes.append(0)
            else:
                new_genes.append(1)
        else:
            new_genes.append(move)

    return new_genes

遺伝子のスコアによるソート

def sorts(genes, scores):
    sorted_index = np.argsort(scores)
    sorted_li = []
    for x in sorted_index:
        sorted_li.append(genes[x])
    sorted_li.reverse()
    return sorted_li

主要な関数はこのくらいなので、これを使ってメインを実装していきます。

今回マリオはこちらのライブラリを使用させていただきました。

GitHub: gym-super-mario-bros

実装(メイン)

このような感じにしました。

from nes_py.wrappers import JoypadSpace
import gym_super_mario_bros

import random
import numpy as np

# 移動設定
MOVEMENT = [
    ['right', 'B'],
    ['right', 'A', 'B'],
]

# 遺伝子作成
GENES = create_gene()

# 環境構築
env = gym_super_mario_bros.make('SuperMarioBros-v0')
env = JoypadSpace(env, MOVEMENT)

# 初期設定
TRY_GENERATION = 1000
STEP_COUNT = 10

for x in range(TRY_GENERATION):
    generation_scores = []
    for i, gen in enumerate(GENES):
        stete = env.reset() # 環境リセット
        for j, move in enumerate(gen):
            breaker = False
            for k in range(STEP_COUNT):
                state, reward, done, info = env.step(move)
                if done:
                    breaker = True
                    break
                if i == 0: # 
                    # env.render() # 実際に表示したい場合はコメントアウト
                    pass
            if breaker:
                break
        generation_scores.append(info["x_pos"])
        print("generation: {} genes: {} stops: {} score: {}".format(x + 1, i + 1, j + 1, info["x_pos"]))

    GENES, scores = sorts(GENES, generation_scores)
    NEW_GENES = []
    for k in range(9):
        gene1, gene2 = random.sample(GENES[:10], 2)
        gene1, gene2 = gene.cross(gene1, gene2, mode="one-point")
        NEW_GENES.append(gene1)
        NEW_GENES.append(gene2)
    NEW_GENES = mutation(NEW_GENES)
    NEW_GENES = GENES[:2] + NEW_GENES
    GENES = NEW_GENES
env.close()

結果

やっと遺伝子組み換えマリオがゴールしてくれました！笑 pic.twitter.com/sEFE6RweDA
— そばっしー (@sobasssy) December 15, 2020

簡単なステージではありますが...

第７世代でゴールする個体が現れました

ちょっと早すぎない？まだ２分くらいしか学習してないんだけど

遺伝アルゴリズムの強さを身にしみて感じました。

皆さんもぜひマリオに遺伝子を注入して組み換えまくってくださいね！（笑）

マリオに遺伝子を注入してみた～遺伝アルゴリズム～

はじめに

実装に関して

実装(関数)

実装(メイン)

結果