Pirates and treasure

MaRDI QIDQ2855641zbMATHFDO

Authors Fraser Stewart

Publication date 25 October 2013

Published in Integers (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1208.2432

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

combinatorial gameNP-hard problempirates and treasure

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) 2-person games (91A05) Games involving graphs (91A43) Combinatorial games (91A46)

Abstract: In this paper we introduce a new game; in this game there are two players who play as rival pirate gangs. The goal is to gather more treasure than your rival. The game is played on a graph and a player gathers treasure by moving to an unvisited vertex. At the end of the game, the player with the most treasure wins. We will show that this game is NP-Hard, and we will also look at the structure of this game under the disjunctive sum. We will show that there are cases where this game behaves like a normal play game, and cases where it behaves like a mis`ere play game. We then leave an open problem about scoring play games in general.

Recommendations

• On the complexity and topology of scoring games: of pirates and treasure
• A Nim game played on graphs.
• Scoring games: the state of play
• scientific article; zbMATH DE number 4181366
• On the complexity of the misère version of three games played on graphs

Cited in

(1)

• On the complexity and topology of scoring games: of pirates and treasure

This page was built for publication: Pirates and treasure

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2855641)