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. Now, to implement something like proximity heuristic (I assume you mean "proximity to the last move" here), instead of adding a weight to each point for this purpose, 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. Álvaro. _______________________________________________ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
