JavaScript
遺伝的アルゴリズム
機械学習
人工知能
ブロック崩し

行動を遺伝子とする遺伝的アルゴリズムのブロック崩し攻略

More than 3 years have passed since last update.

はじめに

ブロック崩しを攻略する人工知能を開発しています。前回宣言した通り,各時間の行動を遺伝子とする遺伝的アルゴリズムを実装しました。

遺伝的アルゴリズム

大まかな流れは前回の記事と同じです。大きく違うところは遺伝子です。前回は,行動を決定するニューラルネットワークの重みを遺伝子としていましたが,今回は直接遺伝子が行動を決定します。

初期設定

個体を100個体用意する。
このとき,個体の行動は(-1,0,1)=(左,停止,右)の3つであり,遺伝子数は10000とする。

例えば遺伝子が[0,0,1,0,-1,....]であれば,バーは,停止,停止,右,停止,左,...という動きをする。

var N = 100;//個体数
var individual = new Array(N);
var chrom = 10000;//遺伝子数
//初期の遺伝子決定(ランダム)
for(var n=0;n<N;n++){
    individual[n] = new Array(chrom);
    for(var c=0;c<chrom;c++){
        individual[n][c] = Math.floor(Math.random()*3) - 1;//-1か0か1
    };
};

世代交代モデル

MGGとする。
個体群からランダムに1組の親を選び,n個体の子供を作る。そして,親と子供を含めたn+2個体のうち,もっとも評価の高い個体と,ルーレット選択によって選ばれた1個体を親と入れ替える。

交叉

2点交叉を行う。2点交叉は下の図をみればわかるように,8個体の子供を作る。

2点交叉.png

//親選択
var r1 = Math.floor(Math.random()*N);
var r2 = Math.floor(Math.random()*N);

//二点交叉
//交叉する点を選択
var rand1 = Math.floor(Math.random()*chrom);
var rand2 = rand1 + Math.floor(Math.random()*(chrom-rand1));//0<=r1<r2<遺伝子数
//親+子=2+8 の子供個体をつくる
const CHILDLEN = 10;
var child = new Array(CHILDLEN);
for(var n=0;n<CHILDLEN;n++){
    child[n] = new Array(chrom);
};
for(var c=0;c<chrom;c++){
    var parent=[individual[r1][c],individual[r2][c]];
    child[0][c] = parent[0];//親を代入
    child[1][c] = parent[1];//親を代入

    //上の図のように親個体を代入
    if(c<rand1){
        child[2][c] = parent[0];
        child[3][c] = parent[0];
        child[4][c] = parent[0];
        child[5][c] = parent[0];
        child[6][c] = parent[1];
        child[7][c] = parent[1];
        child[8][c] = parent[1];
        child[9][c] = parent[1];
    }else if(rand1<=c && c<rand2){
        child[2][c] = parent[0];
        child[3][c] = parent[0];
        child[4][c] = parent[1];
        child[5][c] = parent[1];
        child[6][c] = parent[0];
        child[7][c] = parent[0];
        child[8][c] = parent[1];
        child[9][c] = parent[1];                
    }else{
        child[2][c] = parent[0];
        child[3][c] = parent[1];
        child[4][c] = parent[0];
        child[5][c] = parent[1];
        child[6][c] = parent[0];
        child[7][c] = parent[1];
        child[8][c] = parent[0];
        child[9][c] = parent[1];
    };
};

突然変異

//各個体1%で突然変異
const mutantrate = 0.01;
for(var n=0;n<N;n++){
    if(Math.random()<mutantrate){
          //numberOfFrames=個体がゲームした時間 までの遺伝子を突然変異させる
        var m = Math.floor(Math.random()*numberOfFrames);
        individual[n][m] = Math.floor(Math.random()*3) - 1;
    };
};

結果

動画:ブロック崩し 遺伝的アルゴリズム
うまく動いてくれました。前回よりも実行結果が速くいろいろ試すこともできました。

課題

動画のような個体は,多くの犠牲のもと出来上がった個体なので,もっと世代数を減らしたいです。

次回「課題はやらずに前進だ!」

今回遺伝的アルゴリズムがうまく機能したので,次回はこの行動をニューラルネットワークに記憶させます。

参考資料

2点交叉の図
様々な選択・交叉・突然変異
過去の記事
実数値遺伝的アルゴリズムによるニューラルネットワークの重み最適化とブロック崩しへの応用
遺伝的アルゴリズムでナップザック問題を攻略

実装コード

<!DOCTYPE html>
<html lang="ja">
<head>
<meta charset="UTF-8">
<title>ブロック崩し - ニューラルネットワーク - 遺伝的アルゴリズム</title>
<meta http-equiv="Content-Style-Type" content="text/css">
<meta http-equiv="Content-Script-Type" content="text/javascript">
<meta name="robots" content="noindex,nofollow">
<style type="text/css">

body{ -moz-user-select: none; -webkit-user-select: none; -ms-user-select: none; font-size: 20px;}
canvas{ border: none; position: absolute; left: 10px; top: 10px;}
#graph2{ cursor: pointer;}
#data{ position: relative; top: 410px;}
#myPercent{ width: 40px; font-size: inherit;}
#quickCalc{ font-size: inherit;}

</style>
</head>
<body>

<canvas id='graph'></canvas>
<canvas id='graph2'></canvas>
<p id='data'>
    <input type='checkbox' id='resetEverytime' checked>落ちたらリセット<br>
    <input type='text' value='100' id='myPercent'> 
    <input type='button' id='quickCalc' value='描画せずに計算'> 
    <span id='myResult'></span><br>
    <input type="text" id="times" value="100">世代
    <input type="button" id="try" value="計算">
</p>

<script>
(function(){
    //バーを動かす関数
    function moveBar(In){
        var action = In[numberOfFrames];
        if(action==0) reward += 10;
        var tempX = bar.x+action*30; //左右に30ピクセルまたは動かない
        if (tempX<p.r) tempX = p.r; //左の壁に当たったら、それ以上左へは行かない
        else if (tempX>w-p.r) tempX = w-p.r; //右の壁に当たったらそれ以上右へは行かない
        bar.x = tempX;
    };

    function d(ID){ return document.getElementById(ID);}
    var timer;
    var paused = false, gameOver = false, gameEnded = true;
    var numberOfBalls = 0; //使用したボールの数
    var numberOfFrames = 0; //かかったフレーム数(÷33=時間(秒))
    var graph = d('graph'), graph2 = d('graph2');
    var g = graph.getContext('2d'), g2 = graph2.getContext('2d');
    var w = 600, h = 400;
    graph.width = graph2.width = w; graph.height = graph2.height = h;
    g.fillStyle = '#000';
    g.fillRect(0,0,w,h);
    g.save();
    g.font = '30px Arial';
    g.fillStyle = 'white';
    g.fillText('Click to Start',210,220);
    g.restore();

    // pはボール。順にx座標、y座標、半径、速度x成分、速度y成分,色
    var p = {x: 300, y: 20, r: 10, vx: 0, vy: 0, color: '#fff'};

    //barは棒。x座標、yは厚み、Lは長さの半分、edgeは角度が付き始める点の端からの距離
    var bar = {x: 300, y: 10, L: 50, edge: 45, color: '#ff0'};

    //bはブロック。b.xとb.yがともに配列で、xy座標を示す。wはwidthで幅、hはheightで高さ。全て同じ大きさの長方形
    var b = {x: [], y: [], w: 20, h: 10, color: '#88f'};

    var score = 0;

    d('graph2').addEventListener('click',function(){
        if (gameEnded){
            gameEnded = false;
            reset();
            drawBG();
            mainLoop();
        }
        else if (paused){
            paused = false;
            drawBG();
            mainLoop();
        }
        else{
            paused = true;
            clearTimeout(timer);
            g2.font = '30px Arial';
            g2.fillStyle = 'white';
            g2.fillText('paused',250,220);
        }
    },false);

    function reset(){
        bar.x = 300;
        p.x = bar.x; p.y = bar.y+p.r;
        var angle = Math.PI*(10)/180;//Math.PI*(Math.random()*60-30)/180; //-30~30
        p.vx = Math.sin(angle)*12; p.vy = Math.cos(angle)*12; //cosとsinの反転に注意
        b.x = []; b.y = [];
        for (var i=0; i<3; i++) for (var j=0; j<11; j++){
            b.x.push(w/2-10*b.w+j*b.w*2);
            b.y.push(340-i*b.h*2);
        }
        score = numberOfBalls = numberOfFrames = 0;
    }

    function mainLoop(){
        g.fillStyle = '#000';
        g.fillRect(0,0,w,h);
        g.setTransform(1,0,0,-1,0,h);

        //ボールの描画
        g.beginPath();
        g.arc(p.x,p.y,p.r,0,2*Math.PI);
        g.fillStyle = p.color;
        g.fill();
        //ボールの描画

        //バーの描画
        g.fillStyle = bar.color;
        g.fillRect(bar.x-bar.L+p.r+3,0,(bar.L-p.r-3)*2,bar.y); //±3は"遊び"

        //ボールを現在の速度をもとに移動させる
        p.x += p.vx;
        p.y += p.vy;

        //バーを動かす
        moveBar(individual[best[1]]);


        //ここから衝突判定。まずはブロック
        if (p.y>=280){
            for (var i=0,I=b.x.length,hit=false; i<I; i++){
                if ((p.y-b.y[i])*p.vy<0 && Math.abs(p.x-b.x[i])<=b.w && Math.abs(p.y-b.y[i])<=b.h+p.r){
                    p.vy *= -1;
                    hit = true;
                    break;
                }
                else if ((p.x-b.x[i])*p.vx<0 &&Math.abs(p.y-b.y[i])<=b.h && Math.abs(p.x-b.x[i])<=b.w+p.r){
                    p.vx *= -1;
                    hit = true;
                    break;
                }
            }
            if (hit){
                score += 10;
                b.x.splice(i,1); b.y.splice(i,1);
                drawBG();
                if (b.x.length<=0){
                    gameEnded = true;
                    d('graph2').style.cursor = 'pointer';
                    g2.font = '40px Arial';
                    g2.fillStyle = 'white';
                    g2.fillText('SUCCESS !',200,200);
                    var timeLapse = Math.floor(100*numberOfFrames/33)/100;
                    g2.fillText(timeLapse+' sec',220,250);
                    return;
                }
            }
        }
        //↓衝突判定。ここから壁
        if (p.x>w-p.r){ p.x = w-p.r; p.vx *= -1;} //right
        if (p.x<p.r){   p.x = p.r; p.vx *= -1;} //left
        if (p.y>h-p.r){ p.y = h-p.r; p.vy *= -1;} //up
        if (p.y<p.r+bar.y){
            var p_bar = Math.abs(p.x-bar.x);
            if (!gameOver && p_bar<=bar.L){
                var X = (p.x>bar.x) ? 1 : -1; //衝突点のバーの法線ベクトル(X,1);
                if (p_bar<=bar.L-bar.edge) X = 0; //バーの中央
                else if (p_bar<=bar.L-bar.edge/3) X *= (p_bar-bar.L+bar.edge)/100; //0~0.3(バーの端は約73°)
                else X *= 0.3;
                var L = Math.sqrt(X*X+1); //法線ベクトルの長さ
                var vec = {x: X/L, y: 1/L}; //法線ベクトルの正規化
                var dot = vec.x*p.vx+vec.y*p.vy;
                p.y = p.r+bar.y;
                p.vx -= 2*dot*vec.x;
                p.vy -= 2*dot*vec.y;
                if (Math.abs(p.vx)/p.vy>1.5){ //角度が付き過ぎないよう調整
                    var v2 = p.vx*p.vx+p.vy*p.vy;
                    p.vy = Math.sqrt(v2/3.25);
                    p.vx = (p.vx<0) ? -p.vy*1.5 : p.vy*1.5;
                }
            }
            else if (!gameOver && p.y<p.r) gameOver = true;
            else if (gameOver && p.y<-p.r){
                gameOver = false;
                reset();
                numberOfFrames = -1;;
                drawBG();
            }
        }
        numberOfFrames++;
        timer = setTimeout(mainLoop,30); //30ミリ秒後にmainloop実行 (-> 1秒に約30回繰り返す)
    }

    //↓ブロックの描画。動きがないのに毎回描くのは無駄なので、別にして処理を節約。
    function drawBG(){
        g2.clearRect(0,0,w,h);
        g2.font = '20px Arial';
        g2.fillStyle = '#fff';
        g2.fillText('Balls: '+numberOfBalls,15,25);
        g2.fillText('Score: '+score,480,25);
        g2.save();
        g2.setTransform(1,0,0,-1,0,h);
        g2.fillStyle = '#ccf';
        for (var i=0,I=b.x.length; i<I; i++) g2.fillRect(b.x[i]-b.w,b.y[i]-b.h,2*b.w,2*b.h);
        g2.fillStyle = b.color;
        for (var i=0; i<I; i++) g2.fillRect(b.x[i]-b.w+1,b.y[i]-b.h+1,2*b.w-2,2*b.h-2);
        g2.restore();
    };

    console.log("start");
    var reward;


    //↓ここから計算用
    function calculate(In){
        while (numberOfFrames<10000){
            p.x += p.vx;
            p.y += p.vy;
            moveBar(In);
            if (p.y>=280){
                for (var i=0,I=b.x.length,hit=false; i<I; i++){
                    if ((p.y-b.y[i])*p.vy<0 && Math.abs(p.x-b.x[i])<=b.w && Math.abs(p.y-b.y[i])<=b.h+p.r){
                        p.vy *= -1; hit = true; break;}
                    else if ((p.x-b.x[i])*p.vx<0 && Math.abs(p.y-b.y[i])<=b.h && Math.abs(p.x-b.x[i])<=b.w+p.r){
                        p.vx *= -1; hit = true; break;}
                }
                if (hit){
                    score += 10;
                    reward += 10;

                    b.x.splice(i,1); b.y.splice(i,1);
                    if (b.x.length==0) break;
                }
            }
            if (p.x>w-p.r){ p.x = w-p.r; p.vx *= -1;} //right
            if (p.x<p.r){   p.x = p.r; p.vx *= -1;} //left
            if (p.y>h-p.r){ p.y = h-p.r; p.vy *= -1;} //up
            if (p.y<p.r+bar.y){
                var p_bar = Math.abs(p.x-bar.x);
                if (p_bar<=bar.L){
                    var X = (p.x>bar.x) ? 1 : -1; //衝突点のバーの法線ベクトル(X,1);
                    if (p_bar<=bar.L-bar.edge) X = 0; //バーの中央
                    else if (p_bar<=bar.L-bar.edge/3) X *= (p_bar-bar.L+bar.edge)/100; //0~0.3(バーの端は約73°)
                    else X *= 0.3;
                    var L = Math.sqrt(X*X+1); //法線ベクトルの長さ
                    var vec = {x: X/L, y: 1/L}; //法線ベクトルの正規化
                    var dot = vec.x*p.vx+vec.y*p.vy;
                    p.y = p.r+bar.y;
                    p.vx -= 2*dot*vec.x;
                    p.vy -= 2*dot*vec.y;
                    if (Math.abs(p.vx)/p.vy>1.5){ //角度が付き過ぎないよう調整
                        var v2 = p.vx*p.vx+p.vy*p.vy;
                        p.vy = Math.sqrt(v2/3.25);
                        p.vx = (p.vx<0) ? -p.vy*1.5 : p.vy*1.5;
                    }
                }else if (p.y<p.r){
                    break;
                };
            };
            numberOfFrames++;
        };
    };

    //遺伝的アルゴリズム

    //初期設定

    //各時間ごとの行動を遺伝子とする個体を作る

    var N = 100;//個体数
    var individual = new Array(N);
    var chrom = 1000;//遺伝子数

    //初期の遺伝子決定(ランダム)
    for(var n=0;n<N;n++){
        individual[n] = new Array(chrom);
        for(var c=0;c<chrom;c++){
            individual[n][c] = Math.floor(Math.random()*3) - 1;
        };
    };

    //最も良い個体とその番号を入れる配列
    var best = new Array(2);

    document.getElementById("try").addEventListener("click", function(){
        //操作をGENERATION回繰り返す
        var GENERATION = document.getElementById("times").value;
        for(var ge=0;ge<GENERATION;ge++){

            if (ge == GENERATION-1){
                //結果の出力
                var copy_eval = new Array(N);
                for(var n=0;n<N;n++){
                    copy_eval[n] = evaluation(individual[n]);
                }
                best = [copy_eval[0],0];//evaluation(個体)=ゲームスコア
                for(var n=0;n<N;n++){
                    if(copy_eval[n]>best[0]){
                        best[0] = copy_eval[n];
                        best[1] = n;
                    };
                };
                console.log("best : ", best[0], best[1]);
                if(best[0]>1500){
                    console.log("break");
                    break;
                }else{
                    console.log("not break");
                    ge = 0;
                };
            };

            //選択と交叉
            //MGG選択
            const crossrate = 0.8;
            if(crossrate>Math.random()){
                //親選択
                var r1 = Math.floor(Math.random()*N);
                var r2 = Math.floor(Math.random()*N);
                var rand1 = Math.floor(Math.random()*chrom);
                var rand2 = rand1 + Math.floor(Math.random()*(chrom-rand1));//0<=r1<r2<1000
                var crossposition = Math.floor(Math.random()*3);
                //二点交叉
                const CHILDLEN = 10;//2+2^3
                var child = new Array(CHILDLEN);
                for(var n=0;n<CHILDLEN;n++){
                    child[n] = new Array(chrom);
                };
                for(var c=0;c<chrom;c++){
                    var parent=[individual[r1][c],individual[r2][c]];
                    child[0][c] = parent[0];
                    child[1][c] = parent[1];
                    if(c<rand1){
                        child[2][c] = parent[0];
                        child[3][c] = parent[0];
                        child[4][c] = parent[0];
                        child[5][c] = parent[0];
                        child[6][c] = parent[1];
                        child[7][c] = parent[1];
                        child[8][c] = parent[1];
                        child[9][c] = parent[1];
                    }else if(rand1<=c && c<rand2){
                        child[2][c] = parent[0];
                        child[3][c] = parent[0];
                        child[4][c] = parent[1];
                        child[5][c] = parent[1];
                        child[6][c] = parent[0];
                        child[7][c] = parent[0];
                        child[8][c] = parent[1];
                        child[9][c] = parent[1];                
                    }else{
                        child[2][c] = parent[0];
                        child[3][c] = parent[1];
                        child[4][c] = parent[0];
                        child[5][c] = parent[1];
                        child[6][c] = parent[0];
                        child[7][c] = parent[1];
                        child[8][c] = parent[0];
                        child[9][c] = parent[1];
                    };
                };

                var child_eval = new Array(CHILDLEN);
                for(var n=0;n<CHILDLEN;n++){
                    child_eval[n] = evaluation(child[n])
                };


                //最も評価の高い個体の番号を取得
                var top = [child_eval[0],0];
                for(var n=1;n<CHILDLEN;n++){
                    if(child_eval[n]>top[0]){
                        top[0] = child_eval[n];
                        top[1] = n;
                    };
                };

                //ルーレット選択で決定した個体番号の取得
                var total = 0;
                for(var n=0;n<CHILDLEN;n++){
                    total += child_eval[n];
                };
                var arrow = Math.floor(Math.random()*total);
                var select = 0;
                for(var n=0,sum=0.0;n<CHILDLEN;n++){
                    sum += child_eval[n];
                    if(sum>arrow){
                        select = n;
                        break;
                    };
                };

                for(var c=0;c<chrom;c++){
                    individual[r1][c] = child[top[1]][c];
                    individual[r2][c] = child[select][c];
                };      
            };
            //突然変異
            const mutantrate = 0.01;
            for(var n=0;n<N;n++){
                if(Math.random()<mutantrate){
                    var m = Math.floor(Math.random()*numberOfFrames);
                    individual[n][m] = (individual[n][m]+2)%3 - 1;
                };
            };
        };
    },false);

    //誤差関数evaluation(個体[個体番号]) = ゲームスコア
    function evaluation(In){
        reward = 0;
        reset();
        calculate(In);//個体がゲームをする
        return reward//ブロック崩しのスコアを与える
    };
})();
</script>
</body>
</html>

※ コメントアウトは前のコードに依存しているかもしれません。
※ 結果は上にあります。