Developer

さくさく理解する Godot 入門(ただし2Dに限る)応用編 Q学習【第2回】
2022.06.01
Lv1

さくさく理解する Godot 入門(ただし2Dに限る)応用編 Q学習【第2回】

目次

  • 初期化処理
  • フレームごとの処理
  • 学習結果

■初期化処理

まずは、初期化処理コードを下記に示す。

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) がコールされるので、フレームごとの処理はここに記述する。 エージェントの1ステップの移動とQ値テーブルの更新は、この _process(delta) で行っている。

最初に [0, 1] 範囲の乱数を発生させ EPSILON の確率でランダムウォークを行う。
これは「ε-greedy」と呼ばれる処理で、Q学習が局所最適値に陥ることを防ぐためのものだ。
このような迷路の場合、ゴールまでの経路をひとつ見つけると、それがいかに遠回りの経路であっても、 次回以降はその経路ばかりを選択してしまい、それ以上学習が進まなくなってしまうからだ。
その対処として、少ない確率でランダムに行動を選び、局所最適値からの脱出を試みている。

乱数が EPSILON 以上の場合は、現状態で最大のQ値を持つ行動を選択している。

次に選択された行動を実行し、エージェントの位置を更新する。

最後に、Q学習の式の通りに Q値テーブルを更新している。

■学習結果

下図に100ラウンドの学習を行った結果のスクショを示す。

Q値が概ね最短経路を通るように学習できていることがわかる。
実際に動かしてみると、見ていてなかなか面白いので、ぜひビルドして実行してみてほしい。