On the complexity of connection games

DOI10.1016/J.TCS.2016.06.033MaRDI QIDQ307770zbMATH OpenOpenAlexFDO

Authors Édouard Bonnet, Florian Jamain, Abdallah Saffidine

Publication date 5 September 2016

Published in Theoretical Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

complexityPSPACEHavannahHexSlitherTwixt

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Combinatorial games (91A46)

Abstract: In this paper, we study three connection games among the most widely played: Havannah, Twixt, and Slither. We show that determining the outcome of an arbitrary input position is PSPACE-complete in all three cases. Our reductions are based on the popular graph problem Generalized Geography and on Hex itself. We also consider the complexity of generalizations of Hex parameterized by the length of the solution and establish that while Short Generalized Hex is W[1]-hard, Short Hex is FPT. Finally, we prove that the ultra-weak solution to the empty starting position in hex cannot be fully adapted to any of these three games.

Recommendations

• \textsc{Havannah} and \textsc{TwixT} are PSPACE-complete
• A difficulty in particular Shannon-like games
• On the Descriptive Complexity of a Simplified Game of Hex
• On the fairness and complexity of generalized \(k\)-in-a-row games
• The parameterized complexity of positional games

Cites work

• scientific article; zbMATH DE number 1161563 (Why is no real title available?)
• scientific article; zbMATH DE number 2143606 (Why is no real title available?)
• A Combinatorial Problem Which Is Complete in Polynomial Space
• A hierarchical approach to computer Hex
• Dead Cell Analysis in Hex and the Shannon Game
• Deciding first-order properties of locally tree-decomposable structures
• FPT Suspects and Tough Customers: Open Problems of Downey and Fellows
• Finding all solutions and instances of Numberlink and Slitherlink by ZDDs
• Fundamentals of parameterized complexity
• GO Is Polynomial-Space Hard
• Games, puzzles, and computation
• Graph minors. III. Planar tree-width
• Hex and combinatorics
• Hex ist Pspace-vollständig. (Hex is Pspace-complete)
• Improving Monte-Carlo tree search in Havannah
• On the complexity of some two-person perfect-information games
• On the fairness and complexity of generalized \(k\)-in-a-row games
• Parameterized Chess
• Parameterized algorithms
• Parameterized pursuit-evasion games
• Playing games with algorithms: algorithmic combinatorial game theory
• Strong computational lower bounds via parameterized complexity
• The Othello game on an \(n\times n\) board is PSPACE-complete

Cited in

(14)

• The largest connected subgraph game
• The parameterized complexity of positional games
• On the Descriptive Complexity of a Simplified Game of Hex
• Cylinder-Infinite-Connect-Four except for widths 2, 6, and 11 is solved: draw
• \textsc{Havannah} and \textsc{TwixT} are PSPACE-complete
• Complexity of maker-breaker games on edge sets of graphs
• Calculating the Crossing Probability on the Square Tessellation of a Connection Game with Random Move Order: The Algorithm and Its Complexity
• The largest connected subgraph game
• A connectivity game for graphs
• Dead Cell Analysis in Hex and the Shannon Game
• An algorithmic analysis of the Honey-Bee game
• Game connectivity of graphs
• On the fairness and complexity of generalized \(k\)-in-a-row games
• The maker-maker domination game in forests

This page was built for publication: On the complexity of connection games

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