> I have a probability table of all possible moves. What is the > fastest way to pick with probability, possibly with reducing the > quality of probability?! > > I could not find any discussion on this on computer-go, but probably > I missed it :(
I may have misunderstood the question, but there was some discussion on how to pick from moves which have different weights. ... the one I found is from May 2009, and it seems the online archives only go back to 2010! So I've pasted together the thread, below. Darren Question by Isaac: > I'm about to work on heavy playouts, and I'm not sure how to choose a > move during the playout. I intend to have weights for various > features. I thought about 3 versions: > > 1. In a position, calculate all the weights and the total weight. > Then, play one move i with the probability weight_i/total_weight. > > 2. Select a move randomly. Calculate the weight of it, then squash > that weight in the [0,1] range. Play that move with that > "probability". > > 3. Same as 2., but play that move if the "probability" is higher than > a certain treshold. > > Which one do you think works best? I'm looking forward to other > ideas, too. :) Álvaro replies: You have the most control with option 1. You can implement this fast by keeping the sum of the weights for each row and for the total board. You then "roll" a number between 0 and total_weight, and advance through the rows subtracting the probability of each row until you would cross 0, then go along the row subtracting the probability of each point, until you would cross zero. Pick the point where the process ends. I initially implemented a similar scheme using a binary tree, and I think it was Rémi who told me about this method, which is simpler and faster in practice. You may have problems with floating-point precission doing this. The easy solution is using integers for weights, but perhaps there are ways to make the code robust while keeping the more natural floating-point values. Bill Spight also replied: Keeping cumulative weights, as Alvaro suggested, is one way to go. You can improve #1 by choosing a possible play randomly, and then making the play with the probability weight/maximum_weight. _______________________________________________ Computer-go mailing list [email protected] http://computer-go.org/mailman/listinfo/computer-go
