影片狀態：已附影片。 影片來源與說明
Lecture 5–8把兩類問題排在一起：CSP 用變數、domain 與 constraints 壓縮組合搜尋；game trees 則加入會回應你的其他 agent。Project 2讓 Pacman 面對 ghosts，依序實作 reflex agent、minimax、alpha-beta pruning、expectimax 與 evaluation function。
CSP：先縮小選擇，再進入對局
官方 CSP 教材把問題寫成 variables、每個 variable 的 domain，以及限制可同時成立 assignment 的 constraints。最基本的 backtracking 每次替一個 variable 選值；ordering heuristics 決定先選哪個 variable、先試哪個 value，propagation 則在每次 assignment 後刪除已不可能的候選值。它們不改答案集合，而是避免走進早已能判定失敗的分支。
可執行的練習是先打開官方 Discussion 2 的 CSP worksheet：選一題，畫出前三層 backtracking tree；接著分別套用 minimum remaining values 與 forward checking，圈出因此不必展開的節點。對完官方 solution 後，再進 Project 2。這能把「搜尋順序」與「推論刪值」分開，而不是只記縮寫。
三個演算法其實是三種世界觀
Minimax 假設對手會選讓你最差的動作；alpha-beta 不改答案，只剪掉不可能影響決策的分支；expectimax 則以機率模型取代「永遠最壞」的對手。官方 P2 規格甚至提醒，正確的 agent 在部分測試仍會輸——輸贏不是演算法正確性的單一證據。
實作時先定義一個完整 ply：P2 把 Pacman 一步加上所有 ghosts 的回應算成一層。若 depth 的意義弄錯，遞迴結構看似合理，展開數卻會完全不對。
Evaluation function 是模型的一部分
搜尋深度有限時，leaf state 的評分就是 agent 看得到的世界。把距離、食物、ghost 危險與剩餘目標塞成一個分數並不難；難的是讓每一項都有一致尺度，並用固定亂數種子與多局測試分辨進步和運氣。
建議先在紙上畫一棵含兩個 ghosts 的小樹，標出 agent index 與 depth 何時更新，再寫 recursion。完成 minimax 後才加 pruning，最後只替換 ghost node 的聚合規則做 expectimax。這樣每一步都能對回一個清楚假設。
系列導航：上一篇：搜尋與 heuristic｜下一篇：MDP 與強化學習
課程影片來源
官方 Spring 2026 課表與官方 YouTube 播放清單（[CS188 SP26] Live Lectures，28 支）已於 2026-10-10 即時核對，本文嵌入的講課錄影在清單中（課表標為 Recording）。此處不提供未核對的時間跳轉。
原始影片：CS188 Spring 2026 Lecture 5: CSPs I
課程與錄影入口：
查核日期：2026-10-10。
內容核對：已依字幕核對（2026-10-10）：抽樣核對（只讀字幕開頭約五千字元）：確認嵌入的是 Lecture 5，主題為CSPs I（約束滿足問題）；字幕先回顧 search 的假設（單一 agent、確定性、完全可觀察、離散），再引入 CSP 單元，並預告 Project 4 要找看不見的 ghosts。本文其餘章節講的是同單元其他講次與 Project，不是這支影片的內容。
更新紀錄
- 2026-10-10：標註影片狀態，核對錄影來源與取得方式。
- 2026-10-10：重查影片狀態。官方 Spring 2026 課表與 YouTube 播放清單即時核對，嵌入的講課錄影在清單中，狀態改為已附影片。
- 2026-10-10：依字幕核對影片內容。確認嵌入影片是 Lecture 5（CSPs I（約束滿足問題）），主題與本文範圍相符；未發現需更正的影片說法。
參考資料
Loading...