LoginSignup
16
13

More than 5 years have passed since last update.

@simanezumi1989(恒彦 嶋津)

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

Last updated at Posted at 2015-04-18

はじめに

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

遺伝的アルゴリズム

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

初期設定

個体を100個体用意する。
このとき，個体の行動は（-1,0,1）=（左,停止,右）の３つであり，遺伝子数は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とする。
個体群からランダムに１組の親を選び，n個体の子供を作る。そして，親と子供を含めたn+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;
    };
};

結果

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

課題

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

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

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

参考資料

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

実装コード


<!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>

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

16
13
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
16
13