臺灣博碩士論文加值系統

　　近年來，電腦下棋一直為人們所注意，但電腦要擁有較高的棋力，一般均從下棋知識，搜尋演算法和硬體的改良著手。由於下棋的知識非常依賴所下棋的種類，而硬體的速度則取決於電腦的進步，因此本論文著重於搜尋演算法的改進。由於傳統遊戲搜尋樹的演算法，每多加一層深度的搜尋時，所要使得用的的時間和空間都呈指數成長，因此在時間和空間的限制下，使得所能搜尋的層次不足，而造成棋力偏低。所以目前大部分研究硬體方面的加快，來解決這個問題。
　　近年來遺傳演算法廣被使用，其經常被用來尋求解決單一極大值或是極小值的問題。遺傳演算法的優點是能將解答，經過一代一代的演進，使得所求的解答可以在有限時間內逼近最佳解。但是傳統的遺傳演算法只能求出單一的極大解或是極小解，並無法求出極小極大的解答。
　　在本篇論文中我們針對遊戲搜尋樹，提出了數個遺傳演算法，分別解決了一人遊戲樹、兩人遊戲樹和多人遊戲樹的問題，目的是希望能解決傳統無法深層搜尋的缺點，和遺傳演算法求極小極大解的問題。在一人遊戲樹方面，我們提出了遺傳遊戲搜尋樹，利用特殊的編碼原則，解決了一人遊戲樹的問題。在兩人遊戲樹方面，我們提出了三個演算法，包括了直接選擇遺傳演算法、極小極大遺傳演算法和保留樹遺傳演算法。其中以保留樹遺傳演算法的的效果最佳，利用保留樹所評估的遺傳評估值，可找到兩人遊戲樹的逼近最佳解。在多人遊戲樹方面，我們擴展兩遊戲樹中最佳的保留樹遺傳演算法至極大N演算法，來求出多人遊戲樹的解答。
　　最後我們作了一些實驗及分析，證實了所提出的演算法確實在限定時間內可增加搜尋準確度。因此我們所提的方法能夠實際應用並用增進電腦遊戲或是電腦下棋上的人工智慧。

　　The computer chess game has become increasingly important to artificial intelligence researchers on showing the intelligence of machines. There are usually factors in improving the capabilities of a computer chess system-chess domain knowledge, search algorithm, and hardware used. The contents of chess domain knowledge depend on the king of chess played, and the speed of the hardware depends on the technical advance of computers. For traditional game search algorithms, the time spent and the space needed grow exponentially along with the search depth. The search is then usually not deep enough to have a good play due to the time and space constraints.
　　In this thesis. we attempt to apply genetic algorithms to game-tree search for raising the performance. Genetic algorithms are more and more used in recent years. They are mainly used to find solutions to a maximum or a minimum problem. They are based on Darwin's principle of the fittest surrival, and find an optimal of a nearly optimal solution in limited time. Traditional genetic algorithms cannot, however, solve minimax problems.
　　Three kinds of genetic game-tree algorithms are proposed, respectively for one-player, two-player, and multiple-player game trees. A genetic one-player game tree algorithm is first proposed, which uses a special encoding scheme to improve the search performance. Three genetic two-player scheme to improve the search performance. Three genetic two-player game tree algorithms, including the direct-choice, the minimax, and the tree-reservation approaches are then proposed. Among them, the tree-reservation genetic algorithm is the best. It uses the genetic evaluation values kept in the reservation tree to generate the offspring. After generations the best solution will be output as the next step to play. The tree-reservation genetic algorithm is then extended to solve the multiple-player game tree search problem. A genetic max-n algorithm is then proposed.
　　At last, experiments and analysis are made to show the effect of our proposed algorithms. Results show that the accuracy using our algorithms can be raised in a limited amount of time. Our proposed algorithms are thus practical and can be applied to real computer games.