五子棋AI编程硕士论文.pdf

中原大學 資訊工程學系 碩士學位論文 五子棋棋略的演化學習法 Evolutionary Learning for Playing a Gobang Game 指導教授 阮議聰 博士 研 究 生 莊秉文 中原大學 資訊工程學系 碩士學位論文 五子棋棋略的演化學習法 Evolutionary Learning for Playing a Gobang Game 指導教授 阮議聰 博士 研 究 生 莊秉文 中華民國中華民國 九十二九十二 年年 六六 月月 I 中文摘要中文摘要 本篇論文將探討 Genetic Algorithm GA 基因演算法又稱遺傳演算法 運用 在推導五子棋的下棋策略 利用基因演算法之多維空間搜尋法 來找出合適的五 子棋棋略 讓原本是白紙般的下棋策略 透過演化的模擬 快速地學習到致勝的 棋法 本論文的目的在於設計一個演化環境模式 重點於基因演算法在決策樹理 論上的運用並加入了學習機制 並讓基因演算法能有效率及快速地演化到吾人所 需求的結果 論文中提出了兩種演化模式 以不同的演化模式來找出相同的目的 與結果 由於不同模型的設計 使得兩者的演化效率也有程度上的差異 第一種 模式為我較早的想法 第二種為之後改良增強的模式 其中以第二種方法為本論 文研究的重點 其具有著學習能力的演化模式 在當中並提出了從錯誤中學習的 賞罰系統 和提高基因演算法之效率的基因函式庫 而此種設計模型可讓五子棋 的演化學習法能從錯誤中成長 並且在每一世代演化都要比前一世代進步 以希 望減少其演化空轉的可能性 本論文亦根據所提出的方法 實做出一套五子棋的 演化系統 系統根據本論文所提出的方法來演化五子棋的策略 且有遊戲介面可 讓吾人與之對戰 測試其演化的效果 論文的最後附上實驗章節 並對本論文的 方法做驗證及測試 關鍵詞 基因演算法 五子棋 人工智慧 II AbstractAbstract In this paper we will discuss with using Genetic Algorithm GA on producing a strategy for playing a Gobang game the original random strategy at the beginning of the first generation is hard to win an opponent but after the evoulationary process the strategy of GA will become more intelligent The purpose of this paper is designing a evolutionary model for GA it let GA efficiently and quickly obtain the result which conforms to us We proposed two different models to find the same solution or purpose due to different models make the diversity of them in efficient and speed The first model is designed with a general decision tree is not good enough for learning strategy but the second one is suitable for learning and contains two new correcting methods it speed up the learning ability in evolutionary process I show in this paper that how the flow path of evolutionary learning algorithm will be driven Keyword Genetic Algorithms Evolutionary Learning Gobang Game III 致 謝致 謝 本論文能順利完成 感謝指導教授阮議聰老師 於百忙的事務中 不厭其煩 地糾正與指導 亦給我許多啟發與磨練 在理論及系統架構上給我不少的意見及 思考方向 承蒙其他二位口試委員 台大的郭大維老師 中原的練光祐老師 給予學生 論文寶貴的意見 使得學生論文更加完善 在此學生給予最高的感謝 於研究所兩年 許多同學及朋友給我許多意見 使我能順利地完成論文的撰 寫及建構出優良的系統 這些意見與想法將永記心頭 最後 感謝我的家人及父母 在我學生生涯中 用上他們所有的愛心 使我 能順利完成我的學業 在研究所研究期間 非常感謝我的朋友們 慧君 仕熙 諺泯 捷隆 仕達 忠信 以及其他在研究所期間幫助我的人 感謝你們這兩年 來的支持與鼓勵 莊秉文 謹於 中原大學資訊工程學系研究所 中華民國 92 年 6 月 26 日 IV 目 錄目 錄 中文摘要 I Abstract II 致 謝 III 目 錄 IV 圖目錄 VIII 第一章 導論 1 1 1 背景 1 1 1 1 基因演算法概述 1 1 1 2 基因演算法之特性 3 1 1 3 基因演算法運用領域 3 1 1 4 Genetic Programming 4 1 1 5 基因演算法在本論文之運用 4 1 2 論文架構 5 第二章 五子棋策略搜尋樹 一 6 2 1 預設五子棋 AI 的基本演算結構 6 2 2 IF rule Tree 的五子棋基因演算法 9 2 2 1 operators 的設計 9 2 2 2 搜尋樹的建立規則 11 2 3 多目的之 OPERATOR 17 2 3 1 IF rule tree 演化方式 18 2 3 2 主要結構 20 2 3 4 模擬驅動函式演算法 22 2 4 Crossover 膨大化 27 V 2 4 1 評估 subtree 的使用情況 28 2 4 2 Table 記錄法 29 2 5 基因函式庫 31 2 5 1 基因函式庫的用途 31 2 5 2 特殊的 crossover 32 2 6 本章結論 34 第三章 五子棋策略搜尋樹 二 35 3 1 SWITCH tree 型式的五子棋基因演算法 35 3 1 1 operators 的設計 36 3 1 2 SELECTION operator 的內容 board game 的棋型 37 3 1 3 SELECTION operator 加入 不介意值 39 3 2 Weight function 40 3 2 1 棋型的進攻與防守 40 3 2 2 設計的特性 41 3 3 棋型的重要性演化 41 3 3 1 個體 individual 的 fitness 評斷方式 42 3 4 GA SELECTION 44 3 5 GA CROSSOVER 44 3 5 1 CROSSOVER 修正 46 3 6 Mutation 47 3 7 從失敗或成功中學習 48 3 8 基因函式庫 49 3 8 1 與之前的差異點 49 3 8 2 函式庫該存放的內容 49 3 8 3 棋盤空點上的 weight 評估 49 3 8 4 基因函式庫在建立前的準備 50 3 8 5 初代基因函式庫的形成方法 50 VI 3 8 6 插入基因函式庫方式之說明 56 3 8 7 CASE condition 之內容重複時的處理方式 56 3 8 8 基因函式庫的內容修正 56 3 9 用來訓練基因函式庫內容的賞罰系統 57 3 9 1 賞罰系統概述 57 3 9 2 關於 weight 的間隔值 61 3 10 演化的細部機制 62 3 10 1 特別的個體 individual 63 3 10 2 演化完成 64 3 10 3 外部演化 64 3 11 本章結論 64 第四章 演化完成後的去蕪存菁 65 第五章 系統實做與實驗數據 70 5 1 實做程式 70 5 2 針對不同的賞罰對象設定所執行出的數據比較 71 5 3 針對賞罰最後之步數設定所執行出的數據比較 72 5 4 針對有無使用基因函式庫所執行出的數據比較 74 5 5 針對 Crossover rate 的變化之演化的數據比較 76 5 6 針對 Population 數變化之演化的數據比較 77 5 7 針對賞罰系統之不同加權值設定之演化的數據比較 78 5 8 針對棋型中加入不介意符號之演化效能實驗 80 第六章 結論與展望 81 6 1 結論 81 VII 6 2 未來展望 81 參考書目 82 VIII 圖目錄圖目錄 圖 2 21 無規則的演化樹 9 圖 2 22 有規則的演化樹 10 圖 2 31 演化流程圖 19 圖 2 32 Population 的結構圖 20 圖 2 51 GP 插入基因函式庫之示意圖 34 圖 3 11 SWITCH tree 型式的樹狀結構圖 36 圖 3 51 Crossover 圖解 一 44 圖 3 52 Crossover 圖解 二 45 圖 3 53 Crossover 圖解 三 46 圖 3 81 待插入基因函式庫之個體 51 圖 3 82 基因函式庫初代形成圖 52 圖 3 83 個體插入基因函式庫圖 1 53 圖 3 84 個體插入基因函式庫圖 2 54 圖 3 85 個體插入基因函式庫後圖 55 圖 3 91 賞罰系統示意圖 1 58 圖 3 92 賞罰系統示意圖 2 60 圖 3 101 SWITCH tree 架構之演化流程圖 63 圖 4 1 tree 可合併示意圖 66 圖 4 2 tree 可剔除示意圖 68 圖 5 1 程式實做之圖形介面 70 圖 5 3 針對賞罰最後之步數設定之比較圖 72 圖 5 4 模型 A 與 B 針對有無使用基因函式庫的比較圖 74 圖 5 5 針對 Crossover rate 的變化之演化的數據比較圖 76 圖 5 6 針對 Population 數變化之演化的數據比較 77 IX 圖 5 7 針對賞罰系統之不同加權值設定之演化的數據比較圖 78 圖 5 8 針對棋型中加入不介意符號之演化效能實驗圖 80 1 第一章 導論 第一章 導論 1 1 背景 1 1 1 基因演算法概述 1 1 背景 1 1 1 基因演算法概述 基因演算法 Genetic Algorithms 是一種最佳化空間搜尋法 16 其理論 根據是來自於達爾文的演化論即 物競天擇 適者生存 適者生存 不適者淘 汰 達爾文的演化論是以三項觀察為基礎 1 所有的生物都一代一代在改變 2 生物們的特徵可以遺傳 3 生物們都參與生存競爭 所以在這種生存競爭中 優秀的品種有著優良的基因 透過遺傳其後代可能 越來越優秀 而基因不優良的品種 經過許多代之後自然被環境所淘汰 統稱之 為演化 藉自然淘汰作用而推動生物演化的理論便為達爾文演化學說的核心 基因演算法即是由此一論點出發 它是一種 machine learning 的模型 靠 著對模擬自然界的演化方式 運用一些擬生物化的人工運算過程產生一個群體 population 當中有許多個體 individuals 個體由許多染色體構成 當 對特定問題求取最佳解時 再對群體中的每一個體做 evolution 完成後再產生 下一代 方法例如選擇 selection 再結合 recombination 交配 crossover 和突變 mutation 等進行演化 週而復始地進行一代一代的演化 以求得一個最 佳的結果 1 歷史 基因演算法是進化演算法 evolutionary computing 的一種 其在人工 智慧的領域中廣泛地被運用 一個問題的解答可利用基因演算法來將之演化 出來 進化演算法的點子最早是由 1960 年 I Rechenberg 4 所提出的 它的 2 想法很快地讓其他研究人員所採用及研究發展 1975 年時 John Holland 5 和他的學生共同發展出基因演算法 2 基本描述 基因演算法的開端是在一個解集合 稱作 population 每個解稱作一個 individual 中選出特定的一些解 被選中的解將會拿到新的 population 中 使用 並且希望新的 population 的解會被原來的好 根據適合度 fitness 選出來的 individual 將構成子代 offspring 而週而復始地產生新的 population 直到有最合適的結果被產生出 3 基因演算法的控制參數 A A 母體大小 Population Size 母體是由染色體所構成的 而每個染 色體都分別代表著問題的一個解 一群染色體的演化過程 就相當於一 組暫時解同時在解的空間中做平行多維搜尋 B B 交配率 Crossover Rate 為母體中的需要進行交配操作的染色體比 率 C C 突變率 Mutation Rate 突變率有兩種意義 一種是代表染色體上的 基因發生突變的機率 且各個基因發生突變與否 其機率均為獨立的 或是族群中發生突變的染色體比率 D D 適應度函數 Fitness function 透過適應度函數的修正 使得基因演 算法能應用在各種不同的問題上 染色體越佳 其適應值就越高 且在 演化過程中就越容易存活 4 基本基因演算法 basic GA 概述 A A 起頭 隨機產生擁有 n 個 individual 的 population 3 X1 X2 X3 X4 Xn B B fitness 計算 population 中每個 individual 的 fitness 值 f Xn C C 新的 population Selection Crossover Mutation Reproduction D D 循環 回到第 B 步 1 1 2 基因演算法之特性 1 1 2 基因演算法之特性 基因演算法在求解最佳化問題上往往要比傳統最佳化方法具強健性 10 而其有以下特點 一 基因演算法會對其參數進行編碼 利用所編碼的亂數組合進行演化機制 並非直接利用參數本身求解 由於此演化機制的特性使得基因演算法能更 有效率地搜尋全域最佳解 二 基因演算法利用整個群體 population 中的解來搜尋 而非傳統演算法由 單一起始點搜尋 在群體 population 搜尋的優點是可以避免落入局部最 佳解 local optimial solution 的情形 三 基因演算法具有與其它最佳化 optimize 方法結合的彈性 可以針對特定 的問題提供更有效率的求解方式 1 1 3 基因演算法運用領域 1 1 3 基因演算法運用領域 基因演算法常用在人工智慧及數值分析的領域 諸如資料探勘 23 電腦遊戲策略演化 24 最佳控制 25 工作排程問題 26 模糊邏輯系 統 27 而本論文之領域屬於電腦遊戲策略演化中的五子棋決策演化 4 1 1 4 Genetic Programming 1 1 4 Genetic Programming 1992年時John Koza 3 利用基因演算法設計了一套程式來解決了一些問 題 他稱此程式為 Genetic Programming 3 9 他使用了 LISP 語言來 撰寫他的程式 而本論文是採用 C 語言來實現基因演算法 1 1 5 基因演算法在本論文之運用 1 1 5 基因演算法在本論文之運用 電腦遊戲程式在人工智慧領域中 11 12 13 19 28 是有著許多研究 的 最早出現於 17 而最常見的遊戲策略搜尋演算法便是使用 linear evaluation function 方法來找出遊戲的策略 6 並將有名的 minimax 14 15 或 alpha beta 18 演算法賦予其中 而其決策的因子在於遊戲中不同狀態的偵 測及給予適當的對應 weights 藉由 weights 的大小來決定下一步的策略 20 在本論文中 著眼點於基因演算法在決策樹理論上的運用並加入了學習機 制 而選用範例為五子棋棋路決策的推導 利用基因演算法來演化出五子棋的棋 路 並且設定了兩種演化模型 第一種為吾人較早的想法 第二種為之後改良更 好的模型 並加入了學習功能 當然第二個方法為本論文的真正重點 我們都為 兩種模型設定一些 operators 開始演化時就以這些 operators 為元素 亂數組 成一個五子棋的棋法 當然亂數組成的棋法幾乎是白痴棋法 但經過數代演化後 便會脫胎換骨 產生出能與人類相抗衡的下棋步驟 本論文亦根據所提出的方法 實做出一套五子棋的演化系統 系統根據本論文的方法演化五子棋的策略 並有 遊戲介面可讓吾人與之對戰 測試其演化的效果 5 1 2 論文架構 1 2 論文架構 本論文在第二章設計了一個以 IF rule tree 為基礎的五子棋策略搜尋樹 並利用 minimax 法則 2 設計了一個預設五子棋策略的 AI 此 AI 是用來與 GA 對 打及學習的對象 而第三章則提出了以 SWITCH tree 的策略搜尋樹 此方法優於 第二章的方法 亦是本論文的重點 第四章則是簡述搜尋樹的簡化方法 第五章 為本論文主要方法 SWITCH tree 的策略搜尋樹 的實驗數據 最後一章 第六章 為結論 6 第二章 五子棋策略搜尋樹 一 第二章 五子棋策略搜尋樹 一 2 1 預設五子棋 AI 的基本演算結構 2 1 預設五子棋 AI 的基本演算結構 1 棋盤資料結構 首先為整個棋盤建立一張表格用以記錄棋子資訊 使用一個 size size 的二 維陣列 table size size size size 是五子棋棋盤的大小 陣列的每一個 元素對應棋盤上的一個交叉點 可用 0 表示空位 x 和 各代其中一 方的棋子 而這張表也是今後分析的基礎 2 評估棋型表 為 雙 方 各 建 立 一 張 棋 型 表 int computer size size 4 和 int player size size 4 用來存放棋型資料 3 維陣列中的前 2 維表 示棋盤上各點的位置 第 3 維則是此點的狀態紀錄 其值為 0 5 的正整數 這 0 5 代表著什麼意義呢 舉例來說 3 代表此點周圍有著 連續 3 己方子相連 的點 下了此點將會變活 4 用 2 代表 將會活三 的空點 如果末端有對 方的子阻擋則其值變為負值 依此類推 那第 3 維的 size 為何要選擇是 4 呢 是因為棋盤上的每一個點都可以與橫 直 左斜 右斜四個方向的棋子構成不同的棋型 所以一個點總共有 4 個記錄 例 0 表直 1 表橫 2 表左斜 3 表右斜 computer 4 6 0 2 computer 4 6 1 1 computer 4 6 2 2 computer 4 6 3 3 以上即表示在座標 4 6 的點 在直方向有己方 2 子相連 橫方向有 1 己方子 左斜方向有己方 3 子相連 右斜方向有己方 2 子相連 但其末端有對 7 方子阻擋 D 運用 由這兩種資料結構可以判斷出複合棋型 例如 如果同一點上有 2 個 2 就是下次點將雙三 有一個 2 和一個 3 就是將死四活三 負值表示末端有 對方的子阻擋 3 維陣列構成了五子棋的基本資料骨架 之後再加入一些輔評估的 weight 變數便可以處裡各種棋盤的局勢 舉例 棋盤上 點的狀態 weight 1 子 10 2 連子 15 3 連子 40 4 連子 20000 1 阻連子 5 2 阻連子 10 3 阻連子 35 4 阻連子 20000 Integer weight size size initial all value in array to 0 for I 0 to size 1 for J 0 to size 1 8 for K 0 to 4 switch computer I J K case 1 weight I J 10 case 2 weight I J 15 case 3 weight I J 40 case 4 weight I J 20000 case 1 weight I J 5 case 2 weight I J 10 case 3 weight I J 35 case 4 weight I J 20000 以上為五子棋基本評估 weight 的演算法 9 2 2 IF rule Tree 的五子棋基因演算法 2 2 IF rule Tree 的五子棋基因演算法 利用 IF rule tree 的決策樹 7 來搜尋棋盤上所出現棋型的 weight 基本 上依照 2 1 節的棋型判斷法 將一空點的四周分為橫 直 左斜 右斜四個方向 每個方向的狀況都會個別給一個 weight 最後四方向的 weight 相加為最後此點 的 weight 2 2 1 operators 的設計 2 2 1 operators 的設計 在五子棋的例子中 選用了以下 gene operator Function Set IF ELSE IF OR AND EQUAL MORE THAN STATEMENT LIST Terminal Set SET WEIGHT L1 L2 L3 L4 L5 D1 D2 D3 D4 D5 CONST RANDOM NUM 基因演算法中演化決策樹為 random 產生的 但此 random 是要有規律的 random 而非胡亂的產生 如圖 2 21 如果要設計這棵 tree 的驅動函式 是要如何設計呢 答案是不 可能的 因為這 tree 沒有 grammar 沒有規律 就算驅動出來也是無義意 所 L1 SET WEIGHTOR IF ELSEL2 L2 L1 MORE THANAND L1D3 OR D1L3SET WEIGHT 圖 2 21 無規則的演化樹 10 以 tree 的創造是要有一套規則的 依照此規則產生的樹才有辦法被驅動 由圖 2 22 此 tree 是有規則的 是能被驅動的 轉成語句型式就變成 IF L2 1 意義是如果此點之死 2 數目大於 1 call SET WEIGHT IF ELSE MORE THAN L2 1 SET WEIGHT IF ELSE AND L3 EQUAL 2 EQUAL D4 1 SET WEIGHTIF ELSE then else else then 圖 2 22 有規則的演化樹 11 ELSE IF L3 2 AND D4 1 意義是如果此點活 3 數目為 2 死 4 數目為 1 call SET WEIGHT ELSE 2 2 2 搜尋樹的建立規則2 2 2 搜尋樹的建立規則 Definition of Grammar of tree Definition of Grammar of tree selection statement IF conditional expression statement IF conditional expression statement ELSE statement statement selection statement compound statement compound statement 12 call function selection statement conditional expression logical expression relational expression logical expression logical and expression logical or expression logical and expression logical expression logical expression AND OP relational expression logical or expression logical expression logical expression OR OP relational expression relational expression more than expression less than expression equality expression more than expression call function MORE THAN OP variable 13 equality expression call function EQUAL OP variable variable constant unsigned integer range 1 5 constant unsigned integer range 1 2000 call function SET WEIGHT L1 L2 L3 L4 L5 D1 D2 D3 D4 D5 以上為五子棋演算法決策樹的文法規則 所以創建一棵樹時便必須依照 此規則產生 但要如何遵照規則呢 首先在定義 operator 時就要規劃及定義 其所能接的參數 function 的呼叫是要給其傳入參數 傳入的參數個數是 以 function 定義為準 在五子棋演化中其 Function Set 中的各 function 14 operator 當然也有參數定義 而 terminal node 是沒有參數傳入的 以下 為其定義 Definition of Function operator Definition of Function operator IF x y if x than y IF ELSE x y z if x than y or z AND x y if x 0 return 0 else return y OR x y if x 1 return 1 else return y MORE THEN x y if x y return 1 else return 0 EQUAL x y if x y STATEMENT LIST x y x is a action y is a selection statement Definition of Terminal node Definition of Terminal node SET WEIGHT 對棋盤上的一點設定 weight L1 探測棋盤上一點的四個方向 存在 1 個己方棋子的數目 L2 探測棋盤上一點的四個方向 存在 2 相鄰己方棋子的數目 L3 探測棋盤上一點的四個方向 存在 3 相鄰己方棋子的數目 L4 探測棋盤上一點的四個方向 存在 4 相鄰己方棋子的數目 L5 探測棋盤上一點的四個方向 存在 5 相鄰己方棋子的數目 D1 探測棋盤上一點的四個方向 存在 1 相鄰己方棋子的數目 末端有 對方的子阻擋 D2 探測棋盤上一點的四個方向 存在 2 相鄰己方棋子的數目 末端有 對方的子阻擋 D3 探測棋盤上一點的四個方向 存在 3 相鄰己方棋子的數目 末端有 15 對方的子阻擋 D4 探測棋盤上一點的四個方向 存在 4 相鄰己方棋子的數目 末端有 對方的子阻擋 D5 探測棋盤上一點的四個方向 存在 5 相鄰己方棋子的數目 末端有 對方的子阻擋 CONST 0 1 2 3 4 RANDOM NUM integer 1 2000 Definition of Functional argument Definition of Functional argument 表 2 2 IF x y x MORE THAN EQUAL AND OR y SET WEIGHT STATEMENT LIST IF ELSE x y z x MORE THAN EQUAL AND OR y SET WEIGHT STATEMENT LIST y IF IF ELSE AND x y x MORE THEN EQUAL AND OR y MORE THEN EQUAL AND OR OR x y x MORE THEN EQUAL AND OR y MORE THEN EQUAL AND OR EQUAL x y x L1 L2 L3 L4 L5 D1 D2 D3 D4 D5 y CONST MORE THEN x y x L1 L2 L3 L4 L5 D1 D2 D3 D4 D5 y CONST 16 STATEMENT LIST x y x SET WEIGHT y IF IF ELSE 由表 2 2 中的 IF ELSE x y 來說 其能接的第一個子結點 condition 為 AND OR NOT EQUAL MORE THAN 第 2 個結點 than 為 action function 如 SET WEIGHT 17 2 3 多目的之 OPERATOR 2 3 多目的之 OPERATOR 在一般基因演算法應用例子中 如機器人路徑演化 21 22 其在一連 串的 if 判斷後只呼叫一次 action function 後便結束了 但此處五子棋的評 估 weight 是由多種複合情況 點的四個方向 所累加出來的 因此在對棋盤評 分時 action function 不能只執行一次就讓其結束 故創造了一個新的 operator STATEMENT LIST 其語句的意義如下 STATEMENT LIST SET WEIGHT IF condtional 簡單的看出 它是讓 action function 執行後再接一個 IF 其功能就像 if else if 的敘述句 18 2 3 1 IF rule tree 演化方式 Selection 2 3 1 IF rule tree 演化方式 Selection Selection 使用 Standard Method 各 individual 依照其 fitness 大小排列 由 fitness 大的排到小的 Crossover Crossover Crossover 使用本論文所提出的方法 在 2 3 節有討論 在五子棋的演化當中可分為兩個重點 一個是 rule 的演化 另一個是 weight 的演化 主要要先讓 rule 的骨幹演化出主體 才再對 weight 值演化 調整 19 演算法流程 演算法流程 Create Population Simulate the Population Assign suitable fitness to each individual Selection CrossoverMutation Reproduce Reach the goal Yes No Create next generational population Exit Program 圖 2 31 演化流程圖 20 2 3 2 主要結構 2 3 2 主要結構 全部程式以 c 語言撰寫完成 而 tree 的架構使用了 parse tree 的形式 Gene node 的結構定義 class Gene int symbolic int type function or terminal Gene child 只有 function node 才有 child Gene next child next 便是其第 2 個子結點 第一代時要 random 產生的 rule tree 採用深先建樹法 以下是其產生的 演算法 GP GPGP GPGPGPGP Gene child next child next next child Population Population Tree of a GP one Gene 圖 2 32 Population 的結構圖 21 GenerateChild function node 呼叫此函式可替其產生對應的子結點 GenerateFunctionBody node 呼叫此函式可替其產生合適的屬性 GenerateChild Argnument num GenerateFunctionBody Argnument num If Argnument num 1 如果參數大於 1 繼續產依規則生子結點 thisNode next parent thisNode parent thisNode next GenerateChild Argnument num GenerateFunctionBody Argnument num getParentNodeGrammar 取得此 node 之父結點的文法規則 依照文法規則來選則該給予之適合的 operator 及其參數個數 if node can be a function or terminal node 50 的機率讓 Node 為 function node 或 terminal node if Node must be a function node Node RandomSelectFunctionFromParentFunctionSet 22 在父結點的文法集合中隨機選一個 function node 參考表 2 Node child parent thisNode parent Node child GenerateChild Node Argnument num 因為 function 有參數 子結點 故再呼叫 GenerateChild 用來產生子結點 else if Node must be a terminal node Node RandomSelectTerminalFromParentTerminalSet 在父結點的文法集合中隨機選一個 terminal node 參考表 2 所以首先靜態創造一個 IF or IF ELSE node 再呼叫 GenerateChild 即可動態亂數產生一棵樹 2 3 4 模擬驅動函式演算法2 3 4 模擬驅動函式演算法 當一棵樹被創造出來後就要有一套模擬驅動函式來驅動它 故定義了一套演算 法 以下為其演算法 Function node evolution Function node evolution 23 IF x y if x than y FUNCTION IF IF x y if x than y FUNCTION IF if EvalGene current gene s first child EvalGene current gene s second child IF ELSE x y z if x than y or z FUNCTION IF ELSE IF ELSE x y z if x than y or z FUNCTION IF ELSE if EvalGene current gene s first child EvalGene current gene s second child else EvalGene current gene s third child AND x y if x 0 return 0 else return y FUNCTION AND AND x y if x 0 return 0 else return y FUNCTION AND if EvalGene current gene s first child is false 24 return FALSE else return EvalGene current gene s second child OR x y if x 1 return 1 else return y FUNCTION OR OR x y if x 1 return 1 else return y FUNCTION OR if EvalGene current gene s first child return TRUE else return EvalGene current gene s second child MORE THEN x y if x y return 1 else return 0 FUNCTION MORE THEN MORE THEN x y if x y return 1 else return 0 FUNCTION MORE THEN if EvalGene current gene s first child EvalGene current gene s second child 25 return TRUE else return FALSE EQUAL x y if x y FUNCTION EQUAL EQUAL x y if x y FUNCTION EQUAL if EvalGene current gene s first child EvalGene current gene s second child return true else return false STATEMENT LIST x y x is a action y is a selection statement FUNCTION STATEMENT LIST STATEMENT LIST x y x is a action y is a selection statement FUNCTION STATEMENT LIST EvalGene current gene s first child EvalGene current gene s second child Terminal mode evolution Terminal mode evolution 26 SET WEIGHT SET WEIGHT sum of weight current gene s weight L1 L2 L3 L4 L5 D1 D2 D3 D4 D5 L1 L2 L3 L4 L5 D1 D2 D3 D4 D5 傳回相對應的狀態 return INTEGER value CONST CONST return current node s value 驅動引擎演算法 驅動引擎演算法 INTEGER weight 0 初設 weight 為 0 Evaluate 此 function 可得到棋盤上一點的 weight EvalGene NODE 傳入一個 node Return weight DEIFNE RETURN YTPE AS A INREGER RETURN YTPE EvalGene NODE if NODE is a function node 27 switch NODE s symbolic case IF FUNCTION IF s statement case IF ELSE FUNCTION IF ELSE s statement case AND FUNCTION AND s statement case OR FUNCTION OR s statement case STATEMENT LIST FUNCTION STATEMENT LIST s statement else NODE is a terminal node case SET WEIGHT SET WEIGHT s statement case CONST CONST s statement case L1 L1 s statement case D5 D5 s statement 2 4 Crossover 膨大化 2 4 Crossover 膨大化 每一代的演化過程中都會經過 crossover 的步驟 crossover 可能會造成 tree 變得越來越大 樹大可能代表著演化的 rule 越趨齊全 但也可能是虛大 即存在著許多無意義的 subtree expression 其數量過大造成使用過多的記憶 體用量和執行效率減低 28 若各個體中存在許多無意義的 subtree expression 那麼經過 crossover 後 它的數量可能就會更多 這樣會造成演化的效率越來越差 甚至比前代的還 要差 所以本論文改變了傳統 crossover 方法 而提出了一個特別的 crossover 方法 這方法有點遺傳學中的優生學之精神 以下為所提出的幾個要點 要如何避免演化後的 expression 數量過大造成使用過多的記憶體用量和 執行效率減低呢 以下有兩種方法 1 限制 phase tree 的 depth 2 偵測無用或多餘的 sub expression 第一個方法為限制每一 GP tree 的 depth 如此絕對可以避免 crossover 後 tree 越來越大 不過此法會大大影響演化的多元性而影響成果 故不考慮使 用這一種方法 第二個方法是將無用的 sub expression 從 population 中去除 或是用 crossover 及 mutation 方法替換之 在這裡我們選用了第二個方法 不過如此做真的有比較好嗎 當然還是要有一些 規則限制 下節便說明了一些細節 2 4 1 評估 subtree 的使用情況 2 4 1 評估 subtree 的使用情況 為了要了解 GP 中各 subtree 的使用情況 我們在每個 subtree 中加入一個 記數變數 變數值初設為 0 每當各 subtree 若被走到時 記數值則加 1 當一 代的模擬結束後探查各個記數器的值 若為 0 則表示其對應的 subtree 未被走到 過 但在五子棋的例子當中 未被走到的 subtree 未必完全沒有用 當對戰的總 29 棋步不多時 有些 subtree 的判斷式可能就用不到 例如 D4 4 的出現情況相 當少 但又不是不能有這種棋型出現 我們記錄各 subtree 的使用情況是為了要 快速演化出五子棋的基本決策骨幹 記錄的目的是為了下一小節所提到的基因函 式庫之前置步驟 2 4 2 Table 記錄法 2 4 2 Table 記錄法 這個方法是將在演化過程中有被走到過的 subtree 記錄下來 如何才算被走 過呢 一個 subtree 是一個 IF expression 或 IF ELSE expression 其包含了 condition than else 而一個有用的 subtree 是能讓其 condition 判斷為 true 然後執行 then 中的 action function 換句話說 這個 subtree 的 condition expression 有判斷出當時棋局的一種棋型 它是有用的判斷式 故 table 中我們只記錄其 action function 有被執行過的 subtree 以下為 table 表的主要說明 Table 表例 Sub expression Max fitness frequency of Used rank Pointer1 50 12 Pointer2 16 12 Pointer3 20 8 Pointer4 77 1 30 第一欄 Sub expression 放的是指向一 sub expression 的 pointer 第二欄 為一 GP 存在此 su