1,721,004 research outputs found
Tracks from hell — When finding a proof may be easier than checking it
No full textWe consider the popular smartphone game Trainyard: a puzzle game that requires the player to lay down tracks in order to route colored trains from departure stations to suitable arrival stations. While it is already known [Almanza et al., FUN 2016] that the problem of finding a solution to a given Trainyard instance (i.e., game level) is NP-hard, determining the computational complexity of checking whether a candidate solution (i.e., a track layout) solves the level was left as an open problem. In this paper we prove that this verification problem is PSPACE-complete, thus implying that Trainyard players might not only have a hard time finding solutions to a given level, but they might even be unable to efficiently recognize them
Trainyard is NP-Hard
Full text linkRecently, due to the widespread diffusion of smart-phones, mobile puzzle games have experienced a huge increase in their popularity. A successful puzzle has to be both captivating and challenging, and it has been suggested that these features are somehow related to their computational complexity [6]. Indeed, many puzzle games – such as Mah-Jongg, Sokoban, Candy Crush, and 2048, to name a few – are known to be NP-hard [3,4,8,12]. In this paper we consider Trainyard: a popular mobile puzzle game whose goal is to get colored trains from their initial stations to suitable destination stations. We prove that the problem of determining whether there exists a solution to a given Trainyard level is NP-hard. We also provide an implementation of our hardness reduction
Trainyard is NP-Hard
No full textRecently, due to the widespread diffusion of smart-phones, mobile puzzle games have experienced a huge increase in their popularity. A successful puzzle has to be both captivating and challenging, and it has been suggested that these features are somehow related to their computational complexity [6]. Indeed, many puzzle games – such as Mah-Jongg, Sokoban, Candy Crush, and 2048, to name a few – are known to be NP-hard [3,4,8,12]. In this paper we consider Trainyard: a popular mobile puzzle game whose goal is to get colored trains from their initial stations to suitable destination stations. We prove that the problem of determining whether there exists a solution to a given Trainyard level is NP-hard. We also provide an implementation of our hardness reduction
Trainyard is NP-hard
No full textRecently, due to the widespread diffusion of smart-phones, mobile puzzle games have experienced a huge increase in their popularity. A successful puzzle has to be both captivating and challenging, and it has been suggested that this features are somehow related to their computational complexity [5]. Indeed, many puzzle games - such as Mah-Jongg, Sokoban, Candy Crush, and 2048, to name a few - are known to be NP-hard [3, 4, 7, 10]. In this paper we consider Trainyard: a popular mobile puzzle game whose goal is to get colored trains from their initial stations to suitable destination stations. We prove that the problem of determining whether there exists a solution to a given Trainyard level is NP-hard. We also provide an implementation of our hardness reduction1
Errare humanum est? A pilot study to evaluate the human-likeness of a ai othello playing agent
No full textOlivaw is an AI Othello playing agent which autonomously learns how to improve its gameplay by playing against itself. Some top-notch players (including former World Champions) reported that they had the impression that Olivaw's gameplay was human-like. To better investigate the processes related to these impressions, we conducted a pilot study using the Othello Game Evaluation App, a computer application we developed to evaluate pre-recorded Othello games in a controlled setting while assuring an adequate user experience. An exploratory analysis of the results shows that the participants mostly evaluated Olivaw as a human. When asked for a motivation for their choice, some of them reported that they evaluate poor game moves (and, consequently, losing the game) as an indication of the human-likeness of the player
Tracks from hell - when finding a proof may be easier than checking it
Full text linkWe consider the popular smartphone game Trainyard: a puzzle game that requires the player to lay down tracks in order to route colored trains from departure stations to suitable arrival stations. While it is already known [Almanza et al., FUN 2016] that the problem of finding a solution to a given Trainyard instance (i.e., game level) is NP-hard, determining the computational complexity of checking whether a candidate solution (i.e., a track layout) solves the level was left as an open problem. In this paper we prove that this verification problem is PSPACE-complete, thus implying that Trainyard players might not only have a hard time finding solutions to a given level, but they might even be unable to efficiently recognize them
Some Simple Distributed Algorithms for Sparse Networks
Full text linkWe give simple, deterministic, distributed algorithms for computing maximal matchings, maximal independent sets and colourings. We show that edge colourings with at most 2D-1 colours, and maximal matchings can be computed within O(log^* n + D) deterministic rounds, where D is the maximum degree of the network. We also show how to find maximal independent sets and (D+1)-vertex colourings within O(log^* n + D^2) deterministic rounds. All hidden constants are very small and the algorithms are very simple
Motivo: fast motif counting via succinct color coding and adaptive sampling
Full text linkThe randomized technique of color coding is behind state-ofthe-art algorithms for estimating graph motif counts. Those algorithms, however, are not yet capable of scaling well to very large graphs with billions of edges. In this paper we develop novel tools for the "motif counting via color coding" framework. As a result, our new algorithm, motivo, scales to much larger graphs while at the same time providing more accurate motif counts than ever before. This is achieved thanks to two types of improvements. First, we design new succinct data structures for fast color coding operations, and a biased coloring trick that trades accuracy versus resource usage. These optimizations drastically reduce the resource requirements of color coding. Second, we develop an adaptive motif sampling strategy, based on a fractional set cover problem, that breaks the additive approximation barrier of standard sampling. This gives multiplicative approximations for all motifs at once, allowing us to count not only the most frequent motifs but also extremely rare ones. To give an idea of the improvements, in 40 minutes motivo counts 7-nodes motifs on a graph with 65M nodes and 1.8B edges; this is 30 and 500 times larger than the state of the art, respectively in terms of nodes and edges. On the accuracy side, in one hour motivo produces accurate counts of ≈ 10.000 distinct 8-node motifs on graphs where state-of-the-art algorithms fail even to find the second most frequent motif. Our method requires just a high-end desktop machine. These results show how color coding can bring motif mining to the realm of truly massive graphs using only ordinary hardware
- …
