2011年12月10日土曜日

Ragnarok Online の AI に機械学習を入れてみた

Git hub を使えと言われたのだけど、使うのに登録やら設定やらしなければいけないのが面倒なので止めました。
一発ネタの Lua スクリプトを公開するためだけだしなぁ。

ということで久しぶりにブログをアップしてファイル添付をしようと思ったのですが、何と Blogger ではファイルの添付は出来ない模様。

短いとは言えコメント入れたら800行とか行くので、とりあえず Lua で書いた ML の部分だけ。


function dotproduct(v1,v2)
local val = 0
for k,v in pairs(v1) do
if (v2[k]) then
val = val + v * v2[k]
end
end
return val
end

function logsumexp(x,y)
if (not x) then
return y
end
if (x == y) then
return x + 0.69314718055
end
local min = math.min(x,y)
local max = math.max(x,y)
if (max > min + 50) then
return max
else
return max + math.log(math.exp(min-max)+1)
end

end

MLR = {} -- multiclass logistic regression
BLR = {} -- binary class logistic regression

MLR.new = function(num,r,c)
local obj = {}
obj.class = num
obj.eta = r
obj.pcache = {}
obj.cc = c*obj.eta
for i = 1, num, 1 do
obj[i] = {} -- parameters
obj.pcache[i] = {} -- penalties
end

obj.predict = function(self, fv)
local max = nil
local pc = 1
for i = 1, self.class, 1 do
local v = dotproduct(fv,self[i])
max = max or v
if (v > max) then
max = v
pc = i
end
end
return pc
end

obj.update = function(self,cc,fv)
local values = {}
local z = nil
for i = 1, self.class, 1 do
values[i] = dotproduct(fv,self[i])
z = logsumexp(z,values[i])
end
for i = 1, self.class, 1 do
local grad = -math.exp(values[i]-z)
if (i == cc) then
grad = grad + 1
end
for k,v in pairs(fv) do
if (type(v) == "number") then
if (self[i][k]) then
self[i][k] = self[i][k] + self.eta * grad * v
else
self[i][k] = self.eta * grad * v
end
if (not self.pcache[i][k]) then
self.pcache[i][k] = 0
end
local p = self.cc - self.pcache[i][k]
self.pcache[i][k] = self.cc
self[i][k] = self[i][k]/(1+p) -- 本当は正則化のペナルティも減衰させるんだけどとりあえず定数でやっておく
end
end
end
self.cc = self.cc + self.eta
end

return obj
end

BLR.new = function(r)
local obj = {}
obj.eta = r

obj.predict = function(self,fv)
local v = dotproduct(fv,self)
return 1/(1+math.exp(-v))
end

obj.update = function(self,cc,fv) -- cc:1(correct) or 0(incorrect)
local grad = cc - self:predict(fv)
for k,v in pairs(fv) do
if (type(v) == "number") then
if(self[k]) then
self[k] = self[k] + self.eta * grad * v
else
self[k] = self.eta * grad * v
end
end
end
end

return obj
end

----
-- A learning to rank Algorithm
-- Top 1 ListNet
----
ListNet = {}
ListNet.new = function(r,c)
local obj = {}
obj.eta = r
obj.pcache = {}
obj.cc = c*obj.eta

obj.predict = function(self,instances)
local values = {}
local max = nil
local id = nil
for k,v in pairs(instances) do
values[k] = dotproduct(v,self)
max = max or values[k]
id = id or k
if (values[k] > max) then
max = values[k]
id = k
end
end
if (not max) then
return
end
return id
end

obj.update = function(self,instances,c)
local values = {}
local z = nil
for k,v in pairs(instances) do
values[k] = dotproduct(v,self)
z = logsumexp(z,values[k])
end
for k,v in pairs(instances) do
local grad = -math.exp(values[k] - z)
if (c == k) then
grad = grad + 1
end
for i,w in pairs(v) do
if (self[i]) then
self[i] = self[i] + self.eta * grad * w
else
self[i] = self.eta * grad * w
end
if (not self.pcache[i]) then
self.pcache[i] = 0
end
local p = self.cc - self.pcache[i]
self.pcache[i] = self.cc
self[i] = self[i]/(1+p) -- 本当は正則化のペナルティも減衰させるんだけどとりあえず定数でやっておく
end
end
self.cc = self.cc + self.eta
end
return obj
end


学習データがストリームとしてやってくるので、学習率のスケジューリングなどは今回はやっていません。
また、FOBOSによるL2正則化の累積ペナルティが追加学習を行う時にはリセットされています。
何でこんなことになっているのかというと、面倒くさかったというのももちろんある(というか大半はそれ)のですが、Ragnarok Online ではマップごとで出現する敵のタイプが異なるため、敵に関するアクティブになる素性は明らかにマップごとに分かれます。
そのため、ペナルティの累積を常に残しておくと、各マップで学習を行って以前行ったことのあるマップに行くと、AI の学習をさせた途端その事例に含まれる素性のパラメータが全て0になってしまい最初からやり直し・・・ということが想定されるので、そういう風にならないようにしています。
これはどういうことかというと、行動やスキルのモデルファイルは1つに見えますが、実際にはマップごとに別々にモデルを学習しているのと同じ事になっています。

Ragnarok Online の AI 部分については使ってみたいという希望者が居るようなら改めて公開考えてみます。