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

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

***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 win–loss 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.