Playing Games with Algorithms: Algorithmic Combinatorial Game Theory

Abstract

Combinatorial games lead to several interesting, clean problems in algorithms and complexity theory, many of which remain open. The purpose of this paper is to provide an overview of the area to encourage further research. In particular, we begin with general background in Combinatorial Game Theory, which analyzes ideal play in perfect-information games, and Constraint Logic, which provides a framework for showing hardness. Then we survey results about the complexity of determining ideal play in these games, and the related problems of solving puzzles, in terms of both polynomial-time algorithms and computational intractability results. Our review of background and survey of algorithmic results are by no means complete, but should serve as a useful primer.

42 pages, 18 figures. Major revision to survey, and new author. To appear in Games of No Chance III

Cited by in corpus (15)

• A simple proof that the $(n^2-1)$-puzzle is hard
• Gaming is a hard job, but someone has to do it!
• Token Swapping on Trees
• Yin-Yang Puzzles are NP-complete
• Phutball is PSPACE-hard
• Pomax games - a family of partizan games played on posets
• Threes!, Fives, 1024!, and 2048 are Hard
• Lemmings is PSPACE-complete
• Hanabi is NP-hard, Even for Cheaters who Look at Their Cards
• Dots & Boxes is PSPACE-complete
• PSPACE-Complete Two-Color Placement Games
• $2^3$ Quantified Boolean Formula Games and Their Complexities
• Two-Player Tower of Hanoi
• The combinatorial game nofil played on Steiner Triple Systems
• Computational Properties of Slime Trail