Author: Robert Hyatt
Date: 06:30:45 01/23/98
Go up one level in this thread
On January 23, 1998 at 00:18:18, Don Dailey wrote:
>Hi Bob,
>
>Concerning point 1, "psuedo stable evaluations" :
>
>We try really hard to avoid the unstable evaluations. Our philosophy
>(and I realize it's just that so don't blast me please) is that these
>wild swings usually (but not always) indicate a problem with gradualism
>in the program. For instance you may give big bonuses to get to some
>square but no bonus for getting close. Or your endgame threshold is
>not gradual but sudden and harsh so the king goes from being great to
>sucking in one fell swoop. When this happens you don't make fine
>positional
>decisions but everything is based on the one silly point. Some of this
>however is unavoidable, for instance rook gets on 7th and then is driven
>away on the next move.
I agree. I also do things like detect doubled rooks on the 7th, when
the king is on the 8th or there are pawns on the 7th... and also a
doubled queen/rook for the same reason. These are generally "almost
winning" advantages based on watching thousands of games. The problem
then is that one more ply might let me see that I can do this... and
viola... a big swing. And a big problem on the iteration that follows
when I finally see I can do this...
>
>Aske Plaat recommends the mtd increment be based on the granularity of
>your evaluation. If a pawn is 10,000 points your mtd increment should
>be much higher. Also we use a stand pat bonus to smooth out the odd/
>even affect. I don't know if this is common practice or not but I
>assume
>others do it too.
>
I even tried an odd/even estimate, by watching the first shallow
searches
to see what happens iteration to iteration. But that didn't work. it
was
particularly bad against a strong electronic opponent, because they will
make moves that look bad at the first N-1 iterations, but on the last
one
or two, you begin to realize that it really wasn't that bad as you get
deep
enough to see what he saw. And my re-searches went up, on the very
iterations where I didn't want this to happen (last ones vs first ones.)
>Anyway, lot's of room for philisophical disagreement on this one and
>I freely admit there are lot's of issues that interact so I'm definitely
>not claiming you are doing anything wrong.
>
>2. You mentioned extension based on the target score (alpha/beta.) We
>used to do this and eventually threw these out long ago because they
>do cause problems whether you use mtd or not. So far our program
>has met your requirements for MTD candidacy!
mine meets that now. :) royal pain in ass and produces lots of
inconsistent results.
>
>
>3. We did experiment with maintaining upper and lower bounds in the
>hash table and felt that it would help MTD even more. But our
>implementor
>reported no improvement. I may go back and repeat because I never trust
>ideas I didn't implement myself! I think there might be some issues
>with best move too that might make a difference, namely, that with MTD
>you may be storing a best move that is quite horrible, but good enough
>to get a cutoff. Usually this would be poor captures that happen to
>be first in the move list. It's probably just as well to not store
>these (or overwrite these) if you can determine which ones they are.
>
>The principal variation issue is definitely a pain but I haven't
>attacked
>the problem with a vengance and full concentration yet. I think this
>is a solvable problem and will probably work on this next. I hope to
>learn a lot from the effort.
>
>You talked a little about your parallel implementation and indicated
>that PVS was wrong for it. I can't think of any inherent reason for
>this but then again I do not understand the details of your
>implementation.
the problem is that I did analysis on the various alpha/beta bounds at
various points in the tree to try to correctly when a node was an ALL
node vs a CUT node. I didn't try this on MTD of course, since I don't
do this stuff in Crafty (parallel search) yet. But my old approach
would
crash and burn trying to figure out where to search when all the alpha
values in the tree == beta-1...
>
>Our parallel code is trivial to implement and you can probably easily
>read and understand this example code. Note that this routine is
>pretty much completely correct except for a bunch of details that do
>not concern the parallel aspects of it. Also I'm not treating nega-max
>or mini-max correctly, but I'm just showing the process. Please take a
>quick look and tell me if its the basic algorithm you used:
>
>
>cilk int search( POSITION *p, int depth, int move )
>{
> POSITION new_position;
> int cutoff = 0;
>
>
> inlet void search_results(int score)
> {
> /** test for cutoff from any spawned search **/
>
> if ( score > new_position.gamma) {
> cutoff = 1;
> abort; /** Cilk abort function **/
> }
> }
>
>
>
> new_position = *p;
> make( &new, move );
>
>
> /** Search first move serially **/
>
> score = spawn search( &new, depth-1, firstmove );
> sync; /* must sync even though not parallel or this falls through! */
>
> if (score > gamma) return( score );
>
>
>
> /** search all others in parallel **/
>
> for (i=2nd_move; i<=lastmove; i++)
> {
> search_results( spawn search(&cur, depth-1, move[i]) );
> if (cutoff) break;
> }
>
> sync;
>
> return best_score;
>
>}
not even close. My processors were spread out all over the tree once
the search gets underway... but supposedly all working on ALL or PV
nodes only. They know who they are working "with" and how to share
improved alpha/beta bounds as they become available.
It was a horrendously complicated algorithm but it was quite capable
of producing good results with reasonable numbers of processors. For
16 it was nearly 12X faster. On 32 it was 19X faster, so performance
was on the way down at really large numbers of procssors...
>
>
>Essentially we search the first move at any node serially (wait for
>the results) and then spawn all the rest off in parallel. In actual
>practice of course 99% of all this ends up being searched serially
>anyway, especially with 4 processors but if processors are available
>to do the work then they will. Cilk is just a 'c' preprocessor that
>handles
>all the scheduling details. We use a work stealing algorithm so
>that when a processor runs out of work it "steals" work from another
>processor in the order the work was posted (or spawned.)
I did the same thing. We had some simularities from talking with
Bradley
(I assume this is still what he called the "Jamboree search"?? In any
case, my parallel algorithm also did the "stealing" idea...
>
>When a spawn returns from it's search, the "inlet" is invoked and if
>a cutoff is possible the "abort" statement will kill any work that
>is currently being done by other processes and the "sync" will happen
>very quickly.
>
>I think this is essentially the same algorithm most parallel chess
>programs use (Frenchess starts up all processors on the same position
>and uses the hash tables for bookeeping but in principle reduces to a
>very similar algorithm although it looks completely different at first
>glance.)
>
>I hope others see this and realize how trivial it is to implement
>a parallel chess program. SMP are becoming more and more common
>and are easily affordable to most of us. If anyone is interested
>in pursuing this, CILK is available for free and has been ported to
>Alphas, Linux PC's, Sparcs and SGI machines. We have a version
>now also for networked machines. The implementation is as easy
>as you see it here.
I would not say "trivial"... :)
>
>Aske Plaat ported an old version of Crafty to Cilk. Since Crafty
>was designed to be a serial program he had some problems with all
>the global state. But even this did not prevent him from porting
>it in a few days (even though he was completely unfamiliar with the
>code.) If anyone decides to write a parallel program I highly
>recommend encapsulating all your position state (the board and
>relevant state) into a structure. If you are concerned that
>creating new states for each node will be too expensive, don't
>be. Modern processors copy contiguous data extremely rapidly
>and you avoid some work with keeping unmake information (you never
>unmake a move.) The same code (a big benefit of using cilk) will
>produce a serial version of the program that runs very fast and I
>promise it will be competitive with your current serial program.
>(I think I hear someone in the background screaming something about
>data cache but I can't quite make out what they're saying.)
you need to run on a PC. I once did this (copy state) and the best I
could do was 5K nodes per sec on a P5/133... when I got rid of the
state
copy and started make/unmake, I eventually got past 30K. The PC only
has a sustainable bandwidth of 60-70mb/second. Compared to 32 gigabytes
per second on a Cray. Or maybe a gig/sec on your CM-5. You will get
killed copying large structures on a PC however...
>
>Cilk was designed for chess and is extremely efficient. You can
>link in assembly code if that is your thing. All of the parallel
>user routines in cilk get compiled as 2 copies, 1 for speed and
>efficiency and 1 with the parallel bookeeping overhead. Most of
>the time you are executing the fast "serialized" code and only
>when work gets stolen do you suffer from the overhead. The net
>effect is that the parallel code on 1 processor is almost as fast
>as the purely serial program. This is not typical of parallel code.
>
>Also there is no concept of a "boss process" that divy's out work
>etc. You do not need to know or care how many processors are involved
>although you have access to this information if you want it.
>
>This post ends up sounding like a commercial. But I wanted everyone
>to know this is not a secret technology and we WANT people to use
>it. I am not afraid you guy's will get a hold of it and compete
>with me either. My programs are good enough to hold their own and
>I like competition! With CILK, parallel chess is almost trivial
>and I hope some of you give it a try.
>
>- Don
>
>
>
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.