Playing Games with Algorithms: Algorithmic Combinatorial Game Theory

Details Playing Games with Algorithms: Algorithmic Combinatorial Game Theory Playing Games with Algorithms: Algorithmic Combinatorial Game Theory

2001-06-11

arxiv.org/abs/cs/0106019v2

Computer Science

Computational Complexity

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

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Playing Games with Algorithms: Algorithmic Combinatorial Game Theory does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Playing Games with Algorithms: Algorithmic Combinatorial Game Theory, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Playing Games with Algorithms: Algorithmic Combinatorial Game Theory will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-560475