遺伝的アルゴリズムでFlappy Birdモドキを攻略する

はじめに

遺伝的アルゴリズムで魔界村を攻略したり、スーパーマリオを攻略したりと、動画が公開されています。
私もやってみたい！と思いましたが、ニューラルネットと組み合わせて攻略するのはハードルが高い。ならば超単純化したゲームでやってみようということで、Flappy Birdをさらに単純化した、ゲーム「Fight! Blue Bird」を作り、クリアを目指します。
本家のFlappy Birdとの大きな違いは

• 向かっていく(?)土管(柱)がランダムではない
• 土管(柱)を５本クリアしたらゲームクリア

です。
ゲームはJavaScriptで作りました。もろもろの不細工なところはご容赦ください。
ソースはGitHubにありますので、そちらから取得してください。

遺伝的アルゴリズムの適用

遺伝子の定義

このゲームで動かす部分というのは「鳥をジャンプさせる」ところだけです。時間が流れれば勝手に５本分の柱は通り過ぎますので、ただただ鳥をジャンプさせて柱をくぐるだけです。そこで、0.2秒ごとに「ジャンプする」「ジャンプしない」の2値を20秒に渡って保存した１次のベクトルを遺伝子とします。

• 0 : ジャンプしない
• 1 : ジャンプする
• 要素数 : 20 / 0.2 = 100

<例>
G0[100] = [0,1,1,0, .... ,0,0,1]

今回、遺伝子の数は32個とします。
遺伝子の長さ(要素数)が大きいので、遺伝子数を多くしておきました。
初期遺伝子はランダムに作成します。

var GENE_CNT_MAX = 32; // 4*n (n >= 3).
var GENE_ELEM_MAX = 100;
var JUMP_INTERVAL = 200;
...
// GA Objects
var Ga = function () {
    this.gene = new Array(GENE_CNT_MAX);
    for (var i=0; i<GENE_CNT_MAX; i++) {
        this.gene[i] = new Array(GENE_ELEM_MAX+1);
        this.gene[i][0] = 0; // fitness = 0 (init value)
        for (var j=1; j<GENE_ELEM_MAX+1; j++) {
            this.gene[i][j] = Math.round(Math.random());
        }
    }
}

適応度 (fitness)

適応度とは遺伝子が目標にどれだけ近いかを示す指標です。
今回の場合は、単純にゲーム開始からゲームオーバーまでの時間を適応度とします。
画面のスクロール時間は一定なので、適応度が大きければ、鳥の進んだ距離は必然的に長くなります。
一世代分、つまり32個の遺伝子の実行が終わったら、適応度の大きい順(降順)に並べ替えておきます。今回は実装が分かりやすいのでバブルソートを使っています。
実際のソースでは遺伝子(gene[][])の二次元目の先頭(index 0)に適応度を代入し、ソートしやすくしています。そのため、gene[][]の二次元目の要素数は(GENE_ELEM_MAX+1)になります。

// sort gene list by fitness(gene[gene_index][0])
Ga.prototype.geneBubbleSort = function () {
    var temp;
    for (var i=0; i<GENE_CNT_MAX-1; i++) {
        for (var j=GENE_CNT_MAX-1; j>i; j--) {
            if (this.gene[j][0] > this.gene[j-1][0]) {
                for (var k=0; k<GENE_ELEM_MAX+1; k++) {
                    temp = this.gene[j-1][k];
                    this.gene[j-1][k] = this.gene[j][k];
                    this.gene[j][k] = temp;
                }
            }
        }
    }
}

選択・淘汰 (selection)

次世代に残すのは良い遺伝子、つまり適応度の高い遺伝子を残します。
今回は、図のように適応度降順でソートした遺伝子の下位３つを上位３つで上書きします。

// gene must be sorted by fitness before selection.
Ga.prototype.selection = function() {
    for (var i=0; i<GENE_ELEM_MAX+1; i++) {
        this.gene[GENE_CNT_MAX-1][i] = this.gene[0][i];
        this.gene[GENE_CNT_MAX-2][i] = this.gene[1][i];
        this.gene[GENE_CNT_MAX-3][i] = this.gene[2][i];
    }
}

交叉 (crossover)

交叉は次世代の遺伝子を決定する主要な手順です。
今回は一様交叉を採用しています。一様交叉とは２つの遺伝子において、各要素について50％の確率で交換する交叉方法です。
今回の場合、交叉する遺伝子は、適応度降順にソートし選択・淘汰を行ったのちに、インデックスの隣り合う２つの遺伝子で行います。ただし、適応度1位と2位のものは純粋に次世代に遺伝させるために交叉を行っていません。

k=2n ( 0 < n < 32 ) です。

// gene must be sorted by fitness before crossover.
Ga.prototype.crossover = function () {
    var temp;
    for (var i=2; i<GENE_CNT_MAX-1; i+=2) {
        for (var j=1; j<GENE_ELEM_MAX+1; j++) {
            if (Math.random() > 0.5) { // probability = 50%
                temp = this.gene[i][j];
                this.gene[i][j] = this.gene[i+1][j];
                this.gene[i+1][j] = temp;
            }
        }
    }
}

突然変異 (mutation)

突然変異は局所解に陥った場合の脱出に効果があります。
今回は交叉後にランダムに遺伝子を一つ選び、各要素について1%の確率で値を反転させます。

Ga.prototype.mutation = function() {
    var gene_index;
    var elem_index;
    gene_index = Math.floor(Math.random() * GENE_CNT_MAX);
    for (var i=1; i<GENE_ELEM_MAX+1; i++) {
        if (Math.floor(Math.random() * 100) == 0) { // mutation probability = 1%
            this.gene[gene_index][i] = (this.gene[gene_index][i] + 1) % 2;
        }
    }
}

実行方法

GitHubからダウンロードし、ブラウザでindex_ga.htmlを実行するだけです。
あとは頑張る鳥を応援してください。
といってもクリアするまで莫大な時間がかかる（と思われる）ので、ずっと見てるわけにはいかないのですが...
クリアすると、遺伝子を固定したまま実行を続けるので、クリア時の飛び様を見ることができます(そのはずです）。
ちなみに私の環境で18時間実行して、635世代になり、同一世代のいくつかの遺伝子で1本の柱をくぐることができるところまでは確認しましたが、残念ながらいまだクリアできていません。すいません。
このまま一週間くらいは放置してみます。
果たしてこの実装でクリアできるのか？？
無事にクリアできたら、この記事に追記しておきます。
記事の最後に途中経過と結果を載せました。

• 画面の説明

  • (1) 世代番号 - 遺伝子番号 - 遺伝子要素番号
  • (2) 歴代の最大適応度。カッコ内は最大適応度をたたき出した世代番号
  • (3) 適応度の履歴(15個まで)

最大適応度から何本の柱をクリアしたかを求める式は以下です。

\frac{maxfitness - 3000}{1700}

私の拙いコードではありますが、いろいろなパラメータや、交叉の方法、突然変異の起こし方などを変えて、早いクリアを目指してみてください。
今回、私は使いませんでしたが、ルーレット選択をする関数も用意してあります。よろしければお使いください。

Ga.prototype.roulette = function (sum_fitness) {
    var range = 0;
    var tgt = Math.floor(Math.random() * sum_fitness);
    var tgt_index;
    var inc = 0;
    for (var i=0; i<GENE_CNT_MAX; i++) {
        inc += this.gene[i][0];
        if (tgt <= inc) {
            tgt_index = i;
            break;
        }
    }

    return tgt_index;
}

補足

今回作成していて気になったのが、鳥や柱の移動の再現性です。私がJavaScriptに詳しくないのが問題なのですが、実行画面を見ていると、遺伝子が同じでも、違う結果を出すことがあるようです。
setIntervalで鳥や柱の移動を制御しているのですが、どうも20ms～30msくらいぶれることがあるように見えます。
描画自体も最初はrequestAnimationFrameで行っていたのですが、render関数の呼ばれるタイミングがばらける様に見えたので、結局setIntervalで描画しているのも問題なのかもしれません。
このような誤差がある実装なので、クリアするには「平均的に柱を越えられる位置」に収束させる必要があり、クリアに時間がかかるのかもしれません。

おまけ

index.htmlで実行すると人間がプレイできます。なかなか手ごわいです。

• Spaceキー : ゲーム画面で鳥をJump
• ' j 'キー : Title画面などでカーソルを下に移動
• ' k 'キー : Title画面などでカーソルを上に移動
• ' Enter 'キー : Title画面などで決定

実行途中経過と結果

以下のスクリーンショットのような状態です。
まるまる一週間実行して、4943世代、最高適応度 9144。
各世代での適応度の平均値はだいたい7560程度です。
柱の本数でいうと2本は越えられるようになってきています。
どうやら3531世代に天才が生まれて3本の柱を越えたようですが...

本当は動画(gif)で載せたかったのですが、実行しているPCのパワーが貧弱で、デスクトップの映像保存をすると実行結果が変化してしまう、という状態なので、スクリーンショットにしました。
このペースだとクリアするのに1か月くらいかかりそうですが、ここでやめるのも悔しいので、このまま続けることにします。

2016/08/01追記
開始から3週間、ついにクリアしました。
のですが、証拠のスクリーンショットが取れず...
クリアした後は、遺伝子の更新をしないで動作を続行するはずが、不幸にも遺伝子の世代や適応度が表示されない状態で止まってしまいまして、私にも正確に何世代目でクリアしたか分からずじまいです。大事なところでバグるとは情けない...
肉眼で確認できた限りでは、11000世代くらいで、4本の柱を越えて5本目にぶち当たる、という状態だったので、その時点からほどなくクリアしたのだと思います。
歯切れの悪い最後ですいません。
バグを修正して再トライ...するかは未定です。
お粗末様でした。

参考

Flappy Bird
JavaScriptでゲームを作る初心者用のページを参照して、このゲームの原型を作ったのですが、現在そのページが見つけられません...見つけ次第追記します。