AI時代系列(3) 機器學習三部曲: 📘 第三部：《強化學習 —— AI 的決策與進化》
38/100 第四週：📌 時序差分學習 TD
38. 控制遊戲實作：GridWorld 迷宮走法 🧭 訓練會走的 AI！
________________________________________
🎯 單元導讀
強化學習的理論再多，都比不上一次實作來得深刻！
本單元將透過經典的 GridWorld（格子世界），讓你實作出一個會走迷宮的 AI，並搭配 SARSA 或 Q-Learning 學會從嘗試錯誤中學習最短路徑！
________________________________________
🧱 一、什麼是 GridWorld？
GridWorld 是一個離散的 2D 空間：
• 每個格子代表一個「狀態」
• Agent 可選擇「上下左右」四種行動
• 有些格子為牆或陷阱，有些是終點，抵達即獲獎勵
🌐 範例地圖（5x5）：
S . . . G
. # . # .
. . . # .
# # . . .
. . . # T
• S: 起點
• G: 終點（+10 reward）
• T: 陷阱（-10 reward）
• #: 牆（不可通過）
• .: 一般格子（0 reward）
這是一個典型的迷宮環境，其中 S 為起點，G 為終點，抵達 G 可獲得 +10 reward；T 代表陷阱，踩到會損失 -10 reward；# 為障礙牆，無法通過；其餘的 . 為一般可通行格子，不給予任何獎勵或懲罰（reward 為 0）。智慧體需在這個迷宮中透過強化學習學習出最佳路徑，避開陷阱與障礙，最終順利抵達終點 G。這類任務非常適合用來觀察不同強化學習演算法（如 TD(0)、TD(λ)、SARSA、Q-learning）的探索能力、學習速度與路徑選擇差異。
________________________________________
🧠 二、遊戲規則與學習目標
在這個迷宮強化學習任務中，狀態空間 S 定義為所有可通行格子的座標位置 (x, y)；動作空間 A 包含上、下、左、右四個移動方向。獎勵設計為：抵達終點 G 獲得 +10、踩到陷阱 T 扣除 -10，其餘普通格子獎勵為 0。折扣因子 γ 常設為 0.9，用以平衡短期與長期報酬。每個 episode 的結束條件為：成功抵達 G、掉入 T、或移動步數超過上限後自動終止。透過這樣的設計，智慧體可以學習如何在有限次的探索中，逐漸找到避開陷阱、順利抵達終點的最佳路徑。
________________________________________
🧪 三、強化學習演算法選擇
你可以自由選擇以下任一演算法實作控制：
✅ SARSA（On-policy）：
python
Q[s][a] += α * (r + γ * Q[s_next][a_next] - Q[s][a])
✅ Q-Learning（Off-policy）：
python
Q[s][a] += α * (r + γ * max(Q[s_next]) - Q[s][a])
搭配 ε-Greedy 策略進行探索與學習！
________________________________________
💻 四、簡易 Python 實作（Q-Learning 版）
python
import numpy as np
import random
grid_size = 5
actions = ['U', 'D', 'L', 'R']
Q = np.zeros((grid_size, grid_size, len(actions)))
epsilon, alpha, gamma = 0.1, 0.5, 0.9
def is_valid(x, y):
# 邊界與牆的判斷略過，請補上你的地圖邏輯
return 0 <= x < grid_size and 0 <= y < grid_size
def step(state, action):
x, y = state
move = {'U': (-1, 0), 'D': (1, 0), 'L': (0, -1), 'R': (0, 1)}
dx, dy = move[action]
nx, ny = x + dx, y + dy
if not is_valid(nx, ny): return state, -1, False
if (nx, ny) == (0, 4): return (nx, ny), 10, True # G
if (nx, ny) == (4, 4): return (nx, ny), -10, True # T
return (nx, ny), 0, False
def choose_action(state):
if random.uniform(0, 1) < epsilon:
return random.choice(actions)
return actions[np.argmax(Q[state[0]][state[1]])]
for episode in range(500):
state = (0, 0)
done = False
while not done:
a = choose_action(state)
next_state, reward, done = step(state, a)
Q[state[0]][state[1]][actions.index(a)] += alpha * (
reward + gamma * np.max(Q[next_state[0]][next_state[1]]) - Q[state[0]][state[1]][actions.index(a)]
)
state = next_state
這段程式碼實作了一個簡單的 Q-Learning 強化學習迷宮任務。智慧體在一個 5x5 的網格地圖上進行訓練，每次從起點 (0,0) 出發，透過四個方向的行動（上、下、左、右）在地圖中移動。當智慧體走到終點 G (0,4) 可獲得 +10 獎勵，若走到陷阱 T (4,4) 則受到 -10 懲罰，其他格子則獎勵為 0。程式使用 ε-greedy 策略控制探索與利用，當前 Q 值以 Q-learning 更新公式修正，將經驗累積在三維的 Q 表格中。訓練重複 500 回合後，智慧體能逐漸學會如何避開陷阱並成功到達終點。此範例展示了強化學習中狀態-行動值函數學習的核心流程。
______________________________________
📌 五、進階任務挑戰
1️⃣ 改為 SARSA 學習，觀察是否更穩定？
2️⃣ 增加多個陷阱與障礙，測試學習策略
3️⃣ 將獎勵改為「步數越少越好」，設計步數懲罰機制
4️⃣ 改為 TD(λ) 更新，加入 Eligibility Traces 提高效率
________________________________________
✅ 六、小結與啟示
• GridWorld 是強化學習中最經典的測試環境之一，訓練 AI 學會「試錯 → 學習 → 最佳決策」
• 結合 Q-Learning 或 SARSA，可讓 AI 在沒有模型的情況下找到通往目標的最短路徑
• 可視為未來訓練機器人、自駕車與遊戲 AI 的縮影
