Havannah and TwixT are PSPACE-complete

DOI10.1007/978-3-319-09165-5_15zbMath1444.91049OpenAlexW2145500551WikidataQ55891786 ScholiaQ55891786MaRDI QIDQ2947922

Florian Jamain, Abdallah Saffidine, Édouard Bonnet

Publication date: 29 September 2015

Published in: Computers and Games (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-09165-5_15

zbMATH Keywords

complexityHavannahconnection gamesabstract strategy gamesTwixT

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Combinatorial games (91A46) Algorithmic game theory and complexity (91A68)

Cites Work

• Unnamed Item
• Unnamed Item
• On the complexity of connection games
• Hex ist Pspace-vollständig. (Hex is Pspace-complete)
• On the complexity of some two-person perfect-information games
• Improving Monte–Carlo Tree Search in Havannah
• Dead Cell Analysis in Hex and the Shannon Game
• Playing Games with Algorithms: Algorithmic Combinatorial Game Theory
• GO Is Polynomial-Space Hard
• A Combinatorial Problem Which Is Complete in Polynomial Space
• A hierarchical approach to computer Hex

This page was built for publication: Havannah and TwixT are PSPACE-complete