On Jul 21, 2008, at 10:26 PM, "Álvaro Begué" <[EMAIL PROTECTED]>
wrote:
On Mon, Jul 21, 2008 at 7:32 PM, Jason House
<[EMAIL PROTECTED]> wrote:
I'm starting heavy plyouts, with variable move selection weights. The
proximity heuristic seems like a performance killer since most
weights would
require an update with each move.
How do others handle this? Is proximity reserved for the search tree?
How do others store data for rapid lookup?
Ignoring the proximity heuristic, the data structure I use is a 19x19
+ 19 + 1 structure (the weight of each point, the sum of the weights
for each row and the total sum of weights). In order to update the
weight for one point, you need to adjust three numbers. To pick a
random point during the playout, pick a random number between 0 and
the total sum, go along the rows subtracting the weight of each row
from that number until you would get to 0 or less, and then go through
the point in that row subtracting the weight of each point from the
number until you would get to 0 or less. This is how Remi told me he
was doing it, and it's a very good method. I was using a binary tree
before, which has much more expensive updates.
That seems like a good method, especially when updates are rare.
Now, to implement something like proximity heuristic (I assume you
mean "proximity to the last move" here),
That and possibly penultimate proximity.
instead of adding a weight to
each point for this purpose,
Adding of weights is much easier. Remí's paper uses multiplication of
weights which means one must scan the surrounding area to compute the
addative weights. I think the paper used a very large area for
proximity... up to distance 17, IIRC.
you can keep these weights on a separate
table, which has coordinates that are relative to the last move, and
where you also have a global number that is the sum of all the weights
associated with the proximity heuristic. Then you can start the move
picking by deciding if you are going to pick a move based on proximity
or based on the rest of the heuristics (you have the total weight of
both, so just flip a biased coin), and then pick the move one way or
the other. If the outcome of this first bifurcation is that you will
pick a move based on proximity, you pick a relative jump from the last
move following the probability distribution prescribed by the
heuristic. It is very possible that this point will be occupied or
outside the board, in which case you can simply reject the result and
try again.
I don't know if I explained that very clearly, and I never got around
to implementing it myself, but that's how I intend to implement
proximity. Well, I actually only wanted to boost the weight for
immediate neighbors of the last move, in which case I can count how
many of them are empty and have many fewer rejections.
I hope you find this plan useful.
At a minimum, it's interesting._______________________________________________
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
