[D-CHESS] Tree partitioning

Eric Gindrup gindrup at okway.okstate.edu
Thu Aug 27 16:29:22 EDT 1998


     There is one core problem with distributed chess.
     
     Once you've distributed the <initial position, search-depth> pairs, 
     how do you prevent multiple clients generating (large) identical 
     sub-trees during their evaluation?
     
     For a single machine, this is easily done using a hash table to keep 
     track of which positions have already been generated.  Sharing this 
     between clients would require immense bandwidth.
     
     Suggestion: make a small hash table.  Select one hash table entry to 
     be the "stop" entry.  No position in the "stop" bin is ever used to 
     generate new positions.
        A well-chosen hash would partition the cyclic digraph of board 
     configurations without disconnecting the graph.  (If the graph were 
     to be disconnected, then there would be board positions that could 
     not be reached by the search vaguely described above.)
     
     The cyclic graph of positions can be easily striated by piece 
     counts.  However, the edge density of the graph of board positions 
     is still so high that dividing solely by piece counts will not 
     partition the graph sufficiently.  Further, divisions based on piece 
     counts promote "shallow, wide" search subspaces instead of "deep, 
     narrow" ones.
     
     Alternatively, if there were a well-developed notion of compactness 
     on the set of board positions, then one could fully develop a 
     "pencil" of compact subgraphs vertically through the striations.  An 
     assigned set would be either a pencil or a sub-pencil (a pencil 
     intersected with a striation).
     
     This is relatively "high falutin'" and hard to implement in real 
     code, especially small code.  So I don't see how a forward evolution 
     approach is going to result in a system that could be distributed 
     over the D.Net computer.  This computer has odd properties, 
     especially in latency and the extreme NUMA-ness of its nodes.
     
     The reverse evolution, from endgames toward the starting position 
     seems somewhat more partitionable onto the set of nodes presented by 
     the D.Net computer.  A "block" would be a collection of pieces plus 
     the set of outcomes attainable by each subset of those pieces with 
     only one piece removed.  I.e., the client determines which of the 
     subset outcomes are reachable from the given board position.
     
     This analysis could turn chess into a game like Nim.  Black, e.g., 
     is trying to make a member of a certain set of "win for black" 
     positions occur while white is trying to at least keep a "stalemate" 
     opportunity alive.  (Of course, white should be trying to maneuver 
     into a forced win for white...)  What we would be building is a 
     catalog of positions from which the outcome is certain as well as an 
     evolution tree from "nearby" positions toward positions where the 
     outcome is certain.
     
     This evolution tree would provide ample input stimulus for a neural 
     network.  If the "ideal" evolution operator were simple enough to be 
     represented in the particular network, then it (might) learn a fast 
     method to push a given board position toward a certain win.
        (Assuming of course that chess is a biased game in the sense of 
     game theory.)
        Similarly, another net could be developed to always push for a 
     stalemate.
     
     But I don't see how to make the forward evolution technique work.  
     Like raytracing the amount of wasted work would be enormous.  
     Reverse tracing doesn't waste any work because only those rays that 
     hit the film are created.  Similarly, reverse evolution in chess 
     only generates predecessor states that lead to known outcomes (or 
     "highly probable outcomes").
            -- Eric Gindrup ! gindrup at owkay.okstate.edu

--
To unsubscribe, send 'unsubscribe d-chess' to majordomo at lists.distributed.net



More information about the d-chess mailing list