🚀 go-pugleaf

tao@ginger.princeton.edu (Terry Tao) writes:
>[original chess is solvable, but...]
>... simultaneous chess though, is much more tricky.  Obviously, by symmetry,
>there is no dead certain winning strategy by White or Black, otherwise you
>just play it against itself and get a contradiction.  Thus, for any strategy
>X, there exists a strategy Y such that the chance of X winning against Y is
>the same as the chance of Y winning against X.  Proof: take Y=X.  Hence,
>there is no strategy that is superior to everything, but maybe it is
>superior against every strategy NOT identical to itself.

What's this "chance" showing up in the game?  I was under the
impression chess, whether taking turns or simultaneous, was
deterministic.  Or are we assuming each player's strategy is
randomized?  If so, I believe it's a theorem that if there is an
optimal randomized strategy then there is one with distribution
[0,0,0,...,1,0,0,0...], i.e. not actually using the randomness.
(This is illustrated, though not proven, in the following paragraph.)

However, there is a problem when you introduce simultaneity.  (Gee, I
started this post intending to show that there WASN'T...)  Suppose we
simplify the rules immensely to a one-round game in which each player
outputs a bit; I win if they're equal, the other player wins if
they're not.  If I have no knowledge of my opponent's strategy, and
if (for example) I assume a uniform distribution over {0,1}, then no
strategy is any better than any other for me.  (Using randomness
myself would neither help nor hurt.)  On the other hand, if I assume
anything other than a uniform distribution in what my opponent is
doing right now, my optimal strategy is obvious: do (with probability 1)
whatever I think my opponent is most likely to do.

But in either case, the "value of the game" is not only not solvable, but
not even well-defined since there is no strategy to force a win or a draw
by EITHER player.  The same is almost certainly true of simultaneous
chess; I leave it to the chess players to construct a situation in
which I can choose move A or B, my opponent can choose move C or D,
and I can force a win in cases (A,C) and (B,D) while my opponent can
force a win in cases (A,D) and (B,C).

The non-recursion-theorists in the crowd will now be saying "so
because you can't solve it, you declare it to be undefined."  Not so.
The classic example of a "game" whose outcome is well-defined but not
computable is the Turing halting problem, which I suspect can be
framed in chess terms: you have an infinite board on which are some
finite (but variable from game to game) number of pieces, there are no
3-repetitions or 50-move rules, and the question is "can either player
force a win or a stalemate, or will the game go on forever under the
assumptions that both players prefer continuing the game to losing?"
(I haven't checked for sure that the halting problem is reducible to
this, but I think it is.)

-- 
					Stephen Bloch
				sbloch@silver.cs.umanitoba.ca