[rc5] v3

Sebastian Kuzminsky kuzminsk at taussky.cs.colorado.edu
Thu Oct 23 21:33:09 EDT 1997


jeff at delta.com (Jeff Woods) wrote:
] The distributed chess computer idea really piques my interest.   If Deep
] Blue won't play Kasparov, then let's get a championship match up against
] distributed.net..... 200 million moves a second:  BAH!    Watch 10,000
] Pentiums analyze EVERY possible move.   


   Let's take a look at what distributed chess engine might look like.




   First of all, how much data does it take to encode a chess position?


   There are some fancy high-pack schemes, but a rough BOTE calculation
will do for now.  There are 64 squares, so it takes 6 bits to uniquely
identify a square.  There are sixteen pieces and sixteen pawns on the
board.  If each one has a 6-bit square identifier, then thats 32 * 6 =
192 bits.  The 16 pawns may have been promoted to any of four pieces, or
be un-promoted in which case they may be allowed to en-passant right or
left or not at all, that's seven options for another another 3 bits
each, 16 * 3 = 48.  Finally, both sides may be allowed to castle long or
short, 2 bits per side, 2 * 2 = 4 bits.  What did i forget?


   That's 192 + 48 + 4 = 244 bits, or 30.5 bytes.




   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.)


   We could use some smarts in the proxies, knowledge of local network
topologies.




   The official distributed.net chess engine has been under development
for some time.  When will we get to see it?




Hm,
Sebastian

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



More information about the rc5 mailing list