I think you could do this with a binary tree - at each node keep a total of the weight values of the subtree below the node.
If the pattern was hashed, then each bit could define a branch of the tree, 0 = left branch 1 = right branch. Then you have a very simple divide and conquer algorithm. The tree would not be perfectly balanced, but even with a lousy (fast) hash function it would be more than adequate. You could have a massive populations of things to select from probabilistically and this would still be very fast. - Don On Wed, Jul 15, 2009 at 7:06 PM, Mark Boon <tesujisoftw...@gmail.com> wrote: > When using patterns during the playout I had improvised some code to > select patterns randomly, but favour those with higher weights more or > less proportionally to the weight.. > > I was wondering though if there's an established algorithm for > something like this. To be a little more precise, if I have a set of > values and two of those are represented by A and B. If A is twice as > high as B it should have twice the chance to be selected. If there's a > third value C that is 1.5 times A then it should be 1.5 times as > likely to be selected as A and 3 times as likely as B. Etc. > > There are many strategies I can think of that make a randomly weighted > selection from a set. But none of them are really straightforward. So > I'd be interested to hear how others handled something like this. And > if there's maybe a standard known algorithm, this kind of thing must > appear in a lot of fields. > > Mark > _______________________________________________ > computer-go mailing list > computer-go@computer-go.org > http://www.computer-go.org/mailman/listinfo/computer-go/ >
_______________________________________________ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
