應用組合對局知識解決遊戲及改良搜尋效能

Abstract

本篇論文，主要是應用組合對局知識解決遊戲及改良搜尋效能。組合對局理論已經成為許多益智遊戲分析的基本數學模型，其利用數學代數的特性來降低問題的複雜度。本論文主要研究三種組合對局遊戲，包括三角殺棋(Triangular Nim)、XT Domineering及NoGo。 首先，三角殺棋是一種Nim的變形，是流行台灣及中國的二人遊戲。本論文使用Retrograde方法，全解九層三角殺棋盤面，並運用旋轉及對稱方法，降低記憶空間需求達5.72倍，並增進運算速度達4.62倍。 第二、本論文介紹新的組合對局遊戲XT Domineering及其數學分析，XT Domineering其變化來自於Domineering。變化後的規則，在遊戲中所有盤面皆為微數字(Infinitesimal)，計算得出所有3×3盤面的遊戲值(Game values)，並得出每一盤面的遊戲值為8種基本微數字的線性組合，利用一個簡單代數和的式子，即可以迅速算出雙方勝敗，以取代搜尋全部遊戲樹(Game tree)。 第三、本論文分析2011年BIRS組合對局會議提出的一種新的組合對局遊戲NoGo，計算其許多4×4 NoGo盤面的遊戲值，發現其最高溫度（Temperature）為2，並在研究中推導出一些基本定理，以幫助我們瞭解NoGo遊戲特性。

In this thesis, we study to solve games and improve search performances with embedded combinatorial game knowledge. Combinatorial game theory (CGT) has become the common fundamental mathematical model for the analysis of many intelligent games. CGT uses algebra characteristics to reduce the complexity of many intelligent games. For this study, we investigate three combinatorial games, including Triangular Nim, XT Domineering and NoGo. First, Triangular Nim, one variant of the game Nim, is a common two-player game in Taiwan and China. Using a retrograde method, we strongly solve nine layer Triangular Nim. In our design, improved by removing some rotated and mirrored positions, the program reduces the memory by a factor of 5.72 and the computation time by a factor of 4.62. Secondly, we introduce a new combinatorial game, named XT Domineering, together with its mathematical analysis. XT Domineering is modified from the Domineering game with the game value of each position becoming an infinitesimal. We calculate the game values of all 3×3 positions and shows that each 3×3 position’s game value is a linear combination of 8 elementary infinitesimals. A simple rule is presented to determine the optimal outcome of any sum of these positions, instead of searching the whole game trees. Thirdly, NoGo is a game introduced by the organizers of the BIRS workshop on Combinatorial Game Theory 2011 for being a completely new combinatorial game. We calculate the game values of many 4×4 NoGo positions and find the maximum of temperature is 2 among them. We also present some propositions to help us understand the characteristics of NoGo game.