0
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

小さな鬼ごっこから始める強化学習③ 〜逃げを自動化して学習を回す & 端スタック対策〜

0
Posted at

ezgif.com-video-to-gif-converter.gif

はじめに

強化学習で鬼ごっこAIを作ってみたいと思い、シリーズ形式で記録しています。

始めた理由はシンプルで、

  • 試験勉強中に大きなアプリ開発を始めると止まらなくなりそうだった
  • 勉強しながらでも「進捗が見える」ものを作りたかった
  • 小さいものが成長していくのを見るのが好き

前回は Q-learning の基本構造を実装しました。

しかし実際に動かしてみると、

  • 鬼が成長しているように見えない
  • 壁にぶつかり続ける
  • 負のQ値なのに同じ行動を続ける
  • さらに、画面端に突っ込み続けてスタックする

…など、疑問と「バグっぽい挙動」が一気に出てきました。

そこで今回は、

「そもそも学習が回る環境になっているのか?」

を見直し、
逃げを自動化して経験を大量に積めるようにする + 端スタックを潰す
という2つをやりました。


なぜ逃げを自動化するのか?

これまで逃げ(runner)は人間操作でした。

でもこれ、強化学習的には結構つらいです。

  • 人間の動きが毎回違う(再現性が低い)
  • 鬼にとって「同じ状態なのに結果がブレる」
  • エピソード数が稼げない(手で動かすと限界がある)

強化学習はざっくり言うと、

同じ状況で、似た結果が返るほど学習が進む

という性質が強いです。

なのでまずは、

安定した逃げAIを用意して、鬼が大量に経験を積める環境を作る

ことにしました。


実装した逃げAI(超シンプル版)

やったことはシンプルです。

  • 8方向+停止の候補を用意
  • 少し先の位置を仮計算
  • 鬼から最も離れられる方向を選ぶ
  • 壁の中に入りそうなら強いペナルティ

(※コード中の RUNNER_DIRS は 9方向候補です)

def choese_runner_dir(runner, chaser, runner_R, walls):
    best_dir = Vector2(0,0)
    best_score = -1e18
    look = 35.0

    for d in RUNNER_DIRS:
        if d.length_squared() > 0:
            d = d.normalize()

            p = runner + d * look

            wall_p = 0.0
            for w in walls:
                if w.collidepoint(p.x, p.y):
                    wall_p += 10000.0

            dist = (p - chaser).length()
            score = dist - wall_p

            if score > best_score:
                best_score = score
                best_dir = d

    return best_dir

これだけでも、

  • 人間よりブレが少ない
  • 変な操作ミスがない
  • 「鬼から距離を取る」を一貫してやる

という性質になるので、鬼の学習が安定して回りやすくなりました。


学習設計の見直しで気づいたこと

① 「負のQ値なのに同じ行動をする」は異常ではない

Q-learning は

Q値の絶対値ではなく「相対的に一番マシ」を選ぶ

ので、もし全行動がマイナスなら、

  • -0.5
  • -1.0
  • -3.0

の中から -0.5 を選び続けるのは普通に合理的です。

「負だからやめる」ではなく、
「他よりマシだから選ぶ」が起きます。


② 状態が粗いと学習できない(state aliasing)

今の状態は

  • 距離(近・中・遠)
  • 角度(左・正面・右)

だけです。

つまり同じ「近くて正面」でも、

  • 壁の前なのか
  • 開けた場所なのか
  • 端に近いのか

みたいな重要情報が区別できません。

この「違う状況が同じ状態に潰れてしまう」現象を state aliasing と呼びます。

強化学習は

状態に含まれていない情報は学べない

ので、ここは今後の改善ポイントになりました。


③ 壁にぶつかり続けるのは“バグ”ではなく報酬設計の結果

例えば、

  • 距離が縮む報酬が大きい
  • 壁ペナルティが小さい
  • 捕獲報酬がさらに大きい

という設計だと、

「壁に当たっても最終的に捕まえられればOK」

という方針で学習しても理論上は正しいです。

つまり、バグっぽい挙動の正体が「報酬設計」だったりします。


問題:画面端で鬼がスタックする

今回もうひとつ潰したかったのがこれです。

  • 学習が進むほど最大Qを引きやすくなる(ε-greedy)
  • 端に張り付いた状態で「外向き行動(右端で右)」を選ぶ
  • ずっと同じ行動になり、見た目としてスタックする

状態が「距離×角度」だけだと、

  • 普段は強い行動(例:右)
  • 端では最悪な行動(例:右)

が同じ状態に混ざって平均化されるので、端回避が学習しにくいのもあります。


対策①:画面端クランプを“半径対応”にする

円キャラなのに 0〜WIDTH でクランプすると、中心が端まで行けてしまい、めり込みやすくなります。

そこで中心座標を 半径ぶん内側に収めます。

runner.x = max(runner_R, min(runner.x, WIDTH - runner_R))
runner.y = max(runner_R, min(runner.y, HEIGHT - runner_R))
chaser.x = max(chaser_R, min(chaser.x, WIDTH - chaser_R))
chaser.y = max(chaser_R, min(chaser.y, HEIGHT - chaser_R))

同様に「端で速度を止める判定」も、0 / WIDTH ではなく R / (WIDTH-R) に合わせます。

if chaser.x <= chaser_R and chaser_vel.x < 0: chaser_vel.x = 0
if chaser.x >= WIDTH - chaser_R and chaser_vel.x > 0: chaser_vel.x = 0
if chaser.y <= chaser_R and chaser_vel.y < 0: chaser_vel.y = 0
if chaser.y >= HEIGHT - chaser_R and chaser_vel.y > 0: chaser_vel.y = 0

対策②:端付近で“外向き行動”を選んだら即ペナルティ

「端に張り付いた後、座標変化が起きないから罰が入りにくい」問題を潰すために、

端に近い状態で、さらに外へ行こうとしたら(行動として)罰

を入れました。

EDGE_EPS = 20.0
if chaser.x >= WIDTH - chaser_R - EDGE_EPS and move_dir.x > 0: reward -= 1.0
if chaser.x <= chaser_R + EDGE_EPS and move_dir.x < 0: reward -= 1.0
if chaser.y >= HEIGHT - chaser_R - EDGE_EPS and move_dir.y > 0: reward -= 1.0
if chaser.y <= chaser_R + EDGE_EPS and move_dir.y < 0: reward -= 1.0

これで「右端で右」みたいな行動が Q値的に弱くなりやすくなって、端スタックが減りました。


今回の本質的な学び

今回やったことは

  • 逃げを自動化して学習を回しやすくする
  • 端スタックを物理と報酬の両面で潰す

という改善でしたが、実際に得たのは

  • Q値は絶対値じゃなく「相対評価」
  • 状態に入ってない情報は学べない(state aliasing)
  • “バグっぽい挙動”が報酬設計から生まれる

という理解でした。


おわりに

今回は

  • 逃げを自動化して、学習が回る環境を作る
  • 端スタックを「半径対応クランプ」+「外向き行動ペナルティ」で潰す

をやりました。

実は上のGIFではうまく動いてそうに見えるが学習を進めていくと何故かプレイヤーを追いかけない状態に陥ってしまいます。

次回はそれを解決できたらいいなと思ってます


最終コード

クリックで展開
import pygame
import random
from pygame.math import Vector2
import math

pygame.init()

# 画面設定
WIDTH = 800
HEIGHT = 600
screen = pygame.display.set_mode((WIDTH,HEIGHT))
font = pygame.font.SysFont(None, 28)
clock = pygame.time.Clock()

# ゲーム変数
runner = Vector2(400,300)
runner_R = 10
runner_vel = Vector2(0,0)
runner_max_speed = 320.0
runner_response = 12.0

chaser = Vector2(150,150)
chaser_R = 12
chaser_vel = Vector2(0,0)
chaser_max_speed = 520.0
chaser_response = 10.0

# チェイサーの行動
chaser_actions = 0
ACTION_INTERVAL = 0.1
action_timer = 0.0
prev_dist = None

# タイマー関連
episode_time = 0.0
TIME_LIMIT = 10.0
timeouts = 0

# 捕まる距離
CATCH_DIST = runner_R + chaser_R
caught = 0

# Q学習関連
NUM_STATES = 9
NUM_ACTIONS = 5
Q = [ [0.0 for a in range(NUM_ACTIONS)] for s in range(NUM_STATES) ]
alpha = 0.15
gamma = 0.98
epsilon = 0.10
prev_state = None
prev_action = None

# 壁リスト
walls = [
    #pygame.Rect(200, 150, 300, 20),
    pygame.Rect(100, 350, 20, 180),
    #pygame.Rect(500, 320, 100, 20),
]

ACTIONS = [
    Vector2(0,0),
    Vector2(0,-1),
    Vector2(0,1),
    Vector2(-1,0),
    Vector2(1,0),
]

RUNNER_DIRS = [
    Vector2(0,0),
    Vector2(0,-1),
    Vector2(0,1),
    Vector2(-1,0),
    Vector2(1,0),
    Vector2(-1,-1),
    Vector2(1,-1),
    Vector2(-1,1),
    Vector2(1,1),
]

def resolve_circle_rect(pos, vel, r, rect):
    nx = max(rect.left, min(pos.x, rect.right))
    ny = max(rect.top, min(pos.y, rect.bottom))
    nearest = Vector2(nx, ny)
    delta = pos - nearest
    d2 = delta.length_squared()
    if d2 >= r * r:
        return pos, vel
    dist = delta.length()
    if dist == 0:
        n = Vector2(0,-1)
        dist = 1e-6
    else:
        n = delta / dist
    pos += n * (r - dist)
    vdot = vel.dot(n)
    if vdot < 0:
        vel -= n * vdot
    return pos, vel

def reset():
    global runner, chaser, runner_vel, chaser_vel, move_dir
    runner = Vector2(400,300)
    chaser = Vector2(150,150)
    runner_vel = Vector2(0,0)
    chaser_vel = Vector2(0, 0)
    move_dir = Vector2(0, 0)

def get_state(runner, chaser, move_dir):
    dist = (runner - chaser).length()
    if dist < 80:
        dist_bin = 0
    elif dist < 250:
        dist_bin = 1
    else:
        dist_bin = 2

    to_runner = runner - chaser
    if to_runner.length_squared() == 0:
        angle_bin = 1
    else:
        if move_dir.length_squared() > 0:
            forward = move_dir
        else:
            forward = to_runner.normalize()
        dir_to_runner = to_runner.normalize()
        cross_z = forward.x * dir_to_runner.y - forward.y * dir_to_runner.x
        dot = forward.dot(dir_to_runner)
        if dot > 0.707:
            angle_bin = 1
        else:
            angle_bin = 0 if cross_z > 0 else 2
    state_id = dist_bin * 3 + angle_bin
    return state_id, dist_bin, angle_bin, dist

def select_action(state_id):
    if random.random() < epsilon:
        return random.randint(0, NUM_ACTIONS - 1)
    qs = Q[state_id]
    m = max(qs)
    candidates = [i for i, v in enumerate(qs) if v == m]
    return random.choice(candidates)

def choese_runner_dir(runner, chaser, runner_R, walls):
    best_dir = Vector2(0,0)
    best_score = -1e18
    look = 35.0
    for d in RUNNER_DIRS:
        if d.length_squared() > 0:
            d = d.normalize()
            p = runner + d * look
            wall_p = 0.0
            for w in walls:
                if w.collidepoint(p.x, p.y):
                    wall_p += 10000.0
            dist = (p-chaser).length()
            score = dist - wall_p
            if score > best_score:
                best_score = score
                best_dir = d
    return best_dir

move_dir = Vector2(0,0)
AUTO_RUNNER = True
running = True

while running:
    dt = clock.tick(60) / 1000.0
    episode_time += dt
    time_left = TIME_LIMIT - episode_time
    reward = 0.0

    for event in pygame.event.get():
        if event.type == pygame.QUIT:
            running = False

    screen.fill((20,25,25))

    if AUTO_RUNNER:
        move = choese_runner_dir(runner, chaser, runner_R, walls)
    else:
        keys = pygame.key.get_pressed()
        move = Vector2(0,0)
        if keys[pygame.K_d]: move.x += 1
        if keys[pygame.K_a]: move.x -= 1
        if keys[pygame.K_s]: move.y += 1
        if keys[pygame.K_w]: move.y -= 1

    if move.length_squared() > 0:
        move = move.normalize()
        desired_vel = move * runner_max_speed
    else:
        desired_vel = Vector2(0,0)

    if runner_vel.length_squared() > runner_max_speed * runner_max_speed:
        runner_vel = runner_vel.normalize() * runner_max_speed
    runner_vel += (desired_vel - runner_vel) * (1.0 - pow(2.718281828, -runner_response * dt))
    runner += runner_vel * dt

    state_id, dist_bin, angle_bin, dist = get_state(runner, chaser, move_dir)

    action_timer += dt
    if action_timer >= ACTION_INTERVAL:
        action_timer = 0.0
        chaser_actions = select_action(state_id)
    move_dir = ACTIONS[chaser_actions]
    desired_chaser_vel = move_dir * chaser_max_speed
    chaser_vel += (desired_chaser_vel - chaser_vel) * (1.0 - pow(2.718281828, -chaser_response * dt))
    chaser += chaser_vel * dt

    EDGE_EPS = 20.0
    if chaser.x >= WIDTH - chaser_R - EDGE_EPS and move_dir.x > 0:
        reward -= 1.0
    if chaser.x <= chaser_R + EDGE_EPS and move_dir.x < 0:
        reward -= 1.0
    if chaser.y >= HEIGHT - chaser_R - EDGE_EPS and move_dir.y > 0:
        reward -= 1.0
    if chaser.y <= chaser_R + EDGE_EPS and move_dir.y < 0:
        reward -= 1.0

    if runner.x <= runner_R and runner_vel.x < 0:
        runner_vel.x = 0
    if runner.x >= WIDTH - runner_R and runner_vel.x > 0:
        runner_vel.x = 0
    if runner.y <= runner_R and runner_vel.y < 0:
        runner_vel.y = 0
    if runner.y >= HEIGHT - runner_R and runner_vel.y > 0:
        runner_vel.y = 0
    if chaser.x <= chaser_R and chaser_vel.x < 0:
        chaser_vel.x = 0
    if chaser.x >= WIDTH - chaser_R and chaser_vel.x > 0:
        chaser_vel.x = 0
    if chaser.y <= chaser_R and chaser_vel.y < 0:
        chaser_vel.y = 0
    if chaser.y >= HEIGHT - chaser_R and chaser_vel.y > 0:
        chaser_vel.y = 0

    before_clamp = chaser.copy()
    runner.x = max(runner_R, min(runner.x, WIDTH - runner_R))
    runner.y = max(runner_R, min(runner.y, HEIGHT - runner_R))
    chaser.x = max(chaser_R, min(chaser.x, WIDTH - chaser_R))
    chaser.y = max(chaser_R, min(chaser.y, HEIGHT - chaser_R))

    if (chaser - before_clamp).length_squared() > 1e-6:
        reward += -2.0

    before_chaser = chaser.copy()
    for w in walls:
        runner, runner_vel = resolve_circle_rect(runner, runner_vel, runner_R, w)
        chaser, chaser_vel = resolve_circle_rect(chaser, chaser_vel, chaser_R, w)

    if (chaser - before_chaser).length_squared() > 1e-6:
        reward += -0.5

    state_id, dist_bin, angle_bin, dist = get_state(runner, chaser, move_dir)
    reward -= 0.02

    if prev_dist is not None:
        reward += (prev_dist - dist) * 0.50
    prev_dist = dist

    done = False
    if episode_time >= TIME_LIMIT:
        timeouts += 1
        done = True
        reward += -20.0

    if (runner - chaser).length() < CATCH_DIST:
        caught += 1
        done = True
        reward += 100.0

    if prev_state is not None and prev_action is not None:
        best_next = 0.0 if done else max(Q[state_id])
        Q[prev_state][prev_action] += alpha * (reward + gamma * best_next - Q[prev_state][prev_action])

    prev_state = state_id
    prev_action = chaser_actions

    if done:
        prev_state = None
        prev_action = None
        prev_dist = None
        episode_time = 0.0
        reset()
        state_id, dist_bin, angle_bin, dist = get_state(runner, chaser, move_dir)

    pygame.draw.circle(screen, (80, 140, 255), (int(runner.x), int(runner.y)), runner_R)
    pygame.draw.circle(screen, (220, 60, 60), (int(chaser.x), int(chaser.y)), chaser_R)

    for w in walls:
        pygame.draw.rect(screen, (90, 90, 90), w)

    text = font.render(
        f"Time: {time_left:4.1f}s dist:{dist:5.1f} Qmax:{max(Q[state_id]):6.2f} Action:{chaser_actions} Qcur:{Q[state_id][chaser_actions]:4.2f} Cght: {caught}",
        True,
        (230, 230, 230)
    )
    screen.blit(text, (10, 10))
    pygame.display.flip()

pygame.quit()
0
1
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
0
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?