[net.puzzle] TWO PLAYER GAMES

qts@houxa.UUCP (J.RAMMING) (02/24/86)

In many games (see my 'pennies puzzle' posting) it is not immediately
obvious that a particular player has a winning strategy.  However,
there may be certain games in which it is immediately clear that a 
particular player DOES NOT have a winning strategy.

Puzzle:  Examine the following proof about two player games.
	 Which condition(s), if any, must exist in order for it to 
	 be valid?  If these conditions exist, cite a game or
	 class of games to which this proof applies.  

	 Alternately, consider the possibility that there is a
	 flaw in the proof.

Proof:   1)  Assume that the second player has a winning strategy.
	 2)  Then clearly, the first player should make a random move.
	     He can then win if, for the remainder of the game, he
	     follows the second's players winning strategy.  
	 3)  This is a contradiction, therefore assumption (1) is 
	     false.  We conclude that THE SECOND PLAYER DOES
	     NOT HAVE A WINNING STRATEGY.

J. Christopher Ramming

UUCP:  decvax!bellcore!houxa!qts
HOME:  (201) 542-2079
WORK:  (201) 949-9531

dsr@uvacs.UUCP (Dana S. Richards) (02/27/86)

> Puzzle:  Examine the following proof about two player games.
> 	 Which condition(s), if any, must exist in order for it to 
> 	 be valid?  If these conditions exist, cite a game or
> 	 class of games to which this proof applies.  
> 
> Proof:   1)  Assume that the second player has a winning strategy.
> 	 2)  Then clearly, the first player should make a random move.
> 	     He can then win if, for the remainder of the game, he
> 	     follows the second's players winning strategy.  
> 	 3)  This is a contradiction, therefore assumption (1) is 
> 	     false.  We conclude that THE SECOND PLAYER DOES
> 	     NOT HAVE A WINNING STRATEGY.
> 
The usual answer to the question is Positional Games: games
where pieces are placed, not moved, and a win results if a configuration
appears at some point.  For example, getting 5-in-a-row is such game,
but getting exactly five is not (since having the configuration appear
is not sufficient.)  Alternatively, having an extra piece on the board
cannot hurt you.
The pennies game is not really a positional game, hence a better
explanation should be forthcoming.