Game Values, Temperature, and Enumeration of Placement Games

点击翻译按钮获取中文摘要

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.