On Mon, Jul 21, 2008 at 10:41 PM, Jason House <[EMAIL PROTECTED]> wrote: > 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.
Yes, adding of weights is a lot easier, but I find it hard to justify theoretically. It's a little late now to try to make a detailed discussion of this tricky point, but I am more or less convinced that the right thing to do would be multiplicative in nature. This additive hack might work well enough and it's simpler, so I would give it a try. In the case of using only immediate neighbors, you can actually do the multiplicative thing without much overhead over what I proposed earlier. > > >> 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 > [email protected] > http://www.computer-go.org/mailman/listinfo/computer-go/ > _______________________________________________ computer-go mailing list [email protected] http://www.computer-go.org/mailman/listinfo/computer-go/
