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
      0 references
      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

      Identifiers

      0 references
      0 references
      0 references
      0 references
      0 references
      0 references