[rc5] v3

Eric Gindrup gindrup at okway.okstate.edu
Tue Oct 28 14:59:47 EST 1997


        Round numbers: ~80 plys with an average splay (number of distinct 
     moves) of ~30 (fewer in the opening and many more in the midgame).  
     This gives a wild estimate of 30^80 moves ~= 2^400 which is roughly 
     like RC5-400 (RC5-32/12/50).  There are of course repetitions.
     
        It would seem that the following would be a good way to break down 
     the total analysis of chess that is being talked about.
     
        1) Got with the original idea of completely analyzing endgame 
     positions of certain ("small") numbers of pieces.
        2) Now that we have a large body of "known problems" to reduce 
     toward, assign (initial board position, "signatures") pairs to each 
     client.
        The "signatures" are sets of hash values of board descriptions that 
     indicate "vertical" boundaries in the search graph for chess games.  
     (A graph because, a few moves in, there are multiple paths to the same 
     game state.)  A client does not continue to evaluate a generated 
     position with a "signature" value.  It is returned to the proxy and 
     checked against the dictionary of assigned states.  If it has not been 
     assigned, it is assigned, with a larger set of signatures.
        The idea is to partition the search space by the signatures and 
     successively refine by adding signatures so as to avoid redundant 
     client work.  A board position that has a signature value is 
     (putatively) assigned to a different client and needs to be handled by 
     that client.
     
        This means that there are two search graphs involved.  The clients 
     would be searching a subgraph of the set of all chess games and the 
     servers would be detecting "cross-over" points between the distinct 
     subgraphs.  It would probably be a good idea to assign several similar 
     positions to the same client and have it report cross-overs to the 
     servers.  In any event, partitioning the search space is very 
     difficult.
            -- Eric Gindrup ! gindrup at okway.okstate.edu


______________________________ Reply Separator _________________________________
Subject: Re: [rc5] v3 
Author:  <rc5 at llamas.net > at SMTP
Date:    1997/10/27 22:59


On Mon, 27 Oct 1997, Bill Plein wrote:
     
> Describing a board configuration and the move therein would take a lot more 
> data than describing a single RC-128 key, and describing all possible board 
> configurations and all possible moves for that board. Whoa, that's a HUGRE 
> library.
     
I think he was referring to the total possible combinations of board 
configurations.
     
RC5/128 has a tad more than
34,028,236,691,000,000,000,000,000,000,000,000,000 total 
possible keys.
     
I have no idea how many possible combinations there are in chess... :-P
     
Joseph
     
************************************************************************** 
** C. Joseph Fisk (mdmbkr)                           mdmbkr at chillin.org ** 
** Visit http://www.distributed.net - the world's fastest supercomputer ** 
**************************************************************************
     
     
----
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