A difficulty in particular Shannon-like games

A difficulty in particular Shannon-like games

0.00 Avg rating0 Votes
Article ID: iaor19911655
Country: Netherlands
Volume: 30
Issue: 1
Start Page Number: 87
End Page Number: 90
Publication Date: Jan 1991
Journal: Discrete Applied Mathematics
Authors:
Abstract:

There is a simple theory of strategy for generalized Shannon switching games (on edges). This theory naturally gives an algorithm of polynomial order. On the other hand Reisch states the PSPACE completeness of judging who can win in all the positions of Hex. The purpose of this paper is to discuss the difficulty not of a class but of each particular game. It will be seen that any strategy theory of a certain type cannot be applied either to Hex of 42 vertices or to a certain 3-pair game, though it can be applied to all 2-pair games. Here, an n-pair game is a game played on the edge set of a graph where a designated player intends to connect at least one of the given n pairs of terminals.

Reviews

Required fields are marked *. Your email address will not be published.