RE: computer-go: Sharing Go modules - ready for download

["Mark Boon" <tesuji@xxxxxxxxx>]

> -----Original Message-----
> From: owner-computer-go@xxxxxxxxxxxxxxxxx
> [mailto:owner-computer-go@xxxxxxxxxxxxxxxxx]On Behalf Of Eric Boesch
> Sent: Wednesday, June 20, 2001 3:25 AM
> To: computer-go@xxxxxxxxxxxxxxxxx
> Subject: Re: computer-go: Sharing Go modules - ready for download
>
> Suppose you have 10,000 rules, R1 through R10000.  Each rule involves 15
> random predicates or their negations out of a set of 52
> predicates, labeled
> A-Z and a-z.  For example:
>
> If A,C,G,g,p,r, and u are false, and D,F,H,f,h,m,s, and y are true, then
> rule P5332 is satisfied.
>
> Since the predicates in the rules are randomly distributed, it hardly
> matters which predicate you use to start your binary search with.
>  You could
> just as well use alphabetical order:
>
> #1 Is A true?  If yes, go to #2.  If no, go to #55223423321.
> #2 Is B true?  If yes, go to #3.  If no, go to #25234234323.
> ...
> #99442343132 Rule 5332 is satisfied.
>
> After answering at most 52 questions, and probably a little
> fewer, you will
> know which rules have been satisfied.  The problem is that even
> if you merge
> common subtrees, this will only help trim a few nodes at the
> bottom of the
> tree.  Further from the leaves -- after 40 questions, for example
> -- there
> will be essentially no common subtrees, meaning the tree will have spread
> out to 2**40 different nodes, which is impractical.
>

I'm not following all this, it's way too complicated. You are seeing a
theoretical problem that is easily solved in practice. If there are no
common sub-trees from a certain point, there's no reason at all to continue
maintaining a tree structure. Instead you can make a leaf node that contains
a list of the remaining questions. If you think about it you'll find that
this way the tree will contain as many leafs as there are patterns. And in
practise the number of internal nodes remains very limited as well, provided
you take good care in which order you insert the questions in the tree.