[Beowulf] commercial clusters

[Robert G. Brown]

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:rgb at phy.duke.edu