[Beowulf] Go-playing machines

Wed Jun 25 07:39:49 PDT 2008

You raise an interesting question there, which is: "how are humans  
doing it".

When i discussed this recentely with a brain researcher (so the type of
researcher that really puts brains in a 3-Tesla MRI scanner) i also  
quoted the
old fashioned theories as that the brain works at like 12Hz.

His answer was very surprising (apologies to not know the English  
word for
it) that the central part at where all the brain cells connect to, is  
at far higher
speed than what i assumed it is taking decisions. Something in the order
of 200 kHz to 400 Mhz. The thing unknown in how it exactly works to  
researchers
is this high speed central nerve system.

Thousands of times faster than i assumed it worked at, which was my  
big surprise.

If we multiply that speed by a few billion brain cells then obviously  
we should revisit
our idea on how the brain works. Maybe a new entry in wiki is needed  
for them as well :)

As for the 1000^3 cube, there is of course a lot of searching  
algorithms that are yet there
waiting for us to get invented. Simple ideas sometimes work rather  
well when combined
with a few others.

The classical example open to invention still is multiplication of  
big numbers and matrix calculations;
to avoid questions there and zoom in: if it is possible to first do  
some slow conversion to fourier space, then
multiply it there and then convert it back to radix2, obviously it is  
also possible to have a direct O (n log n)
algorithm that can achieve a bigger throughput of bits per limbs  
multiplied.

The real fundamental problem there has more to do with: "what do  
companies pay for".
Companies hardly ever pay for research, they let government pay for  
that in general.
Companies are there to produce products and earn on them. Any form of  
research objectively
seen therefore is overhead unnecessary, where they only invest in  
when it is absolutely necessary.

Additionally most departments of universities where sometimes a few  
PHD's are doing research,
they have little experience yet in their field. Fields are so  
advanced nowadays, it not seldom takes 10 years to
master it. Most professors are fulltime busy with meetings and have no
time to even keep up with the latest theories and developments in  
their fields.

The number of persons that really can do research therefore is really  
limited and fundamental research like
investigating new manners of doing a matrix calculation more  
efficient, is hardly getting sponsored,
even when there is a direct military reason to do so.

As i figured out the hard way, first proving you can do better than  
other scientists and THEN asking for funding,
is not clever either.

So to get back on the original brain question: "how are humans doing it"
My answer is that the majority messes up so bigtime, that it is  
unclear how *some* are doing it.

Vincent

On Jun 25, 2008, at 4:10 PM, Robert G. Brown wrote:

> On Wed, 25 Jun 2008, Vincent Diepeveen wrote:
>
>> Chess has indeed more than 10^40 positions. Latest mathematical  
>> calculation as published in ICGA journal came to 10^43.
>>
>> There is 2 points:
>>   a) playing the best move doesn't require searching the entire  
>> search space,
>>        so who knows maybe searching 10^18 nodes with a huge  
>> hashtable and good evaluation function,
>>        we might already play the best move.
>
> :-) That's true and funny at the same time.  "Only" 10^18  
> positions, at
> "only" a nanosecond each takes "only" a gigasecond, which since a year
> is \pi x 10^7 seconds IIRC, is "only" around \pi x 10 Gigasearch- 
> years.
>
> It is a difficult problem, in other words.  It's what makes it fun, I
> suppose.  And equally obviously, human brains don't work anything like
> this way on it.  To me it is more fun to speculate on how the human
> brain does it WITHOUT anything like the capability to process
> giga-giga-trees.  It clearly prunes things down to some much more  
> finite
> order extremely quickly by discarding nearly all of this space from  
> the
> beginning, and YET the space that remains is often the good one to the
> best that even Big Blue can parse out otherwise.
>
>>   b) To get to 10^43 calculation power, we do not need a processor  
>> that exists out of 10^43 particles. All we need is
>> a processor that is hosting 10^43 internal movements, which is a  
>> lot easier to get acomplished, than building that
>> cpu of 10^43 in size.
>
> I'm not sure what you mean by that.  All silicon processing has the
> usual serial and parallel components and accomplishes work (per
> processor) with a gigahertz scale serial barrier, leaving it many,  
> many
> orders of magnitude short even in parallel. Yes, neural network
> processing in the brain has way fewer (maybe 10^11) neurons, but each
> neuron has thousands of synaptic connections to other neurons and the
> network formed has staggering complexity.  Big enough that the chess
> problem could actually fit in its entirety inside with room enough for
> the go problem left over.  And still be nearly "empty", and work
> in an extremely parallel fashion.
>
> There aren't a whole lot of candidate architectures for a parallel
> processing system that can do this sort of thing, but I agree that  
> this
> is "all" we need.  It's just not terribly easy to accomplish, because
> the problem is hard (and fun).
>
> One encounters numbers that scale like this in physics (stat mech)  
> quite
> often, actually.  If you work out the states in e.g. Monte Carlo
> sampling of a very simple 100x100x100 simply cubic Ising ferromagnet
> lattice (where each site contains a spin that can hold one of two
> states) the number of states in the system is 2^(1,000,000).  This  
> is "a
> big number" at least at first glance.
>
> If one then traces through "moves" through the system from any given
> starting state through all the various intermediary states to all the
> possible final states, one creates a space with e.g. [2^1000000]^N
> configurational trajectories for N steps.  Ooo, maybe THAT is a big
> number, at least if N is reasonably large (say, a few thousand).
>
> Out of all of those states, a MUCH MUCH SMALLER set of states  
> represents
> the only ones that are "likely" to be seen if the system is in
> equilibrium at any given temperature.  How to find this needle in a  
> very
> "large" (and yet tiny -- we're talking a mere million atoms when
> physical systems big enough to see contain, um, a lot more than  
> this and
> have continuous spins instead of discrete ones) haystack?
>
> Importance sampling Monte Carlo lets you discard nearly all moves in a
> Markov process that takes you from any starting configuration to the
> "relevant" part of phase space rather quickly (considering) and then
> samples that space effectively.  It rejects far, far, far more states
> than there are particles in the Universe with a metaphorical  
> "sniff" as
> being absurdly unlikely and homes right in on the likely suspects.
>
> I think that this is a much better model, or metaphor, for how humans
> think than search trees.  Humans really suck at search trees, with  
> their
> fundamentally serial attention focus and conscious processing speed
> measured in tens of transactions per second on a good day.  We  
> excel at
> "intuition", at the instantaneous parallel pruning of enormous  
> spaces to
> the relevant part.
>
>    rgb
>
>>
>> In technical areas that people like to hear about, it is  
>> impossible as a single person to fight unpaid all the desinformation.
>> The biggest problem there is professors who seek publicity, or  
>> cover up for total nonsense thesis of their students.
>>
>> I tried to have some sort of discussion with Jonathan Schaeffer  
>> about a student of him quoting MTD is ok in his thesis.
>>
>> What i skipped in fact is the total nonsense about parallel  
>> speedup in game tree searching from his student idea being:
>> make the most inefficient searcher on planet earth, then  
>> parallellize it and of course because even random move orderings
>> would improve your program then, also the parallellism gets a  
>> decent speedup as a result of all that inefficiency;
>> the classical approach.
>>
>> Also MiT is notorious bad in game tree search.
>>
>> I will give yet 1 more example.
>>
>> I remember they claimed in articles a great speedup (50% or so  
>> even) in game tree search at supercomputers.
>>
>> Now my chessprogram has a lot of chessknowledge and also is doing  
>> all sorts of mobility, which requires expensive
>> scans. That slows down the nodes per second that my chessprogram  
>> Diep can get.
>>
>> The search frame from MiT slows down the searchspeed of their  
>> chessengine by a staggering factor 40.
>>
>> At the same SGI Origin3800 hardware in fact my slow Diep engine  
>> gets MORE nodes per second, and a lot more,
>> than MiT's cilkchess chess engine.
>>
>> Not because single core mine is any faster. In fact single core  
>> cilkchess without cilkframe used to be factor 20.
>>
>> Additionally there is nowhere anything statistical significant  
>> done there. All speedups of supercomputers are never carrying
>> a table with what is its speedup with 95% sureness.
>>
>> Doing publications just to show how it should be done and disprove  
>> and prove a number of algorithms (especially disprove nonsense),
>> is already quite a tough challenge and i can be busy for years  
>> there, as there is hundreds of such publications, just from the  
>> past few
>> years to disprove and show the better alternative.
>>
>> It's a technical science, there is not many who really are expert  
>> there, progress goes *real* fast.
>>
>> In the end what matters for engines is not how strong it plays  
>> against you, it matters how strong you play against competitors :)
>>
>> On Jun 25, 2008, at 7:14 AM, Robert G. Brown wrote:
>>
>>> On Wed, 25 Jun 2008, Vincent Diepeveen wrote:
>>>>> one player's position -- or one of those distant pieces placed  
>>>>> early in
>>>>> the game -- causes their entire effort to "unravel" and turn  
>>>>> into a
>>>>> disaster.  That's almost twice the number of plys in an entire  
>>>>> chess
>>>>> game, and is still only the first third or so of the game.
>>>> See above for correct calculation.
>>>>> If you or your friend disagree with this, well, feel free to  
>>>>> edit the
>>>>> wikipedia article(s) with examples that contradict it, but the
>>>>> mathematics and difficulty of pruning the Go trees suggest that it
>>>>> isn't.
>>>> See above for disproof of that.
>>> Very educational and interesting.  But I was also serious -- if  
>>> you can
>>> (and it sounds like you can) you should consider editing the  
>>> wikipedia
>>> articles.
>>> I'm not COMPLETELY convinced -- I'll be a lot more convinced when  
>>> I can
>>> get a GPL Go engine that will play a decent game on my laptop...;-)
>>>
>>>   rgb
>>> -- 
>>> Robert G. Brown                            Phone(cell):  
>>> 1-919-280-8443
>>> Duke University Physics Dept, Box 90305
>>> Durham, N.C. 27708-0305
>>> Web: http://www.phy.duke.edu/~rgb
>>> Book of Lilith Website: http://www.phy.duke.edu/~rgb/Lilith/ 
>>> Lilith.php
>>> Lulu Bookstore: http://stores.lulu.com/store.php?fAcctID=877977
>>
>
> -- 
> Robert G. Brown                            Phone(cell): 1-919-280-8443
> Duke University Physics Dept, Box 90305
> Durham, N.C. 27708-0305
> Web: http://www.phy.duke.edu/~rgb
> Book of Lilith Website: http://www.phy.duke.edu/~rgb/Lilith/Lilith.php
> Lulu Bookstore: http://stores.lulu.com/store.php?fAcctID=877977
>