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
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.
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
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
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
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
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
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
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
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
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
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
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.
, 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
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
...@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
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
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
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
, 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
20 matches
Mail list logo