This code should work with "r -= weights[i++]" in the loop body, and comes down
to a linear search through
cumulative sum of the weights. If the weights will be static for a number of
selections, you can store the
cumulative weights in an array and use binary search for selecting the move.
So setting up the table is O(n),
but selecting moves based on those weights is O(log n).
If the weights are constantly being updated, there's a tradeoff between Peter's
code and the tree-based approach:
Peter's code is O(1) for updating weights and O(n) for selections, while the
tree-based approach is O(log n) for updates
and selections.
[You can get practically quicker selection using Peter's code if you keep the
weights sorted in decreasing order, but then updates
become O(n) worst-case (probably O(1) amortized, though).]
Steve
On Thu, 16 Jul 2009, Don Dailey wrote:
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/
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/
--
Steve Kroon | Computer Science Division, Stellenbosch University
(084) 458 8062 (Cell) | (086) 655 4386 (Fax) | kroonrs (Skype)
http://www.cs.sun.ac.za/~kroon | kr...@sun.ac.za
_______________________________________________
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
