We analyze the computational complexity of the popular computer games Threes!, 1024!, 2048 and many of their variants. For most known versions expanded to an m x n board, we show that it is NP-hard to decide whether a...
详细信息
We analyze the computational complexity of the popular computer games Threes!, 1024!, 2048 and many of their variants. For most known versions expanded to an m x n board, we show that it is NP-hard to decide whether a given starting position can be played to reach a specific (constant) tile value. (C) 2018 Elsevier B.V. All rights reserved.
Undirected Vertex Geography (UVG) is an impartial two-person game played on a (undirected) graph G with a specified vertex u. Players, Alice and Bob, alternately choose a vertex that has not been chosen before and tha...
详细信息
Undirected Vertex Geography (UVG) is an impartial two-person game played on a (undirected) graph G with a specified vertex u. Players, Alice and Bob, alternately choose a vertex that has not been chosen before and that is adjacent to the last chosen vertex. Alice plays first, choosing an adjacent vertex of u. The first player who is unable to choose a vertex loses. Determining whether Alice has a winning strategy in this game (the UVG problem) is known to be solvable in polynomial time. In this paper we study the complexity of the short version of this game (the short-UVG problem) in which it is asked whether Alice has a winning strategy that requires at most k moves, with k part of the input. We show that the short-UVG problem is PSPACE-complete even for bipartite graphs whereas a polynomial algorithm can be designed for trees. Finally, we introduce a partizan version of the UVG-game which we believe is of independent interest. We provide some preliminary results and conclude with many open problems. (C) 2018 Elsevier B.V. All rights reserved.
In this paper we study a cooperative card game called Hanabi from the viewpoint of algorithmic combinatorial game theory. In Hanabi, each card has one among c colors and a number between 1 and n. The aim is to make, f...
详细信息
In this paper we study a cooperative card game called Hanabi from the viewpoint of algorithmic combinatorial game theory. In Hanabi, each card has one among c colors and a number between 1 and n. The aim is to make, for each color, a pile of cards of that color with all increasing numbers from 1 to n. At each time during the game, each player holds h cards in hand. Cards are drawn sequentially from a deck and the players should decide whether to play, discard or store them for future use. One of the features of the game is that the players can see their partners' cards but not their own and information must be shared through hints. We introduce a single-player, perfect-information model and show that the game is intractable even for this simplified version where we forego both the hidden information and the multiplayer aspect of the game, even when the player can only hold two cards in her hand. On the positive side, we show that the decision version of the problem to decide whether or not numbers from 1 through n can be played for every color can be solved in (almost) linear time for some restricted cases. (C) 2017 Elsevier B.V. All rights reserved.
This paper investigates the popular card game UNO (R) from the viewpoint of algorithmic combinatorial game theory. We define simple and concise mathematical models for the game, including both cooperative and uncooper...
详细信息
This paper investigates the popular card game UNO (R) from the viewpoint of algorithmic combinatorial game theory. We define simple and concise mathematical models for the game, including both cooperative and uncooperative versions, and analyze their computational complexity. In particular, we prove that even a single-player version of UNO is NP-complete, although some restricted cases are in P. Surprisingly, we show that the uncooperative two-player version is also in P. (c) 2013 Elsevier B.V. All rights reserved.
Dominoes is a popular and well-known game possibly dating back three millennia. Players are given a set of domino tiles, each with two labeled square faces, and take turns connecting them into a growing chain of domin...
详细信息
ISBN:
(纸本)9783319078908;9783319078892
Dominoes is a popular and well-known game possibly dating back three millennia. Players are given a set of domino tiles, each with two labeled square faces, and take turns connecting them into a growing chain of dominoes by matching identical faces. We show that single-player dominoes is in P, while multiplayer dominoes is hard: when players cooperate, the game is NP-complete, and when players compete, the game is PSPACE-complete. In addition, we show that these hardness results easily extend to games involving team play.
We consider DISJOINT ARROWS, a new bounded-length two-player partizan combinatorialgame. In this game the two players, Alice and Bob, alternate in choosing vertices on a directed graph and no player is allowed to sel...
详细信息
We consider DISJOINT ARROWS, a new bounded-length two-player partizan combinatorialgame. In this game the two players, Alice and Bob, alternate in choosing vertices on a directed graph and no player is allowed to select a vertex previously selected. At each round Alice selects a vertex u and Bob has to reply choosing a new vertex in the out-neighborhood of u. The first player who cannot move loses. We prove that deciding whether Bob can endure k rounds when k is part of the input is a PSPACE-complete problem. Moreover we prove that the parameterized version of the problem is AW[*]-complete. Thus we provide a new member for the small set of problems known complete for the class AM. (C) 2013 Elsevier B.V. All rights reserved.
We study the parameterized complexity of four variants of pursuit-evasion on graphs: SEEDED PURSUIT EVASION, SHORT SEEDED PURSUIT EVASION, DIRECTED PURSUIT EVASION and SHORT DIRECTED PURSUIT EVASION. Both SEEDED PURSU...
详细信息
We study the parameterized complexity of four variants of pursuit-evasion on graphs: SEEDED PURSUIT EVASION, SHORT SEEDED PURSUIT EVASION, DIRECTED PURSUIT EVASION and SHORT DIRECTED PURSUIT EVASION. Both SEEDED PURSUIT EVASION and SHORT SEEDED PURSUIT EVASION are played on undirected graphs with given starting positions for both the cops and the robber. DIRECTED PURSUIT EVASION and its short variant are played on directed graphs, with the players free to choose their starting positions. We show for SEEDED PURSUIT EVASION and DIRECTED PURSUIT EVASION that finding a winning strategy for the cops is AW[*]-hard when we parameterize by the number of cops. Further, we show that the short (k-move) variants of these problems (SHORT SEEDED PURSUIT EVASION and SHORT DIRECTED PURSUIT EVASION) are AM[*]-complete when we parameterize by both the number of cops and turns. (C) 2010 Elsevier B.V. All rights reserved.
In the popular computer game of Tetris, the player is given a sequence of tetromino pieces and must pack them into a rectangular gameboard initially occupied by a given configuration of filled squares;any completely f...
详细信息
In the popular computer game of Tetris, the player is given a sequence of tetromino pieces and must pack them into a rectangular gameboard initially occupied by a given configuration of filled squares;any completely filled row of the gameboard is cleared and all filled squares above it drop by one row. We prove that in the offline version of Tetris, it is NP-complete to maximize the number of cleared rows, maximize the number of tetrises (quadruples of rows simultaneously filled and cleared), minimize the maximum height of an occupied square, or maximize the number of pieces placed before the game ends. We furthermore show the extreme inapproximability of the first and last of these objectives to within a factor of p(1-epsilon), when given a sequence of p pieces, and the inapproximability of the third objective to within a factor of 2 - epsilon, for any epsilon > 0. Our results hold under several variations on the rules of Tetris, including different models of rotation, limitations on player agility, and restricted piece sets.
暂无评论