AI HW2 一條龍教學：未知地圖探索 Agent

2026-10-04｜人工智慧導論（成大朱威達）作業二，個人作業，10/15（四）23:59 截止

一句話結論
agent.py 已經寫好、測過，也經過獨立審查：老師的 3 張公開地圖全部成功、0 次撞牆，平均 94.48 分； 在 5,400 張模擬地圖上 0 失敗、0 撞牆。預估正式 9 張隱藏地圖的平均約 91 分（大概落在 88～94 之間：我模擬了兩萬次「抽 9 張考一次」，中間 90% 的結果落在 88.4～94.2；前提是隱藏地圖跟公開地圖一樣把終點放得遠。如果終點是隨便放的，預估約 88.8 分）。 你只剩「改 zip 檔名、上傳」兩個動作。

這份文件的五個部分

建議讀法（每天 90 分鐘以內）

這是估計的份量。Day 1 是測試日，做完看實際花多久再調整。B 部分是這次新加的，如果 Day 2 讀不完就拆成兩天。

檔案在哪裡

我做了什麼（完整工作紀錄）

結論：從找題目到交件檔，一共 24 個步驟。核心是「先做一個模擬考，再用模擬考比較好幾種走法，挑分數最高、而且絕對不會失敗的那個」。所有實驗的程式和數字都留在電腦裡，可以重跑。

為什麼要寫這一節

這份作業的程式是我寫的。你要交出去、也要能在考試時講出來，所以你需要知道「它是怎麼被做出來的」，而不是只看到最後的成品。

每一步我都寫了：做了什麼、為什麼要做、結果是什麼。

階段一：搞清楚題目（步驟 1～4）

階段二：做模擬考工具（步驟 5）

「終點隨便放」這個選項是保險：萬一老師的隱藏地圖不是把終點放遠，我們的策略也不能變差。

階段三：比較走法、調整參數（步驟 6～10）

階段四：寫正式版、驗證（步驟 11～14）

階段五：教學與審查（步驟 15～17）

哪些是我做的、哪些要你做

A1　作業在問什麼

結論：寫一個「蒙著眼睛走迷宮」的小機器人程式。它每一步只能摸到上下左右四格，要靠自己的記憶找到終點，而且路走得越少，分數越高。你只要寫 agent.py 這一個檔案。

A1.1　用故事講一次

想像你被蒙住眼睛，丟進一個格子迷宮。

你只知道兩件事：迷宮有多大（例如 10 列 × 10 欄），還有你站在哪一格。

你不知道牆在哪，也不知道終點在哪。

每次要走之前，你可以伸手摸一摸上、下、左、右四格。每一格只會是三種東西之一：

你決定往哪走、走一步。再摸一次、再決定、再走一步。一直重複，直到走進終點。

斜對角的格子摸不到，兩格以外的也摸不到。終點只有在你隔壁時，你才會知道它在那裡。

A1.2　地圖長什麼樣

這是老師給的第 1 張公開地圖（maps/public_map_01.json），10×10。起點標成 S、終點標成 G：

          col →  0 1 2 3 4 5 6 7 8 9
row ↓  0         . . . . . . . . . G
       1         . . # . # . . . . .
       2         . . . . . . . . . .
       3         . . . . # . . . # .
       4         # . . # . # . . . .
       5         . . . . . . . . # #
       6         # . . . . . . . . .
       7         S . . . . . . . . .
       8         . # . . . # . . # .
       9         . . . . . . # . . #

. 是路，# 是牆。機器人看不到這張圖。這張圖只有老師的評分程式看得到。

座標怎麼讀

每一格用 (row, col) 表示，也就是（第幾列, 第幾欄）。

• row（列）：從上往下數，最上面是 0。
• col（欄）：從左往右數，最左邊是 0。
• 所以左上角是 (0, 0)。這張圖的起點 S 是 (7, 0)：第 7 列、第 0 欄。終點 G 是 (0, 9)。

A1.3　機器人一開始知道什麼、不知道什麼

老師另外保證了幾件事，可以放心：

• 起點到終點一定有路，不會出現走不到的題目。
• 起點不是終點，終點也不會在起點的隔壁。所以第一步一定摸不到 GOAL，一定要探索。
• 地圖只有三種大小：10×10、15×15、20×20。
• 可以重複走同一格，可以回頭。走回頭路只是多用一步，不額外扣分、也不算撞牆。

A1.4　一步裡面發生什麼事

每一步都是同樣的三拍，一直重複：

第 1 拍收到的資料，在 Python 裡長這樣（這包資料叫 percept，感知）：

{
    "position": (7, 0),          # 你現在站在第 7 列、第 0 欄
    "neighbors": {
        "UP": "WALL",
        "DOWN": "FREE",
        "LEFT": "WALL",
        "RIGHT": "FREE",
    },
}

四個方向每次都會給，值只會是 "FREE"、"WALL"、"GOAL" 三種之一。

A1.5　實際看一次：前三步

下面是我們的最終版機器人，在第 1 張公開地圖上真正走的前三步（從程式實際執行的紀錄抄下來）：

對照上面的地圖看：

• 第 1 步摸到「左邊是 WALL」。可是地圖上 (7, 0) 左邊沒有 #，那是地圖外面。這就是「邊界也叫 WALL」的例子。
• 第 1 步摸到「上面是 WALL」，對照地圖，(6, 0) 確實是 #。
• 第 2 步摸到「下面是 WALL」，對照地圖，(8, 1) 確實是 #。
• 它沒有往下走，而是往右。為什麼？第 0 步時它算出：右邊那格後面分到 77 格霧、划算度 0.6341；下面那格後面只有 19 格霧、划算度 0.0298。右邊比較划算。（怎麼算的，C3、C4 會講。）
• 第 1、2 步走到選中的格子後，各重選一次，選到 (7, 2)、(7, 3)，所以一路往右。

A1.6　整張地圖走完的樣子

同一張地圖，機器人走過的格子標成 *：

. . . . . . . * * G
. . # . # . . * . .
. . . . . . . * . .
. . . . # . . * # .
# . . # . # . * . .
. . . . . . . * # #
# . . . . . . * * *
S * * * * * * * * *
. # . . . # . . # .
. . . . . . # . . #

它沿第 7 列往右走到 (7, 9)，往上一格到 (6, 9)。再上面 (5, 9) 是牆，所以往左兩格到 (6, 7)，沿第 7 欄一路往上到 (0, 7)，最後往右兩格走進 G (0, 9)。

多走的 4 步，就是「因為看不到地圖，必須付出的探索成本」。

A1.7　每一種動作的結果

A1.8　步數上限

每張地圖最多可以用「4 × 列數 × 欄數」步。撞牆也算在裡面。

步數用完還沒到終點，那張就 0 分。上限其實很寬：等於每一格可以走 4 次。加了「安全閥」（C3）之後，所有測試裡最多只用掉上限的約 30%，包含審查員專門造來刁難程式的地圖。不過這是實測結果，理論上沒辦法保證一定不會超過（原因見 C6）。

A1.9　老師給的檔案，各自在做什麼

把整個作業想成一場考試：

正式評分時，老師會換成 9 張你沒看過的隱藏地圖（README 只說三種尺寸各三張；「三種風格各一張」是我從公開地圖推測的）。公開的 3 張只是讓你練習，不算成績。

A1.10　評分程式怎麼使用你的程式

這是 public_grader.py 的核心流程，我改寫成白話：

agent = Agent()                          # 照你的設計圖，造出「一台」機器人

for 每一張地圖:
    env = GridEnvironment(這張地圖)       # 準備好迷宮和裁判
    agent.reset(列數, 欄數, 起點)          # 告訴機器人：新地圖開始了，忘掉上一張

    while 還沒走到終點 and 步數還沒用完:
        percept = env.observe()          # 第 1 拍：裁判告訴機器人四周是什麼
        action = agent.act(percept)      # 第 2 拍：機器人回答往哪走
        env.step(action)                 # 第 3 拍：裁判真的執行這一步

注意兩件事：

1. 機器人只造一次，三張地圖都是同一台在走。所以每張新地圖開始時，reset() 一定要把舊的記憶清乾淨。不然它會拿第 1 張地圖的牆和路，來規劃第 2 張地圖的路線：可能以為某處是路結果撞牆，或以為某些地方已經探索過而跳過。
2. 你的程式不用自己讀地圖、不用自己移動、不用自己算步數。那些都是裁判的事。你只負責「回答往哪走」。

A1.11　Python 小補充：為什麼記憶要放在 self 裡

先講它在做什麼：讓機器人能記住上一步發生過的事。

• class Agent 是機器人的設計圖。
• Agent() 是照設計圖做出一台機器人（做出來的這一台叫「物件」）。
• self 就是「這台機器人自己」。
• self.known 是「這台機器人口袋裡的筆記本」。

為什麼一定要放在 self 上？

因為 act() 每一步都會被重新呼叫一次。在 act() 裡面寫的普通變數（例如 known = {}），這一步結束就消失了，下一步什麼都不記得。

放在 self 上（self.known = {}）就不一樣：它掛在機器人身上，會一直留到下一步、下下一步。

README 也特別提醒：「請使用 instance variables（例如 self.internal_map、self.visited、self.path）保存資訊」。instance variable 就是「掛在 self 上的變數」。

A1.12　你要寫的三個方法

老師給的空白範本，act() 裡只寫了 return "UP"，也就是永遠往上走。我實際跑過：3 張地圖全部失敗，每一步都撞牆（10×10 那張 400 步撞了 400 次）。因為起點上面剛好是牆，它就一直撞同一面牆。你的工作就是把這一行換成聰明的決策。

A1.13　三種地圖風格

公開地圖的 JSON 檔裡有一個 style 欄位，標明風格。隱藏地圖推測也是這三種（README 說三種尺寸各三張，但沒說風格；這是我從公開地圖推測的）：

# # # # # # # # # # # # # # #
# . . . # . . . . . . . . . #
# . # . # # # . # # # . # . #
# . # . . . # . # S . . # . #
# . # # # # # . # . # # # # #
# . . . # . . . # . . . . . #
# # # . # # # # # # # # # . #
# . # . . . . . . . . . . . #
# . # # # # # # # # # # # . #
# . # . . . . . . . . . # . #
# G # . # # # # # # # . # . #
# . # . # . # . . . . . # . #
# . # . # . # . # # # # # . #
# . . . . . # . . . . . . . #
# # # # # # # # # # # # # # #

# # # # # # # # # # # # # # # # # # # #
# . . . . . . . . . . . # . . . . . . .
# . # . # . # . # # # . # # . # # . # #
# . . . . . . . # . . . . . . . # . S .
# . # # # # # . # . # # # . # . # . . .
# . # . . . . . # . . . . . # . . . . .
# . # . # . # . # . # # # . # . # . # .
# . # . . . . . . . # . . . . . # . . .
# . # . . . # . # . . . # # # # # . # .
# . . . # . # . . . # . . . . . . . # .
# # # . # . # . . . # . # # . . # . # .
# . G . # . # . . . # . # . . . # . . .
# # # . # . # . # . # # # . # . # . . .
# . . . # . . . # . . . . . # . . . # .
# . # . # # # . # # # . # . # # . . # .
# . # . . . . . # . # . . . # . . . . .
# . # # . # # # # . # . # . # . # . . #
# . # . . . . . . . # . . . # . # . . .
# . # # # . . . . # # . # . . . # . # .
# . . . # . # . . . . . # . . . . . # .

A1.14　其他規定（有些違反會 0 分）

A1.15　自己跑跑看

想親眼看結果，照這樣做：

1. 打開終端機（VS Code 下方的 Terminal 就可以）。
2. 切到作業資料夾：
   cd "C:\D槽\TAICA課程\人工智慧導論\HW2\HW2"
3. 跑模擬考：
   py -3.11 public_grader.py
4. 想看每一步怎麼走：
   py -3.11 public_grader.py --verbose

README 寫的指令是 python3 public_grader.py，那是 Linux 的寫法。在你的 Windows 上用 py -3.11，意思是「指定用 Python 3.11 來跑」，跟正式評分環境同版本。

你應該會看到：

Map                    | Result     | Steps      | Collisions
-----------------------+------------+------------+-------------
public_map_01          | SUCCESS    | 20         | 0
public_map_02          | SUCCESS    | 45         | 0
public_map_03          | SUCCESS    | 70         | 0

Successful maps : 3/3

注意：這個成績表不會印分數。分數是我用老師的公式另外算的（C2 節）。

所以對你的影響是：這份作業的重點不是「寫很多程式」，而是「想出一個聰明的走法」。程式本身大約 230 行（含註解），規則都在這一節了。接下來 A2 節講分數怎麼算，然後 B 部分講背後的邏輯框架。

A2　分數怎麼算

結論：每張地圖＝ 80 分基本分 ＋ 最多 20 分效率分 − 撞牆扣分。拿高分的三個關鍵：一定要走到、永遠不撞牆、少走冤枉路。

老師的公式

沒走到終點（步數用完）：  這張 0 分

走到終點：
    實際移動步數 = 總步數 − 撞牆次數
    效率 = min(1, 最短路線步數 / 實際移動步數)
    撞牆扣分 = min(10, 撞牆次數)
    這張分數 = 80 + 20 × 效率 − 撞牆扣分

作業成績 = 9 張隱藏地圖的平均

「最短路線步數」是老師用完整地圖算出來的。你的 Agent 看不到這個數字。

舉例

假設某張地圖最短要走 20 步：

三個關鍵，一個一個看

所以對你的影響是：只要程式正確、不失敗，每張至少 80 分（模擬考裡最低是 80.15）。分數高低差在「探索策略」：在老師的 3 張公開地圖上，最終版平均比 DFS 多 5.47 分，單張最多多 11.15 分（公開地圖 01：96 對 84.85）。我們的最終版預估約 91 分。

B1　Agent 是什麼

結論：Agent 就是「會看、會想、會動」的東西。課本把任何 AI 都看成一個 Agent：從環境收到感知，決定一個動作，再把動作做回環境裡。這份作業的機器人就是一個標準的 Agent。

B1.1　一個 Agent 有三個部分

想像一台掃地機器人：

• 它有感應器，可以知道地上髒不髒、前面有沒有牆。
• 它有一個大腦，根據感應到的東西決定要做什麼。
• 它有輪子和吸塵器，可以真的去做。

課本 Ch2 第 2 頁的定義就是這三件事：Agent 透過 sensors（感應器）感知環境，透過 actuators（執行器，例如輪子、手臂）對環境做動作。

B1.2　Agent function：從「看過的東西」對應到「動作」

課本 Ch2 第 3 頁說：Agent 的行為，可以用一個 agent function（Agent 函數）描述。它把「到目前為止收到的所有感知」（叫 percept sequence，感知序列）對應到一個動作。

重點在「到目前為止所有的」。好的 Agent 不是只看眼前這一刻，而是參考它看過的全部東西。

所以對你的作業的影響是：機器人應該把每一步摸到的東西都記下來（這就是 self.known 筆記本），用「全部記憶」來做決定，而不是只看眼前四格。

B1.3　理性的 Agent（rational agent）

課本 Ch2 第 5～7 頁：理性的 Agent，就是在它所知道的範圍內，選擇「預期會讓表現分數最高」的動作。

注意三件事：

1. 表現分數（performance measure）是外面的人定的。這份作業裡，就是老師的評分公式（A2）。
2. 理性不等於全知。機器人看不到整張地圖，所以它不可能每次都走最短路。理性的意思是：用手上有的資訊，做出最好的猜測。
3. 所以「多走了一些冤枉路」不代表它不理性。只要它在當時的資訊下選了最划算的路，就是理性的。

B1.4　PEAS：描述一個任務的四個面向

課本 Ch2 第 9 頁：設計 Agent 之前，先用 PEAS 把任務講清楚。PEAS 是四個英文字的開頭：

B2　這是什麼樣的環境

結論：課本用六、七組「二選一」來分類環境。這份作業的環境是：部分可觀察、單一 Agent、確定性、序列式（sequential）、靜態、離散；known／unknown 那一項有爭議，考試建議答 unknown（見下面的提醒）。其中「部分可觀察」最重要，因為它決定了機器人一定要有記憶。

B2.1　為什麼要分類環境

不同的環境，要用不同的 Agent。就像下象棋和開車，需要的能力完全不同。

先搞清楚環境是什麼樣子，才知道 Agent 該具備哪些能力。課本 Ch2 第 11～14 頁列了這些分類。

B2.2　逐項看

B2.3　「部分可觀察」帶來的後果

因為看不到全部，Agent 必須自己記住看過的東西，拼出一張「自己知道的地圖」。

這直接決定了下一節要講的：這份作業需要哪一種 Agent。

B3　四種 Agent，這份作業要哪一種

結論：課本由簡單到複雜介紹四種 Agent。只看眼前的「反射型」在迷宮裡會繞圈子；這份作業需要的是「有記憶（model-based）＋有目標（goal-based）＋會算划算度（utility-based）」的 Agent。我們的程式三樣都有。

B3.1　反射型 Agent（simple reflex agent）：只看眼前

課本 Ch2 第 18～19 頁：只根據現在這一刻的感知做決定，完全不管以前看過什麼。規則像「如果怎樣，就做什麼」（condition-action rule）。

例子：「右邊是路就往右；不然下面是路就往下⋯⋯」。

課本說它只在環境「完全可觀察」時才行得通。這份作業是部分可觀察，所以反射型會出問題：

• 它不記得哪裡走過，可能在兩格之間來回走，或繞著同一圈一直轉。
• 它不記得哪裡是死路，走出死路後可能又走回去。
• 最後步數用光，那張地圖 0 分。

B3.2　有記憶的 Agent（model-based reflex agent）

課本 Ch2 第 20～21 頁：為了處理「看不到全部」，Agent 要維護一個內部狀態（internal state），記住現在看不到的那部分世界。這個內部狀態根據「過去所有的感知」來更新。

在我們的程式裡，內部狀態就是 self.known：每一格摸過的結果都寫在裡面。

B3.3　有目標的 Agent（goal-based agent）

課本 Ch2 第 22～23 頁：光知道世界長怎樣還不夠，還要知道想去哪裡。有目標的 Agent 會考慮「如果我這樣做，會發生什麼事？會不會更接近目標？」

我們的目標是「走進 GOAL」。程式會規劃路線（用 BFS），而不是只看下一步。注意：因為終點在哪裡不知道，BFS 規劃的是走到「選中的邊境」的路線，不是走到終點的路線。

B3.4　效用導向的 Agent（utility-based agent）

課本 Ch2 第 24～25 頁：當有好幾個可以追求的目標，或者結果不確定時，光有目標不夠。Agent 要對每個選擇打一個分數（叫 utility，效用），選預期效用最高的。課本特別說：效用導向的 Agent 能處理「部分可觀察」帶來的不確定性。

這正是我們的情況：

• 地圖上同時有好幾個「可以去探索的地方」（後面會叫它邊境）。
• 不知道終點在哪一個方向。
• 所以我們幫每個邊境算一個「划算度」＝「估計的寶藏價值 ÷（要走的步數＋2）」，選最高的。這個划算度就是效用。
• 注意：「寶藏價值」是我們自己設計的估計分數（越遠的未知格分數越高），不是真正算出來的機率。

B3.5　整理

課本的四種 Agent 是一層一層往上加能力的，所以「是 utility-based」也同時代表它有記憶、有目標。

B4　把問題寫成「搜尋問題」

結論：課本 Ch3 說，任何「從起點走到目標」的問題，都可以用五個要素描述。把迷宮套進這五個要素，就可以用搜尋演算法（BFS、DFS、A*）來處理。

B4.1　五個要素

課本 Ch3 第 5 頁用「從 Arad 開車到 Bucharest」當例子。我們把迷宮套進去：

課本還說：解（solution）就是一串從初始狀態走到目標的動作；解的好壞用路徑成本衡量。成本最低的解叫最佳解（optimal solution）。

這份作業的「最短路線步數」（評分公式裡的 optimal_steps）就是最佳解的成本。

B4.2　狀態空間：把迷宮看成一張「圖」

把每一個可以站的格子想成一個點，相鄰、可以走過去的兩格之間連一條線。這樣迷宮就變成一張由點和線組成的圖。所有狀態加起來叫狀態空間（state space）。

課本 Ch3 第 9 頁說：搜尋演算法從初始狀態出發，一步一步展開可能的動作，形成一棵搜尋樹（search tree）。樹根是初始狀態，樹枝是動作，每個節點是一個狀態。

B4.3　評估搜尋演算法的四個標準

課本 Ch3 第 11 頁：

B5　三種基本搜尋：BFS、DFS、A*

結論：三種方法的差別只在「下一個先展開誰」。BFS 先展開近的，保證找到最短路；DFS 先往深處鑽，省記憶體但不保證最短；A* 用「估計離終點多遠」來挑，又快又能找到最短，但前提是知道終點在哪。

B5.1　共同的骨架：frontier（待展開清單）

三種方法都用同一個骨架：

1. 手上有一份「等著被展開的節點」的清單。課本叫它 frontier。一開始只有起點。
2. 從清單裡挑一個節點拿出來。
3. 是目標就結束；不是的話，把它的鄰居（還沒看過的）加進清單。
4. 重複。

課本 Ch3 第 12 頁說：所有搜尋策略的差別，就在於節點被展開的順序。

B5.2　BFS（廣度優先搜尋，Breadth-first search）

課本 Ch3 第 13～15 頁：先展開起點，再展開起點的所有鄰居，再展開鄰居的鄰居⋯⋯一層一層往外。

怎麼做到「一層一層」：清單用排隊的方式（先進先出，FIFO）。先加進去的先拿出來，所以近的一定先被處理。

小例子：3×3 的空地，從左上角 A 出發。

A B C
D E F
G H I

距離 1 的全部處理完，才輪到距離 2，再輪到距離 3。所以每一格第一次被加進排隊時的距離，就是最短距離。

所以對你的作業的影響是：我們的程式每一步都用 BFS，在「已經知道的地圖」上算出走到每一格的最短步數。

B5.3　DFS（深度優先搜尋，Depth-first search）

課本 Ch3 第 18～20 頁：永遠先展開最深的節點。一條路走到底，走不通才退回上一個岔路換一條。

怎麼做到「先往深處」：清單用疊盤子的方式（後進先出，LIFO）。最後加進去的先拿出來。

B5.4　A*（A-star）：有方向感的搜尋

BFS 和 DFS 都是「盲目」的：它們不知道目標大概在哪個方向（課本叫 uninformed search，無資訊搜尋）。

如果有一點線索，例如「目標大概在東北邊」，就可以優先往那邊找。這種線索叫 heuristic（啟發式函數），寫成 h(n)：估計從節點 n 到目標還要花多少（Ch3 第 27 頁）。

A* 每次挑這個值最小的節點展開（Ch3 第 31 頁）：

f(n) = g(n) + h(n)
g(n) = 從起點走到 n 已經花了多少
h(n) = 估計從 n 到目標還要多少
f(n) = 估計「經過 n 的整條路」總共多少

在格子地圖上，最常用的 h(n) 是曼哈頓距離：上下差幾格＋左右差幾格。

A* 什麼時候保證找到最短路（Ch3 第 32～33 頁）：

• admissible（可容許）：h(n) 從不高估真正的剩餘成本。這樣 tree search 版的 A* 保證最短。
• consistent（一致）：從 n 走一步到 n′，h(n) 不會大於「這一步的成本＋h(n′)」。graph search 版的 A*（會記住走過哪裡、不重複展開）需要這個更強的條件才保證最短。

曼哈頓距離在格子地圖上兩個條件都滿足。

B5.5　三種方法比較

B6　線上搜尋：看不到地圖時怎麼辦

結論：這份作業就是課本 Ch4 的「線上搜尋」（online search）：走一步、看一下、想一下、再走一步。評分公式就是投影片講的 competitive ratio（競爭比）。我們的做法是「記住地圖＋用 BFS 走到最值得探索的邊境」。

B6.1　離線 vs. 線上

課本 Ch4 第 29 頁（投影片角落編號 56）：

課本 Ch4 第 30～31 頁還說：線上搜尋的 Agent，不實際走到某個狀態、做某個動作，就不知道結果。這份作業也一樣：不走到那一格旁邊，就不知道那格是路還是牆。

B6.2　競爭比（competitive ratio）：怎麼評價線上 Agent

課本 Ch4 第 33 頁（角落編號 60）：

競爭比 = Agent 實際走的路徑成本 ÷ 如果事先知道地圖時的最短路徑成本

越小越好，最好是 1（等於直接走最短路）。

回頭看這份作業的評分公式（A2）：

效率 = 最短路線步數 ÷ 實際移動步數

在 0 次撞牆時，剛好是競爭比倒過來。競爭比 2（走了最短的兩倍）→ 效率 0.5 → 效率分 10 分。

兩個細節：

• 老師的「實際移動步數」不算撞牆；課本的「實際路徑成本」每個動作都算。所以只有 0 撞牆時兩者才完全一樣。我們的程式永遠 0 撞牆，所以剛好一樣。
• 公式裡的 min(1, …) 實際上不會起作用，因為成功時實際走的路一定不會比最短路還短。

所以老師評分裡的效率分那一項，就是課本評價線上搜尋 Agent 的方式。80 分基本分、失敗 0 分、撞牆扣分，則是老師另外加的規則。

B6.3　課本的提示：線上搜尋要「就近展開」

課本 Ch4 第 34 頁（角落編號 61）：

• 每走一步，Agent 收到新的感知，就把它補進自己的地圖。
• 線上 Agent 要「實際走過去」才能展開一個節點。如果像 BFS 那樣在不同分支間跳來跳去，每跳一次都要真的走很遠的路，非常浪費。
• 所以線上搜尋最好就近展開。DFS 剛好有這個性質：下一個要展開的通常就在旁邊。

這就是為什麼課本的經典線上搜尋 Agent 是 DFS 型的。

B6.4　我們比課本的 DFS 更進一步

DFS 型的線上 Agent 有一個缺點：走到死路時，它要一格一格原路退回到上一個岔路。

我們的做法是：

1. 記住整張已知地圖（不只記一條路）。
2. 找出所有「站上去就能看到新東西」的格子，叫邊境（C1 會詳細講）。
3. 用 BFS 在已知地圖上算最短路線，直接抄近路走到想去的邊境，不用原路退回。
4. 有好幾個邊境時，用「划算度」挑最值得去的（C3）。

這種做法在機器人領域叫做以邊境為基礎的探索（frontier-based exploration）。課本投影片沒有用這個名字，是機器人探索的常見做法。

BFS 在這裡的角色變了：它不是用來「展開搜尋樹找終點」，而是用來「在已經知道的地圖上算走路路線」。這兩件事不一樣，考試時要講清楚。

B6.5　從框架到實作：剩下唯一要決定的事

到這裡，框架都有了：

剩下唯一要動腦的問題：有好幾個邊境時，先去哪一個？

這個選擇決定了冤枉路的多寡，也就決定了效率分。C 部分就是在回答這個問題：先比較四種選法（C2），再講最終版怎麼選（C3）。

C1　三個基本工具

結論：所有走法都靠三個工具：記憶地圖（記住摸過什麼）、邊境（哪裡還有東西沒看過）、BFS（在已知的路上找最短路線）。

工具 1：記憶地圖

Agent 每摸一次，就把結果寫進一本筆記本。程式裡這本筆記本叫 self.known，是一個 Python 的 dict（字典：用「座標」查「狀態」）。

self.known[(4, 7)] = "FREE"   # 我站過的地方，一定是路
self.known[(5, 7)] = "WALL"   # 摸到下面是牆
self.known[(4, 6)] = "FREE"   # 摸到左邊是路

筆記本裡沒有寫到的格子 = 未知。未知的格子可能是路、牆、或終點。

README 特別提醒：「沒有看到牆壁，不代表已確認該格可通行」。所以我們只在已知是 FREE 的格子上規劃路線，不會賭未知的格子能走。

工具 2：邊境（frontier）

先講它在做什麼：找出「站上去才能看到新東西」的格子。

想一想：你要怎樣才能看到一個未知的格子？答案是：走到它旁邊，摸一下。

所以有用的目的地是：已知是路、而且旁邊還有未知格子的格子。這種格子就叫邊境（frontier），意思是「已知世界和未知世界的交界」。

精確地說，一格要同時符合 4 個條件才是邊境：

1. 已經知道它是一般的路（不是牆、不是霧，也不是終點）。
2. 不是機器人現在站的那一格。
3. 從機器人現在的位置，只走「已知的路」走得到。
4. 它的上下左右，至少有一格在地圖裡面、而且還是未知的。

下面是一個例子。@ 是你，. 是已知的路，# 是已知的牆，? 是未知，F 是邊境：

情境：你從左邊那格 . 出發，往右走到最右邊那格 .，再走回中間的 @。走過的三格，每一格都摸過它的上下左右。

? ? ? ? ?
? F F F ?
# . @ . #
? F # F ?
? ? ? ? ?

每個 F 都是「已知是路」，而且旁邊都還有 ?，站上去就能看到新格子。

走過的三格（兩個 . 和 @）四周都已經摸過了，旁邊沒有 ?，所以它們都不是邊境。

終點只有在「旁邊」時才摸得到，而且一摸到，程式就直接走進去（C3 的步驟 2）。所以還在找的時候，終點一定還沒被摸到過，一定藏在某個 ? 裡。所以探索＝不斷走到邊境，把 ? 變成已知，直到摸到 GOAL。

工具 3：BFS（廣度優先搜尋）

先講它在做什麼：從你現在的位置出發，算出走到每一格「最少要幾步」，以及「第一步該往哪走」。

做法像丟一顆石頭到水裡，漣漪一圈一圈往外擴：

1. 第 0 圈：你自己，距離 0。
2. 第 1 圈：你旁邊「已知是路」的格子（不含未知的格子），距離 1。
3. 第 2 圈：第 1 圈旁邊、還沒算過的格子，距離 2。
4. 一直擴下去，直到沒有新格子。

因為是一圈一圈擴，第一次碰到某格時的圈數，一定就是最短距離。這是 BFS 最重要的性質。Ch3 第 13～15 頁講 BFS 怎麼一層一層展開；「保證最短」是從這個展開順序推出來的，投影片文字沒有直接寫這句。

我們的 BFS 只在「已知是 FREE」的格子上擴散。它從機器人現在站的格子出發（不是地圖一開始的起點），順便記下「走到每一格，第一步要往哪個方向」。這樣選好目的地之後，馬上知道這一步要回傳什麼。

所以對你的影響是：這三個工具是每一種走法共用的骨架。不同的走法只差在「有好幾個邊境時，先去哪一個」。

C2　四種走法比一比

結論：我做了模擬考，比較四種走法。在公開地圖、以及「終點放遠處」的模擬地圖上，最終版最好，比最基本的 DFS 多 3.56 分（終點偏遠時）；如果終點是隨便放的，最終版跟走法 C 打平（88.78 對 88.79），只比 DFS 多 0.64 分。

四種走法

實際走一遍：四種走法在同一張地圖上的回放

結論：同一張地圖、同一個起點，四個機器人同時出發。按「播放」就能看到它們每一步怎麼走：誰一開始就走錯方向、誰一直走回頭路、誰直直走到終點。

這不是動畫示意，是四種走法的程式真的跑一遍記下來的每一步。

四種走法的差別，只有一件事：下一個要去哪一個黃色格子。下面每一種都講清楚四件事：看什麼、選哪個、平手怎麼辦、會不會中途改主意。

建議看法：先選「公開地圖 01」，按「只看 D. 最終版」，然後一直按「下一步」。每按一次，地圖下面的解說框就會告訴你：這一步用了什麼資訊、怎麼算、算出來的數字、所以往哪邊走。解說裡的 ①②③ 對應地圖上標了 1、2、3 的黃色格子。看完 D，再換「只看 A」「只看 B」「只看 C」比較。

所以對你的影響是：考試如果問「你的走法跟 DFS 差在哪」，可以用公開地圖 01 的第一步當例子：DFS 照固定順序往下走、離終點越來越遠；最終版會估計哪一邊的未知區域比較可能有終點，直接往那邊走。

為什麼要「偏好遠處」？——老師的地圖有規律

我分析了三張公開地圖：終點離起點的路程，比地圖上百分之幾的格子還遠？

三張都很遠。所以合理推測：老師出題時，故意把終點放在離起點遠的地方。這是推測，不是老師講的；所以我也測了「終點隨便放」的情況，確認最終版在那種情況下也不會變差。

公開地圖成績（老師給的 3 張）

四種走法撞牆次數都是 0。02 號地圖四種都剛好走最短路（45 步），因為那是一個死路型迷宮，運氣好第一次就選對岔路。

模擬考成績（每種情況 2,700 張隨機地圖）

這張表用的是同一批地圖（亂數種子 777，三種大小 × 三種風格，每組 300 張）。C3 安全閥那張表、工作紀錄裡的數字，用的是別批地圖（種子 2026），所以數字會差一點點，不是算錯。

3 張公開地圖太少，運氣成分很大。所以我寫了一個地圖產生器，模仿老師的三種地圖風格，每種尺寸、每種風格各產 300 張，用老師的公式算分。

怎麼讀這張表：

• 終點偏遠時（我們相信老師是這樣出題），最終版最好，比 DFS 多 3.5 分。
• 終點隨便放時，C 和 D 打平：88.79 對 88.78，只差 0.01 分。把同一批地圖逐張相減，差距的標準誤是 0.137，0.01 遠小於它，等於沒有差別。所以最終版「賭錯」也不會吃虧。
• 每一種都 0 失敗。

C3　最終版的想法

結論：把每個邊境想成一扇門，門後面有一片未知的「地盤」。地盤裡離起點越遠的格子越可能藏著終點。算出每扇門的「寶藏分 ÷ 走過去的步數」，挑最划算的門走過去，而且選定了就一直走向它，直到它不再是邊境才重新挑。

七個步驟

每一步都從步驟 1 開始。步驟 2 如果發現終點，就直接走進去，後面都不做。否則做 3、6、7；步驟 4、5 只在「需要重新挑目標」時才做。「需要重新挑」的意思是：還沒有目標（剛出發），或舊目標已經不是邊境了。程式實際執行的順序是 1 → 2 → 3 → 6 →（需要時才做 4 → 5）→ 7。

步驟 4：分地盤

先講它在做什麼：決定每一個未知格子「屬於哪一扇門」。

想像每個邊境同時派出一隊人，往未知區域擴散。可是每隊的出發時間不一樣：機器人走到那個邊境要 d 步，那隊就晚 d 步出發。

每個未知格子，被哪一隊先碰到，就歸那一隊。兩隊在同一圈碰到同一格時，歸 BFS 順序在前的那個邊境。隊伍只能穿過未知格子，不能穿過已知的路或牆。

這樣一來，每扇門後面就有一塊自己的地盤。這種做法叫「多起點 BFS」（multi-source BFS），同時從好幾個起點一起擴散。

步驟 5：寶藏分怎麼算

每個未知格子都有一個「藏著終點的可能性分數」：

注意：這裡的「起點」是這張地圖一開始的出發格（reset() 給的 start_position），不是機器人現在站的位置。

遠近 = 這格離起點的曼哈頓距離 ÷ (地圖列數 + 地圖欄數)
分數 = 遠近 ** 6          （遠近的 6 次方）

曼哈頓距離（Manhattan distance）就是「只能橫著走、直著走」時的格數：上下差幾格＋左右差幾格。像在棋盤街道的城市裡走路。

為什麼要 6 次方？因為次方會把「遠」和「近」的差距放大。在 10×10 地圖上：

所以一個很遠的格子，價值是中間格子的 30 倍以上。意思是：「近的地方幾乎不可能藏終點，遠的地方才值得去看」。

一扇門的寶藏分 = 它地盤裡所有未知格的分數加起來。

6 這個數字是我用模擬考試出來的。在 900 張「終點偏遠」的地圖上（有承諾、分母加 2），次方 2、4、6、8、10 的平均分分別是 90.52、91.01、91.31、91.21、91.15，6 最高。次方 0（等於不看遠近）只在還沒加承諾的版本試過，是 89.02。

步驟 5（續）：划算度

划算度 = 寶藏分 ÷ (走過去的步數 + 2)

舉例（這兩行是假設的數字，用來說明公式；真實數字見 C4）：

為什麼要「+2」？它的作用是縮小「近處邊境」的優勢。不加的話，步數 1 和步數 2 的邊境，划算度差 2 倍，Agent 會很容易被旁邊的小角落吸走；加 2 之後變成「3 比 4」，只差約 1.33 倍，遠方的大片未知區比較有機會勝出。（步數最少是 1，不會除以 0。）2 這個數字是模擬考試出來的：加 1 和加 2 幾乎一樣（終點偏遠 91.33 對 91.31、終點隨機 88.74 對 88.76），加 3 是 91.16，所以選 2。（加 6 只在還沒加承諾的版本試過，比較差。）

步驟 5 的安全閥：走太久就改成「先去最近的」

先講它在做什麼：程式自己數已經走了幾步。超過步數上限的 5% 之後，需要重選目標時，就不再「偏好遠處」，改成「先去離自己最近的邊境」。

精確地說：程式數的是「這張地圖 act() 被呼叫了幾次（包含這一次）」。這個數字大於 0.05 × 4 × 列數 × 欄數，安全閥才啟動。所以 10×10 地圖是從第 21 次呼叫開始。它只在需要重選目標的那一刻起作用，不會取消已經選好的目標。

在 3 張公開地圖和回放的 4 張地圖上，最終版都在安全閥啟動前就走到終點了（公開地圖：20／45／70 步，門檻 20／45／80 步）。

為什麼要加：獨立審查員專門造了一張刁鑽地圖，讓舊版程式走了 812 步（上限 900），只差 88 步就 0 分。原因是探索快結束時，只剩一些零散的小角落沒看過，舊版照「離起點多遠」決定先去哪個，結果在地圖兩端來回跑。

為什麼不會少分：「偏好遠處」真正有用的時候，是一開始決定往哪個大方向走。走了一陣子之後：

• 如果終點真的在遠處，前面那段「往遠處走」已經幫上忙了。
• 如果還沒找到，代表已經走了很多冤枉路，效率分本來就剩不多了。這時候最重要的是「不要步數用完」，所以改走保守的「最近優先」。

實際數字：同一批地圖上，沒有安全閥 91.10／88.86，安全閥 5% 是 91.18／88.96，沒有變差。

實驗結果（試過 5%、7.5%、10%、15%、20%、25%、30%、40%，用三批不同的地圖確認）：

平均分那一欄是同一批 2,700＋2,700 張地圖（跟調參數用的同一個亂數種子 2026，但每組 300 張，比調參數時的 100 張多）。另外兩批地圖（種子 777、4242）的結論相同：安全閥越早啟動越安全，平均分不會變差。

這個做法完全合規：程式只用到 reset() 給的地圖大小，加上自己數的步數，沒有偷看任何地圖資訊。

步驟 6：承諾——這一步是「不會失敗」的關鍵

一開始我沒有這一步。結果在 900＋900 張模擬地圖上，依參數不同，有 0～11 張失敗了（0 分）。

原因是「三心二意」：Agent 每走一步，地盤就重新分一次，划算度也跟著變。它可能這一步覺得 A 門好、往 A 走一步；下一步又覺得 B 門好、往回走一步⋯⋯就這樣在兩扇門之間來回踱步，把步數用光。

解法：一旦選定目標，就一直走向它，直到它不再是邊境（走到了，或它旁邊的未知格已經被摸到）才重新挑。加上之後，5,400 張壓力測試 0 失敗。平均分只差一點：以次方 4 那組為例，終點偏遠 91.08 → 91.01（少 0.07），終點隨機 88.76 → 88.80（多 0.04）。用一點點分數，換到「不會失敗」，很划算。

C4　用真實數字算一遍：BFS、寶藏分、四種走法怎麼選

結論：四種走法每一步都在做同一件事：從黃色格子（邊境）裡挑一個去。差別只在「打分數的公式」。這一節拿公開地圖 01 的兩個真實時刻，把每一個數字算給你看。這些數字是程式實際算出來的，不是我編的。

C4.1　第一個例子：第 0 步，剛出發

這就是回放裡「大家分道揚鑣」的那一刻。機器人站在起點（7, 0），只摸了一次四周：

@ 機器人　黑色＝已知的牆　黃色字母＝邊境　灰色＝霧（還不知道）

• 上面 (6, 0) 是牆；左邊是地圖外面（不在圖上）。
• 下面 (8, 0)、右邊 (7, 1) 是路，而且它們旁邊都還有霧，所以它們是邊境，叫 A、B。
• 其他 96 格全部是霧。

步驟一：BFS 算「走過去要幾步」

這一步很簡單：A、B 都在隔壁，都是 1 步。BFS 詳細怎麼跑，第二個例子（C4.2）再講，因為那時候格子比較多。

步驟二：分地盤——「分到 77 格霧」是什麼意思

定義：「① 分到 77 格霧」的意思是：現在地圖上的 96 格霧裡面，有 77 格是「從 ① 出發，比從 ② 出發更快摸得到」的。這 77 格就叫 ① 的「地盤」。

為什麼要這樣分？因為終點一定藏在某一格霧裡。如果終點在 ① 的地盤裡，從 ① 出發去找最快；在 ② 的地盤裡，從 ② 出發最快。所以「地盤有多大、地盤裡的霧有多遠」，就代表「走向這個黃色格子，有多大機會找到終點」。

怎麼分：兩隊人同時往霧裡擴散

規則（照程式 _share_unknown_cells 的做法）：

1. 每個黃色格子派一隊人。出發時間＝機器人走到那個黃色格子要幾步。① 和 ② 都是 1 步，所以同時出發。
2. 每一輪，每一隊從「自己已經佔領的格子」往上下左右擴一格，佔領還沒被佔、而且是霧的格子。
3. 只能走進霧，不能走進已知的牆或已知的路。
4. 同一輪兩隊搶同一格：先處理的那隊先搶到。先處理的是 BFS 先找到的黃色格子，也就是 ②（下面那格；因為 BFS 照上、下、左、右看，「下」比「右」先）。
5. 一直擴散，直到所有霧都被佔領。

實際過程（紅底的 ①＝被 ① 佔領的霧，藍底的 ②＝被 ② 佔領的霧，灰色＝還沒被佔的霧，黃底＝黃色格子本身，紅色 @＝機器人，黑色＝已知的牆）：

看第 1 輪：① 在右邊那格，往上佔了 (6, 1)、往右佔了 (7, 2)。② 在下面那格，往下佔了 (9, 0)、往右佔了 (8, 1)。
(8, 1) 其實 ① 往下也碰得到，兩隊同一輪搶同一格。但 ② 先處理，所以 (8, 1) 歸 ②。

為什麼最後 ② 只拿到最下面兩列：

• 第 8 列的每一格，① 和 ② 都在同一輪碰到，② 先處理，所以全部歸 ②。
• 第 9 列在第 8 列下面，從 ② 那邊過去比較近，也歸 ②。
• 第 7 列以上，從 ① 出發都比較近，全部歸 ①。

所以 ② 拿到第 8 列 9 格＋第 9 列 10 格＝19 格，① 拿到其餘 77 格。合計 96 格，就是全部的霧。

步驟三：算寶藏分——每一格霧值多少分

先講它在做什麼：猜「終點在這一格」的可能性有多高。我們觀察到老師的終點都放得離起點很遠，所以：離起點越遠的霧，分數越高。

每一格霧的分數這樣算：

遠近 = 這格離起點的格數（曼哈頓距離） ÷ (列數 + 欄數)
分數 = 遠近 ** 6           （遠近乘自己 6 次）

這張地圖 10 列 10 欄，所以除以 20。舉三格當例子：

右上角一格的分數，是中間那格的 30 倍以上。這就是「6 次方」的效果：把遠和近的差距放大。

一個邊境的寶藏分＝它地盤裡所有霧的分數加起來。下面這張表把霧按「離起點幾格」分組，一組一組加：

A 的地盤都在起點附近（離起點最多 11 格），每格分數都很小，加起來只有 0.0895。B 的地盤包含很多遠方的霧，加起來 1.9023，是 A 的 21 倍。

步驟四：算划算度，挑最高的

划算度 = 寶藏分 ÷ (走過去幾步 + 2)

A（下面）：0.0895 ÷ (1 + 2) = 0.0298
B（右邊）：1.9023 ÷ (1 + 2) = 0.6341   ← 最高，D 選它

同一個時刻，四種走法各選哪個

重點：C 也想「往遠處走」，但它只看邊境那一格本身離起點多遠。下面那格和右邊那格離起點都是 1 格，所以 C 分不出差別。D 看的是邊境後面整片霧，所以看得出右邊那一大片比較值得去。

C4.2　第二個例子：第 12 步，邊境變多了

最終版已經走了 12 步：沿著第 7 列往右走到底，再往上一格、往左兩格，現在站在 (6, 7)。地圖上有 14 個邊境。

BFS 是怎麼跑的

先講它在做什麼：從機器人現在的位置出發，算出走到每一格「已知的路」最少要幾步，順便記下「第一步要往哪走」。它只走已知是路的格子，不走霧、不走牆。

做法像排隊領號碼：

1. 機器人自己先排進隊伍，距離 0。
2. 從隊伍最前面叫一個人出來，看他上下左右四格。
3. 是已知的路、而且還沒算過的，就給它「出來的人的距離 + 1」，排到隊伍最後面。
4. 重複，直到隊伍空了。

因為「先排的先處理」，距離 1 的全部處理完，才會輪到距離 2 的。所以每一格第一次拿到的號碼，就是最短距離。

看四周的順序：上一步是往左走的，所以先看「左」，再看上、下、右。這樣兩條路一樣短的時候，會優先繼續直走。

實際的前 8 輪：

一直做到隊伍空了，全部的結果（數字＝走過去要幾步；字母旁的小數字＝那個邊境要幾步）：

四種走法各選哪個

重點：

• B 只看「近不近」，A 和 B 一樣近，它照順序挑了 A，往回走：離終點的真實步數從 8 步變成 9 步（機器人自己不知道這件事）。
• C 和 D 這次選一樣，但理由不同：C 是因為「B 這一格離起點比較遠」；D 是因為「B 後面那片霧最大、最遠」（它的地盤是 15 格，旁邊 A 只有 6 格）。
• 這時候已經走了 12 步，還沒超過 20 步（10×10 地圖步數上限 400 的 5%），所以安全閥還沒啟動，D 還在用划算度。

C4.3　四個公式放在一起

所以對你的影響是：考試問「你的 Agent 怎麼決定下一步」，可以直接用第 0 步這個例子：兩個邊境一樣近，但右邊那個後面有 77 格霧、寶藏分 1.90，下面那個只有 19 格、0.09，所以往右。

C5　逐段讀程式

結論：agent.py 分成「老師規定的三個方法」和「八個小幫手」。每個小幫手只做一件事：其中五個對應 C3 節的步驟，另外三個（_step、_inside、_safe_move）是基本工具和備案。

整份程式的地圖

reset()：每張新地圖都從零開始

def reset(self, rows, cols, start_position):
    self.rows = rows
    self.cols = cols
    self.start_position = tuple(start_position)
    self.known = {}            # 筆記本：座標 → "FREE" / "WALL" / "GOAL"
    self.target = None         # 目前要去的邊境
    self.last_action = None    # 上一步的方向（平手時繼續直走）
    self.steps_taken = 0       # 這張地圖已經走了幾步（安全閥用）

這裡每一個記憶都重新建立，所以換地圖時不會帶著舊記憶。

act()：外面包一層保險

def act(self, percept):
    self.steps_taken += 1      # 每被問一次，就是走一步
    try:
        return self._decide(percept)
    except Exception:
        return self._safe_move(percept)

try / except 的意思是：「試著做；萬一中途出錯，不要整個當掉，改做備案」。

為什麼要這樣？因為如果程式出錯，老師的評分程式會判那張地圖 0 分。有了備案，最慘也只是走一步不太聰明的路。正常情況下備案永遠用不到（壓力測試時我把保險拿掉跑，0 次出錯）。

_decide()：主流程

position = tuple(percept["position"])
neighbors = percept["neighbors"]

# 1. 記憶：自己站的格子一定是路；四個鄰居照摸到的寫
self.known[position] = "FREE"
for action, status in neighbors.items():
    self.known[self._step(position, action)] = status

# 2. 旁邊有終點就走進去
for action in MOVES:
    if neighbors[action] == "GOAL":
        return action

# 3. BFS，挑出所有邊境（不包含自己站的這格）
distance, first_move = self._bfs_from(position)
frontiers = [cell for cell in distance
             if cell != position and self._unknown_count(cell) > 0]
if not frontiers:                       # 找不到邊境（實際上不會發生，見 C6）
    return self._safe_move(percept)

# 6. 承諾：舊目標還是邊境，就不換
if self.target not in frontiers:
    self.target = self._choose_target(frontiers, distance)   # 4 + 5

# 7. 走最短路線的第一步
self.last_action = first_move[self.target]
return self.last_action

注意第 3 步：distance 只包含「已知是 FREE、而且走得到」的格子。所以挑出來的邊境一定走得到，走過去的路上也一定沒有牆。

_bfs_from()：一圈一圈擴散

distance = {position: 0}        # 走到每格要幾步
first_move = {position: None}   # 走到每格的第一步方向
queue = deque([position])       # 排隊等著往外擴的格子
while queue:
    cell = queue.popleft()      # 先進先出：先處理比較近的
    for action in order:
        n = self._step(cell, action)
        if n not in distance and self.known.get(n) == "FREE":
            distance[n] = distance[cell] + 1
            first_move[n] = first_move[cell] or action
            queue.append(n)

deque 是 Python 內建的「排隊隊伍」，從尾巴加入、從頭拿出（先進先出）。這就是 BFS 能「一圈一圈」的原因：近的先排、先處理。

first_move[cell] or action 的意思：cell 是現在正在往外擴的那一格。如果 cell 已經有「第一步」，新格子就沿用它；如果 cell 就是機器人自己（它的第一步是 None，還沒有），那這一步的方向 action 就是第一步。

order 會把「上一步的方向」排第一。這樣兩條路一樣短的時候，Agent 會繼續直走，不會左右扭來扭去。

_share_unknown_cells()：分地盤

buckets = {}
for f in frontiers:                     # 每個邊境在「自己的距離」那一層出發
    buckets.setdefault(distance[f], []).append((f, f))

owner = {}
level = min(buckets)
while buckets:
    for cell, frontier in buckets.pop(level, []):
        for action in MOVES:
            n = self._step(cell, action)
            if self._inside(n) and n not in self.known and n not in owner:
                owner[n] = frontier     # 這個未知格歸這個邊境
                buckets.setdefault(level + 1, []).append((n, frontier))
    level += 1

buckets 是「一層一層的籃子」：第 L 層的籃子裝「總距離＝ L」的（格子, 歸屬的邊境）。總距離＝機器人走到那個邊境的 d＋從邊境穿過霧走到那格的格數。每個邊境一開始放在第 d 層的籃子，所以遠的邊境等於「晚出發」。

只擴散到未知格（n not in self.known），因為我們要分的是未知的地盤。

_choose_target()：算划算度

if self.steps_taken > SAFE_FRACTION * 4 * self.rows * self.cols:
    return min(frontiers, key=lambda f: distance[f])        # 安全閥：最近的邊境

owner = self._share_unknown_cells(frontiers, distance)      # 分地盤

span = self.rows + self.cols                                # 列數 + 欄數
sr, sc = self.start_position                                # 地圖一開始的起點
value = {f: 0.0 for f in frontiers}                         # 每個邊境的寶藏分，從 0 開始
for cell, frontier in owner.items():
    far = (abs(cell[0] - sr) + abs(cell[1] - sc)) / span   # 曼哈頓距離 ÷ (列+欄)
    value[frontier] += far ** POWER                         # 加進那扇門的寶藏分

best, best_ratio = None, -1.0
for f in frontiers:                                         # 照 BFS 找到的順序
    ratio = value[f] / (distance[f] + COST_OFFSET)          # 划算度
    if ratio > best_ratio:                                  # 只有「嚴格比較大」才換人
        best, best_ratio = f, ratio
return best

因為只有「嚴格比較大」才換人，兩個邊境划算度一樣時，會留下比較早出現的那個，也就是 BFS 先找到的那個。

所以對你的影響是：考試如果問「你的 Agent 怎麼決定下一步」，你可以照 _decide() 的七個註解順序講一遍，每一步都對得上程式。

C6　為什麼不會撞牆、不會卡死

結論：「不撞牆」和「一定會結束、一定會找到終點」這兩件事，都有道理可以證明。但「一定在步數上限內找到」證明不了，那一點是靠大量實測支撐的。

C6.1　為什麼永遠不撞牆（可以證明）

1. 旁邊有 GOAL 時，我們走進 GOAL，不是牆。
2. 其他時候，我們走的是 BFS 路線的第一步。
3. BFS 只會走「已知是 FREE」的格子（self.known.get(n) == "FREE"）。
4. 「已知是 FREE」一定是真的：感知不會出錯，地圖也不會改變。
5. 所以第一步一定是走進一條真的路，不會是牆。

_safe_move()（備案）也只會選 FREE 或 GOAL 的方向。它會在兩種情況被叫到：

• _decide() 執行時出錯（被 try/except 接住）。
• 找不到任何邊境（if not frontiers）。下面 C6.2 會證明這種情況其實不會發生。

它只有在「四面都是牆」時才會回傳 "UP" 去撞牆。但這不會發生：起點一定有一個鄰居是路（因為起點到終點有路，而終點不在起點旁邊）；之後走到的每一格，至少「走來的那一格」是路。

C6.2　為什麼一定會找到終點（可以證明，但沒有步數保證）

分三段想。

第一段：還沒找到終點時，一定還有邊境可以去

• 起點到終點一定有一條路。沿著這條路從起點往終點走。
• 終點現在還是未知的（一摸到終點，程式就直接走進去了，所以還在找就代表還沒摸到），所以這條路上一定有「第一個未知格」。
• 它的前一格已經知道是路，而且從起點沿著已知的路走得到。機器人是從起點一路走過來的，所以「現在的位置」和起點也用已知的路連著。因此從現在的位置，也走得到這一格。
• 這一格旁邊有未知格，所以它是邊境。它也不會是我們自己站的格子，因為自己站的格子四周都已經摸過了。
• 所以只要還沒找到終點，就一定至少有一個邊境。這也表示程式裡 if not frontiers 那個分支實際上跑不到。

第二段：每換一次目標，至少有一個未知格變成已知

目標只會在兩種情況下被換掉：

1. 走到目標了。站上去之後會摸到它的四個鄰居，它旁邊的未知格就變成已知。
2. 還沒走到，目標就不再是邊境了。這代表它旁邊的未知格，在路上已經被我們從別的格子摸到了。

兩種情況都至少有一格從「未知」變成「已知」。

在換目標之前，我們一直沿著最短路線走向同一個目標。每走一步，離目標就近一步：新摸到的資訊只會「多發現路」，不會讓已知的路消失，所以距離只會變短、不會變長。因此每一段都在有限步內結束。

第三段：未知格是有限的

地圖最多 400 格，所以未知格最多 400 個。每換一次目標至少少一個，所以換目標的次數有限。

終點就藏在某個未知格裡。第一段說「還沒找到就一定有邊境可以去」，第二段說「每一趟都會減少未知格」，所以在未知格用完之前，一定會摸到終點。

所以對你的影響是：考試問「你的 Agent 為什麼不會撞牆」可以講證明；問「為什麼一定找得到終點」可以講三段論證；但要誠實補一句「步數上限內完成是實驗驗證的，不是證明的」。

D1　怎麼驗證的、還有什麼風險

結論：做了三種驗證，全部通過。最大的不確定是「隱藏地圖跟我模擬的不一樣」，所以 91 分是預估，不是保證。

三種驗證

預估分數

正式考試是 9 張（README 說三種尺寸各三張；我假設三種風格各一張）。我用「終點放遠處」的模擬地圖，模擬了兩萬次「抽 9 張考一次」：

單張地圖來看：一半的地圖在 90.9 分以上，有 11% 的地圖拿到滿分 100。

還有什麼風險

D2　獨立審查結果

結論：三個互相獨立的審查員都沒有找到會讓作業被判 0 分的問題。但它們找到了一個程式的安全風險（最慘情況用掉 90% 步數）和文件裡 7 個會影響考試答案的錯誤，全部已經修好並重新驗證。

D2.1　為什麼要找「別人」來審查

自己寫的東西自己檢查，很容易「看到自己想看的」。所以我派了三個全新的 AI 審查員：

• 它們看不到我的想法和對話，只拿到老師的規定、程式和文件。
• 每個只負責一個方向，而且被要求「假設有錯，去找出來」。
• 它們不准改任何檔案，只能回報。修改由我來做，修完再重新驗證。

D2.2　三個審查員各做了什麼

D2.3　程式的修改：加了「安全閥」

審查員 2 找到的問題：它造出一張 15×15 地圖，讓程式走了 812 步，上限 900 步，只差 88 步就會 0 分。

原因：「偏好遠處」太強。探索快結束時，地圖上只剩零星的小死角，程式照「離起點多遠」決定先去哪個，而不是照「離自己多近」，結果在地圖兩端來回跑。那張地圖上它換了 118 次目標，其中 19 趟長途移動就花了 684 步。

修法：程式自己數已經走了幾步。超過步數上限的 5% 之後，就改成「先去離自己最近的邊境」。詳見 C3 的「安全閥」。

修完的結果：

舊版程式備份在 C:\D槽\TAICA課程\人工智慧導論\HW2\agent_v1_before_safety.py，舊的 zip 在 zip_v1_before_safety.zip，想退回隨時可以。

同時也修了 agent.py 裡一行說明文字：原本說「+2 是為了避免除以很小的數」，審查員指出不對（步數最少是 1，不會除以 0）。改成正確的理由：縮小近處邊境的優勢。

D2.4　文件的修改：7 個會影響考試答案的錯誤

D2.5　其他修正（容易誤會、小問題）

• C6 證明重寫：補上三個缺口。最重要的是誠實寫出：只能證明「一定會找到終點」，不能證明「一定在步數上限內」，那一點靠實測。
• 評分和競爭比的關係：原本說「評分就是競爭比」，改成「效率分那一項，在 0 撞牆時剛好是競爭比的倒數」。
• A2 的計分例子：改成跟 README 一樣的「總共 43 步、撞牆 3 次（實際移動 40 步）」。
• A1.14 標題：從「違反就 0 分」改成「有些違反會 0 分」，並逐條寫出 README 的根據。
• 「三種風格各一張」：README 沒這樣說，改標成推測。
• 「划算度＝找到終點的機會」：寶藏分不是真的機率，改成「估計的寶藏價值」。
• A* 的描述：不是「BFS 加方向感」，而是「用 f = g + h 排優先順序的搜尋」。
• DFS 的完備性：補上「什麼情況下保證找得到」，考試常問。
• 預估分數的前提：補上「前提是終點放得遠；隨便放約 88.8」。
• 步數使用率、執行時間：原本寫的 44%、0.05 秒都太樂觀，改成實測值。
• 投影片引用：改正 Ch4 標題原文、理性 Agent 的頁數、utility 那句漏掉的字。
• 調參過程的紀錄：實驗程式被反覆改寫，舊的數字查不到了。補了一份紀錄檔 HW2\lab\EXPERIMENT_LOG.md。

D2.6　審查後還剩下的風險

D3　怎麼交件

結論：zip 已經打包好了，你只要把檔名改成自己的學號姓名，上傳到 NTU COOL。

步驟

1. 打開 C:\D槽\TAICA課程\人工智慧導論\HW2\。
2. 找到 學號_姓名.zip。
3. 改名成你的學號和姓名，例如 P76123456_王小明.zip。底線是半形的 _，不要留大括號。
4. 到 NTU COOL 的 Homework 2 上傳這個 zip。截止：10/15（四）23:59。

老師 README 的繳交前檢查（逐條對過）

D4　結論：一條龍總回顧

結論：這份作業從頭到尾是一條因果鏈：看不到地圖 → 要有記憶 → 要找邊境 → 要用 BFS 走過去 → 要決定先去哪個邊境 → 用划算度＋承諾來決定 → 驗證不會失敗、不會撞牆 → 預估約 91 分。

D4.1　一條龍：每一環為什麼接到下一環

D4.2　數字總表

D4.3　如果只能記五句話

1. 這份作業是 線上搜尋（online search）：看不到地圖，只能邊走邊看。評分裡的效率分，就是 competitive ratio 的倒數（0 撞牆時剛好相等）。
2. 環境是 部分可觀察的，所以 Agent 必須有 記憶（model-based），只看眼前的反射型會繞圈。
3. 每一步找出所有 邊境（已知是路、旁邊還有未知格），用 BFS 在已知地圖上走最短路線過去；只走已知的路，所以 永遠不撞牆。
4. 有好幾個邊境時，用 划算度＝估計的寶藏分 ÷（步數 + 2） 挑一個（utility-based）；因為終點通常離起點遠，遠處的未知格權重比較高。
5. 選定之後 承諾走向它（它不再是邊境才換），避免來回踱步；再加上格子數有限，所以 一定找得到終點。走超過步數上限的 5% 就改去 最近的邊境（安全閥），讓最慘情況也離步數上限很遠。

E1　跟課本的對照表

結論：這份作業就是 Ch4 投影片「Online Searching Agents with Unknown Environments」（線上搜尋）的實作，評分裡的效率分就是投影片講的 competitive ratio（競爭比）倒過來。另外也用到 Ch2 的環境分類、Agent 種類，和 Ch3 的 BFS。

這一節是 B 部分的濃縮對照表，考前快速複習用。每個觀念的詳細說明在 B1～B6。

Ch4：線上搜尋（最直接相關）

出處：Chapter 4 Search in Complex Environments.pdf PDF 第 29～35 頁（投影片角落編號 56～63）

Ch2：這是什麼樣的環境？

出處：Chapter 2 Intelligent Agents.pdf 第 11～14 頁

Known vs. unknown 那一列是我依投影片定義（"state of knowledge about the laws of physics of the environment"）判斷的，老師沒有針對這份作業講過。

Ch2：這是哪一種 Agent？

出處：Chapter 2 Intelligent Agents.pdf 第 20～25 頁

Ch3：搜尋演算法

出處：Chapter 3 Solving Problems by Searching.pdf BFS 第 13～15 頁、DFS 第 18～20 頁、A* 第 31～35 頁

• BFS：我們每一步都用它在已知地圖上找最短路線。
• frontier：Ch3 的 frontier 是「搜尋樹裡等著被展開的節點」。作業裡的 frontier 是「已知和未知的交界格」。名字一樣，概念相近（都是「下一個要去探索的地方」），但不是同一個東西，考試要分清楚。
• A*：需要知道終點在哪才能算 heuristic（估計離終點多遠）。這份作業終點未知，所以不適用。

E2　考試可能怎麼問

結論：下面是我根據投影片內容推測的題目（老師沒說會考這些）。題目用英文出（期末考是英文出題），可以用中文作答。答案收在摺疊裡，先自己想再打開。

Q1. What is the difference between offline search and online search?

Q2. Define the competitive ratio.

Q3. Describe the task environment of an agent exploring an unknown grid maze where it can only sense its four neighbors.

Q4. Why does an online search agent prefer DFS-like local expansion over BFS-like expansion?

Q5. Why is the agent in HW2 a model-based agent?

Q6. Can A* be used directly to find the goal in HW2? Why or why not?

Q7. 你的 Agent 怎麼保證不會撞牆？怎麼保證不會無限繞圈？

Q8. 你的探索策略是什麼？為什麼比 DFS 好？

E3　名詞小字典

結論：這份作業會遇到的詞，一行一個白話。

本報告的每一項判斷都來自實際查證（讀老師的 README 與程式、實際執行公開測試與模擬考、對照課程投影片原文）。標明「推測」的部分（終點放遠是老師的出題習慣、考試可能怎麼問、Known vs. unknown 的歸類）不是老師講的。