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