- 學位論文
電腦對局知識取得與應用
Knowledge Abstraction and Its Applications in Computer Games
摘要
電腦對局是一個人工智慧的子領域，包含許多廣為人知的棋類遊戲，如西洋棋、象棋、圍棋等。一般來說，目前棋類程式所採用的演算法主要可分為兩大類，其一是搜尋演算法，窮舉對局樹中在有限深度內的所有節點，加以計算並找出最佳走法。另一類是蒙地卡羅演算法，以隨機抽樣的概念為主，以統計的方法找出目前盤面的最佳走法。電腦西洋棋目前棋力屬於特級大師等級；電腦象棋目前的棋力約在大師與特級大師之間；而電腦圍棋的棋力約在初段上下。 各種棋類都相當需要良好的演算法配合準確度高的專家知識，才能夠使棋力達到一定水準。目前棋類知識大多仍以傳統式人工輸入為主，不但曠日費時，而且各種棋類之間的知識無法通用，例如象棋與西洋棋雖然都有子力、位置等知識，但為了使棋力能有效提升，卻必須將這兩種棋分開討論。可見知識本身在不同的棋類皆有差異，但若能找到自動取得知識的方法，則可能套用到各種不同的棋類上。 一般棋類遊戲大致可以區分為開局、中局與殘局等三部分。本論文提出自動化知識建構系統的主要概念，對開局、中局、殘局等各階段分別提出不同的解決方案，以取得並應用各階段的知識。在開局方面，採用自動化知識建構法，可建立出有效而龐大的開局知識庫。在中局方面，我們提出兩種方法來取得知識：使用文字擷取方式取得大量含有評註盤面的知識、以及建立兵種知識庫自動推論系統等兩種方式，皆可自動獲取大量可靠的知識。在殘局方面，除了一般常用的以回溯分析法建立殘局知識庫以外，我們提出自動歸納殘局知識庫而得到殘局知識的方法。
並列摘要
There are many interesting games in the computer game area, such as Western chess, Chinese chess and Go. Chess and Chinese chess programs are currently developed by canonical game-tree searching algorithm, which computes all nodes within a limited depth in a game tree and finds the move of the highest score according to a certain evaluation function. Recently best Go programs are developed by Monte Carlo algorithms, which obtain a best move by performing a statistical strategy on a large number of random games. Today's computer chess programs are at the level of grandmasters; computer Chinese chess programs are almost at the level of masters and grandmasters; the playing strength of the current best Go programs are about 1 Dan. A computer game program with a good algorithm and reliable expert knowledge can achieve high playing strength. However, knowledge in many programs are designed manually, which is time consuming. Furthermore, knowledge in a game is too specific to be used in another game. For example, though it is popular to use table representation for the material and location knowledge in Chinese chess and Western chess, knowledge in the two games still needs to be discussed individually to effectively improve the playing strength of a program. Thus, knowledge is ad hoc in each game, but if we use automatic construction method to create knowledge, it can be applied to many other games. A game is generally divided into three phases: the opening game, the middle game and the endgame. In this dissertation, we propose a concept of using automatic systems to retrieve specific knowledge for the opening game, the middle game, and the endgame. In the opening game, we use an automatic knowledge system construction method to build a large opening knowledge base. In the middle game, we propose two methods to retrieve knowledge: 1) automatically parsing game records annotated by human masters to obtain large amount of position information, and 2) using an automatic constructing and inferencing system to generate a large knowledge base of material combinations. Both methods emphasize the utility of acquire massive reliable knowledge. In the endgame, when we already have endgame databases constructed by retrograde analysis, we can incorporate an automatic induction system to absorb endgame knowledge from the endgame databases.