On Mon, 9 Oct 2006, Richard Walsh wrote:
There are some very subtle things at work here. We are want to fall in love with the countable and not-quite-infinite where our powers have some play between the trivial and unfathomable. This is perhaps because reality seems to be more probably uncountable and infinite relative to those same powers. Playing games, whatever the stripe, is as alluring to the mind as a women's smile is to the heart--we can't help it.
I'm already in love with countability. Either reality is a countable infinity with cardinality similar to the integers or an uncountable infinity with cardinality similar to the reals, where a conjecture of Cantor says there ain't nothin' in between (a problem that probably should be on the list of millenium problems, BTW, although it may be there "by the back door" buried in the P/NP problem). Similarly the halting problem probably belongs there. The Yang-Mills problem and Navier-Stokes problem (IMO) do NOT belong there -- much as I love them as a physicist they aren't really pure math -- might as well ask for a consistent and complete TOE, why stop with Yang-Mills? Why Navier-Stokes when the mathematical world abounds with nonlinear PDEs and complex/chaotic multivariate systems? Games, now, are definitely countable, but may or may not halt (at least, not without a rule for a draw). Thereafter the question is are they P or NP-complete? This in turn is related to the "global vision" problem -- if you have to enumerate all possible outcome trees in order to compute the win, well, that doesn't scale too well. If, on the other hand, there exists any local strategy that "compresses" that tree to guaranteed wins (or maximal opportunities of not losing should the opponent deviate from a winning pathway) without ever enumerating the tree(s), then you MAY gain a scaling advantage. Examples of the latter include e.g. tic-tac-toe, with an obvious symmetry group, so that there are really only three possible initial moves, not nine, and where optimal strategies can be compressed to where the game is "decided" by the first two or three moves followed by a trivial strategy of blocking any imminent win. One IMAGINES that similar compressions exist for variants of Go or Go-Mo-Ku -- clearly the human brain manages some extraordinary things there -- but we are WAY far away from being able to compute them, and chess is still a relatively simple problem in comparison. I have no idea whether or not real compression has been attempted in Go programs. For example, there are certain structures that "naturally occur" in tactical Go play -- ladders, solutions to simple "problems" associated with local piece positions -- that a computer can extrapolate "wholistically" from a suitable library of either precompute sequences or easily computed sequences. In principle a computer can exploit those extrapolated game sequences over long ranges much more rapidly and correctly than a human and use them to guide long range piece placement, without ever attempting a full descent into an outcome tree that includes ALL possible positions. Then there is the possibility of a computer using stochastics and mapping out probabilities instead of deterministic outcomes -- if the computer plays here (strategically) instead of there (locally tactically) the computer will "probably" realize a net territorial benefit when everything is played out. The same sort of thing applies in chess, of course -- humans don't extrapolate the entire tree, only the parts that they deem "likely" to be relevant in the future progression of the game. Sometimes they are mistaken...;-) The point is, computers can do a MUCH better job of computing probabilities than people can, if anyone ever tried writing stochastic game players for zero-sum games that cannot otherwise be computed. All really interesting stuff, and yeah, at least PARTS of it are or are related to very definitely millenium-level mathematics or set theory or computer science problems -- stuff that could legitimately be called HPC even though it may not use a single floating point number. Make it do anything non-deterministic in game play and it even needs those rng's and floating point numbers... rgb -- Robert G. Brown http://www.phy.duke.edu/~rgb/ Duke University Dept. of Physics, Box 90305 Durham, N.C. 27708-0305 Phone: 1-919-660-2567 Fax: 919-660-2525 email:[EMAIL PROTECTED] _______________________________________________ Beowulf mailing list, Beowulf@beowulf.org To change your subscription (digest mode or unsubscribe) visit http://www.beowulf.org/mailman/listinfo/beowulf
