🚀 go-pugleaf

I've made another posting on this topic that makes a similar point, but 
I hope that this one will be more fun.

There have been a number of posts about the solvability of chess that
argue that:

	i)  chess is theoretically solvable (i.e. assuming no time or
memory limitations, a computer could play perfect chess, simply by
exhaustive search of the game tree).

	ii) chess is practically insoluble (i.e. given what we know
about physics and the size and age of the universe, exhaustive search
of the game tree cannot be done).  

The corollary that is usually implicitly drawn is:

	iii) optimal chess cannot practically be played.

I would like to propose a game that is similar to chess in both (i)
and (ii) above, but that can practically be played optimally.   
Call it, um, Integer-chess.

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

Here is a game of Integer-chess, played optimally by both sides:

	White:  1
	Black:  2
	White:  3
	Black:  4
	[..]
	White:  X
	Black:  (concedes)

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.  

My question is:  how can we conclude that (iii) is true of chess if it
is not true of Integer-chess?

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