Computer Chess Club Archives


Search

Terms

Messages

Subject: DIEP parallel in Paderborn - technical and detailed story

Author: Vincent Diepeveen

Date: 15:19:59 06/28/99


>But - to come back to your program vince (or is this now OFF-TOPIC here >?!?!:-))
>what has happened to diep from your point of view vince ?
>Can you give me a report about diep in paderborn from your point of
>view as an operator ?!Would be interesting for me...or email me ...

Yes, what happened to DIEP.

Well, very important to mention is that just 2 days before
paderborn started i finally had a DIEP version that didn't crash
instantly parallel under linux.

So i didn't have time for a lot of things.
To list them
   - improving endgame
   - testing the new search
       - a few weeks before paderborn i rewrote a lot of things,
         and i'm still rewriting it. To list things i rewrote or changed:
             - move ordering
             - hashtables
             - selective searching
             - forward pruning
             - qsearch
            So in short everything that has to do with the search. Just before
            paderborn i tested the hashtable changes very well, as i
            had bad experiences with that.
   - testing the linux version (this would break me this tournament)
      bugs known to me:
         - sometimes it crashes
         - it might get a deadlock
         - bugs in extensions. i knew there were bugs in diep extensions,
           as extensions were only made for single cpu.
   - egtb from nalimov not added
   - no tournament book improvement, the huge book did improve a little though
   - operator mistakes. linux version allows a lot of faults
   - bugfixing some known faults in evaluation. problems of
     current middlegame evaluation
        - it knows shit about closed positions
        - it prefers too much a knight above bishop, because in
          end of 98 i had added a lot of knight bonusses without
          tuning, so it prefers quite quickly a knight over a bishop

A major problem in tournaments is programs getting hung. If you get
hung but cannot prove it's hung then you're smoked. Example: if a program
prints: "i'm hung", then it's obviously hung and you are allowed to
reboot. If a program just does nothing, then it will simply forfeit.

At the day the tournament started i improved my process monitor.
Every few seconds i could see now whether diep had a deadlock, which
would allow me prove that it was hung, and therefore i could reboot it.

Already few weeks before paderborn i noticed the extension problems.
The extensions were using some global arrays, and that's kind of tough
in the parallellism i use (which is an improved cray blitz version).

So i turned all extensions off, except for the check extension and
the normal qsearch extensions.

I simply decided i didn't need them in paderborn anyway, as i would
run at the quad xeon 400Mhz from Hyatt, university of Alabama.

Compared to previous hardware 4x400Mhz Xeon kicks butt. 4x400 = 1600Mhz Xeon,
and Xeon is way faster for my DIEP than PII. Secondly i could use 450mb
memory for hashtables at the Xeon.

As evaluation is so awful slow in DIEP (or to put it in Frans Morsch words:
"wasting clocks") very important for me is to store it in hashtable.
In combination with some 8 probes this bigger hashtable really helps
DIEP a lot.

The speedup of the 4x400Mhz xeon with 450Mb hash compared to
a PII-450 NT is about 5 times for DIEP, as the speedup of 4 processors
for DIEP is 4.06 . The more difficult a position is the
bigger the speedup. Speedups over 10 times at 4 processors are not an
exception for DIEP. Now this is theoretical not possible will some say.
Dead wrong. It is.

I'm using nullmove! My fliprate (chance that <= alfa node becomes
>= beta) is less than 1% and the chance that
first move gives a cutoff is just 80%. I can of course improve the
chance that first move gives a cutoff, but then still my speedup is 4.0
as i never split in cutoff nodes (i split in alfa nodes) and
the chance that near the root a node appears to be a cut node is
way less than 1% (and the more near the root the bigger this chance).

So far the history before paderborn. To be sure that i wouldn't get
big disasters in Paderborn i ran the last 2 days my DIEP fulltime at the
icc. It didn't do bad at the internet at all at 4 processors. It
was very stable and didn't blunder. So it seemed.

Afterwards i regret like hell that i didn't test at 40 in 2 level with it
by hand.

That was kind of impossible however, just 2 days before paderborn...


                 THOUGHTS ABOUT THE HOLES IN DIEP

It took till just before paderborn that i started worrying about the bad
health in which DIEP was. As i would search 14 or 15 ply anyway i didn't
care much about lacking extensions.

Before Round 1.
The firewall in alabama where my machine is
was set to my provider xs4all.nl

I pay a lot of money to xs4all.nl (so do Frans Morsch and Ed Schroeder).
xs4all.nl has a big advantage above most providers: it's fast to the
USA where my computer is. I pay big money to get to Paderborn (hotel, car).
I pay big money to enter the tournament (200 guilder or $100).

I SPENT 6 MONTHS TO GET MY PROGRAM TO RUN PARALLEL AT N PROCESSORS
FROM WHICH I NEEDED ALREADY 3 MONTHS TO GET IT TO WORK PARALLEL UNDER LINUX.

Bob did everything to set up the machine perfect. I'm not sure what time
it was in the United States the day before when we tested it, but
it must have been 3 AM there.

The Xeon worked brilliant, so it seemed (the day before).

Then it gets monday. SO NOT SUNDAY. 50 metres from the tournament hall a
bunch of kids started playing at the WWW.

Short after i connected to the USA and our game started
i get the error from the internet:

   "CONNECTION CLOSED, INTERNET IS TOO SLOW".

Now i got very sick of this. The friendly systemadministrator
in the tournament hall soon figured out that the many thousands of
miles from xs4all.nl to alabama were not the problem. those thousands
of miles were done within 0.4 seconds. The problem was Paderborn to
Amsterdam, because there was a certain german provider in between
which caused all the delay. I never heart from the provider before
i never wanna hear from it in the future... :)

So i could shake it the first round. No internet for DIEP. Bruce was so
polite to wait for me, setting up a small PC i brought with me.

So i played with a small hashtable and a slow program at a PII-450
the first round. You probably already figured it out.

Something weird happened that game. First move out of book actually.
First move out of book was not my small PC, but Ferret. It played h6.
Actually this move was already made before i got the "internet is too
slow for you" error, so what i already feared happened. Diep liked
the knight too much and captured it.

Later i would figure out that at the quad xeon this would not have
happened. However, searching another few plies deeper it would have
played it again. Soon i'll tune this problem away in DIEP.

So bad luck stroke. Then ferret played really well. Bruce wasn't
happy with c7c5, but later study revealed it was an excellent move
played by ferret.

So DIEP lost the first round. It wasn't a thriller, it was chanceless
actually after bxf6? In some positions programs really play well. Ferret
played very good this game. Although i was pissed because of internet
not working i wonder whether it (for the result)
would have mattered against Ferret playing that kind of chess. I guess not.

Before the second round:
The systemadministrator (apologies for forgetting his name) had
arranged a faster route to alabama for me. A secured shell!
Yes people, security! I always wondered why ssh existed, but i learned
that day that it was an excellent way of connecting.

A message send to alabama now was only like 0.200 seconds totally needing...
...thanks to the fast secured paderlinx machine in paderborn.

I could kiss the man. No longer slow internet. the next 6 rounds i
would be using a fast connection.

interesting detail: as cilkchess also was using the internet i directly
asked the systemadministrator to arrange a quick connection to america
for Don Dailey too.

As a result of that 'vague' question from me i had to log in as "chesscilk".

Second round starts. Internet is quick, but now my own errors start slipping
in as well as program errors. Losing this game was my own big fault.

First of all i made a book error. For some weird reason i simply
played without tournament book. So a few moves after book DIEP could
objectively already resign. Even the smallest experience in
computerchess learns however that this is not that smart.

We got into a very tactical position and although some may say otherwise,
that was initially DIEP's big luck. DIEP played against the 186 processor PII450
Conners program which is completely selective, not a single
form of brute force.

Now this means that some lines conners
sees hundreds of moves. other lines it
only sees a few moves.

Just getting a program to work that is using this kind of search
is very difficult. Winning the German Open with it is absolutely an
outstanding performance.

During the whole game i had the feeling that i completely outsearched
my opponent everywhere. Diep searched about 14 to 15 ply nearly
every move.

In later games i would learn that this wasn't
the case (in later games conners would show material advantage or
disadvantage moves before the opponent would see it).

DIEP simply evaluated the position quite well and fought back for
many moves.

At some point the opponent played a knight to g3, and then directly
DIEP showed a repetition score. It would take moves before the
opponent would see 0.00 too, although move afterwards it would also drop
considerable.

Now we get into a position which is classical for the computer.

For like 20 moves both programs show a draw score. Then slowly DIEP
gets happier and thinks it can win. Instead of pushing
some pawns it happily exchanges to an endgame which is dead lost.

So here happened what i feared most: getting into an endgame where diep
knows shit from.

Game still not over, because DIEP has an awful amount of pawns left.
Opponent grabs some pawns and DIEP seems to walk into a drawn endgame.

Both programs drop to near zero, but at the internet they already
figured out with EGTB that this endgame is a win for white. Too bad for
DIEP. Opponent plays simply the right moves without EGTB (some in the
last seconds!) and gets a winning position.

The rest of the game should have been easy for white,
because the opponent told me that he had all 4 men egtb,
and implicitly asks me to resign.

Then when we threaten to get into a 4 men, i see suddenly that
the opponent prints out all kind of weird things in german.

As i happen to know german a little (i can read it better as i can read
english) i feel dicked.

Conners simply doesn't play with 4 men there!

It searches a long long time for every move before playing it, and
when starting to search it prints out all kind of warnings and it doesn't
ponder or something. When we get a 3 men then suddenly it plays within
a few seconds all moves (it seemed to have 3 men). So that's the reason
why i play this game on till mate, because i felt dicked.

In all the commotion/emotion during the game i made here a huge error:
i didn't watch too carefully what diep prints out. This later in the
tournament will break diep simply.

Third round my opponent is Neurologic. I feel full of confidence here
and i could not complain about opening here. Diep plays in my eyes
a weird move (b4) and then the opponent plays a very dangerous sacrafice
which in my eyes objectively could not be very good. After the game
when doing some analysis it would appear to me that the sacrafice wasn't
that easy to refute.

Then a bug happens. After 2 hours of playing and after
many minutes of thinking in the time of the opponent DIEP
would under linux (under windows this never happened of course
otherwise bug would have been out) set it's time to infinite and
after substraction get timeleft = 0:00:00.00

This means that next move after opponent plays a move it would think:
"i have zero seconds left for the rest of the game so i must make my
move instantly". It would do a 1 ply search and then make the move.

Now this had happened also against Conners, but i didn't notice this.
This would happen in more games, but against neurologic this bug
really hurted. Diep directly lost a pawn and also lost the initiative,
which in the given position was even worse. Opponent gets a very won
position, but then DIEP starts to fight back. Then at a sudden point
where i was already hoping that DIEP might win the game,
i clearly miss some extensions and opponent sees a briljant
combination which leads to a queen versus 2 rooks ending which is
dead draw. After some moves where both my nice opponent and me had to get
used to the position being equal, we decide to a draw which actually was
very fair.

So in short: Diep had bugs that cost material and
Opponent saw a nice tactical combination (rxf3). One must be silly
to be unhappy with that. I had peace with it.

Now that i was aware of this problem in DIEP next round against
Ruy Lopez i had to watch my steps. This time i had to deal with
Spaniards from which 1 of both only spoke Spanish so communication
was kind of hard too. Only one of them spoke english.

Before the game i started a chat with them.
The chessprogram ruylopez
was not their first gameplaying program. They had experience
making a spanish-checkers program.

So far so well. Then i started asking some questions why their program
was so slow (compared to most chessprograms getting like 100k nodes
a second). At the PII450 they ran at they got
a little less than 30k nodes a second, which is not exactly
fast for a chessprogram. So i asked whether they had a lot of knowledge
in their program, considering DIEP only got 50k nodes a second
(although at 4 xeon processors, so 1 xeon processor gives diep
around 12.5k nodes a second) in their program.

To my big surprise they directly told me they had a huge amount
of knowledge in their program, probably a lot more than i have in DIEP.

Well they had the right person in front of them to tell that!

It appeared their program was using an old djgpp compiler for DOS,
which is not exactly fast, and they were running under DOS.

Their program didn't have any kind of mobility or attacktables,
because they had put all their 'knowledge' in the piece square
tables, a search strategy which in principle already sucks.

Game starts, and soon after book we get a position i never saw before,
diep saying it's in the minus out of book.
Then the bug happens and diep makes the c7-c6 move very quickly
I still don't know whether c7c6 is really that bad.

Obviously it isn't a blunder. I want to synchronize time, but
then my opponents (obviously hoping for another few 1 ply searches)
complain and get the tournament director.

In this case Don Beal, as v/d Herik was extremely busy.

Don Beal clearly didn't know that it wasn't allowed to synchronize time,
like was approved bye the players in WMCCC in 1997 in Paris, but he would
ask Tony Marsland to look it up in the rules of 1997 (they made
before the wccc99 a big mistake by copying the rules from wmccc before
the players had meeted).

Talking about clear rules...

Enfin, i make the appointment with Don Beal
that i would synchronize time before typing the move and do
this every move.

This obviously worked and from then on DIEP fought back and played
really brilliant. At a certain point i think it misses an exchange to
a won endgame (it didn't exchange at d5), but later analysis revealed
that DIEP was correct in its middlegame judgement. It thought black
was having a way better position. AFter sacraficing the pawn at h3
DIEP already found black way better. The opponent saw +1.00 for itselve
as it was a pawn up... ...talking about knowledge.

Then ruylopez planned b4 for several moves. Only last seconds it dissappeared
as best move from the screen. It obviously was an en passant hashing bug,
so i asked them whether they hashed en passant. Big questionmarks on the
face of my opponent and i couldn't explain to my opponents why one should
hash en passant, so i didn't try to explain that for the third time.

As an extra prize ruylopez also managed to slowly close in its own queen at
d5, which caused DIEP's eval to jump to +2.20 for black...

They explained this as "ruy lopez doesn't know about trapped queens". How
surprising...

My opponents still thinking they were slightly better, but both
clearly following every letter that was outputted by and inputted to
my unix terminal, they got rather nervious then. Also my big smile
probably said enough about how the position actually was.

To my big surprise they resigned at the right moment.

Then the 5th round started. Diep was paired against Mini. Mini is written
by Don Dailey, quite some years ago. Mini ran at a single PII-450 and doesn't
have a takeback function nor a setup the position.

Regrettably it was rather hard to talk to the operator, cuz he knows shit
from computerchess. I find it very hard to talk with an operator. everything
at the screen gets explained wrong. Nevertheless he was a nice man. A german
belonging to the cilk team. The cilk team is rather big. Actually the big
professor who has written so many books that i have in my possession
was there too: Leierson. Lucky i could exchange a few words during
the game with him.

Cilk really is a very promising language. In contradiction
to all my big efforts to parallellize DIEP, writing in cilk this goes a lot
simpler. Regrettably when starting the parallel version of DIEP, there
was no port of CILK to windows (the first demand for something is
that it must work both in windows and linux before i can use it; interface
is of course something different) otherwise i might have done better in
paderborn...

Anyone who still must start his parallel project here gets a free tip from me:
Don't go fiddle with difficult parallellization, simply use CILK, let
that language handle the parallellism and keep only busy making a good
program!

The alternative to cilk is years of bugfixing the parallel code.

Anyway, i already spent 6 months to making my program parallel, so
CILK was too late for me to save me.

Anyway, game starts and DIEP plays shit i think. DIEP itselve apologized for
that by showing mainlines that ended all in endgames. I think i definitely
can do something with this middlegame. DIEP obviously wasn't that bad
after opening, but in my eyes completely blew it.

I think nowadays programs search that deep (i got 14/15 ply this game
every move) that just a single weak chain in the evaluation (in diep's
case endgame) will cause you to lose. For a rather simple reason: all
lines it saw were already exchanged into endgame. If it then evaluates
a lost endgame position to be better for white, then you're having a major
problem. Well that is what happened.

So in short diep was awfully lost in the endgame, but then DIEP got lucky.
Let's not forget that DIEP searched at 4 processors with half a gigabyte
of hash and the opponent at a single cpu.

So diep completely outsearched the opponent. Now that never is a disadvantage.
However, if both programs are completely misevaluating a position, then
outsearching your opponent might be crucial. Diep reported that mini missed
it's last winning chance (f7-f6) after which diep took over the game
and fought its way back. Still fighting mini chose to walk with its king
to the other side of the board, getting outside quadrant of the passed pawn
of DIEP. AFter diep prevented the opponent from sacraficing its last bishop
to the pawn, DIEP directly saw itselve winning. Then the opponent started
smelling something and slowly lost the game.

So in short diep as very lucky to win this game. Bad endgamejudgement
brought it to an endgame. hardware advantage probably won the game then.

6th round DIEP played eugen. Eugenio is probably one of the nicest men
i ever met. So i was very happy to play him. The big example for Eugenio
is genius. He really loves that program. Eugen searches a lot like it.
Not very deep, tactical a lot deeper than the nominal depth it shows though.

Bad luck struck for DIEP. Not a big gap in DIEP caused the bad luck,
but me myselve and i. I fiddled in order to get a new tournament book
to work. It didn't work. after this fiddling i forgot to check whether
i set back the old tournament book back correctly. So this game
diep again didn't play without a good book.

that was directly clear in the opening. first move out of book diep said
it was -0.80 down. Not very happy. Even worse, diep also grabbed the d4
pawn, a move i didn't even consider myselve. After that we quite quickly got
an endgame and my DIEP completely misevaluated that. It thought it had
a better position!

Well that was dead wrong. the whole endgame was lost for black.
So again the deepsearching DIEP here exchanged into a lost position because
its endgame evaluation sucks bigtime.

Then Eugen played very well. especially its Rb6
earns a big exclamation mark. I'm sure eugen played at least as well as
it's big example, and that for many moves.

then when getting into the endgame i clearly saw the big advantage of
big hashtables. Eugen searching 9 to 11 ply. Diep getting 18 to 20 ply
in the endgame. Quite a difference!

Although evaluation was dead wrong (-0.80), the complete win for white
was at my screen. Now eugen clearly started playing worse
as its big example and blew it to a draw.

The 6th round was a big bummer for me.

Where the previous 5 rounds i had played without problems at the quad
xeon, during monday-friday, it now was Saturday.

My chesscilk connection didn't work. Internet again didn't work.
i could now connect quickly to xs4all.nl, but of course that didn't work
as the firewall was set to paderlinx.

So i started playing from my PII450.
Within a few moves diep
got into an endgame against francesca. Now although i could not
complain about the bookline here and i could not complain about the
endgame position, my biggest fear again became true. Diep had an endgame.
For the first time however DIEP had a way better endgame.

Then bad luck struck and Diep simply grabbed the g7 pawn,
which i directly recognized as a major blunder.

This combination is way too deep for any program, so a program can only
see positional that grabbing the pawn is bad. half of all programs i tried
even at huge depths grab that pawn.

Diep with bad tuned endgame parameters definitely grabs that pawn.
Also at depths like 18-20 plies.

So a quad wouldn't have mattered here. After bxg7?? black had a lot of
simple and forced moves and was forced into a won position. Big bummer.
So i resigned.

So in short this game again diep's poor endgame knowledge lost, and this
time a faster machine would not have helped.


                      AFTER PADERBORN

After Paderborn i started analyzing "what did i learn" and "what to do now".
My first action was to analyze other programs and DIEP.

First of all i was amazed how well Lambchop played in paderborn, just
getting a 9 ply search.

Actually the average level in paderborn still amazes me. The level in
paderborn was very high.

Against a strong program getting out of book with more than half a pawn
down simply means that winning the game is near to impossible.

The weakest chain in most programs is surprisingly either the endgame
or the middlegame. Not a single game diep came won out of the openingsbook.

Except for ferret and eugen all opponents played very bad in the middlegame,
when compared to diep. Except for mini all other programs played better or
just as bad in the endgame.


                  CONCLUSIONS

Parallellism is the future.
Not a single program will in the future be able to play without EGTB
in search.
Winning the endgame for most programs is gonna get very tough.
Near to no program plays very well in the middlegame. It's about the plan.
When a program has the right plan and a way better position, then
you can about resign.
Bad tested programs are dinosaurs. They get massacred,
as a single big problem in a program will, because of the huge search depths,
immediately backtrack to the root and get at your board.
Programs without a lot of knowledge don't know how to progress, or simply allow
or force opponents to place their pieces better.

Quality is more important than quantity. I guess Lambchop clearly proved that.

                FUTURE WORK

Since last Tuesday 22th i'm slowly working on DIEP now.
I'm right now working at the search. Experimenting a lot
with forward pruning versus brute force search.
I simply kicked out all forward pruning. Only nullmove and alfabeta is what i
use. Experimenting with last ply pruning now though a little.
It scores shit at testsets. Positionally its however just as fast as
the very selective version i used in paderborn.

After some toying the next few weeks with this i will work after that
at my endgame evaluation and fix the knight versus bishop parameters.

For the next months and further my graphical windows
version must be made ready for commercial usage. Plan to release again
after this summer.

After that i plan to learn diep how to play the kings indian defence with
black. I already started that project a year ago, but some defences seem
quite hard for programs to understand...

Greetings,
Vincent





This page took 0.23 seconds to execute

Last modified: Thu, 07 Jul 11 08:48:38 -0700

Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.