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

[Patrick Stiegeler <stiegele@xxxxxxxxxxxxxxxxxxxxxxxxxx>]

thank you, heikki, eric and mark!

by combining your three statements i got a lot of inspiration!!

seems, that this sort of decision tree is quite common to you. i would be
interested in how many and how big patterns one could test in what time
with this approach. has anyone made some experiments?

patrick

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