Zobrazeno 1 - 10
of 22
pro vyhledávání: '"Ferland, Matthew"'
In this paper, we address a natural question at the intersection of combinatorial game theory and computational complexity: "Can a sum of simple tepid games in canonical form be intractable?" To resolve this fundamental question, we consider supersta
Externí odkaz:
http://arxiv.org/abs/2403.04955
Autor:
Ferland, Matthew, Kher, Vikram
In this paper, we give simple NP-hardness reductions for three popular video games. The first is Baba Is You, an award winning 2D block puzzle game with the key premise being the ability to rewrite the rules of the game. The second is Fez, a puzzle p
Externí odkaz:
http://arxiv.org/abs/2202.10529
Publikováno v:
In Theoretical Computer Science 24 July 2024 1005
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 sums as well as the winnability.
Externí odkaz:
http://arxiv.org/abs/2109.05622
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-complete to compute. This exhibit
Externí odkaz:
http://arxiv.org/abs/2106.02114
In this paper, we study a colorful, impartial combinatorial game played on a two-dimensional grid, Transverse Wave. We are drawn to this game because of its apparent simplicity, contrasting intractability, and intrinsic connection to two other combin
Externí odkaz:
http://arxiv.org/abs/2101.07237
Recently, a standardized framework was proposed for introducing quantum-inspired moves in mathematical games with perfect information and no chance. The beauty of quantum games-succinct in representation, rich in structures, explosive in complexity,
Externí odkaz:
http://arxiv.org/abs/2011.03704
Autor:
Ferland, Matthew, Burke, Kyle
We investigate the combinatorial game Slime Trail.This game is played on a graph with a starting piece in a node. Each player's objective is to reach one of their own goal nodes. Every turn the current player moves the piece and deletes the node they
Externí odkaz:
http://arxiv.org/abs/1712.04496
Recently, quantum concepts inspired a new framework in combinatorial game theory. This transformation uses discrete superpositions to yield beautiful new rulesets with succinct representations that require sophisticated strategies. In this paper, we
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::1154c032d017c65d1961f0dd296241d6
Autor:
Shindler, Michael, Pinpin, Natalia, Markovic, Mia, Reiber, Frederick, Kim, Jee Hoon, Carlos, Giles Pierre Nunez, Dogucu, Mine, Hong, Mark, Luu, Michael, Anderson, Brian, Cote, Aaron, Ferland, Matthew, Jain, Palak, LaBonte, Tyler, Mathur, Leena, Moreno, Ryan, Sakuma, Ryan
Publikováno v:
Computer Science Education; Sep2022, Vol. 32 Issue 3, p288-312, 25p