[Beowulf] Go-playing machines

[Vincent Diepeveen]

Yes i realize very well what you mean Robert, though i partly agree
the problem is 2 fold:

a) i don't get paid to do it, if one were part of an university that  
is different

b) having a chessprogram i'm used to hear wrong information all the  
time,
games are so so popular, everyone likes to do statements about game  
tree search,
ANN's, GA's, Monte Carlo, automatic parameter tuning and whatever  
falls under
my Artificial Intelligence expertises; if i would try to correct it  
all that is more than a fulltime job.
Just correcting the nonsense that Thesis spit as being the truth, is  
already total impossible.

To give a popular example of misconecption in Thesis,
not a single world top engine can use the MTD algorithm from Aske Plaat,
as it is worse than other forms of search. In fact it is that bad,  
that the difference in playstrength is
real huge. Most use something like PVS or some windowed form of  
alfabeta as the starting algorithm.
Difference between windowed forms of alfabeta versus PVS is hardly  
measurable for some programs,
but the difference with MTD is so huge, that a program plays  
significantly worse using it; it is pretty easy also to know why.
I've listen on the net several times a few arguments why MTD performs  
so bad, yet Aske moved from Netherlands
to the institute "MiT", so they keep quoting him. I could quote tens  
of things like that. Fact is i'm not paid to publish
articles.

A minimal TV crew was here in my backyarden (1 cameraman also doing  
sound and a reporter),
their TV channel a tiny one (RTV),
but they had plans also to sell it to National Geographic. As usual a  
very stubborn
setup they wanted to show thing X and were not interested in all kind  
of interesting
things Y, which IMHO is more interesting to show the audience; i'd  
argue for a reporter
doing this type of documentary it is far better to start interviewing  
and while interviewing
you hear from the experts such interesting stuff that you can make a  
far better documentary
with more relevant questions; so letting experts talk rather than the  
reporter, which defines the
typical reporters problem. It is this reporters problem that causes a  
lot of nonsense to get spit
into the ether.

They started spitting information they had been given by other  
persons (a professor).

Now Jaap van den Herik, didn't do too bad there actually.

Relevant for this mailing list is this piece of information they had  
for processing power.

The quote i got from them being more or less:

"chess has more than 10^40 positions, that is more than there is  
particles in planet earth,
so processors can never get that amount of calculation power,  
therefore it is impossible to create the unbeatable player in chess".

Realize this is from someone who decides also on what the next  
supercomputer of Dutch Government is gonna be for scientists.

The above statement is wrong for several reasons. Regarding the  
number of particles that are in planet earth,
i'll skip that discussion. I'm no expert on that, so i cannot do a  
statement there.

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.

     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.

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
>