论文标题
二手影响实例
Bipartite instances of INFLUENCE
论文作者
论文摘要
游戏影响力是一款得分的组合游戏，该游戏已于2020年由Duchene等人引入。它是米尔诺（Milnor）得分游戏宇宙的良好代表，即球员错过轮到他从来没有有趣的游戏。首先通过转移非评分组合游戏的均值和温度概念和温度来给出新的一般结果。然后将这些结果应用于影响，以完善阶段工会的情况。游戏得分的计算复杂性也得到了解决，并被证明是PSPACE完成的。我们最终通过对网格，超振管或圆环等结构的最佳分数给出明确的策略和界限时，将其关注一些特定的影响案例。
The game INFLUENCE is a scoring combinatorial game that has been introduced in 2020 by Duchene et al. It is a good representative of Milnor's universe of scoring games, i.e. games where it is never interesting for a player to miss his turn. New general results are first given for this universe, by transposing the notions of mean and temperature derived from non-scoring combinatorial games. Such results are then applied to INFLUENCE to refine the case of unions of segments. The computational complexity of the score of the game is also solved and proved to be PSPACE-complete. We finally focus on some specific cases of INFLUENCE when the graph is bipartite, by giving explicit strategies and bounds on the optimal score on structures like grids, hypercubes or torus.
