兩個原創卵石遊戲的研究

組合遊戲是一類沒有隨機因素及有勝負結果的遊戲，且其進行過程中所有玩家皆有公開完整的信息。根據玩家數量的不同，這類遊戲可以分為單人遊戲、兩人遊戲、或多人遊戲。在本論文中，我們研究了兩個自創的、在有向圖的棋盤上移動「卵石」的組合遊戲。對於第一個遊戲，它是從 Kontsevich (1981) 的卵石遊戲中推廣而來的單人遊戲，其中我們將遊戲擴展為在任何有向圖的棋盤上進行，而不只是在二維棋盤上進行。我們發現了一個有趣的對偶定理：若兩個遊戲所設定的初始盤面是「對偶的」，則此兩個遊戲同時可解或同時不可解。對於第二個遊戲，它是稱為「 Drop-or-Hop」的兩人游戲。此遊戲能歸類為「在一般勝利條件下的無偏博弈遊戲」（normal impartial game）。在本論文中，我們介紹如何計算此遊戲的任何盤面是否為必勝盤面。此外，我們亦討論如何計算任何盤面的「尼姆值」(nim value)，使得我們能夠知道多個獨立的 normal impartial game 一起玩時的必勝策略。此外，我們亦研究了此遊戲的幾種變形，例如可以在更一般化的棋盤上進行，或稍為改變規則而成的「Breed-or-Hop」遊戲。

關鍵字

棋盤；尼姆遊戲

並列摘要

Combinatorial games are games with perfect information and no chance moves, and with a win-or-lose outcome. Depending on the number of players, these games can be classified into solitaire (single-player), two-player, or multiplayer games. In this thesis, we study two self-invented variants of the pebble game, where the latter is a type of combinatorial games that is played by moving ``pebbles'' along a directed graph. For the first game, it is a solitaire game generalized from the pebble game of Kontsevich (1981), where instead of playing the game on a two-dimensional chessboard, we extend the game to be played on any directed graph. We show an interesting duality theorem, such that if two initial configurations c and c' of the game are a ``dual", then the game with configuration c is solvable if and only if the game with configuration c' is solvable. For the second game, it is a novel two-player normal impartial game called ``Drop-or-Hop". We show how to determine if a certain configuration of the game is a winning position or not. Moreover, we show how to compute the ``nim value" of any configuration, which allows us to determine the winning position when the game is played in parallel with other normal impartial games. Furthermore, we study several variants of the game, say when it is played on more general kinds of chessboards, or when the rules are slightly changed so that the game becomes another game called ``Breed-or-Hop".