From: woodstck@hal.com (Nathan Hess)
Newsgroups: rec.games.go,rec.games.chess,rec.games.board,rec.games.programmer
Subject: Re: Strategic games, computational cost & implications
Date: 26 Aug 92 16:02:17 GMT
Reply-To: woodstck@hal.com (Nathan Hess)
Organization: HaL Computer Systems, Inc.; Campbell, CA
NNTP-Posting-Host: nest.hal.com

Forwarded message for Howard, who doesn't have USENET access:



doshay@ursa.arc.nasa.gov (David Doshay) wrote:
>The computational complexity of a game is normally taken to be the number
>of possible games.

This has almost no relation whatsoever to normal measures of computational
complexity, which talk about FAMILIES of games (e.g. Go on NxN boards).
NxN Go and Hex were easily proved to be at least PSPACE-hard; NxN Chess has
also been proved PSPACE-hard (with some difficulty, and making up of rules).
Last year there were rumors that NxN Go had been shown to be EXPTIME-complete
through a devious construction involving massive numbers of kos, but I haven't
seen the proof so I can't comment further.  It's certainly clear that, due to
kos extending the length of the game, it is not trivial to prove that Go is
even *in* PSPACE (it would not be if the maximum length of a game was not
bounded by a polynomial in the board size).  Hex is clearly in PSPACE, and
thus is PSPACE-complete.  The same is true for Chess if the extended draw rule
is that after a number of moves equal to the boardsize the game is drawn.

The difficulty with even THESE criteria, rigorous as they are, is shown by the
case of Bridg-It.  NxN Bridg-It is PSPACE-complete, if you consider it to be
the problem of solving arbitrary full-board problems.  However, NxN Bridg-It
is also solveable in linear time and space (or perhaps O(Nlog(N)) time if memory
accesses take logarithmic time in the address size), if considered as the
problem of playing a full game starting from an empty board, due to a trivial
pairing strategy.  So the fact that arbitrary board situations can be extremely
difficult to solve means NOTHING about the complexity of playing a game from
an empty board.  Go could be extremely easy.  If you don't believe me, just
consider Go with Black getting 5 points of komi and being allowed to play
mirror Go.

>for Go the number is close to 361! ... You could say it is smaller by 4! or
>maybe 8! because of symmetery in the board

The board symmetry reduces it by something like 8, not nearly 4! or 8!.  The
first move is less than 8 because not all points have 8-fold symmetry - some
have only 4-fold (and one has only 1-fold).  On the other hand, a few moves
still have some symmetry after the first move (e.g. 3-3, 3-10, 10-10), which
pushes it up a little (less than a factor of 2); but these are precisely the
moves which had less than 8-fold symmetry in the first place.  Since all games
eventually become asymmetric, this means that all these factors must work out
to give an exactly 8-fold reduction when taken together.

Move sequence reconvergence of k moves could lead to a division by k!, if you
count positions with the same stones but different histories as the same (it
might NOT make sense to do so under the generalized ko rule, for example).  In
that case, after 20 moves you would have something over 361! / (341!*20!) or
"361 choose 20" positions (the excess is due to capturing sequences where order
matters).  The peak of this is around k=180, for which "361 choose 180" / 8
gives a lower bound to the number of possible positions even factoring out
board symmetry.  However, this is less than 361! by a factor of 181!*180!*8,
which is not what I would call "close".

I find such trivial approaches as counting games or positions to be rather
pointless.  There are real, VITAL questions here which are much deeper and
more important.  My own hot button at the moment:

	(1) Laura Yedwab showed in her MIT master's thesis that a certain
	    endgame subset of Go was PSPACE-complete, or more accurately,
	    that such a subset PLUS one simple game that she was not able
	    to embed in a Go situation were PSPACE-complete.

	(2) PSPACE-complete problems are generally considered to be a quantum
	    level of difficulty harder than NP-complete problems, which are
	    already too hard to solve easily.  So we should expect that Yedwab's
	    game would be extremely difficult.

	(3) However, she also showed that there is an approximation strategy
	    that gets within a fixed amount of the optimum, and is trivial to
	    compute, for arbitrarily large games.  In fact, the more complex
	    the game, the better (proportionally) the strategy does.

Now, the above is not a paradox - we know that for some hard problems, it is
only hard to get the exact answer, but getting within (say) 5% may be easy.
However, most results of this nature are for NP-complete problems.  It is a
little surprising to find a PSPACE-hard analog, and leads to speculation that
game-theoretic approaches to PSPACE-hard problems might (as a side benefit)
yield excellent approximate algorithms for some of the classic NP-complete
problems as well.  I would welcome more research in this area, but don't have
much time for it myself right now.  PhD candidates in CS theory take note ...

	Howard A. Landman
	landman@xpoint.com
Newsgroups: rec.games.go