In the loop i is always zero. I think your code is wrong.
You probably meant to loop over all the weights (or I should say on average
half the weights), and this code is slow if there are a lot of weights.
2009/7/16 Peter Drake <dr...@lclark.edu>
> I must be missing something. Isn't the obvious trick:
> int r = random(<sum of weights>);
> int i = 0;
> while (r > weights[i]) {
> r -= weights[i];
> }
> return i;
>
> This way, you only have to generate one random number.
>
> Peter Drake
> http://www.lclark.edu/~drake/ <http://www.lclark.edu/%7Edrake/>
>
>
>
> On Jul 15, 2009, at 8:55 PM, Zach Wegner wrote:
>
> On Wed, Jul 15, 2009 at 10:37 PM, David Fotland<fotl...@smart-games.com>
> wrote:
>
> So many complex ideas :) Why not just multiply the weight of each pattern
>
> by a random number and pick the biggest result?
>
>
> David
>
>
> That involves generating N random numbers and then doing N-1
> comparisons. The n-ary tree has only 1 random number and log N
> comparisons, but has to be
> incrementally updated (log N adds).
>
> Also, I don't think the distribution is the same. Imagine two moves a
> and b, with weights 2 and 1. The probabilities should be a=2/3 b=1/3,
> but if you select two random numbers in a finite range, there's only a
> 1/4 chance that the second number is more than twice the first, which
> is needed for b to be selected. I could be wrong here though.
>
> Zach
> _______________________________________________
> 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/
>
_______________________________________________
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
