Edited at

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

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>

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

※ 結果は上にあります。