2 Search Results for "Yedidia, Adam"

Document
DOI: 10.4230/LIPIcs.FUN.2021.9
Magic: The Gathering Is Turing Complete

Authors: Alex Churchill, Stella Biderman, and Austin Herrick

Published in: LIPIcs, Volume 157, 10th International Conference on Fun with Algorithms (FUN 2021) (2020)

Abstract
Magic: The Gathering is a popular and famously complicated trading card game about magical combat. In this paper we show that optimal play in real-world Magic is at least as hard as the Halting Problem. This provides a positive answer to the question "is there a real-world game where perfect play is undecidable under the rules in which it is typically played?", a question that has been open for a decade [David Auger and Oliver Teytaud, 2012; Erik D. Demaine and Robert A. Hearn, 2009]. To do this, we present a methodology for embedding an arbitrary Turing machine into a game of Magic such that the first player is guaranteed to win the game if and only if the Turing machine halts. Our result applies to how real Magic is played, can be achieved using standard-size tournament-legal decks, and does not rely on stochasticity or hidden information. Our result is also highly unusual in that all moves of both players are forced in the construction. This shows that even recognising who will win a game in which neither player has a non-trivial decision to make for the rest of the game is undecidable. We conclude with a discussion of the implications for a unified computational theory of games and remarks about the playability of such a board in a tournament setting.
Cite as

Alex Churchill, Stella Biderman, and Austin Herrick. Magic: The Gathering Is Turing Complete. In 10th International Conference on Fun with Algorithms (FUN 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 157, pp. 9:1-9:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{churchill_et_al:LIPIcs.FUN.2021.9,
  author =	{Churchill, Alex and Biderman, Stella and Herrick, Austin},
  title =	{{Magic: The Gathering Is Turing Complete}},
  booktitle =	{10th International Conference on Fun with Algorithms (FUN 2021)},
  pages =	{9:1--9:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-145-0},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{157},
  editor =	{Farach-Colton, Martin and Prencipe, Giuseppe and Uehara, Ryuhei},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2021.9},
  URN =		{urn:nbn:de:0030-drops-127706},
  doi =		{10.4230/LIPIcs.FUN.2021.9},
  annote =	{Keywords: Turing machines, computability theory, Magic: the Gathering, two-player games}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2020.78
Faster Random k-CNF Satisfiability

Authors: Andrea Lincoln and Adam Yedidia

Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)

Abstract
We describe an algorithm to solve the problem of Boolean CNF-Satisfiability when the input formula is chosen randomly. We build upon the algorithms of Schöning 1999 and Dantsin et al. in 2002. The Schöning algorithm works by trying many possible random assignments, and for each one searching systematically in the neighborhood of that assignment for a satisfying solution. Previous algorithms for this problem run in time O(2^(n (1- Ω(1)/k))). Our improvement is simple: we count how many clauses are satisfied by each randomly sampled assignment, and only search in the neighborhoods of assignments with abnormally many satisfied clauses. We show that assignments like these are significantly more likely to be near a satisfying assignment. This improvement saves a factor of 2^(n Ω(lg² k)/k), resulting in an overall runtime of O(2^(n (1- Ω(lg² k)/k))) for random k-SAT.
Cite as

Andrea Lincoln and Adam Yedidia. Faster Random k-CNF Satisfiability. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 78:1-78:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{lincoln_et_al:LIPIcs.ICALP.2020.78,
  author =	{Lincoln, Andrea and Yedidia, Adam},
  title =	{{Faster Random k-CNF Satisfiability}},
  booktitle =	{47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)},
  pages =	{78:1--78:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-138-2},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{168},
  editor =	{Czumaj, Artur and Dawar, Anuj and Merelli, Emanuela},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.78},
  URN =		{urn:nbn:de:0030-drops-124857},
  doi =		{10.4230/LIPIcs.ICALP.2020.78},
  annote =	{Keywords: Random k-SAT, Average-Case, Algorithms}
}
  • Refine by Author
  • 1 Biderman, Stella
  • 1 Churchill, Alex
  • 1 Herrick, Austin
  • 1 Lincoln, Andrea
  • 1 Yedidia, Adam

  • Refine by Classification
  • 1 Theory of computation → Algorithmic game theory
  • 1 Theory of computation → Random search heuristics

  • Refine by Keyword
  • 1 Algorithms
  • 1 Average-Case
  • 1 Magic: the Gathering
  • 1 Random k-SAT
  • 1 Turing machines
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 2 2020

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact