基因演算法應用於資訊不完全之對局

Application of Genetic Algorithm in Imperfect Information Game

陳福村(Fu-Chung Chen)

指導教授 ： 王永鐘

國立臺北科技大學/電資學院/電機工程系研究所/碩士(2009年)

摘要

使用傳統電腦對局理論所設計之人工智慧，需要較多的人為經驗做為電腦運算之依據，而因此造成電腦棋力之高低隨著程式設計者本身棋力之高低而有不同。本論文提出利用電腦演化計算(Evolutionary Computation)的相關技術，使電腦能在錯誤中自我學習，在最少的人為操作因素下演化棋力。一般對局遊戲可區分為完全資訊(Perfect Information)，如象棋、西洋棋，以及不完全資訊(Imperfect Information)，如暗棋，橋牌。本篇論文著重於不完全資訊的對局遊戲，由於局面充滿了未知資訊，本篇論文提出利用模糊演算法(Fuzzy Algorithm)幫助電腦估計未知情況，以減少誤判的可能性，並精確的計算出最佳策略。

關鍵字

基因演算法 ； 人工智慧 ； 電腦對局 ； 暗棋

並列摘要

Algorithms derived out of the traditional game theory often rely heavily upon human experiences as computational aid; hence the designer's prowess at the game determines the performance of those algorithms. In this paper, we present a technique based on evolutionary computation, which allows the computer to learn from mistakes, henceforth evolves with minimum human interference.
In game theory, a game can be classified into two types: perfect information, like chess, Chinese chess; or imperfect information, such as bridge, dark chess. This paper focuses on game of imperfect information, and introduces a fuzzy algorithm to help the computer find an optimal strategy among all possible solutions.

並列關鍵字

Genetic Algorithm ； Artificial Intelligence ； Computer Game ； Dark Chess

參考文獻

[14] 莊秉文，五子棋棋略的演化學習法，碩士論文，中原大學資訊工程學系，桃園，2003。

[16] 陳俊傑，具備學習能力的6x6 Othello程式之設計與製作，碩士論文，長榮大學資訊管理學系碩士班，台南，2007。

[1] J. V. Neumann and O. Morgenstern, Theory of Games and Economic Behavior, USA:Princeton University Press, 1953, pp.85-91.

[2] C. E. Shannon, "Programming a Computer for Playing Chess," Philosophy Magazine, vol.41, No.314, 1950, pp. 256-275.

[3] D. E. Knuth and R. W. Moore, "An Analysis of Alpha-Beta Pruning," Artificial Intelligence, vol. 6, 1975, pp. 293-326.