Combinatorial Game Theory
Combinatorial Game Theory
复制标题
组合博弈论
DOI：
10.1515/9783110755411
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Jan. 9–Jan
中科院分区：
文献类型：
--
作者：
Jan. 9–Jan
主讲人：Elwyn Berlekamp（加州大学伯克利分校）标题：关于最新优惠券围棋锦标赛的报告摘要：2010年底，韩国举行了优惠券围棋锦标赛。这次演讲将概述比赛和结果。主讲人：凯尔伯克（维滕贝格大学）标题：邻居Nim：一个PSPACE完全的NimG变体摘要：邻居Nim是Nim的一个版本，其中堆嵌入到图的顶点上。一个回合包括穿越一条边（与最后一次进攻相邻），然后从结果顶点上移除棍子。即使堆大小很小，游戏也是PSPACE困难的。主讲人：特里斯坦·卡泽纳夫（巴黎-多菲纳大学）题目：温度的蒙特-卡罗近似的发展摘要：演讲者：Erik Demaine（麻省理工学院）题目：几何难题摘要：演讲者：Aviezri Fraenkel（魏茨曼科学研究所）标题：学习如何击败你的分数比蒂游戏对手摘要：在两堆上的公平拿走游戏的P -位置通常将正整数分成两个不相交的序列。在这里，我们考虑的情况下，P -位置的先验给定的两个序列的交集具有无限的基数。挑战在于为具有给定P -位置的博弈找到合适的简洁的博弈规则。我们提出了一个解决方案，在两个异国情调的记数系统，似乎第一个这样的问题。演讲者：JP格罗斯曼（D. E. Shaw）Title：Searching for Periodicity in .6摘要：.6是唯一未解的个位数八进制游戏。在这个“拿来就破”的游戏中，一步棋包括从堆中移除一个bean，并将该堆中剩余的bean留在1或2个非空堆中。我们必须说明，这个博弈的nim值最终是周期性的;找到周期（如果存在的话）需要快速计算nim值。我们回顾了“稀有值”算法，该算法有效地将前N个nim值的计算时间从O（N2）减少到O（N）。我们提出了几个低层次的优化，并展示了如何并行计算，从而显着的额外的加速。发言人：Alan Guo & Mike Weimerskirch（杜克大学; Macalester学院）题目：Misere游戏中的格点方法摘要：在堆大小为d的正常游戏堆中的位置可以被认为是格C = Nd的元素。我们将C嵌入Zd，Zd\C被宣布为失败位置。Misère游戏类似于游戏板C = Nd \ {（0，0，. . .，0）}。这可以推广到任意的游戏板。这种游戏的最佳策略使用希尔伯特级数的描述提供了一种替代Plambeck的商幺半群方法。
Speaker: Elwyn Berlekamp (University of California, Berkeley) Title: Report on the latest Coupon Go tournament Abstract: Late in 2010 a Coupon Go tournament was held in Korea. This talk will give an overview of the tournament and the results. Speaker: Kyle Burke (Wittenberg University) Title: Neighboring Nim: a PSPACE-complete NimG variant Abstract: Neighboring Nim is a version of Nim where heaps are embedded onto vertices of a graph. A turn consists of traversing an edge (adjacent to the last play) then removing sticks from the resulting vertex. Even with small heap sizes, the game is PSPACE-hard. Speaker: Tristan Cazenave (Paris-Dauphine University ) Title: Developments on the Monte-Carlo approximation of temperature Abstract: Speaker: Erik Demaine (MIT ) Title: Geometric Puzzles Abstract: Speaker: Aviezri Fraenkel (Weizmann Institute of Science) Title: Learn How To Beat Your Fractional Beatty Game Opponent Abstract: The P -positions of impartial take-away games on two piles usually split the positive integers into two nonintersecting sequences. Here we consider the case where the P -positions are given a priori as two sequences whose intersection has infinite cardinality. The challenge is to find appropriate succinct game rules for a game having the given P -positions. We present a solution in terms of two exotic numeration systems, for a seemingly first such problem. Speaker: JP Grossman (D. E. Shaw ) Title: Searching for Periodicity in .6 Abstract: .6 is the only unsolved single-digit octal game. In this take-and-break game, a move consists of removing a bean from a heap and leaving the remaining beans from that heap in exactly 1 or 2 non-empty heaps. It is conjectured that the nim-values for this game are eventually periodic; finding the period (if it exists) requires fast computation of the nim-values. We review the ”rare values” algorithm that effectively reduces the computation time for the first N nim-values from O(N2) to O(N). We present several low-level optimizations and show how to parallelize the computation, resulting in significant additional speedups. Speaker: Alan Guo & Mike Weimerskirch (Duke University; Macalester College) Title: Lattice point methods in misere games Abstract: Positions in normal play heap games with bounded heap size d can be thought of as elements of the lattice C = Nd. We imbed C in Zd, with Zd\C declared to be defeated positions. Misère play is treated similarly with gameboard C = Nd \ {(0, 0, . . . , 0)}. This can be generalized to arbitrary gameboards. A description of the optimal strategy of such games using Hilbert Series provides an alternative to Plambeck’s Quotient Monoid approach.