[D-CHESS] Tree partitioning
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,
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
Similarly, another net could be developed to always push for a
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