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?

小さな鬼ごっこから始める強化学習② 〜Q-learningを実装してみる〜

0
Posted at

2-gif.gif

q-tableをもとに動く鬼を作成。ε-greedyを使って学習

はじめに

主はQiitaもAIも初心者です。
読みづらくても許してください m(_ _)m

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

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

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

前回は 「学習を入れられる環境」 を作りました。

今回はついに
Q-learningの基礎構成を実装していきます。


まずは鬼を学習させる

鬼ごっこなので、

  • 鬼を学習させる
  • 逃げを学習させる

どちらも考えられます。

ですが今回は 鬼を学習させます。

理由はシンプル。

報酬設計が直感的だから

鬼の報酬はめちゃくちゃ分かりやすい:

  • 距離が縮んだ → +
  • 捕まえた → ++
  • 時間切れ → −
  • 壁にぶつかった → −

ほぼ迷いません。

一方で逃げは、

  • どれくらい距離を保てばいい?
  • 壁に近づくのはダメ?
  • 旋回し続けるのはOK?

と、急に難しくなります。

強化学習は「報酬設計」が超重要です。

最初はシンプルにいきます。


強化学習とは何か?

ざっくり言うと:

「この状態で、この行動をすると、将来どれくらい得か?」

を学習するものらしいです。


Q-learningとDQNの違い

強化学習には色々ありますが、有名なのは:

  • Q-learning
  • DQN

最初はQ-learningがおすすめらしいので、今回はそれでいきます。

Q-learning DQN
状態の扱い 離散(区切る) 連続のまま
記憶 Qテーブル ニューラルネット
学習の正体 表を埋める 関数を近似する
実装難易度 低い 高い
今の自分向き ◎ ○

今回は「仕組みを理解する」のが目的なので
ニューラルネットは使いません。


Q-learningとは?

Q-learningとは:

「状況ごとに、どの行動がどれくらい得かを数値で覚える学習」

です。


基本構成

要素 意味 鬼ごっこでの例
状態 s 今の状況 距離・角度
行動 a 取れる選択 上下左右停止
報酬 r 良さの点数 捕まえたら+50
Q(s,a) 期待値 この行動どれくらい得?

Q値とは?

「状態 s で 行動 a をしたら、将来も含めてどれくらい得できそうか」

という期待値です。

更新式はこれ:

Q(s,a) ← Q(s,a) + α ( r + γ maxQ(s',a') − Q(s,a) )
記号 意味
α 学習率
γ 将来の重み
r 今回の報酬
maxQ(s',a') 次状態で一番良さそうな行動

正直、最初は「そういうもの」として使いました。

でも後でちゃんと理解したい。


連続状態を離散化する

今のゲームは位置が連続値です。

でもそれをそのままQ-tableにすると
状態数が爆発します。

なので今回は区切ります。

状態の設計

距離:

  • 近
  • 中
  • 遠

角度:

  • 左
  • 正面
  • 右

つまり

3 × 3 = 9状態

これなら扱えます。


状態取得関数の解説

def get_state(runner, chaser, move_dir):

やっていることは:

  1. 距離を3段階に分ける
  2. 角度を3段階に分ける
  3. 0〜8のstate_idに変換

距離bin

dist = (runner - chaser).length()

距離を計算して、

if dist < 80:
    dist_bin = 0
elif dist < 200:
    dist_bin = 1
else:
    dist_bin = 2

ゲーム感覚で調整してOKです。


角度binの考え方

ここが少し重要。

鬼の「向き」に対して、逃げが

  • 左にいるか
  • 正面か
  • 右か

を判定しています。

内積(dot)

dot = forward.dot(dir_to_runner)

→ どれくらい正面か

外積(cross)

cross_z = forward.x * dir_to_runner.y - forward.y * dir_to_runner.x

→ 左右の判定

こうして3分類しています。

最後に:

state_id = dist_bin * 3 + angle_bin

で0〜8に変換。


ε-greedyとは?

Q-learningでは、

  • ずっと最大Q値を選ぶだけ
    ではダメです。

なぜなら最初は全部0だから。

そこで使うのが:

ε-greedy法

if random.random() < epsilon:
    return ランダム行動
else:
    return 最大Q値の行動

つまり:

  • εの確率で探索
  • それ以外は活用

今回は:

epsilon = 0.20

20%はランダム。


Qテーブルの初期化

NUM_STATES = 9
NUM_ACTIONS = 5

Q = [[0.0 for _ in range(NUM_ACTIONS)] for _ in range(NUM_STATES)]

9×5の表です。


Qの更新部分

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]
    )

ここが強化学習の心臓。

やっていることは:

予想と現実のズレを少しずつ修正している


報酬設計

今回の報酬:

  • 距離が縮む → +0.02 × 差分
  • 捕まえる → +50
  • タイムアウト → -20
  • 壁衝突 → -0.5

今の問題点

  • 壁にぶつかり続ける
  • 画面端に張り付く
  • あまり成長しているように見えない

Qmaxが急に大きくなったりする。

「これ正常…?」ってなる。


感想

なぜ壁にぶつかり続けるのだろうか?

という感想です。

最終コード

クリックで展開
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 = 460.0
runner_response = 12.0

chaser = Vector2(150,150)
chaser_R = 12

chaser_vel = Vector2(0,0)
chaser_max_speed = 420.0
chaser_response = 10.0

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

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

# 壁リスト
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), # 右
]

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.20  # 探索率

prev_state = None
prev_action = None

# チェイサーの行動
chaser_actions = 0

ACTION_INTERVAL = 0.5 # 秒
action_timer = 0.0

prev_dist = None

running = True

# 壁ブロックとの衝突判定関数
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():
    runner = Vector2(400,300)
    chaser = Vector2(150,150)
    runner_vel = Vector2(0,0)
    chaser_vel = Vector2(0, 0)
    return runner, chaser, runner_vel, chaser_vel

# 状態取得関数
def get_state(runner, chaser, move_dir):
    """
    状態 = (距離bin, 角度bin) を 0〜8 の state_id に変換して返す
    dist_bin: 0=近, 1=中, 2=遠
    angle_bin: 0=左, 1=正面, 2=右
    """

    #距離計算
    dist = (runner - chaser).length()

    if dist < 80:
        dist_bin = 0
    elif dist < 200:
        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: #cos45度 
            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):
    # ε-greedy法で行動を選択
    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)  # 最大Q値の行動

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

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))

    # プレイヤー操作
    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

    # 画面端で止まる処理
    if runner.x <= 0 and runner_vel.x < 0: runner_vel.x = 0
    if runner.x >= WIDTH and runner_vel.x > 0: runner_vel.x = 0
    if runner.y <= 0 and runner_vel.y < 0: runner_vel.y = 0
    if runner.y >= HEIGHT and runner_vel.y > 0: runner_vel.y = 0
    if chaser.x <= 0 and chaser_vel.x < 0: chaser_vel.x = 0
    if chaser.x >= WIDTH and chaser_vel.x > 0: chaser_vel.x = 0
    if chaser.y <= 0 and chaser_vel.y < 0: chaser_vel.y = 0
    if chaser.y >= HEIGHT and chaser_vel.y > 0: chaser_vel.y = 0

    before_clamp = chaser.copy()

    runner.x=max(0,min(runner.x,WIDTH))
    runner.y=max(0,min(runner.y,HEIGHT))
    chaser.x=max(0,min(chaser.x,WIDTH))
    chaser.y=max(0,min(chaser.y,HEIGHT))

    if (chaser - before_clamp).length_squared() > 1e-6:
        reward += -0.5  # 境界にぶつかって移動できなかったら小さなペナルティ

    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)

    if prev_dist is not None:
        reward += (prev_dist - dist) * 0.02 #距離が縮まったら正の報酬、離れたら負の報酬
    
    prev_dist = dist

    done = False
    # タイムアップ、捕まった判定
    if episode_time >= TIME_LIMIT:
        timeouts += 1
        episode_time = 0.0
        reward += -20.0
        prev_dist = None
        done = True

    if(runner - chaser).length() < CATCH_DIST:
        caught += 1
        episode_time = 0.0
        reward += 50.0
        prev_dist = None
        done = True

    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
        runner, chaser, runner_vel, chaser_vel = reset()
        move_dir = Vector2(0, 0)
        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"Caught: {caught} Timeouts: {timeouts} TimeLeft: {time_left:4.1f}s "
        f"Action:{chaser_actions} S:{state_id} Dbin:{dist_bin} Abin:{angle_bin} dist:{dist:5.1f} "
        f"R:{reward:6.2f} eps:{epsilon:.2f} Qmax:{max(Q[state_id]):6.2f}",
        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?