Playing Games with Algorithms: Algorithmic Combinatorial Game Theory

• Published in 2001
• Added on 2018-01-23

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.

Links

• http://arxiv.org/abs/cs/0106019v2
• http://arxiv.org/pdf/cs/0106019v2

Other information

BibTeX entry

@article{PlayingGameswithAlgorithmsAlgorithmicCombinatorialGameTheory,
	key = {PlayingGameswithAlgorithmsAlgorithmicCombinatorialGameTheory},
	type = {article},
	title = {Playing Games with Algorithms: Algorithmic Combinatorial Game Theory},
	author = {Erik D. Demaine and Robert A. Hearn},
	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.},
	comment = {},
	date_added = {2018-01-23},
	date_published = {2001-04-10},
	urls = {http://arxiv.org/abs/cs/0106019v2,http://arxiv.org/pdf/cs/0106019v2},
	collections = {Basically computer science,Games to play with friends,Combinatorics,Computational complexity of games},
	url = {http://arxiv.org/abs/cs/0106019v2 http://arxiv.org/pdf/cs/0106019v2},
	year = 2001,
	urldate = {2018-01-23},
	archivePrefix = {arXiv},
	eprint = {cs/0106019},
	primaryClass = {cs.CC}
}