Game Values, Temperature, and Enumeration of Placement Games

组合游戏是像国际象棋或围棋那样的双人信息游戏。组合博弈论研究的是谁赢以及如何赢。这里用到的两个关键概念是博弈值和博弈温度。博弈值表示一名玩家相对于另一名玩家的优势有多大，博弈温度大致告诉我们采取某一步棋有多紧急，在游戏程序中用于寻找好棋。在许多组合游戏中，棋子被放置在棋盘上，之后不移动或移除它们，这些被称为放置游戏。我们将着眼于植入游戏的一个子类，即强植入游戏。这些游戏具有其他游戏所不具备的额外属性，例如最近证明的与其他数学对象的联系以及它们的游戏树结构，这些都可以用于它们的分析。之前已经研究过几个sp游戏，利用它们的结构，但是，对于大多数来说，没有获胜策略是已知的。利用sp博弈的属性（允许使用额外的分析工具），我们将研究组合博弈理论中的三个重要问题：(1)sp博弈中可能出现什么博弈值？(2) sp游戏的最高温度是多少？有多少个职位？对这三个问题的研究将以多种方式影响组合博弈论。一般来说，限制强布局游戏的游戏价值将改善分析这类游戏的算法，使其更容易确定获胜策略。游戏价值和温度有着内在的联系，所以前者的结果也可以为后者提供约束技术。根据游戏本身或棋盘的属性限制可能的最高温度将改进游戏程序使用的算法，从而减少找到好棋所需的计算时间。最后，列举游戏中的位置数量有助于确定分析这些游戏的计算成本，并告知在特定游戏中假设非交替玩法是否在计算上更有效。应用这三个领域的研究结果将导致电脑游戏程序成为更强大的玩家，因此这些程序甚至可能引入以前没有考虑过的新策略。

Combinatorial games are 2-player, perfect information games like Chess or Go. Combinatorial game theory is the study of who wins these games and how. Two key concepts used are game values, which indicate how large an advantage one player has over the other, and game temperature, which roughly tells us how urgent it is to make a certain move and is used in game playing programs to find good moves. In many combinatorial games pieces are placed on a board without moving or removing them later, and these are called placement games. We will be looking at a subclass of placement games known as strong placement (SP-) games. These games have additional properties that other games do not have, such as recently proven connections to other mathematical objects and the structure of their game tree, which can be used in their analysis. Several SP-games have been studied previously, taking advantage of their structure, but, for most, no winning strategy is known. Using the properties of SP-games, which allow for additional analysis tools, we will be investigating three questions of importance in combinatorial game theory: (1) What game values can possibly appear in SP-games? (2) What is the maximum possible temperature of an SP-game? (3) How many positions are there? Work on these three questions will impact combinatorial game theory in a variety of ways. Restricting game values for strong placement games in general will lead to improved algorithms for the analysis of such games, making it easier to determine a winning strategy. Game values and temperatures are intrinsically linked, so results for the former can also inform techniques for bounding the latter. Restricting the possible maximum temperature based on properties of the game itself or the game board will improve the algorithms used by game playing programs, and thus decrease the computational time needed to find good moves. Finally, enumerating the number of positions in a game helps to determine the computational cost of analyzing these games and will inform whether it is computationally more efficient to assume non-alternating play for a specific game. Applying results from all three areas of interest will lead to computer game playing programs becoming stronger players, and thus these programs may even introduce new strategies not previously considered.