Term Project--Search Methodologies In Games
四, 01/11/2007 - 23:09 — CloudEX"
資工三甲 493511553 樓維恩
Chapter1 前言
每個人從小到大或多或少都玩過電動玩具，而最早的電玩遊戲都是單人遊戲為主，單人遊戲中，益智遊戲也佔了很大的一部分，棋 弈類遊戲，包括象棋、圍棋、跳棋、五子棋、西洋棋等，都是相信經典的遊戲，也是打發時間的好玩具，可以挑戰人腦是否能贏過電腦，而電腦沒有大腦，只是一堆 電子零件，它又是怎麼思考的呢？它怎麼知道下一步棋該怎麼下呢？在幾十年前，軟硬體設備遠不如現今的年代，就已經有了這類遊戲，這次的目的主要在探討這些 遊戲中所使用的演算法。
[@more@]
Chapter2 背景
2-1 Search Tree的分類
對於一般的益智遊戲或問題探討，解題的方法就是使用「search」，尋找一個最佳的解，一般search都會搭配tree的資料結構來表示，而解決一個search tree的方式主要有兩種：
1. Data-driven search，又稱Forward chaining，即指從起點出發，尋找終點。通常是我們知道每個node的狀態(條件、規則等)。
2. Goal-driven search，又稱Backward chaining，和Forward chaining相反，是由終點出發，回頭找尋起點。某些情況下，我們不清楚「規則」，不了解問題發生的原因，但知道其結果，則使用Backward chaining。
在很多情況下，Backward chaining會比Forward chaining更好用更有效率，最明顯的例子就是每個人都有玩過的走迷宮，常常我們會發現要從起點走到終點很難，可能繞了一大圈結果發現是死路，但從終點往回走卻非常簡單。但是Backward chaining的方式限定於"已知終點"的情況，故Forward chaining還是比較泛用的方法。故此次決定著重於Forward chaining的部分。
專家系統(expert system)也是採用Forward chaining的方式，從已知的原因(條件)推導出未知的結果。
Forward chaining最常用的兩種演算法為：
1. Depth-First Search
Depth-First Search是一種很常用的搜尋演算法，其名的由來在於它是往最深的那個點走，每一條路徑都走到底，若沒路了再回頭
其用了"Chronological backtracking"的方法，若走到死路則回頭。在電腦應用上，尋找資料在硬碟中的位置也是使用Depth-First Search。
但在某些情況下，若問題的複雜度很高，其tree的展開非常的大，甚至趨近無限大，使用Depth-First Search將會非常沒有效率甚至找不到解。
2. Breadth-First Search
和Depth-First Search相對的另一個方法是Breadth-First Search
和Depth-First Search往最深的level走下去的方法不同，Breadth-First Search是先將最淺的level的每個node走過一次，再往下個level走。適合用在當tree的深度很淺的時候，效率非常的高。但若目標(終點)在最深層，Breadth-First Search的效率就遠不如Depth-First Search。
2-2 Search方法的特性
上面介紹了一些不同的search方法，不同的方法在不同的問題上會有優劣，適合解決的問題也不同。故有幾樣特性用來評估一個演算法是否適用在某個問題：
■ complexity
■ completeness
■ optimality
■ admissibility
1. Complexity：分為time complexity和space complexity，time complexity最直觀的方式就是計算其總共花了多少時間，但一般使用Big-O描述time complexity而非一個時間值。space complexity則是記憶體(儲存空間)的使用量。complexity通常只用來衡量一個演算法的解是否合適，因為通常最快的方法找出的解都不會是最好的。
2. Completeness：第二個評估的特性就是「是否解出答案」，很簡單的，若演算法無法解出答案，則對這個問題完全沒有幫助(有時候可能問題本身就是無解，但必須能發現"無解"這個解答)。
3. Optimality：有時問題可能不只一種解答，若能找到最佳的答案則稱之"optimal"。optimal的演算法不一定有效率，它可能要花較多的時間去尋找答案，但找到的答案卻會是最佳的。
4. Admissibility：有些時候optimal的定義會被當成是「最快的」，這時就使用admissibility來代替optimality，而optimal則用admissible來代替。
Chapter3 Game Tree和實際應用
3-1 Game Tree
Game Tree，簡單的說，就是用tree來表示目前棋局的情況，和之後可能的走法
Game Tree實際使用的演算法有很多種，在這裡只討論其中兩種：
1. Minimax：
在Minimax的演算法中，將tree的每個level從root開始依序設為MAX、MIN、MAX、MIN…
使用Depth-First Search，在MAX的level時，從其child node中挑選最大的值放入；在MIN的level時則從其child node中挑選最小的值放入，最後回到root的值就是解。
2. Alpha-Beta Pruning
Alpha-Beta Pruning演算法是在Minimax的演算法上加入α值和β值，分別表示MAX level node的下限和MIN level node的上限，目的在於將tree中不必要的分枝給修剪(cut)掉。
若假設tree的深度為d，每個node的child數都為b，總共的node數為n(n=bd)
則Minimax的time complexity為O(bd)，而Alpha-Beta Pruning的time complexity可減為O(bd/2)，明顯的比Minimax的演算法好。
3-2 實際遊戲應用
找了一些比較簡單常見的遊戲，和解決這些遊戲的實作方法，但在此只簡單介紹一些所找到的一些文獻中的實作方法，並不詳細敘述其步驟。
■井字遊戲
3*3的井字遊戲所有可能的排列組合共有39=19683種，比起西洋棋或其他遊戲擁有上兆種排列組合，井字遊戲算是非常簡單的。
在3*3的井字遊戲中可以直接使用Depth-First Search或Breadth-First Search，在對手下了一步棋之後，直接評估剩下的8種的可能走法，再進一步評估更深層的更多可能解，最後統計這8種走法哪一個能得到最多的勝局計分，找出最佳的走法。
但在5*5的井字遊戲中就沒辦法使用這種方法，因為總共的組合有325=847,288,609,443，8千多億種，勢必得犧牲演算法執行的深度去換取執行的效率。在5*5的情況下，有一種方法是使用判斷「可能連成直線」的方法，在對手下第一步和第二步之間尋找關聯性，只判斷是否有可能連成一直線，可減少search的深度。
■五子棋
五子棋的棋盤比起井字遊戲大上非常多，所以絕不可能考慮所有可能組合，故有人想出使用一些五子棋的規則來設計演算法：
首先在棋盤上的每個空位都設一個cost值，初始值為0。當對手或自己每下一步棋，則判斷此步棋的直、橫、斜列是否有可能達成活四/活三(死四/死三)等，給予不同的cost值，cost值愈高的則代表這步棋愈重要，愈需要優先下這步。
但是每下一步棋就要將cost值歸零重新計算，較浪費時間。
■象棋
在象棋中因為棋子有很多種類，不像五子棋只分為黑棋和白棋，象棋每種棋子都有其特定走法。做法是先建立一個「殘局知識庫」，藉由目前盤面上所剩棋子，去評估若某一子被吃掉後可能最造成勝局、負局或和局，判斷哪一步是最佳的。這個作法只需展開一層game tree就可找到解，不會因為殘局的困難度而影響執行的時間。
■圍棋
圍棋的規則又更複雜了，要設計一個強大的圍棋判斷演算法，設計者本身的棋力也要夠強，因為圍棋的規則雖然簡單但卻有非常多種變化，除了 一般下棋的原則外，又有很多矛盾的例外。其中一種作法是判斷棋盤上的黑白子是否交纏在一起，將搜尋法裡分為攻和防兩種不同模組，這兩種模組互相呼叫，形成 一個game tree，再以AND-OR方式進行搜尋，並且要加入非常多各種棋法的判斷條件，此必須要有相當程度的圍棋能力。
■走迷宮
又被稱作「老鼠走迷宮」，走法算是誤打誤撞，沒有計畫的走。
實作方法其實跟這次Lab中的Sudoku一樣，直接採用recursive(backtracking)的方式實作，先設定好要先往上、下、左、右哪一邊前進，設定好順序後就開始走，若走到死路就回頭，跟Sudoku「走到無解的狀態就回頭」是一樣的道理。
Chapter4 結論
解決一個問題的演算法可能有千百種，而是否恰當、實用、有效率、容易實作都還是得先經過一番評估。該如何從這麼多演算法中挑出適合的， 除了要先了解一些演算法的基本概念外，還要多參考一些其他資料，參考他人對於類似的問題有哪些更好的解決方法。在我們看來一些遊戲雖然玩起來很簡單，但要 如何讓電腦學會怎麼去判斷下一步該如何走又是另一回事，對於不同的遊戲，除了要挑選適當的方法，還要先了解遊戲的規則，才能加入適合的判斷條件，以提升程 式執行效能，雖然電腦執行速度很快，但若方法使用不當，很可能會讓玩遊戲的使用者等待過久，甚至導致程式當掉。對於益智遊戲這種電腦會需要「思考」的程 式，和人工智慧也有相當大的關係，而人工智慧的範疇也非常大，要寫出一個複雜的遊戲其實非常不容易，要對演算法和遊戲都有一定程度的了解才能完全實作出一 個好的遊戲演算法。
參考資料：
[1]井字遊戲的設計與製作 DESIGN AND IMPLEMENTATION OF TIC-TAC –TOE，王仲民，台灣科技大學電子工程系
[2] http://www.cyut.edu.tw/~fmlee/course/ai/NilssonAI/ch12-2.htm
Adversarial Search，蕭明芳、楊景森、陳武成、蘇祐新
[3] http://www.jfvs.tpc.edu.tw/jfvs/教學組/專題報告/91資訊科/教師研究.doc
[4]智慧型程式設計上課講義，許見章教授，輔仁大學資訊工程學系
[5] http://bbs.wefong.com/archiver/?tid-1183090.html
[6]象棋殘局回溯分析演算法之實作與評估 Retrograde Analysis Algorithm for Chinese Chess Endgames: Implement and Evaluation，方浩任，Institute of Information Science，Academia Sinica, Nankang 11529 Taipei, Taiwan
[7]棋串攻防搜尋中不進子的辨識與處理方法 Identifying Squeeze-Forbidden Conditions and Processing Them in Block-Capturing Search，嚴礽麒、劉邦鋒、許舜欽http://weco.net/blog/cloudex/11-jan-2007/1746
橫向優先搜尋 (breadth-first search)
breadth-first search 是以某一節點為出發點，先拜訪所有相鄰的節點。再依序 拜訪與剛才被拜訪過的節點相鄰但未曾被拜訪過的節點，直到所有相鄰的節點都已被 拜訪過。 因此，進行 breadth-first search 時，需要使用 queue ，以便記錄拜訪的順序。
- 起始。
- 假設從 a 開始拜訪，我們將 a 放進queue。
QUEUE queue front a queue back
接下來把 a 從queue中取出，a 有三個節點可以拜訪 (b, c, d)。
QUEUE queue empty
- 假設我們選擇先拜訪 b ，我們將 b 放進queue。
QUEUE queue front b queue back
- 再來，假設我們選擇拜訪 c ，我們將 c 放進queue。
QUEUE queue front b c queue back
- 我們選擇拜訪 d ，我們將 d 放進queue。
QUEUE queue front b c d queue back
由於已經拜訪過所有與 a 相鄰的節點，我們從queue中取出下一個元素 b， b 有兩個節點可以拜訪 (e, f)。
QUEUE queue front c d queue back
- 假設我們選擇先拜訪 e ，我們將 e 放進queue。
QUEUE queue front c d e queue back
- 再來我們選擇拜訪 f ，我們將 f 放進queue。
QUEUE queue front c d e f queue back
由於已經拜訪過所有與 b 相鄰的節點，我們從queue中取出下一個元素 c， c 沒有節點可以拜訪。
QUEUE queue front d e f queue back
由於已經拜訪過所有與 c 相鄰的節點，我們再從queue中取出下一個元素 d， d 可以拜訪 g。QUEUE queue front e f queue back
- 我們選擇拜訪 g ，我們將 g 放進queue。
QUEUE queue front e f g queue back
由於已經拜訪過所有與 d 相鄰的節點，我們從queue中取出下一個元素 e， e 沒有節點可以拜訪。
QUEUE queue front f g queue back
由於已經拜訪過所有與 e 相鄰的節點，我們從queue中取出下一個元素 f， f 沒有節點可以拜訪。
QUEUE queue front g queue back
由於已經拜訪過所有與 f 相鄰的節點，我們從queue中取出下一個元素 g， g 沒有節點可以拜訪。
QUEUE queue empty
由於 g 也沒有節點可以拜訪，此時 queue 已經全部清空，breadth-first search完成。
人工智慧是探討研究一種偉大電腦機器的學門, 這種機器不只是人類文明的決定性工具, 它更可能成為地球上最重要的新興族群, 而知識庫系統是展現其應用能力的典型。 ~yth
課程最新公告:
| 公 告 事 項 | 說 明 |
| 1月11日 星期五 9:00~11:00 Room:234 | 期末考, open book 考題: 1. 題目敘述..., 若依最大期望效用(maximum expected utility)的原則計算，則應該做怎樣的決策? 2.知識擷取(knowledge acquisition)常用的方法有哪三種? 3. 請找出下表中的是否有納許均衡 4.試問消費者今日購物的機率和零售商今日進行特價的機率各為多少時為混合策略的納許均衡 5.請畫出payoff table並說明理性的決策應該是什麼? |
| 12月28日 | 平常考, open book 考題: 1. resolution 2. forward chaining & backward chaining
|
| 11月9日 | 期中考, open book 考題: 1. 假設你想從下圖所示的迷宮中的目前位置尋找出路從Exit脫離困境，圖中空白的格子代表可以走的路，其他為障礙物無法通過，請依下列各種search方法分別依序標示(2, 3, 4, …)找到出口的每一步過程: (a)breadth first search (b)depth first search (c)best first greedy search (d)A* search 2. 利用minimax演算法求下圖的game tree 3. 利用alpha-beta pruning演算法求下圖的game tree 4.請用真值表的方法證明... 5.命題邏輯, 述語邏輯, 邏輯推論 |
| 11月2日 | 平常考, open book 考題: 1. A* Search 2. hill-climbing(爬山)法 3. greedy local search(貪婪局部搜尋)和stochastic hill climing(隨機爬山法) |
| 時間: 9:10~12:00 地點: 234
|
課程名稱 : 知識庫系統(Knowledge-based systems)
教科書 : 人工智慧, 現代方法 2/e, 高超群 編譯, 全華圖書
課程教學大綱、教學進度及投影片 :
| 投 影 片 | 內 容 | 教 科 書 閱 讀 |
| 1 | 緒論 | 第一章 |
| 2 | 智慧型代理人 | 第二章 |
| 3 | 利用搜尋法解決問題 | 第三章 |
| 4-1,4-2 | 利用資訊的搜尋方式 | 第四章 |
| 5 | 限制滿足問題 | 第五章 |
| 6 | 對抗式搜尋 | 第六章 |
| 7 | 邏輯代理人 | 第七章 |
| 8 | 一階邏輯 | 第八章 |
| 9 | 一階邏輯的推論 | 第九章 |
| 10 | 知識表示法 | 第十章 |
| 11 | 不確定性 | 第十三章 |
| 12-1,12-2 | 不確定性的知識表示法 | 第十四章 |
| 13-1,13-2 | 機率推理 | 第十五章 |
| 14 | 關於時間的機率推理 | 第十六章 |
| 15 | 制定複雜決策 | 第十七章 |
補充教材:
| 投 影 片 | 內 容 | 教 科 書 閱 讀 |
| 1 | forward chaining vs. backward chaining | |
| 2 | Naive Bayesian Classifier |
Q & A :
| 日 期 | 問 題 | 參 考 答 案 |
考古題 :
◤網路資源◥
1. 8 puzzle
[配合課本第三章的 華容道遊戲例子之程式。依照Wikipedia,華容道一詞源於《三國演義》中"諸葛亮智算華容，關雲長義釋曹操"的故事，指赤壁之戰曹操兵敗被迫逃走，最後到華容道時關羽顧念舊情，網開一面讓曹操離去。]
[可以自行繪圖然後針對此圖形展示breadth-first search和depth-first search的功能]
[書上第三章的四個演算法Breadth-First 、Depth-First、 Depth-Limited、Iterative Deepening可以透過此程式來實驗比較]
[可以利用8-puzzles遊戲來比較書上第三、 四章的演算法Breadth-First 、Depth-First、Iterative Deepening、Greedy search、A* search、Branch-and-Bound search]
5. Solution of N-Queens Problem by Genetic Algorithm
[可以觀摩用基因演算法來解N后問題]
[這是取材自MIT6.034課程網站的一張圖, 學過演化論的各位, 請問你的感想!]
6. Stochastic local search based CSP solver
[可以觀摩用各種局部搜尋演算法來解8后等最佳化問題]
7. Minimax & Alpha-beta pruning
[3或4層的game tree, 可以隨機產生各個節點的評估值讓你實驗minimax和alpha-beta pruning演算法]
[這是一本不錯的邏輯學教科書]
9. LogicCoach
[這裡有邏輯私人教師的軟體可以下載]
[有不受時間限制的個人版Visual Prolog軟體可以練習寫Prolog程式]
11.Game Theory
[請各位同學來這裡玩玩囚犯的困局]
<修改日期-2008.1.08>
--
[垃圾桶] 裡沒有會話群組？
沒有留言:
張貼留言