On the complexity of connection games

DOI10.1016/J.TCS.2016.06.033zbMATH Open1371.91027arXiv1605.04715OpenAlexW2397940737MaRDI QIDQ307770FDOQ307770

Authors: Édouard Bonnet, Florian Jamain, Abdallah Saffidine 

Publication date: 5 September 2016

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

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.

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

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

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)

Cites Work

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

Cited In (14)

• Dead Cell Analysis in Hex and the Shannon Game
• Cylinder-Infinite-Connect-Four except for widths 2, 6, and 11 is solved: draw
• \textsc{Havannah} and \textsc{TwixT} are PSPACE-complete
• The largest connected subgraph game
• The largest connected subgraph game
• The parameterized complexity of positional games
• Game connectivity of graphs
• A connectivity game for graphs
• An algorithmic analysis of the Honey-Bee game
• On the Descriptive Complexity of a Simplified Game of Hex
• 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
• 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)