Computer Science Department Gaming Tree(AI對弈樹) Author : 9717133 Huan Po Lin Computer Science Department December 25th 2009
前言 「我聽到的會忘記，我看到的能記住，我做過的才真正明白」 ─ 華盛頓博物館 從做中學
大綱 遊戲觀察 搜尋範例 搜尋想法(運用Gaming Tree) 實作解題 程式解析 優化 總結
遊戲觀察 拿最後一個輸掉 → 結束條件是全部都不剩
搜尋範例 紅色點（勝） 藍色點（輸） Root Node 1 Node 2 Node 3 Node 11 Node 12 Node 21 Player 1 Player 2 Player 1
搜尋想法 在Gaming Tree之中，去搜尋跟枚舉所有的狀況出來，每一個節點對於該玩家只有兩種情況 ─ 贏或輸 Win Lose
搜尋想法 則對一個Gaming Tree來說，如果這一個節點可以找到一個對手會輸的子節點，那對自己就是勝利的節點了 Root Node 1
實作解題 Problem 6: Yakumo is not AO CHIAO http://ttcpc.nctucs.tw/files/ttcpc09.pdf 在實作上面需要做到窮舉所有情況，因此可以採用任何一種窮舉搜尋(Exhaustive search)，可以利用DFS或者是BFS來實作
實作解題 實作遞迴想法→ 結束情況(End condition)? -> Yes 回傳是勝利還是輸 -> No 繼續遞迴搜尋子情況
程式解析 bool cal() { if(heap[0] == 0 && heap[1] == 0 && heap[2] == 0) return true; //已經結束啦 for(int i = 0; i < maxN; i++) for(int j = 1; j <= heap[i]; j++) //枚舉拿珍珠的情況 heap[i] -= j; if( cal() == 0 ) //別人的失敗就是我的快樂 heap[i] += j; return true; } return false;
優化 在殘局的情況其實有很多是重複的，譬如說第一排剩下2顆、第二排剩下3顆而第三排剩下1顆的情況，可能出現數十次，因此可以用一個表去記錄說如果該情況出現過，那就可以直接回傳該點是勝還是負或者是尚未知道
總結 妳應該學到了 如何分析一個對弈遊戲 如何實作妳的搜尋 如何優化妳的搜尋