目次
- 初期化処理
- フレームごとの処理
- 学習結果
■初期化処理
まずは、初期化処理コードを下記に示す。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 | const CELL_WIDTH = 64 # セル幅const MAZE_WIDTH = 12 # 横方向セル数const MAZE_HEIGHT = 10 # 縦方向セル数const MAZE_SIZE = MAZE_WIDTH * MAZE_HEIGHT # 全体セル数const REWARD_GOAL = 1.0const REWARD_TRAP = -1.0var 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値の方向に移動するので、 毎回移動可能かどうかを調べなくても、その方向に移動することはなくなる。
ゴール位置の場合は、ゴール位置を保存しておき、後でゴール位置を高速に参照可能にしている。
迷路はエディタで自由に変更可能なので、初期化時にタイルマップを参照し、処理を行っているというわけだ。
■フレームごとの処理
下記にフレームごとの処理コードを示す。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 | const ALPHA = 0.2const GAMMA = 0.99const 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++ライブラリ 連載目次
