Yuki Nakata's Blog

One color just reflects another

カテゴリ: 人工知能

スーパーマリオブラザーズ 人工知能で世界最速を目指そう! の続きです。

前回、遺伝的アルゴリズムで50~60世代位でステージ1-1をクリアできるようになりました。

今回は世界最速を目指そう!できるかな?

 
世界最速動画です。つい最近、World Recordが更新されました。

で、よく見ると1-1ドラム管を使ってワープしているじゃないですか。いやあ面倒なことになりました。

つまり、下キーを使わなければドラム管ワープできません。前回は上キーと下キーは 入力しない設定にしていました。

ワープなしの最速を目指すということで逃げましょうか。

1-1のタイムを見ると29秒66です。約30秒。どこまで近づけるか?

とりあえず前回のプログラムを改良していきます。

クリアフラグを付けます。マリオがゴールポールにしがみつくと、メモリーアドレス 0x001Dが3になります。

ポールの下に着地するとメモリーアドレス 0x001Dが2になります。これを利用します。そのときのタイムを取得します。

タイムは0x07F8/A Digits of time (100 10 1)です。399から減っていきます。

とりあえずゴールしたらタイムボーナス。TIme * 100点追加。これで動かしてみます。

あとFceuxでLuaScriptを動かすとき、TurboModeで高速に動かしています。

Windowsだと早いのですが、ラズベリーパイだと遅い。ほとんどノーマルスピードと変わりありません。

やりました!コツがわかってきました。まずは結果画像を見てください。
smb-ga1
左から世代、平均評価値、クリアしたマリオの数です。

35世代でまずクリアするようになりました。

41世代、20人中14人がクリア!30分動かしてこの成果です。

評価値も結構安定するようになりました。

遺伝的アルゴリズムでやってみて、数字をちょこちょこ調整しています。

今の段階では
マリオは20体用意。
優秀なマリオを4体に絞る
一点交差、
突然変異は1%がベストです。

あとは下キー入力とベストタイムを表示させてみます。
2016/11/25

require("auxlib");
print ("Hello World!")


key = {}

key["up"] = false;
key["left"] = false;
key["down"] = false;
key["right"] = false;
key["A"] = false;
key["B"] = false;
key["start"] = false;
key["select"] = false;

math.randomseed(os.time())


marioCross = {} --マリオの十字キー
marioA = {} --マリオのAボタン
marioB = {} --マリオのBボタン

marioCross2 = {} --マリオの十字キー コピー用
marioA2 = {} --マリオのAボタン コピー用
marioB2 = {} --マリオのBボタン コピー用

marioGeneration = 1 --世代
marioPlayer = 1
marioMaxPlayer = 20 --マリオ20体用意する
marioValue1 = {} --評価値 右へ行くほど高くなる
marioValue2 = {} --評価値 降順ソート用
marioValue3 = {} --評価値 値が小さい程優秀なマリオ
totalValue = 0
averageValue = 0
averageValue2 = 0
marioClear = 0
clearFlag = 0
timeBonus = 0
deadBonus = 0
deadFlag = 0
  
marioDistance = 0 --マリオが進んだ距離
marioXPosition = 0 -- 0~最大値255までの値をとる
marioHPosition = 0 -- ステージ1-1は12分割される 0~12までの値をとる
totalInput = 100
frameCount = 1
p = 1
q = true
r = true
x = 1
y = 1
z = 1
tableLen = 0
select = false


function tableReset(t)
for k in pairs (t) do
t[k] = nil
end
for i = 1, marioMaxPlayer do
t[i]  = {}
end
end

--マリオを20体生成する
function marioGenerator()
for i = 1, marioMaxPlayer do
marioCross[i]  = {} 
marioA[i] = {}
marioB[i] = {}
end
for i = 1, marioMaxPlayer do
for j = 1, totalInput do
 marioCross[i][j] = math.random(13)
 marioA[i][j] = math.random(20)
 marioB[i][j] = math.random(10)
 --print(i, j, marioA[i][j])
end
end
end

--1から4までの数字を返す
--数字の小さい方が優秀なため、1と2を多く返したい
function onetoeight()
local i
local r
r = math.random(100)
if (r < 40) then
i = 1
elseif (40 <= r and r < 80) then
i = 2
elseif (80 <= r and r < 90) then
i = 3
elseif (90 <= r) then
i = 4
end
--print(i)
return i
end

--マリオを遺伝的アルゴリズムで再生成する
function marioReGenerator()
--table.sort(marioValue2)
--降順でソートする
table.sort(marioValue2, function (a,b) return a>b end)
--print(marioValue1)
--print(marioValue2)
totalValue = 0
averageValue = 0
for i = 1, marioMaxPlayer do
for j = 1, marioMaxPlayer do
 if(marioValue1[i] == marioValue2[j]) then
  marioValue3[i] = j
 end
end
totalValue = totalValue + marioValue1[i]
end
--print(marioValue3)
averageValue = totalValue / marioMaxPlayer
print(marioGeneration.." Generation  Value = "..averageValue.."  Clear = "..marioClear.." / 20")
marioClear = 0
tableReset(marioCross2)
tableReset(marioA2)
tableReset(marioB2)
--優秀なマリオ 1~8位までをコピーする
p = 1
for i = 1, marioMaxPlayer do
if( marioValue3[i] <= 8) then
marioCross2[p] = marioCross[i]
marioA2[p] = marioA[i]
marioB2[p] = marioB[i]
p = p + 1
end
end
tableReset(marioCross)
tableReset(marioA)
tableReset(marioB)
--いわゆる交叉 xとyが選ばれた親マリオの変数
for i = 1, marioMaxPlayer do
x = onetoeight()
y = onetoeight()
for j = 1, totalInput / 2 do
marioCross[i][j] = marioCross2[x][j]
marioA[i][j] = marioA2[x][j]
marioB[i][j] = marioB2[x][j]
end
for j = totalInput / 2, totalInput do
marioCross[i][j] = marioCross2[y][j]
marioA[i][j] = marioA2[y][j]
marioB[i][j] = marioB2[y][j]
end
end
--突然変異
for i = 1, marioMaxPlayer do
for j = 1, totalInput do
r = math.random(100)
if (r == 1) then
marioCross[i][j] = math.random(13)
end
r = math.random(100)
if (r == 1) then
 marioA[i][j] = math.random(20)
end
r = math.random(100)
if (r == 1) then
 marioB[i][j] = math.random(10)
end
end
end
--前世代より上回ったらキー入力を増やす
if(averageValue2 < averageValue ) then
totalInput = totalInput + 70
--print(totalInput)
tableLen =table.maxn(marioCross[1])
--print(tableLen)
for i = 1, marioMaxPlayer do
for j = tableLen + 1, totalInput do
 marioCross[i][j] = math.random(13)
 marioA[i][j] = math.random(20)
 marioB[i][j] = math.random(10)
 --print(i, j, marioA[i][j])
end
end
end
averageValue2 = averageValue
end

--評価値を計算する
function calculateValue()
marioXPosition = memory.readbyte(0x0086)
--0x006D mario Position max 12
  marioHPosition = memory.readbyte(0x006D)
  marioDistance = marioHPosition * 256 + marioXPosition
  marioValue1[marioPlayer] = marioDistance + timeBonus + deadBonus
  marioValue2[marioPlayer] = marioDistance + timeBonus + deadBonus
  --print(marioPlayer, marioValue1[marioPlayer])
end

--変数初期化 ソフトリセット
function resetFunction()
  marioHPosition = 0
  marioXPosition = 0
  marioDistance = 0
  timeBonus = 0
  clearFlag = 0
  deadBonus = 0
  deadFlag = 0
  
  --totalInput = totalInput + 10
  --marioGenerator()
  
  if(marioPlayer < marioMaxPlayer) then
  --print(marioPlayer)
  marioPlayer = marioPlayer + 1
  else
  --世代交代
 
  marioReGenerator()
  marioPlayer = 1
  marioGeneration = marioGeneration + 1
  end
  emu.softreset()
  frameCount = 1
end


function testiup()
function turboAction(self, a) 
emu.speedmode("maximum")
gui.text(10,10,"pressed me!");
end;
function normalAction(self, a) 
emu.speedmode("normal")
gui.text(10,10,"pressed me!");
end;
-- Create a button
turboButton = iup.button{title="Turbo Speed Button"};
-- Set the callback
turboButton.action = turboAction;
normalButton = iup.button{title="Normal Speed Button"};
normalButton.action = normalAction;
box = iup.vbox {turboButton,normalButton}
-- Create the dialog
dialogs = dialogs + 1;
handles[dialogs] = iup.dialog{ box, title="IupDialog Title"; };
-- Show the dialog (the colon notation is equal 
-- to calling handles[dialogs].show(handles[dialogs]); )
handles[dialogs]:show();

end

testiup();
marioGenerator()

while true do
--if (marioPlayer == 1) then
--print(marioGeneration.."generation")
--end
--print(marioPlayer)
local joy = joypad.read(1)
if (joy["select"]) then
if (select == true) then
emu.speedmode("nothrottle")
gui.text(10,10,"High Speed")
else
emu.speedmode("normal")
gui.text(10,10,"Normal Speed")
end
select = not select
end
--ゴールした場合
  if(memory.readbyte(0x001D) == 3 and clearFlag == 0) then
  local timeA, timeH, timeT, timeO
  clearFlag = 1
marioClear = marioClear + 1
timeH = memory.readbyte(0x07F8)
timeT = memory.readbyte(0x07F9)
timeO = memory.readbyte(0x07FA)
timeA = (100 * timeH) + (10 * timeT) + timeO
--print(timeA)
timeBonus = timeA * 10
  end
--死亡した場合
if(memory.readbyte(0x075A) == 1 and deadFlag == 0) then
  deadFlag = 1
deadBonus = -200
  end
  
--入力が無くなった場合と死亡した場合、評価値を算出しリセット
if(totalInput < frameCount or memory.readbyte(0x075A) == 1) then
memory.writebyte(0x075A, 8)
--print(marioPlayer, totalInput, frameCount, memory.readbyte(0x075A))
    calculateValue()
    resetFunction()
  end
  
  
  
key["up"] = false;
key["down"] = false;
if( marioCross[marioPlayer][frameCount] == 1) then
key["left"] = true;
key["right"] = false;
else
key["right"] = true;
key["left"] = false;
  end

  if(marioA[marioPlayer][frameCount] == 1) then
key["A"] = false;
else
key["A"] = true;
end

  if(marioB[marioPlayer][frameCount] == 1 ) then
key["B"] = false;
else 
key["B"] = true;
end

  -- Execute instructions for FCEUX
  joypad.set(1, key)

  
  

  --スタート画面に戻ったらスタートボタンを押す
  if(memory.readbyte(0x07F8) == 4 and memory.readbyte(0x07F9) == 0  and memory.readbyte(0x07FA) == 1) then
    joypad.set(1, {start = true})
    --print("reset")
    frameCount = 1
  end

  emu.frameadvance() -- This essentially tells FCEUX to keep running

  --print (memory.readbyte(0x0086));

  frameCount = frameCount + 1
end   

スーパーマリオブラザーズ 人工知能で世界最速を目指そう!

 

これをマネしてやってみたいと思います。

ステージ1-1をクリアできることは確認しています。

スーパーマリオブラザーズ ステージ1-1世界最速を目指して見ましょう。

必要なものはFCEUXというエミュレーターとスーパーマリオブラザーズのロムです。 あとはメモ帳のようなテキストエディタです。

Win、Linux, Macでもできるでしょう。

FCEUXにはコミュニケーション機能が付いており、LuaScriptを使うことでゲームをコントロールすることができます。

私もLuaScriptは初めてでしたが、Pythonみたいなものと思って構いません。ほぼPythonです。

やってみて思ったのが非常に面白い。だってマリオが動くんですから。 300px-スクラッチキャット
スクラッチの猫を動かすようなものです。マリオを動かしてみましょう。

辛気臭いC言語やるよりよっぽど良いでしょう。 

まず初めはhelloworldを表示させます。

ファイル名は何でもいいのですが、SMB-GA.luaにしました。

print ("Hello World!")
スーパーマリオブラザーズを読み込んでSMB-GA.luaを実行するとHello Worldが表示されます。

 fceux1
マリオを右に動かしてみましょう。
print ("Hello World!")

--無限ループ
while true do
  joypad.set(1, {right=true})
  emu.frameadvance()
end 

スタートを押してゲームを開始、スクリプトを実行するとマリオが右へ進みます。
もちろん最初のクリボーにぶつかり、死にます。

ゲームを改造します。
マリオの残機を99にしてみましょう。

ToolからMemory Searchを起動します。
fceux2
アドレス075AのValueというところを見てください。2になっています。

この2がマリオの残り数を表示しています。ここを99にすると99人になります。
同じように点数を12345670、コインを99に変更します。

ゲームによってメモリーの意味が違ってきます。
Super Mario Bros.:RAM map このサイトを参考にするといいでしょう。

fceux3
print ("Hello World!")

--無限ループ
while true do
  joypad.set(1, {right=true})
  
  --マリオの残機を99に変更する
  memory.writebyte(0x075A, 99)
  
  --得点を12345670に変更する
  memory.writebyte(0x07DD, 1);
  memory.writebyte(0x07DE, 2);
  memory.writebyte(0x07DF, 3);
  memory.writebyte(0x07E0, 4);
  memory.writebyte(0x07E1, 5);
  memory.writebyte(0x07E2, 6);
  memory.writebyte(0x07E2, 7);
  
  --コインを99に変更する
  memory.writebyte(0x07ED, 9);
  memory.writebyte(0x07EE, 9);
  
  emu.frameadvance()
end 

ここまでくればできたようなもので、あとはクリアできるようにキーボード入力を入れたらいいだけです。もちろんそこは機械学習で最適化をさせていきます。

難しいです。ある程度こちらで動きを促してやらないと永久にクリアできません。
右を多く、大ジャンプを多くしてやります。

2016/11/23現在のプログラム
60世代ぐらいで1-1をクリアできるようになります。試してみてください。

require("auxlib");
print ("Hello World!")


key = {}

key["up"] = false;
key["left"] = false;
key["down"] = false;
key["right"] = false;
key["A"] = false;
key["B"] = false;
key["start"] = false;
key["select"] = false;

math.randomseed(os.time())


marioCross = {} --マリオの十字キー
marioA = {} --マリオのAボタン
marioB = {} --マリオのBボタン

marioCross2 = {} --マリオの十字キー コピー用
marioA2 = {} --マリオのAボタン コピー用
marioB2 = {} --マリオのBボタン コピー用

marioGeneration = 1 --世代
marioPlayer = 1
marioMaxPlayer = 20 --マリオ20体用意する
marioHalfPlayer = 20 / 2
marioValue1 = {} --評価値 右へ行くほど高くなる
marioValue2 = {} --評価値 降順ソート用
marioValue3 = {} --評価値 値が小さい程優秀なマリオ
totalValue = 0
averageValue = 0
averageValue2 = 0

marioDistance = 0 --マリオが進んだ距離
marioXPosition = 0 -- 0~最大値255までの値をとる
marioHPosition = 0 -- ステージ1-1は12分割される 0~12までの値をとる
totalInput = 100
frameCount = 1
p = 1
q = true
r = true
x = 1
y = 1
tableLen = 0
select = false


function tableReset(t)
for k in pairs (t) do
t[k] = nil
end
for i = 1, marioMaxPlayer do
t[i]  = {}
end
end

--マリオを20体生成する
function marioGenerator()
for i = 1, marioMaxPlayer do
marioCross[i]  = {} 
marioA[i] = {}
marioB[i] = {}
end
for i = 1, marioMaxPlayer do
for j = 1, totalInput do
 marioCross[i][j] = math.random(13)
 marioA[i][j] = math.random(20)
 marioB[i][j] = math.random(10)
 --print(i, j, marioA[i][j])
end
end
end

--マリオを遺伝的アルゴリズムで再生成する
function marioReGenerator()
--table.sort(marioValue2)
--降順でソートする
table.sort(marioValue2, function (a,b) return a>b end)
--print(marioValue1)
--print(marioValue2)
totalValue = 0
averageValue = 0
for i = 1, marioMaxPlayer do
for j = 1, marioMaxPlayer do
 if(marioValue1[i] == marioValue2[j]) then
  marioValue3[i] = j
 end
end
totalValue = totalValue + marioValue1[i]
end
--print(marioValue3)
averageValue = totalValue / marioMaxPlayer
print(marioGeneration.." Generation  averageValue  "..averageValue)
tableReset(marioCross2)
tableReset(marioA2)
tableReset(marioB2)
--優秀なマリオ 1~8位までをコピーする
p = 1
for i = 1, marioMaxPlayer do
if( marioValue3[i] <= 8) then
marioCross2[p] = marioCross[i]
marioA2[p] = marioA[i]
marioB2[p] = marioB[i]
p = p + 1
end
end
tableReset(marioCross)
tableReset(marioA)
tableReset(marioB)
--いわゆる交叉 xとyが選ばれた親マリオの変数
for i = 1, marioMaxPlayer do
x = math.random(8)
y = math.random(8)
for j = 1, totalInput / 2 do
marioCross[i][j] = marioCross2[x][j]
marioA[i][j] = marioA2[x][j]
marioB[i][j] = marioB2[x][j]
end
for j = totalInput / 2, totalInput do
marioCross[i][j] = marioCross2[y][j]
marioA[i][j] = marioA2[y][j]
marioB[i][j] = marioB2[y][j]
end
end
--突然変異
for i = 1, marioMaxPlayer do
for j = 1, totalInput do
r = math.random(100)
if (r == 3) then
marioCross[i][j] = math.random(13)
 marioA[i][j] = math.random(20)
 marioB[i][j] = math.random(10)
end
end
end
if(averageValue2 < averageValue ) then
totalInput = totalInput + 50
end
averageValue2 = averageValue
--print(totalInput)
tableLen =table.maxn(marioCross[1])
--print(tableLen)
for i = 1, marioMaxPlayer do
for j = tableLen + 1, totalInput do
 marioCross[i][j] = math.random(13)
 marioA[i][j] = math.random(20)
 marioB[i][j] = math.random(10)
 --print(i, j, marioA[i][j])
end
end
end

--評価値を計算する
function calculateValue()
marioXPosition = memory.readbyte(0x0086)
--0x006D mario Position max 12
  marioHPosition = memory.readbyte(0x006D)
  marioDistance = marioHPosition * 256 + marioXPosition
  marioValue1[marioPlayer] = marioDistance
  marioValue2[marioPlayer] = marioDistance
  --print(marioPlayer, marioValue1[marioPlayer])
end

--変数初期化 ソフトリセット
function resetFunction()
  marioHPosition = 0
  marioXPosition = 0
  marioDistance = 0
  --totalInput = totalInput + 10
  --marioGenerator()
  
  if(marioPlayer < marioMaxPlayer) then
  --print(marioPlayer)
  marioPlayer = marioPlayer + 1
  else
  --世代交代
 
  marioReGenerator()
  marioPlayer = 1
  marioGeneration = marioGeneration + 1
  end
  emu.softreset()
  frameCount = 1
end


function testiup()
function turboAction(self, a) 
emu.speedmode("maximum")
gui.text(10,10,"pressed me!");
end;
function normalAction(self, a) 
emu.speedmode("normal")
gui.text(10,10,"pressed me!");
end;
-- Create a button
turboButton = iup.button{title="Turbo Speed Button"};
-- Set the callback
turboButton.action = turboAction;
normalButton = iup.button{title="Normal Speed Button"};
normalButton.action = normalAction;
box = iup.vbox {turboButton,normalButton}
-- Create the dialog
dialogs = dialogs + 1;
handles[dialogs] = iup.dialog{ box, title="IupDialog Title"; };
-- Show the dialog (the colon notation is equal 
-- to calling handles[dialogs].show(handles[dialogs]); )
handles[dialogs]:show();

end

testiup();
marioGenerator()

while true do
--if (marioPlayer == 1) then
--print(marioGeneration.."generation")
--end
--print(marioPlayer)
local joy = joypad.read(1)
if (joy["select"]) then
if (select == true) then
emu.speedmode("nothrottle")
gui.text(10,10,"High Speed")
else
emu.speedmode("normal")
gui.text(10,10,"Normal Speed")
end
select = not select
end
--入力が無くなった場合と死亡した場合、評価値を算出しリセット
if(totalInput < frameCount or memory.readbyte(0x075A) == 1) then
memory.writebyte(0x075A, 8)
--print(marioPlayer, totalInput, frameCount, memory.readbyte(0x075A))
    calculateValue()
    resetFunction()
  end

key["up"] = false;
key["down"] = false;
if( marioCross[marioPlayer][frameCount] == 1) then
key["left"] = true;
key["right"] = false;
else
key["right"] = true;
key["left"] = false;
  end

  if(marioA[marioPlayer][frameCount] == 1) then
key["A"] = false;
else
key["A"] = true;
end

  if(marioB[marioPlayer][frameCount] == 1 ) then
key["B"] = false;
else 
key["B"] = true;
end

  -- Execute instructions for FCEUX
  joypad.set(1, key)

  
  

  --スタート画面に戻ったらスタートボタンを押す
  if(memory.readbyte(0x07F8) == 4 and memory.readbyte(0x07F9) == 0  and memory.readbyte(0x07FA) == 1) then
    joypad.set(1, {start = true})
    --print("reset")
    frameCount = 1
  end

  emu.frameadvance() -- This essentially tells FCEUX to keep running

  --print (memory.readbyte(0x0086));

  frameCount = frameCount + 1

はむくんさんのライフゲームの世界が素晴らしいです。

自分でも簡単にできますので再現してみましょう。

Gollyというソフトをダウンロードします。最新版はバージョン2.7です。

Golly ダウンロード

実行してみるとわかりますが、Patterns -> Life の中にライフゲームのサンプルが入っています。

Golly


ライフゲームの世界1
 
周期416の X型をしたgunです。
Patterns -> Life -> Guns ->  2c5-spaceship-gun-p416.rle

ライフゲームの世界2 複雑系

Oscillators 振動子編
Patterns -> Life -> Osillators -> DRH-oscillators.rle

ライフゲームの世界3 複雑系

宇宙船編
Patterns -> Life -> Spaceships ->smallest-low-period.rle
Patterns -> Life -> Spaceships ->adjustable-Corder-lineship.rle
Patterns -> Life -> Spaceships ->adjustable-Corder-lineship.rle

ライフゲームの世界4 複雑系

Synthesis編 合成
Patterns -> Life -> Synthesis -> make-harbor.rle
Patterns -> Life -> Synthesis -> make-p11.rle
Patterns -> Life -> Synthesis -> make-p33.rle

ライフゲームの世界5 複雑系

休憩編
Golly2

横に8192セル並べるとフラクタル図形を作ることができます。
適当な名前でrleファイルを作成し、メモ帳で開いてみてください。
次をコピーで張り付けて保存してください。

#CXRLE Pos=-52,0
x = 8192, y = 1, rule = B3/S23
8192o!

 
ライフゲームの世界6  複雑系

Puffer編 しゅぽしゅぽ列車
Patterns -> Life -> Puffers -> puffer-train.rle
Patterns -> Life -> Puffers -> line-puffer-superstable.rle
Patterns -> Life -> Puffers -> c4-diagonal-puffer.rle
Patterns -> Life -> Puffers -> zigzag-wickstrecher.rle

ライフゲームの世界7  複雑系

Breeder編 移動式のグライダー銃
Patterns -> Life -> Breeders -> breeder.lif
Patterns -> Life -> Breeders -> c4-diag-switch-engines.rle
Patterns -> Life -> Breeders -> spacefiller.rle
Patterns -> Life -> Guns -> golly-ticker.rle

ライフゲームの世界8  複雑系

メタピクセル編
ついにライフゲームでライフゲームを作ります。圧巻。
何を言ってるかわからねえが、そういうことです。
Patterens -> HashLife -> metapixel-gallaxy.mc.gz
Patterens -> HashLife -> metapixel-p216-gun.mc.gz
メタピクセルは遅いので+キーを押してステップ数を上げて、早回ししてください。

ライフゲームの世界 最終回

自己複製編
ジョン・フォン・ノイマンとかいう化け物が登場します。
彼は頭の中だけで自己複製するコンピューターを作り上げました。

ライフゲームのように格子状で単純な規則をあてはめる、そのようなモデルをセルオートマンという。
つまりライフゲームはセルオートマンの中の一つだ。

gollyの中にセルオートマンのパターンは見つかりませんでした。探しておきます。
簡単に再現できますので試してみてください。













↑このページのトップヘ