五子棋棋略的演化學習法

Evolutionary Learning for Playing a Gobang Game

莊秉文(Bing-Wen Chuang)

指導教授 ： 阮議聰

中原大學/工學院/資訊工程研究所/碩士(2003年)

https://doi.org/10.6840/cycu200300220

摘要

本篇論文將探討Genetic Algorithm(GA)基因演算法又稱遺傳演算法，運用在推導五子棋的下棋策略，利用基因演算法之多維空間搜尋法,來找出合適的五子棋棋略，讓原本是白紙般的下棋策略，透過演化的模擬，快速地學習到致勝的棋法。

本論文的目的在於設計一個演化環境模式，重點於基因演算法在決策樹理論上的運用並加入了學習機制，並讓基因演算法能有效率及快速地演化到吾人所需求的結果，論文中提出了兩種演化模式，以不同的演化模式來找出相同的目的與結果，由於不同模型的設計，使得兩者的演化效率也有程度上的差異，第一種模式為我較早的想法，第二種為之後改良增強的模式，其中以第二種方法為本論文研究的重點，其具有著學習能力的演化模式，在當中並提出了從錯誤中學習的賞罰系統，和提高基因演算法之效率的基因函式庫，而此種設計模型可讓五子棋的演化學習法能從錯誤中成長，並且在每一世代演化都要比前一世代進步，以希望減少其演化空轉的可能性，本論文亦根據所提出的方法，實做出一套五子棋的演化系統,系統根據本論文所提出的方法來演化五子棋的策略，且有遊戲介面可讓吾人與之對戰，測試其演化的效果，論文的最後附上實驗章節,並對本論文的方法做驗證及測試。

關鍵字

基因演算法 ； 五子棋 ； 人工智慧

並列摘要

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.

並列關鍵字

Genetic Algorithms ； Evolutionary Learning ； Gobang Game

參考文獻

[2] B.W.Ballard，”The *-minimax search procedure for trees containing chance nodes，”Artificial Intelligence，Vol.20，1983，pp.346-367

[3] John R.Koza. Genetic Programming: On the Programming of Computers by Meansof Natural Selection. MIT Press，1992

[5] J.H.Holland，Adaptation in Natural and Artificial Systems.Ann Arbor，MI:Univ. of Michigan Press，1975

[6] Chuen-Tsai，Ying-Hong Liao，Jing-Yi Lu，Fu-May Zheng，”Genetic Algorithm Learning in Game Playing with Multiple Coaches” Evolutionary Computation， 1994，P.239 ，CH2，vol.1

[8] Tackett, W.A.; “Mining the genetic program”, Expert , IEEE, Volume: 10 Issue: 3 , June 1995 Page(s): 28 -38