31 Search Results for "Uno, Yushi"


Volume

LIPIcs, Volume 226

11th International Conference on Fun with Algorithms (FUN 2022)

FUN 2022, May 30 to June 3, 2022, Island of Favignana, Sicily, Italy

Editors: Pierre Fraigniaud and Yushi Uno

Document
Complete Volume
LIPIcs, Volume 226, FUN 2022, Complete Volume

Authors: Pierre Fraigniaud and Yushi Uno

Published in: LIPIcs, Volume 226, 11th International Conference on Fun with Algorithms (FUN 2022)


Abstract
LIPIcs, Volume 226, FUN 2022, Complete Volume

Cite as

11th International Conference on Fun with Algorithms (FUN 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 226, pp. 1-450, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@Proceedings{fraigniaud_et_al:LIPIcs.FUN.2022,
  title =	{{LIPIcs, Volume 226, FUN 2022, Complete Volume}},
  booktitle =	{11th International Conference on Fun with Algorithms (FUN 2022)},
  pages =	{1--450},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-232-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{226},
  editor =	{Fraigniaud, Pierre and Uno, Yushi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2022},
  URN =		{urn:nbn:de:0030-drops-159693},
  doi =		{10.4230/LIPIcs.FUN.2022},
  annote =	{Keywords: LIPIcs, Volume 226, FUN 2022, Complete Volume}
}
Document
Front Matter
Front Matter, Table of Contents, Preface, Conference Organization

Authors: Pierre Fraigniaud and Yushi Uno

Published in: LIPIcs, Volume 226, 11th International Conference on Fun with Algorithms (FUN 2022)


Abstract
Front Matter, Table of Contents, Preface, Conference Organization

Cite as

11th International Conference on Fun with Algorithms (FUN 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 226, pp. 0:i-0:xii, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{fraigniaud_et_al:LIPIcs.FUN.2022.0,
  author =	{Fraigniaud, Pierre and Uno, Yushi},
  title =	{{Front Matter, Table of Contents, Preface, Conference Organization}},
  booktitle =	{11th International Conference on Fun with Algorithms (FUN 2022)},
  pages =	{0:i--0:xii},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-232-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{226},
  editor =	{Fraigniaud, Pierre and Uno, Yushi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2022.0},
  URN =		{urn:nbn:de:0030-drops-159703},
  doi =		{10.4230/LIPIcs.FUN.2022.0},
  annote =	{Keywords: Front Matter, Table of Contents, Preface, Conference Organization}
}
Document
Pushing Blocks by Sweeping Lines

Authors: Hugo A. Akitaya, Maarten Löffler, and Giovanni Viglietta

Published in: LIPIcs, Volume 226, 11th International Conference on Fun with Algorithms (FUN 2022)


Abstract
We investigate the reconfiguration of n blocks, or "tokens", in the square grid using line pushes. A line push is performed from one of the four cardinal directions and pushes all tokens that are maximum in that direction to the opposite direction by one unit. Tokens that are in the way of other tokens are displaced in the same direction, as well. Similar models of manipulating objects using uniform external forces match the mechanics of existing games and puzzles, such as Mega Maze, 2048 and Labyrinth, and have also been investigated in the context of self-assembly, programmable matter and robotic motion planning. The problem of obtaining a given shape from a starting configuration is know to be NP-complete. We show that, for every n, there are sparse initial configurations of n tokens (i.e., where no two tokens are in the same row or column) that can be compacted into any a×b box such that ab = n. However, only 1×k, 2×k and 3×3 boxes are obtainable from any arbitrary sparse configuration with a matching number of tokens. We also study the problem of rearranging labeled tokens into a configuration of the same shape, but with permuted tokens. For every initial configuration of the tokens, we provide a complete characterization of what other configurations can be obtained by means of line pushes.

Cite as

Hugo A. Akitaya, Maarten Löffler, and Giovanni Viglietta. Pushing Blocks by Sweeping Lines. In 11th International Conference on Fun with Algorithms (FUN 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 226, pp. 1:1-1:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{a.akitaya_et_al:LIPIcs.FUN.2022.1,
  author =	{A. Akitaya, Hugo and L\"{o}ffler, Maarten and Viglietta, Giovanni},
  title =	{{Pushing Blocks by Sweeping Lines}},
  booktitle =	{11th International Conference on Fun with Algorithms (FUN 2022)},
  pages =	{1:1--1:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-232-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{226},
  editor =	{Fraigniaud, Pierre and Uno, Yushi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2022.1},
  URN =		{urn:nbn:de:0030-drops-159719},
  doi =		{10.4230/LIPIcs.FUN.2022.1},
  annote =	{Keywords: Reconfiguration, Global Control, Pushing Blocks, Permutation}
}
Document
A Practical Algorithm for Chess Unwinnability

Authors: Miguel Ambrona

Published in: LIPIcs, Volume 226, 11th International Conference on Fun with Algorithms (FUN 2022)


Abstract
The FIDE Laws of Chess establish that if a player runs out of time during a game, they lose unless there exists no sequence of legal moves that ends in a checkmate by their opponent, in which case the game is drawn. The problem of determining whether or not a given chess position is unwinnable for a certain player has been considered intractable by the community and, consequently, chess servers do not apply the above rule rigorously, thus unfairly classifying many games. We propose, to the best of our knowledge, the first algorithm for chess unwinnability that is sound, complete and efficient for practical use. We also develop a prototype implementation and evaluate it over the entire Lichess Database (containing more than 3 billion games), successfully identifying all unfairly classified games in the database.

Cite as

Miguel Ambrona. A Practical Algorithm for Chess Unwinnability. In 11th International Conference on Fun with Algorithms (FUN 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 226, pp. 2:1-2:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{ambrona:LIPIcs.FUN.2022.2,
  author =	{Ambrona, Miguel},
  title =	{{A Practical Algorithm for Chess Unwinnability}},
  booktitle =	{11th International Conference on Fun with Algorithms (FUN 2022)},
  pages =	{2:1--2:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-232-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{226},
  editor =	{Fraigniaud, Pierre and Uno, Yushi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2022.2},
  URN =		{urn:nbn:de:0030-drops-159721},
  doi =		{10.4230/LIPIcs.FUN.2022.2},
  annote =	{Keywords: chess, helpmate, unwinnability, timeout, dead position}
}
Document
Pushing Blocks via Checkable Gadgets: PSPACE-Completeness of Push-1F and Block/Box Dude

Authors: Joshua Ani, Lily Chung, Erik D. Demaine, Yevhenii Diomidov, Dylan Hendrickson, and Jayson Lynch

Published in: LIPIcs, Volume 226, 11th International Conference on Fun with Algorithms (FUN 2022)


Abstract
We prove PSPACE-completeness of the well-studied pushing-block puzzle Push-1F, a theoretical abstraction of many video games (first posed in 1999). We also prove PSPACE-completeness of two versions of the recently studied block-moving puzzle game with gravity, Block Dude - a video game dating back to 1994 - featuring either liftable blocks or pushable blocks. Two of our reductions are built on a new framework for "checkable" gadgets, extending the motion-planning-through-gadgets framework to support gadgets that can be misused, provided those misuses can be detected later.

Cite as

Joshua Ani, Lily Chung, Erik D. Demaine, Yevhenii Diomidov, Dylan Hendrickson, and Jayson Lynch. Pushing Blocks via Checkable Gadgets: PSPACE-Completeness of Push-1F and Block/Box Dude. In 11th International Conference on Fun with Algorithms (FUN 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 226, pp. 3:1-3:30, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{ani_et_al:LIPIcs.FUN.2022.3,
  author =	{Ani, Joshua and Chung, Lily and Demaine, Erik D. and Diomidov, Yevhenii and Hendrickson, Dylan and Lynch, Jayson},
  title =	{{Pushing Blocks via Checkable Gadgets: PSPACE-Completeness of Push-1F and Block/Box Dude}},
  booktitle =	{11th International Conference on Fun with Algorithms (FUN 2022)},
  pages =	{3:1--3:30},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-232-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{226},
  editor =	{Fraigniaud, Pierre and Uno, Yushi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2022.3},
  URN =		{urn:nbn:de:0030-drops-159737},
  doi =		{10.4230/LIPIcs.FUN.2022.3},
  annote =	{Keywords: gadgets, motion planning, hardness of games}
}
Document
Fun Slot Machines and Transformations of Words Avoiding Factors

Authors: Marcella Anselmo, Manuela Flores, and Maria Madonia

Published in: LIPIcs, Volume 226, 11th International Conference on Fun with Algorithms (FUN 2022)


Abstract
Fun Slot Machines are a variant of the classical ones. Pulling a lever, the player generates a sequence of symbols which are placed on the reels. The machine pays when a given pattern appears in the sequence. The variant consists in trying to transform a losing sequence of symbols in another one, in such a way that the winning pattern does not appear in any intermediate step. The choice of the winning pattern can be crucial; there are "good" and "bad" sequences. The game results in a combinatorial problem on transformations of words avoiding a given pattern as a factor. We investigate "good" and "bad" sequences on a k-ary alphabet and the pairs of words that witness that a word is "bad". A main result is an algorithm to decide whether a word is "bad" or not and to provide a pair of witnesses of minimal length when the word is "bad". It runs in O(n) time with a preprocessing of O(n) time and space to construct an enhanced suffix tree of the word.

Cite as

Marcella Anselmo, Manuela Flores, and Maria Madonia. Fun Slot Machines and Transformations of Words Avoiding Factors. In 11th International Conference on Fun with Algorithms (FUN 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 226, pp. 4:1-4:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{anselmo_et_al:LIPIcs.FUN.2022.4,
  author =	{Anselmo, Marcella and Flores, Manuela and Madonia, Maria},
  title =	{{Fun Slot Machines and Transformations of Words Avoiding Factors}},
  booktitle =	{11th International Conference on Fun with Algorithms (FUN 2022)},
  pages =	{4:1--4:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-232-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{226},
  editor =	{Fraigniaud, Pierre and Uno, Yushi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2022.4},
  URN =		{urn:nbn:de:0030-drops-159743},
  doi =		{10.4230/LIPIcs.FUN.2022.4},
  annote =	{Keywords: Isometric words, Words avoiding factors, Index of a word, Overlap, Lee distance}
}
Document
Chess Is Hard Even for a Single Player

Authors: N.R. Aravind, Neeldhara Misra, and Harshil Mittal

Published in: LIPIcs, Volume 226, 11th International Conference on Fun with Algorithms (FUN 2022)


Abstract
We introduce a generalization of "Solo Chess", a single-player variant of the game that can be played on chess.com. The standard version of the game is played on a regular 8 × 8 chessboard by a single player, with only white pieces, using the following rules: every move must capture a piece, no piece may capture more than 2 times, and if there is a King on the board, it must be the final piece. The goal is to clear the board, i.e, make a sequence of captures after which only one piece is left. We generalize this game to unbounded boards with n pieces, each of which have a given number of captures that they are permitted to make. We show that Generalized Solo Chess is NP-complete, even when it is played by only rooks that have at most two captures remaining. It also turns out to be NP-complete even when every piece is a queen with exactly two captures remaining in the initial configuration. In contrast, we show that solvable instances of Generalized Solo Chess can be completely characterized when the game is: a) played by rooks on a one-dimensional board, and b) played by pawns with two captures left on a 2D board. Inspired by Generalized Solo Chess, we also introduce the Graph Capture Game, which involves clearing a graph of tokens via captures along edges. This game subsumes Generalized Solo Chess played by knights. We show that the Graph Capture Game is NP-complete for undirected graphs and DAGs.

Cite as

N.R. Aravind, Neeldhara Misra, and Harshil Mittal. Chess Is Hard Even for a Single Player. In 11th International Conference on Fun with Algorithms (FUN 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 226, pp. 5:1-5:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{aravind_et_al:LIPIcs.FUN.2022.5,
  author =	{Aravind, N.R. and Misra, Neeldhara and Mittal, Harshil},
  title =	{{Chess Is Hard Even for a Single Player}},
  booktitle =	{11th International Conference on Fun with Algorithms (FUN 2022)},
  pages =	{5:1--5:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-232-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{226},
  editor =	{Fraigniaud, Pierre and Uno, Yushi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2022.5},
  URN =		{urn:nbn:de:0030-drops-159753},
  doi =		{10.4230/LIPIcs.FUN.2022.5},
  annote =	{Keywords: chess, strategy, board games, NP-complete}
}
Document
Rolling Polyhedra on Tessellations

Authors: Akira Baes, Erik D. Demaine, Martin L. Demaine, Elizabeth Hartung, Stefan Langerman, Joseph O'Rourke, Ryuhei Uehara, Yushi Uno, and Aaron Williams

Published in: LIPIcs, Volume 226, 11th International Conference on Fun with Algorithms (FUN 2022)


Abstract
We study the space reachable by rolling a 3D convex polyhedron on a 2D periodic tessellation in the xy-plane, where at every step a face of the polyhedron must coincide exactly with a tile of the tessellation it rests upon, and the polyhedron rotates around one of the incident edges of that face until the neighboring face hits the xy plane. If the whole plane can be reached by a sequence of such rolls, we call the polyhedron a plane roller for the given tessellation. We further classify polyhedra that reach a constant fraction of the plane, an infinite area but vanishing fraction of the plane, or a bounded area as hollow-plane rollers, band rollers, and bounded rollers respectively. We present a polynomial-time algorithm to determine the set of tiles in a given periodic tessellation reachable by a given polyhedron from a given starting position, which in particular determines the roller type of the polyhedron and tessellation. Using this algorithm, we compute the reachability for every regular-faced convex polyhedron on every regular-tiled (≤ 4)-uniform tessellation.

Cite as

Akira Baes, Erik D. Demaine, Martin L. Demaine, Elizabeth Hartung, Stefan Langerman, Joseph O'Rourke, Ryuhei Uehara, Yushi Uno, and Aaron Williams. Rolling Polyhedra on Tessellations. In 11th International Conference on Fun with Algorithms (FUN 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 226, pp. 6:1-6:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{baes_et_al:LIPIcs.FUN.2022.6,
  author =	{Baes, Akira and Demaine, Erik D. and Demaine, Martin L. and Hartung, Elizabeth and Langerman, Stefan and O'Rourke, Joseph and Uehara, Ryuhei and Uno, Yushi and Williams, Aaron},
  title =	{{Rolling Polyhedra on Tessellations}},
  booktitle =	{11th International Conference on Fun with Algorithms (FUN 2022)},
  pages =	{6:1--6:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-232-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{226},
  editor =	{Fraigniaud, Pierre and Uno, Yushi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2022.6},
  URN =		{urn:nbn:de:0030-drops-159761},
  doi =		{10.4230/LIPIcs.FUN.2022.6},
  annote =	{Keywords: polyhedra, tilings}
}
Document
Beedroids: How Luminous Autonomous Swarms of UAVs Can Save the World?

Authors: Quentin Bramas, Stéphane Devismes, Anaïs Durand, Pascal Lafourcade, and Anissa Lamani

Published in: LIPIcs, Volume 226, 11th International Conference on Fun with Algorithms (FUN 2022)


Abstract
Bee extinction is a great risk for humanity. To circumvent this ineluctable disaster, we propose to develop beedroids, i.e., small UAVs mimicking the behaviors of real bees. Those beedroids are endowed with very weak capabilities (short-range visibility sensors, no GPS, light with a few colors, ...). Like real bees, they have to self-organize together into swarms. Beedroid swarms will be deployed in cuboid-shaped greenhouse. Each beedroid swarm will have to indefinitely search for flowers to pollinate in its greenhouse. We model this problem as a perpetual exploration of a 3D grid by a swarm of beedroids. In this paper, we propose two optimal solutions to solve this problem and so to save humanity.

Cite as

Quentin Bramas, Stéphane Devismes, Anaïs Durand, Pascal Lafourcade, and Anissa Lamani. Beedroids: How Luminous Autonomous Swarms of UAVs Can Save the World?. In 11th International Conference on Fun with Algorithms (FUN 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 226, pp. 7:1-7:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{bramas_et_al:LIPIcs.FUN.2022.7,
  author =	{Bramas, Quentin and Devismes, St\'{e}phane and Durand, Ana\"{i}s and Lafourcade, Pascal and Lamani, Anissa},
  title =	{{Beedroids: How Luminous Autonomous Swarms of UAVs Can Save the World?}},
  booktitle =	{11th International Conference on Fun with Algorithms (FUN 2022)},
  pages =	{7:1--7:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-232-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{226},
  editor =	{Fraigniaud, Pierre and Uno, Yushi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2022.7},
  URN =		{urn:nbn:de:0030-drops-159771},
  doi =		{10.4230/LIPIcs.FUN.2022.7},
  annote =	{Keywords: Bee extinction, luminous swarms of beedroids, perpetual flower pollination problem, greenhouse}
}
Document
Priority Queues with Decreasing Keys

Authors: Gerth Stølting Brodal

Published in: LIPIcs, Volume 226, 11th International Conference on Fun with Algorithms (FUN 2022)


Abstract
A priority queue stores a set of items with associated keys and supports the insertion of a new item and extraction of an item with minimum key. In applications like Dijkstra’s single source shortest path algorithm and Prim-Jarník’s minimum spanning tree algorithm, the key of an item can decrease over time. Usually this is handled by either using a priority queue supporting the deletion of an arbitrary item or a dedicated DecreaseKey operation, or by inserting the same item multiple times but with decreasing keys. In this paper we study what happens if the keys associated with items in a priority queue can decrease over time without informing the priority queue, and how such a priority queue can be used in Dijkstra’s algorithm. We show that binary heaps with bottom-up insertions fail to report items with unchanged keys in correct order, while binary heaps with top-down insertions report items with unchanged keys in correct order. Furthermore, we show that skew heaps, leftist heaps, and priority queues based on linking roots of heap-ordered trees, like pairing heaps, binomial queues and Fibonacci heaps, work correctly with decreasing keys without any modifications. Finally, we show that the post-order heap by Harvey and Zatloukal, a variant of a binary heap with amortized constant time insertions and amortized logarithmic time deletions, works correctly with decreasing keys and is a strong contender for an implicit priority queue supporting decreasing keys in practice.

Cite as

Gerth Stølting Brodal. Priority Queues with Decreasing Keys. In 11th International Conference on Fun with Algorithms (FUN 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 226, pp. 8:1-8:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{brodal:LIPIcs.FUN.2022.8,
  author =	{Brodal, Gerth St{\o}lting},
  title =	{{Priority Queues with Decreasing Keys}},
  booktitle =	{11th International Conference on Fun with Algorithms (FUN 2022)},
  pages =	{8:1--8:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-232-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{226},
  editor =	{Fraigniaud, Pierre and Uno, Yushi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2022.8},
  URN =		{urn:nbn:de:0030-drops-159787},
  doi =		{10.4230/LIPIcs.FUN.2022.8},
  annote =	{Keywords: priority queue, decreasing keys, post-order heap, Dijkstra’s algorithm}
}
Document
Zero-Knowledge Proof of Knowledge for Peg Solitaire

Authors: Xavier Bultel

Published in: LIPIcs, Volume 226, 11th International Conference on Fun with Algorithms (FUN 2022)


Abstract
Peg solitaire is a very popular traditional single-player board game, known to be NP-complete. In this paper, we present a zero-knowledge proof of knowledge for solutions of peg solitaire instances. Our proof is straightforward, in the sense that it does not use any reduction to another NP-complete problem, and uses the standard design of sigma protocols. Our construction relies on cryptographic commitments, which can be replaced by envelopes to make the protocol physical. As a side contribution, we introduce the notion of isomorphisms for peg solitaire, which is the key tool of our protocol.

Cite as

Xavier Bultel. Zero-Knowledge Proof of Knowledge for Peg Solitaire. In 11th International Conference on Fun with Algorithms (FUN 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 226, pp. 9:1-9:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{bultel:LIPIcs.FUN.2022.9,
  author =	{Bultel, Xavier},
  title =	{{Zero-Knowledge Proof of Knowledge for Peg Solitaire}},
  booktitle =	{11th International Conference on Fun with Algorithms (FUN 2022)},
  pages =	{9:1--9:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-232-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{226},
  editor =	{Fraigniaud, Pierre and Uno, Yushi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2022.9},
  URN =		{urn:nbn:de:0030-drops-159798},
  doi =		{10.4230/LIPIcs.FUN.2022.9},
  annote =	{Keywords: Zero-Knowledge Proof, Peg Solitaire}
}
Document
Nimber-Preserving Reduction: Game Secrets And Homomorphic Sprague-Grundy Theorem

Authors: Kyle W. Burke, Matthew Ferland, and Shang-Hua Teng

Published in: LIPIcs, Volume 226, 11th International Conference on Fun with Algorithms (FUN 2022)


Abstract
The concept of nimbers - a.k.a. Grundy-values or nim-values - is fundamental to combinatorial game theory. Beyond the winnability, nimbers provide a complete characterization of strategic interactions among impartial games in disjunctive sums. In this paper, we consider nimber-preserving reductions among impartial games, which enhance the winnability-preserving reductions in traditional computational characterizations of combinatorial games. We prove that Generalized Geography is complete for the natural class, ℐ^P, of polynomially-short impartial rulesets, under polynomial-time nimber-preserving reductions. We refer to this notion of completeness as Sprague-Grundy-completeness. In contrast, we also show that not every PSPACE-complete ruleset in ℐ^P is Sprague-Grundy-complete for ℐ^P. By viewing every impartial game as an encoding of its nimber - a succinct game secret richer than its winnability alone - our technical result establishes the following striking cryptography-inspired homomorphic theorem: Despite the PSPACE-completeness of nimber computation for ℐ^P, there exists a polynomial-time algorithm to construct, for any pair of games G₁, G₂ in ℐ^P, a Generalized Geography game G satisfying: nimber(G) = nimber(G₁) ⊕ nimber(G₂).

Cite as

Kyle W. Burke, Matthew Ferland, and Shang-Hua Teng. Nimber-Preserving Reduction: Game Secrets And Homomorphic Sprague-Grundy Theorem. In 11th International Conference on Fun with Algorithms (FUN 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 226, pp. 10:1-10:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{burke_et_al:LIPIcs.FUN.2022.10,
  author =	{Burke, Kyle W. and Ferland, Matthew and Teng, Shang-Hua},
  title =	{{Nimber-Preserving Reduction: Game Secrets And Homomorphic Sprague-Grundy Theorem}},
  booktitle =	{11th International Conference on Fun with Algorithms (FUN 2022)},
  pages =	{10:1--10:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-232-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{226},
  editor =	{Fraigniaud, Pierre and Uno, Yushi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2022.10},
  URN =		{urn:nbn:de:0030-drops-159808},
  doi =		{10.4230/LIPIcs.FUN.2022.10},
  annote =	{Keywords: Combinatorial Games, Nim, Generalized Geography, Sprague-Grundy Theory, Grundy value, Computational Complexity, Functional-Preserving Reductions}
}
Document
Quantum-Inspired Combinatorial Games: Algorithms and Complexity

Authors: Kyle W. Burke, Matthew Ferland, and Shang-Hua Teng

Published in: LIPIcs, Volume 226, 11th International Conference on Fun with Algorithms (FUN 2022)


Abstract
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 address the following fundamental questions: - Complexity Leap: Can this framework transform polynomial-time solvable games into intractable games? - Complexity Collapse: Can this framework transform PSPACE-complete games into ones with complexity in the lower levels of the polynomial-time hierarchy? We focus our study on how it affects two extensively studied polynomial-time-solvable games: Nim and Undirected Geography. We prove that both Nim and Undirected Geography make a complexity leap over NP, when starting with superpositions: The former becomes Σ₂^p-hard and the latter becomes PSPACE-complete. We further give an algorithm to prove that from any classical starting position, quantumized Undirected Geography remains polynomial-time solvable. Together they provide a nearly-complete characterization for Undirected Geography. Both our algorithm and its correctness proof require strategic moves and graph contraction to extend the matching-based theory for classical Undirected Geography. Our constructive proofs for both games highlight the intricacy of this framework. The polynomial time robustness of Undirected Geography in this quantum-inspired setting provides a striking contrast to the recent result that the disjunctive sum of two Undirected Geography games is PSPACE-complete. We give a Σ₂^p-hardness analysis of quantumized Nim, even if there are no pile sizes of more than 1.

Cite as

Kyle W. Burke, Matthew Ferland, and Shang-Hua Teng. Quantum-Inspired Combinatorial Games: Algorithms and Complexity. In 11th International Conference on Fun with Algorithms (FUN 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 226, pp. 11:1-11:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{burke_et_al:LIPIcs.FUN.2022.11,
  author =	{Burke, Kyle W. and Ferland, Matthew and Teng, Shang-Hua},
  title =	{{Quantum-Inspired Combinatorial Games: Algorithms and Complexity}},
  booktitle =	{11th International Conference on Fun with Algorithms (FUN 2022)},
  pages =	{11:1--11:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-232-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{226},
  editor =	{Fraigniaud, Pierre and Uno, Yushi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2022.11},
  URN =		{urn:nbn:de:0030-drops-159812},
  doi =		{10.4230/LIPIcs.FUN.2022.11},
  annote =	{Keywords: Quantum-Inspired Games, Combinatorial Games, Computational Complexity, Polynomial Hierarchy, \c{c}lass\{PSPACE\}, Nim, Generalized Geography, Snort}
}
Document
Grabbing Olives on Linear Pizzas and Pissaladières

Authors: Jean-Claude Bermond, Frédéric Havet, and Michel Cosnard

Published in: LIPIcs, Volume 226, 11th International Conference on Fun with Algorithms (FUN 2022)


Abstract
In this paper we revisit the problem entitled Sharing a Pizza stated by P. Winkler by considering a new puzzle called Sharing a Pissaladiere. The game is played by two polite coatis Alice and Bob who share a pissaladière (a p×q grid) which is divided into rectangular slices. Alice starts in a corner and then the coatis alternate removing a remaining slice adjacent to at most two other slices. On some slices there are precious olives of Nice and the aim of each coati is to grab the maximum number of olives. We first study the particular case of 1×n grid (i.e. a path) where the game is a graph grabbing game known as Sharing a linear pizza. In that case each player can take only an end vertex of the remaining path. These problems are particular cases of a new class of games called d-degenerate games played on a graph with non negative weights assigned to the vertices with the rule that coatis alternatively take a vertex of degree at most d. Our main results are the following. We give optimal strategies for paths (linear pizzas) with no two adjacent weighty vertices. We also give a recurrence formula to compute the gains which depend only on the parity of n and of the respective parities of weighty vertices with a complexity in O(h²) where h denotes the number of parity changes in the weighty vertices. When the weights are only {0,1} we reduce the computation of the average number of olives collected by each player to a word counting problem. We solve Sharing a pissaladière with {0,1} weights, when there is one olive or 2 olives. In that case Alice (resp. Bob) grabs almost all the olives if the number of vertices of the grid n = p×q is odd (resp. even). We prove that for a 2×q grid with a fixed number k of olives Bob grabs at least ⌈(k-1)/3⌉ olives and almost always grabs all the k olives.

Cite as

Jean-Claude Bermond, Frédéric Havet, and Michel Cosnard. Grabbing Olives on Linear Pizzas and Pissaladières. In 11th International Conference on Fun with Algorithms (FUN 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 226, pp. 12:1-12:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{bermond_et_al:LIPIcs.FUN.2022.12,
  author =	{Bermond, Jean-Claude and Havet, Fr\'{e}d\'{e}ric and Cosnard, Michel},
  title =	{{Grabbing Olives on Linear Pizzas and Pissaladi\`{e}res}},
  booktitle =	{11th International Conference on Fun with Algorithms (FUN 2022)},
  pages =	{12:1--12:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-232-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{226},
  editor =	{Fraigniaud, Pierre and Uno, Yushi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2022.12},
  URN =		{urn:nbn:de:0030-drops-159826},
  doi =		{10.4230/LIPIcs.FUN.2022.12},
  annote =	{Keywords: Grabbing game, degenerate graph, path, grid}
}
  • Refine by Author
  • 7 Uno, Yushi
  • 2 Burke, Kyle W.
  • 2 Demaine, Erik D.
  • 2 Ferland, Matthew
  • 2 Fraigniaud, Pierre
  • Show More...

  • Refine by Classification
  • 7 Theory of computation → Design and analysis of algorithms
  • 4 Theory of computation → Problems, reductions and completeness
  • 3 Mathematics of computing → Graph algorithms
  • 2 Mathematics of computing → Combinatorial algorithms
  • 2 Mathematics of computing → Discrete mathematics
  • Show More...

  • Refine by Keyword
  • 2 Combinatorial Games
  • 2 Computational Complexity
  • 2 Generalized Geography
  • 2 Nim
  • 2 algorithmic combinatorial game theory
  • Show More...

  • Refine by Type
  • 30 document
  • 1 volume

  • Refine by Publication Year
  • 27 2022
  • 2 2016
  • 1 2017
  • 1 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