自主測試是探索複雜系統龐大狀態空間的強大方法之一。與其手動編寫每個場景的測試案例，自主系統能系統性地探索數百萬種狀態，發現人類測試者難以察覺的邊緣案例。
在這個兩部分的後續系列中，我們將繼續超級瑪利歐兄弟的測試，實作 Antithesis 提出的自主測試方法，他們能自主遊玩並通關遊戲。稍後在第二部分，我們將結合第一系列中開發的行為模型，於自主探索過程中即時驗證正確性。過程中，我們展示自主測試與行為模型的真正威力：系統性探索龐大狀態空間，只需撰寫一次驗證邏輯，即可套用於任何測試驅動器，包括我們自主系統，該系統在每一步驗證行為的同時發現新路徑。
我們的目標是實作自主狀態空間探索，讓瑪利歐在無需人為指導下完成超級瑪利歐兄弟的關卡。
完整實作已開源於我們的 Examples/SuperMario 倉庫。複製程式碼，讓我們深入了解自主狀態空間探索的運作原理！
Antithesis 的文章提出一個意外簡單卻強大的自主探索超級瑪利歐演算法。核心是基於突變的輸入生成器，隨機翻轉輸入位元以創造變異：
此隨機突變方法將遊戲輸入（右、左、跳、動作、下、進入）視為位元組，每個位元代表該鍵是否被按下（1）或未按下（0）。演算法以約10%的機率隨機翻轉個別位元，透過 XOR 當前輸入與隨機遮罩，遮罩為1的位元被翻轉，為0的位元保持不變。透過翻轉位元，演算法生成輸入序列變異，探索遊戲中不同路徑。
選擇此輸入生成演算法的原因是它更貼近遊戲的操作方式：當前按下的鍵很可能在下一幀仍然按著，同時可新增其他鍵。例如，持續按右鍵同時按跳或動作鍵。
然而，隨機輸入生成不足以完成探索。因為瑪利歐隨機移動必然會撞敵人或掉入陷阱而死亡，探索不可能一次完成。必須儲存已走過的路徑（輸入序列），並有策略選擇下一次迭代的路徑。這些路徑有效定義瑪利歐的狀態，因為遊戲是確定性的。
系統被稱為確定性，意指相同輸入必定產生相同輸出。
因此，從相同起點並套用相同輸入序列，必定導致遊戲中瑪利歐相同位置。這表示當我們選擇一條已走過的路徑時，可以重播該路徑，然後嘗試用新突變繼續探索。
路徑選擇需要適應度函數。對超級瑪利歐而言，簡單標準是偏好 x 軸位置最高的路徑，因為通關需向右前進。但總是選擇適應度最高的路徑不可行，因為許多路徑會終止於無法繼續探索的狀態，例如接觸到 Goomba 前或空中即將掉入陷阱。這些狀態無法復原，導致死胡同。
為解決此問題，不能只保留目前最佳路徑，而是需維持不同適應度分數的路徑集合，並用機率分布函數選擇下一條探索路徑。如此一來，我們較可能選擇分數較高的路徑，同時仍給予分數較低路徑探索機會。
此狀態空間探索方法的美妙之處在於其簡潔性。無需理解遊戲機制或手工設計複雜策略。突變過程透過隨機探索自然發現有趣行為，並由適應度評分引導，獎勵遊戲進展。
讓我們回顧該探索系統的運作方式：
這些特性對應於典型的基因演算法：
廣義理解，該方法本質上是一種基因演算法——維持族群、評分適應度、選擇有潛力個體並突變以探索變異。
不過，質疑者可能會提出兩點：缺乏交叉操作，以及輸入序列是否真正算作基因型？
先談基因型問題。傳統基因演算法中，基因型通常編碼多種行為策略，如「多跳躍」、「積極遊玩」、「避免邊緣」。在本系統中，輸入序列編碼的是更具體的能力：達成特定狀態。但這也是一種行為編碼！我們的輸入序列是基因，能達成特定遊戲狀態，是多基因基因演算法框架的有效專化，每條路徑代表達成特定位置的完整行為策略。
至於缺乏交叉，需理解交叉是什麼：一種進化優化技術，透過重組現有基因材料推進族群。交叉結合不同個體的有利特徵，可能產生更優後代，無需新突變。但交叉非必需，是優化手段非基本要求。僅靠突變也能有效探索狀態空間，尤其當路徑逐步構建時。因此，該方法仍是有效基因演算法，只是目前僅依賴突變產生變異，未使用交叉。
此狀態空間探索技術與基因演算法完美對應並非巧合——揭示了測試與演化的根本關聯。
探索複雜狀態空間時，需要：
這正是生物演化所做的。基因不只是指令，而是使生物能達成並存活於族群尚未掌握的環境狀態的特徵。我們的輸入序列扮演相同角色，使瑪利歐能達成尚未探索的遊戲狀態。
有人可能質疑基因演算法是否適用於確定性系統，因為相同輸入必產生相同結果。但確定性反而使基因演算法更強大，因為提供完美可重現性。我們可將非確定性定義為無法控制所有輸入——表面隨機性往往是隱藏狀態。像超級瑪利歐這樣的確定性系統明確揭示此點，為受控演化實驗提供完美可重現性。
認識此方法為基於突變的基因演算法，開啟了數十年演化計算研究的大門，帶來廣泛可能性。
遺憾的是，原文未提供具體實作。既然方法本質是基因演算法，輸入生成、路徑選擇、進度評分與路徑管理有無數變化可試。經過嘗試，我們採用以下實作，雖非最佳，但足以證明方法有效。
核心狀態探索迴圈實作於自主遊玩測試中，協調整個過程。測試反覆從儲存路徑中選擇有潛力路徑，重播至特定遊戲狀態，然後以新生成輸入延伸，持續發現並擴展可達狀態空間。
以下為演算法頂層迴圈：
此優雅迴圈捕捉系統性狀態空間探索精髓，分為探索區間（epoch）結構化發現過程。每個 epoch 中：根據分數選擇路徑，重播至選定狀態，延伸新輸入，評估結果。導致死亡的路徑立即從族群中剔除，專注於可行狀態。每個 epoch 結束時，清理冗餘路徑並選擇新路徑，防止演算法陷入停滯，確保每條有潛力路徑多次嘗試。此結構體現基因演算法核心循環：維持族群（儲存路徑）、評分適應度、選擇有潛力個體、透過突變引入變異（變化續接點與生成輸入，無交叉），並由自然選擇（死亡剔除）推動演化朝向更成功路徑。
讓我們詳細檢視各組件。
輸入生成透過加權動作選擇實作。我們採用混合方法，平衡純探索與結構化遊戲模式。關鍵洞察是純隨機突變過於混亂——瑪利歐需要連貫動作序列才能有效前進。結合加權模糊突變與預定動作模式，我們兼具隨機發現意外解法與符合遊戲機制的人類般移動效率。
路徑選擇實作於選擇函數。策略需平衡利用（最佳發現）與探索（嘗試較差路徑突破瓶頸）。單純「總選最佳」策略失敗於最佳路徑導致無法復原狀態。我們的指數加權給予最佳路徑強烈偏好，同時維持多樣族群。
評分由評分函數計算。評分定義「成功」意義，指導整個演化狀態空間探索。我們使用層級結構與 10 的冪次，創造明確優先順序：完成關卡價值高於關卡內任意位置，向右越遠價值高於速度快。公式 level_num × 10^9 + x_pos × 10^3 + (999 - time) 確保優先順序不衝突：完成第二關的路徑分數必高於仍在第一關的任何路徑，無論後者多快或多遠。
回溯與分割由回溯與分割函數處理。瑪利歐死亡時，我們不想丟棄整條路徑——失敗嘗試中常藏有寶貴進展。回溯移除危險的最後幾幀，提供更安全起點。分割更進一步，提取最高分中間狀態，即使後續動作導致失敗，也保留瑪利歐最佳位置。此回收機制大幅加速探索，保留艱辛取得的進展。
死亡狀態剔除由儲存路徑管理與遊玩迴圈執行。死胡同是演化負擔。積極剔除任何以死亡結束的路徑，並立即刪除失敗的重播路徑，我們維持僅含可行起點的族群。此嚴格選擇壓力防止族群被無法貢獻解決方案的路徑稀釋。雖嚴苛，但有效——適者生存的實踐。
路徑續接實作於遊玩函數。我們不總是重播路徑至終點，而是用三角分布偶爾從較早點續接。此舉透過變化續接點實現突變——嘗試從同一中間狀態不同延伸，可能發現更佳替代方案。高峰值意味通常從終點附近續接（小突變），偶爾早期續接（大突變）防止總是嘗試從同一終點延伸而陷入停滯。
路徑清理由清理函數執行。隨著儲存路徑族群增長，許多路徑變得冗餘——輸入序列略有差異但達成近似位置。保留全部浪費計算資源並稀釋選擇壓力。透過將路徑分組於位置範圍內，僅保留每組最佳，我們維持多樣族群同時剔除近似重複。此壓縮防止族群因邊際差異策略爆炸，保持真實多樣性。
有了上述自主測試，我們開始探索超級瑪利歐狀態空間。
以下為執行自主遊玩測試的基本指令：
預設設定（20秒間隔，每間隔3次嘗試）產生15個 epoch，每個 epoch 3次探索嘗試。因需從頭重播路徑以達選定狀態，實際執行時間依路徑長度變動——預期5分鐘探索約需15至30分鐘。
以下為22分鐘完成的範例執行：
族群包含16條路徑，分數各異，展現清理策略維持的多樣性。我們最佳分數1002836976解碼為：
表示瑪利歐成功前進2836像素，約為第一關總距離70%，證明自主探索可在無領域知識下取得顯著進展。
為每次探索嘗試重播路徑以達特定狀態帶來顯著開銷。因參考實作未包含存檔/續玩功能（檢查點），每次必須從頭重播，為實務限制，降低探索速度。
為加速過程，我們為遊戲加入兩項關鍵功能：
這些測試儀器技術為實務測試標準作法，對自主探索實用性至關重要。生產測試環境中，我們常儀器化系統以控制初始狀態、加速時間、注入錯誤與操控條件——這是有效測試的關鍵。
經過嘗試與錯誤（概率搜尋常態），我們發現以下參數顯著加速尋找解答：
此設定偏向利用（最佳路徑）勝過探索（多樣族群），在針對特定關卡時效果良好。
以下為我們通關第一關的影片：
第一關相對簡單——演算法持續發現地下管道捷徑，繞過大部分障礙。表現優異，瑪利歐！
第二關使用相同參數與全新路徑檔獨立探索：
第二關更具挑戰，因陷阱增多、敵人多樣（Goomba、Koopa、食人花）與移動平台。高幀率設定帶來意外優勢——瑪利歐無敵時間似乎延長，能快速通過危險區域。儘管困難，我們偏向利用策略（總選最佳路徑，停止索引突變，無回溯）成功找到通關路徑。
接著是較難通關的第三關。
第三關有許多導致瑪利歐死亡的路徑——必須精準跳躍跨越大空隙並避開敵人。精準跳躍與敵人迴避的組合使尋找通關路徑更難。儘管如此，第三關仍被通過，上述影片展示我們自主瑪利歐的成功演出。自主測試再度勝利！
我們的 Python 參考實作包含四關，第四關為自主探索測試的最終挑戰：
第四關揭示一個有趣的錯誤（可能因高幀率技巧引起）——碰撞火焰棒時瑪利歐變透明，能繞過所有剩餘障礙抵達終點。無論是否錯誤，演算法成功找到終點，展示自主狀態空間探索能發現傳統測試難以察覺的意外行為。
我們成功展示 Antithesis 自主探索方法的效能，使用我們的 Python 參考實作通過超級瑪利歐兄弟四關。分析方法後，我們將其與基因演算法連結，揭示探索背後的演化計算結構。實作無需人為指導完成所有關卡，發現捷徑、應對複雜敵人模式、掌握精準跳躍，甚至揭露第四關潛在碰撞錯誤。
然而，關鍵限制是：我們的適應度函數僅衡量進度（x 位置、關卡完成），未驗證正確性。我們未檢查瑪利歐速度是否符合預期物理、跳躍是否有合理原因、掉落是否僅在無地面支撐時發生，或移動是否由遊戲狀態因果決定。Antithesis 玩原 NES 遊戲，我們用 Python 實作，這點對正確性驗證至關重要——正確行為檢查需存取內部遊戲變數（速度、碰撞狀態、按鍵）而非僅瑪利歐 x,y 位置。
在行為模型系列（第一與第二部分）中，我們開發了具因果、安全與活性屬性的完整行為模型，逐幀驗證遊戲正確性。在本自主測試系列第二部分，我們將直接將該模型整合至探索迴圈，實時驗證每一幀。此組合強大：自主探索發現龐大狀態空間，行為模型確保全程正確性——不僅尋找通關路徑，更找出隱藏於邊緣案例的正確性錯誤。
🛸 請繼續閱讀《使用行為模型自主測試超級瑪利歐（第二部分）》。