[Beowulf] Go-playing machines
diep at xs4all.nl
Wed Jun 25 06:02:52 PDT 2008
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
b) having a chessprogram i'm used to hear wrong information all the
games are so so popular, everyone likes to do statements about game
ANN's, GA's, Monte Carlo, automatic parameter tuning and whatever
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
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
setup they wanted to show thing X and were not interested in all kind
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
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
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
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
>>> wikipedia article(s) with examples that contradict it, but the
>>> mathematics and difficulty of pruning the Go trees suggest that it
>> See above for disproof of that.
> Very educational and interesting. But I was also serious -- if you
> (and it sounds like you can) you should consider editing the wikipedia
> I'm not COMPLETELY convinced -- I'll be a lot more convinced when I
> get a GPL Go engine that will play a decent game on my laptop...;-)
> 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
More information about the Beowulf