🚀 go-pugleaf

In article <CONVERSE.92Sep27022106@sloth.uchicago.edu> converse@cs.uchicago.edu (timoshenko) writes:

   Here are the rules of Integer-chess:

      Assume that X is some odd number that is greater than the number of possible 
      chess positions.  (say 10^200+1, if that is in fact large enough).

	   1) White starts the game by choosing some number greater than
      0 and less than or equal to X.

	   2) Thereafter, players alternate in choosing integers which
      are greater than 0, and less than or equal to X.  No number that
      has been chosen once by either player can be chosen again.

	   3) Either player wins if:
	       3a) if he or she chooses a number which is less than a number
			previously chosen by the opponent, or if
	       3b) the opponent cannot make a legal move

   [..]
   Since the "game-tree" of this game is as large as that of chess, the 
   optimal game cannot be practically played by (dumb) game-tree search (ii).
   It's also true that its game-tree is finite, so it is theoretically
   solvable (i).  Finally, it should be clear that optimal Integer-chess
   _can_ be practically played.  

Whoops, a follow-up correction:  The optimal strategy I gave before
probably cannot be practically played, since it results in _extremely_
long games.  :-)  But I think that is easily addressed by making the
smart strategy result in short games.  For example, set X = 2^300, and
replace rule (3) with

	   3) Either player wins if 
		1) he or she chooses a power of two which is less than the
                      opponent's previous move, or if
		2) he or she chooses a power of two, when the
                      opponent's previous move was not a power of two.
     
Optimal play:
	White:  1
	Black:  2
	White:  4
	Black:  8
	[..]
	White:  2^300
	Black: concedes

	The point is just that the tree of legal games is _very_
large, yet an optimal strategy is clear.

	--tim


--
-------------------------------------------------------------------------------
Tim Converse  U. of Chicago CS Dept.  converse@cs.uchicago.edu  (312) 702-8584