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
• 财政年份: 2020
• 资助国家: 加拿大
• 起止时间: 2020-01-01 至 2021-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=711144
• 关键词: 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年以来，这个代数框架一直被用来发展一种完整的正常游戏理论，即一场游戏的胜利者是最后一步的玩家。 这项拟议研究的主要目标是提出以下替代正常游戏的理论，重点是第一种。 输球：如果我们宣布赢家是没有拿到最后一步棋的玩家，会怎么样？这种以输取胜的模式被称为悲惨玩法，它的悲惨程度令人费解。正常游戏的数学结构在这里分崩离析，因此痛苦分析在20世纪大多被忽视。2005年，有了一个突破：研究人员引入了一种弱化的平等关系，即两个游戏位置在一个位置子集内可以等价(例如只有国际象棋位置)，即使它们在总体上不相等。等价性从正常的游戏中重建了一些结构，已经取得了很大的进展；但新的见解提出了与它们回答一样多的问题，组合博弈的一般理论正在等待这些开放问题的解决方案。 得分：许多著名的比赛不仅以输球告终，而且还以每位球员的“得分”告终。对于如何最好地对这类游戏进行数学建模，目前还没有达成共识。最近的一种方法显示出了希望，但要确定标准游戏属性如何应用于得分游戏，还有很多工作要做。 图优化是在图(即具有各种连接的节点的集合)上找到问题的“最佳”解决方案的过程。建议的研究包括图论作为辅助研究领域，并将研究以下优化问题。 打包：一个城市如何为尽可能多的手机发射塔选择位置，而不是在任何一个社区都有太多的手机发射塔？建议的研究将开发算法来解决这种顶点布局优化以及类似的问题。 行走：你如何优化一名或多名警卫在博物馆周围行走的巡逻？我们如何才能使用尽可能少的警卫，并限制一个房间可以无人看守的时间？我们如何才能最大限度地减少无人看守的时间，而警卫的数量是固定的？这项拟议的研究将考虑最小支配行走问题的变体，这些问题在视频游戏的人工智能等方面有应用。