Re: [computer-go] Random weighted patterns
I'm about to implement this. Since I have multiple features (patterns, is in atari, is adjacent to last play, etc.), the weight is the product of the weight of all matching features. I'm thinking about having a table of weights, storing the sum of each row and the total (like Rémi suggested). I want to do this incrementally, so if I find a new feature match in a position, I can multiply its weight by the feature's weight. If I remove a feature, I can divide. My question/problem: How do I deal with features that have a weight of zero? I'm sure there are certain 3x3 patterns that have the weight zero, such as ### #*. #.. with * to be played. It's clear that when this pattern matches, the total weight is set to zero. How do I find the resulting weight when removing this pattern, though? Since I can't divide by zero, I would have to reconstruct the weight by checking all features, which would be relatively slow. Is there a way this can be avoided, such as setting all weights to a very low value instead of zero? Regards, Isaac___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Random weighted patterns
Isaac Deutsch kirjoitti: My question/problem: How do I deal with features that have a weight of zero? I'm sure there are certain 3x3 patterns that have the weight zero, such as ### #*. #.. with * to be played. It's clear that when this pattern matches, the total weight is set to zero. Hmm. Say this is a black group, surrounded by white stones and involved in an unsettled semeai: #..# #..# W needs to play in one of the liberties, and they all match your pattern. JP ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Random weighted patterns
In my example, #=border/edge of the board, not black. I was just trying to come up with an example feature that might have weight zero to illustrate my problem. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Random weighted patterns
Isaac Deutsch kirjoitti: In my example, #=border/edge of the board, not black. I was just trying to come up with an example feature that might have weight zero to illustrate my problem. I see. I was already thinking there may be no 3x3 patterns that should never be played. But I cannot think of a counter example to your corner case. Assuming your multiplicative weighting is the best way in the first place, then the epsilon-sized minimum weight seems reasonable. JP ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Random weighted patterns
Isaac Deutsch wrote: I'm about to implement this. Since I have multiple features (patterns, is in atari, is adjacent to last play, etc.), the weight is the product of the weight of all matching features. I'm thinking about having a table of weights, storing the sum of each row and the total (like Rémi suggested). I want to do this incrementally, so if I find a new feature match in a position, I can multiply its weight by the feature's weight. If I remove a feature, I can divide. My question/problem: How do I deal with features that have a weight of zero? I'm sure there are certain 3x3 patterns that have the weight zero, such as ### #*. #.. with * to be played. It's clear that when this pattern matches, the total weight is set to zero. How do I find the resulting weight when removing this pattern, though? Since I can't divide by zero, I would have to reconstruct the weight by checking all features, which would be relatively slow. Is there a way this can be avoided, such as setting all weights to a very low value instead of zero? Cache what features you have, then recomputing the weight will be fast. GNU Go incrementally keeps track of the following features: Black suicide (true/false) White suicide (true/false) Black self-atari (true/false) White self-atari (true/false) Number of stones captured by black move (0, 1, 2, 3+) Number of stones captured by white move (0, 1, 2, 3+) Color to the southeast (empty, white, black, off board) Color to the northeast (empty, white, black, off board) Color to the northwest (empty, white, black, off board) Color to the southwest (empty, white, black, off board) Color to the east (empty, white, black, off board) Color to the north (empty, white, black, off board) Color to the west (empty, white, black, off board) Color to the south (empty, white, black, off board) This information is stored in 24 bits of an integer. The 16 bits related to the local 3x3 pattern are mapped by table lookup to the 1107 rotation/mirroring invariant patterns. The remaining 8 bits are mapped to the following features: Opponent suicide (1 bit) Our self-atari (1 bit) Opponent self-atari (1 bit) Our captures (2 bits) Opponent captures (2 bits) by simple bit transposition depending on color to play. Additionally nearness to the previous move is added as a feature giving 1107*256 combinations, which are finally mapped to pattern weight by table lookup. /Gunnar ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Random weighted patterns
Thanks to both for the elaborate feedback! I was wondering about pattern symmetry, too, and I also had a lookup table in mind since there are only about 65000 combinations (and only a fraction of them legal). I had another idea for the zero weight problem: Keep a counter of how many times this weight was multiplied by zero. This counter can be stored in 1 byte or less, depending on the number of features. If the counter is 0, the weight is the floating point value. Else, the weight is zero. When adding a zero-weight-feature, increase the counter by one, else decrease it by one. This way, the weight doesn't have to be recomputed, although it uses slightly more memory than nicely packing the features in an int like in GNU Go. It seems like the rounding errors that are accumulated this way are insignificant, according to my tests. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Random weighted patterns
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 Fotlandfotl...@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/
Re: [computer-go] Random weighted patterns
Thanks! I had never seen the alias method before and it is quite ingenious! - George On Thu, Jul 16, 2009 at 3:04 AM, Martin Muellermmuel...@cs.ualberta.ca wrote: If you want to take many samples from a fixed, or infrequently changing, distribution, you can do it in O(1) time per sample, with O(n) initial setup costs. This is quite clever and goes by the name of alias method. See http://cg.scs.carleton.ca/~luc/rnbookindex.html, page 107-111 For weighted patterns, the row sum method by Rémi is probably hard to beat. It was discussed here a while ago. Martin ___ 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/
Re: [computer-go] Random weighted patterns
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.. How many patterns, and are the weights constant for the whole game? If relatively few, and constant, you can make a lookup table (with e.g. 1024 entries) where the number of entries for each pattern is proportional to its weight. You then choose with a 0..1023 random number. When more patterns, but only a few distinct weights you can split them into buckets. E.g. a bucket of weight 1 patterns, weight 1.5 patterns, weight 2 patterns, etc. The weight of each bucket is the number of patterns in it times the pattern weight. You first choose a bucket (e.g. using the above lookup table algorithm), then choose uniformly from within the bucket. Darren P.S. I suspect you have already came up with the above algorithms. I had the same question before, and like you realized it wasn't quite as easy as I thought it would be. I'd also like to hear what the standard computer science approach is, if there is one. (I just saw Jason's reply; do you have a good reference describing row sum in more detail?) -- Darren Cook, Software Researcher/Developer http://dcook.org/gobet/ (Shodan Go Bet - who will win?) http://dcook.org/mlsn/ (Multilingual open source semantic network) http://dcook.org/work/ (About me and my work) http://dcook.org/blogs.html (My blogs and articles) ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Random weighted patterns
You might look in the genetic algorithm literature, where they have to do this for fitness-proportional reproduction. A useful buzzword is roulette wheel. Peter Drake http://www.lclark.edu/~drake/ On Jul 15, 2009, at 4:06 PM, Mark Boon 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/
Re: [computer-go] Random weighted patterns
If your weights are all between 0 and 1: do double r = rand(0 to 1) int i = rand(0 to weightCount - 1) until weight[i] r I think that's right. Mark Boon 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/
Re: [computer-go] Random weighted patterns
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/
RE: [computer-go] Random weighted patterns
So many complex ideas :) Why not just multiply the weight of each pattern by a random number and pick the biggest result? David -Original Message- From: computer-go-boun...@computer-go.org [mailto:computer-go- boun...@computer-go.org] On Behalf Of Mark Boon Sent: Wednesday, July 15, 2009 4:07 PM To: computer-go Subject: [computer-go] Random weighted patterns 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/
Re: [computer-go] Random weighted patterns
So many complex ideas :) Why not just multiply the weight of each pattern by a random number and pick the biggest result? Good for 5 patterns, not so good for 5000 patterns. Darren ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
RE: [computer-go] Random weighted patterns
You would only do this for patterns that match in a position. For Many Faces that is typically a few dozen. Many Faces only has about 1800 total patterns in its go knowledge base. Playouts use Mogo patterns, about a dozen total. David -Original Message- From: computer-go-boun...@computer-go.org [mailto:computer-go- boun...@computer-go.org] On Behalf Of Darren Cook Sent: Wednesday, July 15, 2009 8:47 PM To: computer-go Subject: Re: [computer-go] Random weighted patterns So many complex ideas :) Why not just multiply the weight of each pattern by a random number and pick the biggest result? Good for 5 patterns, not so good for 5000 patterns. Darren ___ 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/
Re: [computer-go] Random weighted patterns
On Wed, Jul 15, 2009 at 10:37 PM, David Fotlandfotl...@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/
Re: [computer-go] Random weighted patterns
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 Fotlandfotl...@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/
Re: [computer-go] Random weighted patterns
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 Fotlandfotl...@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/
Re: [computer-go] Random weighted patterns
On Wed, Jul 15, 2009 at 11:37 PM, David Fotland fotl...@smart-games.comwrote: So many complex ideas :) Why not just multiply the weight of each pattern by a random number and pick the biggest result? This is fine if you are looking for the slowest algorithm you can find. But it does have the merit of being straightforward, which is what he was asking for. The binary approach is O(log n) time on average, very efficient. Your approach is O(n). It's like the difference between doing a binary search to find something or scanning the whole list sequentially. If you are looking at less than 5 or 10 patterns there may not be much difference, but I assumed he was choosing among many patterns. - Don David -Original Message- From: computer-go-boun...@computer-go.org [mailto:computer-go- boun...@computer-go.org] On Behalf Of Mark Boon Sent: Wednesday, July 15, 2009 4:07 PM To: computer-go Subject: [computer-go] Random weighted patterns 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/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
