Provably Difficult Combinatorial Games (Q3854623)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 3655350
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Provably Difficult Combinatorial Games |
scientific article; zbMATH DE number 3655350 |
Statements
Provably Difficult Combinatorial Games (English)
0 references
1979
0 references
combinatorial game
0 references
completeness in exponential time
0 references
perfect information
0 references
decision problem
0 references
propositional formulas
0 references
moving markers on a graph
0 references
diagonalization
0 references
polynomial-time reducibility
0 references
This paper investigates the computational complexity of two-person games of perfect information. In particular, it considers the number of computational steps required to decide whether a designated player has a strategy that leads to a win from a given starting position, no matter what strategy the other player uses. Here, the computation time is measured as a function of the size of the starting position. For many games it is known that exponential time is sufficient, and this paper exhibits games for which exponential time is necessary, at least for infinitely many starting positions. The games for which this decision problem is proved to require exponential time are not natural games such as chess, but rather, games devised to illustrate the proof methods. Some of these games are played using propositional formulas. The players move by changing the truth values assigned to certain variables and the winner is, for example, the player who first makes the formula true. Another game considered in the paper is a type of blocking game played by moving markers on a graph. This game is played on an undirected graph where each edge is colored by one of three colors. Each player has a collection of markers that are placed initially on certain nodes of the graph. Certain other nodes are designated as goal nodes for one player or the other. At each move, a player can move one of his markers from one node to another provided that (i) all edges traversed during the move are of the same color, and (ii) all nodes traversed during the move are free of markers. The winner is the first player to move one of his markers to one of his goal nodes. The basic method used to prove that these decision problems require exponential time is a combination of diagonalization and polynomial-time reducibility; this is the same method used by Meyer, Fischer, Rabin and others to prove lower bounds on the complexity of decision problems in logic. Another tool useful in the application of this method to games is the alternating Turing machine that was introduced by Kozen and the authors.
0 references