Monte Carlo Tree Search Assisted Design Decision Making
這個程式是為了模擬一個建築師進行設計時, 要在多個決策選項的搜尋空間中找到能夠被多個評估函數全部接受的決策組合。這些評估函數分為兩種, 有一種是能夠在所有決策都確定以後用電腦進行分析而得到結果的, 例如法規、結構、耗能與工程預算。另一組評估函數是需要專家判斷, 目前無法交由電腦執行, 例如美感、業主偏好、藝術價值等等評估。建築師的任務是要找到能夠通過所有評估項目的決策組合。以下描述兩組MCTS分別描述電腦與設計團隊的作業, 這個研究希望探討MCTS是不是可以提供有用的資訊協助建築設計團隊在設計過程中進行決策。
以下以建築立面的設計為例進行說明：假設建築物立面被分為 n 個區域, 每個區域必須選擇其外牆構造單元, 每個單元有 m 個選項, 因此整個決策空間是由 n 個 m 元選項所構成。每一個構造單元的選用會影響到外牆的結構、工程預算、耗能、採光、隔音等等, 假設目前都已經可以使用電腦運算進行評估, 前提是每一個決策必須都已經確定。建築師另外還需要考慮其他的條件, 必須人為判斷而無法使用電腦評估的, 例如客戶偏好、藝術價值…. 在此情境下, MCTS是否可以發揮其功能, 讓電腦評估的結果可以最大的協助建築師進行決策。建築師需要為n個選項全部決定
搜尋空間：MCTS的搜尋空間是一個16*16的Boolean array, 陣列內256個值給定一個搜尋決策排序之後就定義了一個二元的搜尋樹。搜尋結果必須通過n個檢測函數, 每個檢測函數都通過才算合格。
檢測函數：每一個檢測函數會使用一或多組16*16的Boolean array作為標的, 與受檢測的array逐一進行比對。 每一次比對計算受檢測array與標的array的相似度任一次的比對結果若超過門檻則檢測停止並回傳通過該函數的檢測。
MCTS的搜尋從選擇最優先的決策值開始, 進行expand, simulation之後進行檢測, 檢測結果就進行back propagate, 計算並更新每個決策值的成功率, 一直到被使用者終止為止。
使用者參考各個決策選項的成功率後決定採用某一個或多個決策, 設定其值, MCTS就繼續往下搜尋, 更新後繼未定之決策各選項的成功率。使用者的決策不一定依照所給定的搜尋順序。
以上是第一個執行模式。第二個執行模式則加入第二組MCTS來模擬使用者的決策。第二組所依據的搜尋決策排序未必與第一組相同, 且所使用的評估函數也不相同。第二組進行MCTS, 更新其決策選項之成功率後選定某些決策並設定其值後, 交給第一組MCTS繼續進行程序, 兩組MCTS可以同步進行。第二組在選定決策項目時可以參考第一組MCTS的決策選項成功率, 優先選擇兩組MCTS模擬結果成功率都比較高的選項作為決策, 此部分的決定方式需進一步討論, 初步可以將兩組的成功率乘上權重相加作為選擇依據。
檢測的函數可以選用圖片, sample成16*16矩陣。做法是拿許多張圖片, 定一個16*16的方格, 每一個方格中隨機取一點求rgb的平均, 大或等於128就算白, 小於128就算黑
MCTS其實就是統計取樣, 這個例子中建築師需要做256個二元決策, 如果等到所有的決策都做了才能進行評估, 那一輩子也找不到好設計。MCTS 可以幫建築師用隨機取樣的方式填補其尚未做的決策, 檢測後統計成功率, 告訴建築師目前的決策預期的成功率有多大, 有沒有其他決策選項會有更高的成功率。 254個決策的決策空間如果過於龐大無法在有效時間內運算, 可以縮小。其搜尋困難度可以藉由評估函數的通過率來調整。
實際進行時, 人所組成的設計團隊和電腦同步作業。人在做決策的期間, 電腦24小時不間斷就還未決定的決策進行取樣, 評估後更新決策樹之節點的成功率, 提供給設計者參考。人所構成的設計團隊可能需要幾天的時間, 或許還要開會討論, 在目前階段未定的決策中, 選擇一部份進行決策, 再交給電腦繼續做MCTS
如此來回進行幾個回合之後, 設計團隊確認所有的決策選項, 如果最後的結果可以符合所有的檢測項目就算成功。如果這部分可行, 可以繼續加入優化的功能。就是在所有的評估函數中選擇一個做為優化的目標函數, 原先通不通過的輸出改為得分, 決策樹節點的成功率就變成目標函數的期望值, 設計團隊就可以選擇較高期望值的節點繼續探索更好的設計方案
人和電腦合作的設計流程好像是沒有對手的alphago, 人一步一步把設計做完, 過程中參考電腦提供的各個走法的成功率來做下一步的決策, 與alphago的差別是電腦並不能掌握全部的評估函數, 有一部份是在人的腦中無法用程式處理的。因此我們在電腦模擬時就用兩組檢測函數, 第二組代表人腦冥冥之中的黑箱檢測。最後如果能夠找到設計方案完全符合兩組的檢測函數, 就算勝利。
選擇MCTS的主要原因之一是夠robust, 我們不需要了解搜尋的檢測函數的特性, 有任何需要的評估函數隨時都可以加入搜尋的條件, 也可以隨時撤離不需要的函數。我們也不需要在意搜尋空間太大, 基本上比圍棋小的空間都可以處理, 因此不需要分析搜尋空間的結構以縮小搜尋樹。這兩個特徵都符合設計問題的處理, 也是過去各種方法所遭遇的困境。
