Game Values, Temperature, and Enumeration of Placement Games

放置游戏的游戏值、温度和枚举

• 批准号: RGPIN-2022-04273
• 负责人: Huntemann, Svenja
• 金额: $ 1.38万
• 依托单位: Concordia University of Edmonton
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2022
• 资助国家: 加拿大
• 起止时间: 2022-01-01 至 2023-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=758312
• 关键词: Game; Values; Temperature; Enumeration; Placement

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.

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