Combinatorial Games and Graph Optimization: Losing and Scoring, Packing and Walking

组合博弈和图优化：输球和得分、打包和行走

• 批准号: RGPIN-2017-04607
• 负责人: Milley, Rebecca
• 金额: $ 0.94万
• 依托单位: Memorial University of Newfoundland
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2022
• 资助国家: 加拿大
• 起止时间: 2022-01-01 至 2023-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=755180
• 关键词: Combinatorial; Games; Graph; Optimization; Losing

COMBINATORIAL GAMES have been played for over five thousand years. These are games like chess and checkers: two players, perfect formation, and no luck. It is a remarkable fact that these games, seemingly born of an innate human desire to play and invent, have a beautiful underlying system of abstract mathematics.We can add and subtract game positions, and we can say that two positions are “equal” (even if they appear to be different). By considering game positions abstractly, we can even meaningfully compare a position in chess to a position in checkers. Since 1900, this algebraic framework has been used to develop a complete theory for normal play, where the winner of a game is the player who gets the last move.The primary goal of the proposed research is to advance the theory of the following alternatives to normal play, with emphasis on the first.Losing: What if we declare that the winner is the player who does not get the last move? This “win-by-losing” mode is called misere play, and it is bafflingly miserable. The mathematical structure of normal play falls apart here, and thus misere analysis was mostly ignored in the 20th century. In 2005, there was a breakthrough: researchers introduced a weakened equality relation, whereby two game positions can be equivalent inside a subset of positions (such as only chess positions), even if they are not equal in general. Equivalence rebuilds some of the structure from normal play, and much progress has been made; but new insights have raised as many questions as they have answered, and a general theory of combinatorial games awaits the solutions to these open problems.Scoring: Many well-known games end not only with a winloss but also with a “score” for each player. There has not been a consensus on how to best model such games mathematically. A recent approach is showing promise, but there is much work to be done to determine how standard game properties apply to scoring games.GRAPH OPTIMIZATION is the process of finding the “best” solution to a problem on a graph (that is, a collection of nodes with various connections). The proposed research includes graph theory as a secondary research area, and will investigate the following optimization problems.Packing: How can a city choose locations for as many cell towers as possible, without having too many in any one neighbourhood? The proposed research will develop algorithms to solve this vertex packing optimization, and similar problems.Walking: How can you optimize the patrol of one or more guards walking around a museum? How can we use as few guards as possible, with restrictions on how long a room can go unguarded? How can we minimize unguarded time, with a fixed number of guards? The proposed research will consider variations of the minimum dominating walk problem, which have applications in things like artificial intelligence for video games.

组合游戏已经玩了五千多年。这些游戏就像国际象棋和跳棋：两个玩家，完美的阵型，没有运气。值得注意的是，这些游戏似乎源于人类与生俱来的游戏和发明欲望，它们有一个美丽的抽象数学基础系统，我们可以加减游戏位置，我们可以说两个位置是“相等的”（即使它们看起来不同）。通过抽象地考虑博弈位置，我们甚至可以有意义地将国际象棋中的位置与跳棋中的位置进行比较。自1900年以来，这个代数框架已经被用来发展一个完整的正常游戏理论，其中游戏的赢家是谁得到了最后一步的球员。拟议的研究的主要目标是推进以下替代正常游戏的理论，重点放在第一个。输：如果我们宣布赢家是谁没有得到最后一步的球员？这种“以输取胜”的模式被称为“悲惨游戏”，它令人费解地悲惨。正常游戏的数学结构福尔斯在这里分崩离析，因此在世纪，悲惨分析大多被忽视了。在2005年，有一个突破：研究人员引入了一个弱化的平等关系，即两个游戏位置可以在一个位置子集（例如只有国际象棋位置）内是相等的，即使它们一般不相等。等价性重建了一些正常游戏的结构，并取得了很大的进展;但新的见解提出了许多问题，因为他们已经回答了，和一般的组合游戏理论等待这些开放的问题的解决方案。评分：许多著名的游戏结束时不仅赢了输，但也有一个“得分”为每个球员。对于如何最好地用数学方法来模拟这种游戏，目前还没有达成共识。最近的一种方法显示出了希望，但要确定标准游戏属性如何应用于评分游戏还有很多工作要做。图优化是在图（即具有各种连接的节点的集合）上找到问题的“最佳”解决方案的过程。拟议的研究包括图论作为一个次要的研究领域，并将调查以下优化问题。包装：一个城市如何选择尽可能多的手机信号塔的位置，而不是在任何一个街区太多？拟议的研究将开发算法来解决这个顶点包装优化，和类似的问题。步行：你如何优化巡逻的一个或多个警卫步行在博物馆？我们如何才能使用尽可能少的警卫，限制多久一个房间可以去无人看守？我们如何在有固定数量的守卫的情况下，最小化无人守卫的时间？拟议的研究将考虑最小支配行走问题的变化，这些问题在视频游戏的人工智能等方面有应用。