$p$-adic Manifold Learning and Benchmark Tasks from Impartial Games
We introduce $p$-adic manifold learning, propose an algorithm to solve it, and propose benchmark tasks from impartial games.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Impartial Games: A Challenge for Reinforcement Learning
While AlphaZero-style reinforcement learning (RL) algorithms excel in various board games, in this paper we show that they face challenges on impartial games where players share pieces. We present a concrete example of a…
Board GamesPositionreinforcement-learningReinforcement Learning+1Nimber-Preserving Reductions and Homomorphic Sprague-Grundy Game Encodings
The concept of nimbers--a.k.a. Grundy-values or nim-values--is fundamental to combinatorial game theory. Nimbers provide a complete characterization of strategic interactions among impartial games in their disjunctive su…
Winning the War by (Strategically) Losing Battles: Settling the Complexity of Grundy-Values in Undirected Geography
We settle two long-standing complexity-theoretical questions-open since 1981 and 1993-in combinatorial game theory (CGT). We prove that the Grundy value (a.k.a. nim-value, or nimber) of Undirected Geography is PSPACE-com…
A General Upper Bound for the Runtime of a Coevolutionary Algorithm on Impartial Combinatorial Games
Due to their complex dynamics, combinatorial games are a key test case and application for algorithms that train game playing agents. Among those algorithms that train using self-play are coevolutionary algorithms (CoEAs…
Massively Parallel Proof-Number Search for Impartial Games and Beyond
Proof-Number Search is a best-first search algorithm with many successful applications, especially in game solving. As large-scale computing clusters become increasingly accessible, parallelization is a natural way to ac…