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):
やっていることは:
- 距離を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()
