[rc5] v3

Eric Gindrup gindrup at okway.okstate.edu
Mon Oct 27 15:55:06 EST 1997


        The Bovine chess engine seems to be about exhaustively examining 
     endgame positions.  However, to address you architecture, a slightly 
     more feasible scheme is to have all the clients only report min-max 
     branches.  This reduces the total amount of returned data and ensures 
     that any returned position has the highest rated worst possible 
     (evaluated) outcome associated with it.
        To reduce the granularity of the work, require that only moves in a 
     certain quadrant of the board be evaluated.  Moves out of that 
     quadrant are reported back to the proxies and are reassigned.  This 
     also helps the proxies recognize when a generated move is alread 
     assigned (by counting how which pieces are in each quadrant and seeing 
     if that "signature" of piece distributions has already been assigned).
     
        The largest problem I see is reduction of duplication of effort.
            -- Eric Gindrup ! gindrup at Okway.okstate.edu


______________________________ Reply Separator _________________________________
Subject: Re: [rc5] v3  
Author:  <rc5 at llamas.net > at SMTP
Date:    1997/10/23 20:33


     [snip]
     
   What would the high-level architecture be like?  
     
     
   You would probably have the master server distribute board positions
to the proxies and clients.  The clients would get a board position, 
move a few ply ahead and evaluate, basically doing a few steps of a 
breadth first search from a given starting position.  After a while the 
client stops searching and returns the best of the positions it's found 
so far.  
     
     
     
     
   The I/O problem.
     
     
   Chess has a high enough branching factor that you cant return all the
positions you find.  You have to select the best few.  The branching 
factor of chess is position and context dependent, as an estimate of the 
mid-game branching factor lets use 30.  If the clients does a 1 ply 
search, then for each position retrieved from the server, the client 
would send back about a kilobyte.  For a 3 ply search the response is 
almost a megabyte.  A full 3 ply breadth first search takes no time at 
all.  In the distributed application we're not CPU bound, we're I/O 
bound.
     
     
   There is a tradeoff between having the clients go deep into their own
little branch of the search tree and having them go shallow.  If the 
clients go deep and only return, say, the best 25 positions three ply 
ahead, then the intermediate search (all the other 27000 positions 
examined) are lost.  If there was a long-term payoff sacrifice in one of 
the non-returned branches, we'll never find it.  On the other hand, we 
cant return all 27000 positions, becuase the network would choke.  (Hm, 
or we could all go buy fiber connections to the backbone.)
     
[snip]

Sebastian
     
----
To unsubscribe, send email to majordomo at llamas.net with 'unsubscribe rc5' in the
body.
     


----
To unsubscribe, send email to majordomo at llamas.net with 'unsubscribe rc5' in the body.



More information about the rc5 mailing list