目次
- 初期化処理
- フレームごとの処理
- 学習結果
■初期化処理
まずは、初期化処理コードを下記に示す。
const CELL_WIDTH = 64 # セル幅
const MAZE_WIDTH = 12 # 横方向セル数
const MAZE_HEIGHT = 10 # 縦方向セル数
const MAZE_SIZE = MAZE_WIDTH * MAZE_HEIGHT # 全体セル数
const REWARD_GOAL = 1.0
const REWARD_TRAP = -1.0
var rng = RandomNumberGenerator.new() # 乱数ジェネレータ
func _ready():
rng.randomize() # 乱数ジェネレータシードランダム化
qvalue.resize(MAZE_SIZE) # Q値テーブルサイズ設定
dstToSrc.resize(MAZE_SIZE) # 移動元リストサイズ設定
for i in range(dstToSrc.size()):
dstToSrc[i] = []
qUpLabel.resize(MAZE_SIZE) # 上移動Q値最表示用ラベル
qLeftLabel.resize(MAZE_SIZE) # 左移動Q値最表示用ラベル
qRightLabel.resize(MAZE_SIZE) # 右移動Q値最表示用ラベル
qDownLabel.resize(MAZE_SIZE) # 下移動Q値最表示用ラベル
for y in range(MAZE_HEIGHT): # 全座標について
for x in range(MAZE_WIDTH): # 全座標について
var ix = xyToIX(x, y) # (x, y) → ix 変換
if $TileMap.get_cell(x, y) <= FLOOR2: # ix が床の場合
qvalue[ix] = [0.0, 0.0, 0.0, 0.0] # 上、左、右、下方向に移動Q値
#qvalue[ix] = [1.0, 1.0, 1.0, 1.0] # 上、左、右、下方向に移動Q値（楽観的）
# 上左右下移動Q値最表示用ラベル生成
var label = QValueLabel.instance() # Q値最表示用ラベルインスタンス化
label.rect_position = Vector2(x*CELL_WIDTH, y*CELL_WIDTH)
qUpLabel[ix] = label
add_child(label)
label = QValueLabel.instance()
label.rect_position = Vector2(x*CELL_WIDTH, y*CELL_WIDTH+CELL_WIDTH*0.23)
qLeftLabel[ix] = label
add_child(label)
label = QValueLabel.instance()
label.rect_position = Vector2(x*CELL_WIDTH, y*CELL_WIDTH+CELL_WIDTH*0.23*2)
qRightLabel[ix] = label
add_child(label)
label = QValueLabel.instance()
label.rect_position = Vector2(x*CELL_WIDTH, y*CELL_WIDTH+CELL_WIDTH*0.23*3)
qDownLabel[ix] = label
add_child(label)
# 壁があり移動不可の場合はQ値を -1 に設定
if !canMoveTo(ix - MAZE_WIDTH): qvalue[ix][0] = REWARD_TRAP
else: dstToSrc[ix - MAZE_WIDTH].push_back(ix)
if !canMoveTo(ix - 1): qvalue[ix][1] = REWARD_TRAP
else: dstToSrc[ix - 1].push_back(ix)
if !canMoveTo(ix + 1): qvalue[ix][2] = REWARD_TRAP
else: dstToSrc[ix + 1].push_back(ix)
if !canMoveTo(ix + MAZE_WIDTH): qvalue[ix][3] = REWARD_TRAP
else: dstToSrc[ix + MAZE_WIDTH].push_back(ix)
updateQValueLabel(ix) # ix 位置のQ値を表示
elif $TileMap.get_cell(x, y) == GOAL: # ゴール位置の場合
goalPos = Vector2(x, y) # ゴール位置 (x, y) 保存
goalIX = ix # ゴール位置ix保存
乱数ジェネレータオブジェクトを変数として生成し、randomize() をコールして、乱数系列をランダムにしている。
テストを行う場合は、set_seed(value) でシードを指定し乱数系列を常に同じにすると、デバッグが行いやすい。
次に各種配列のサイズを指定している。ほとんどの配列サイズは MAZE_SIZE だ。
最後に、for 文で x, y を回し、すべてのセルについて以下の処理を行う。
まずは、(x, y) 位置が床であるかどうかをチェックし、そうであればQ値のデフォルト値を設定する。
ついで、Q値表示用のラベルを生成し、そのセル位置に配置する。
最後に (x, y) 位置から上下左右に移動可能かどうかを調べ、不可であれは Q値を最小値（REWARD_TRAP）に設定している。 こうしておけば、通常移動は最大Q値の方向に移動するので、 毎回移動可能かどうかを調べなくても、その方向に移動することはなくなる。
ゴール位置の場合は、ゴール位置を保存しておき、後でゴール位置を高速に参照可能にしている。
迷路はエディタで自由に変更可能なので、初期化時にタイルマップを参照し、処理を行っているというわけだ。
■フレームごとの処理
下記にフレームごとの処理コードを示す。
const ALPHA = 0.2
const GAMMA = 0.99
const EPSILON = 0.05 # この確率でランダム行動
func _process(delta):
if !started: return
var ix = xyToIX(playerPos.x, playerPos.y) # 現在位置
var dir # 移動方向 0:上、1：左、2:右、3:下
var to # 移動先IX
if rng.randf_range(0, 1.0) < EPSILON: # ランダムウォーク
while true: # 移動可能方向が見つかるまでループ
dir = rng.randi_range(0, 3) # [0, 4)
to = ix + [-MAZE_WIDTH, -1, +1, +MAZE_WIDTH][dir]
if canMoveTo(to): # 移動可能の場合
break;
else: # 最大Q値の行動を選択、同じ値がある場合はその中から選択
var mx = REWARD_TRAP - 1 # 最大Q値
var lst = [] # 最大Q値を与えるアクション位置
for i in range(qvalue[ix].size()): # ix 位置の各Q値について
if qvalue[ix][i] != REWARD_TRAP: # 移動不可でない場合
if qvalue[ix][i] > mx: # 最大Q値の場合
mx = qvalue[ix][i] # 値、位置を保存
lst = [i]
elif qvalue[ix][i] == mx: # 最大Q値と等しい場合
lst.push_back(i) # リストに追加
if lst.size() > 1: # 最大Q値を与えるアクションが複数ある場合
dir = lst[rng.randi_range(0, lst.size() - 1)] # ランダムに選択
else: # 最大Q値を与えるアクションがひとつだけの場合
dir = lst[0] # 最初のアクションを選択
to = ix + [-MAZE_WIDTH, -1, +1, +MAZE_WIDTH][dir] # 移動先
moveTo(to) # 移動処理
nSteps += 1
updateStepsLabel()
# Q値テーブル更新処理
var reward = 0 # 報酬
var maxQ = 0 # 最大Q値
match $TileMap.get_cell(playerPos.x, playerPos.y): # 移動先タイルで分岐
GOAL: # ゴールに到達した場合
reward = REWARD_GOAL
started = false
sumSteps += nSteps
if nRound % 10 == 0:
print("avg steps = %.1f" % (sumSteps / 10.0) )
sumSteps = 0
TRAP: # トラップに到達した場合
reward = REWARD_TRAP
started = false
_: # ゴール、トラップ以外の場合
reward = -0.01 # 長くさまようのはマイナス報酬
if qvalue[to] != null:
maxQ = qvalue[to].max() # 最大Q値取得
# 更新処理
qvalue[ix][dir] += ALPHA * (reward + GAMMA * maxQ - qvalue[ix][dir])
updateQValueLabel(ix)
if !started && nRoundRemain != 0: # ゴール到達＆連続実行の場合
nRoundRemain -= 1 # 残りラウンド数デクリメント
if nRoundRemain != 0: doStart() # 残りラウンド数が0でなければスタート処理
Godot では毎フレーム（通常60FPS）ごとに _process(delta) がコールされるので、フレームごとの処理はここに記述する。 エージェントの１ステップの移動とQ値テーブルの更新は、この _process(delta) で行っている。
最初に [0, 1] 範囲の乱数を発生させ EPSILON の確率でランダムウォークを行う。
これは「ε-greedy」と呼ばれる処理で、Q学習が局所最適値に陥ることを防ぐためのものだ。
このような迷路の場合、ゴールまでの経路をひとつ見つけると、それがいかに遠回りの経路であっても、 次回以降はその経路ばかりを選択してしまい、それ以上学習が進まなくなってしまうからだ。
その対処として、少ない確率でランダムに行動を選び、局所最適値からの脱出を試みている。
乱数が EPSILON 以上の場合は、現状態で最大のQ値を持つ行動を選択している。
次に選択された行動を実行し、エージェントの位置を更新する。
最後に、Q学習の式の通りに Q値テーブルを更新している。
■学習結果
下図に100ラウンドの学習を行った結果のスクショを示す。
Ｑ値が概ね最短経路を通るように学習できていることがわかる。
実際に動かしてみると、見ていてなかなか面白いので、ぜひビルドして実行してみてほしい。
TechProjin Godot入門 関連連載リンク
Godotで学ぶゲーム制作
さくさく理解するGodot入門 連載目次
標準C++ライブラリの活用でコーディング力UP!
「競技プログラミング風」標準C++ライブラリ 連載目次
