Eric Boesch wrote:
By the way, does anybody know of any nifty tools or heuristics for efficient probabilistic multi-parameter optimization? In other words, like multi-dimensional optimization, except instead of your function returning a deterministic value, it returns the result of a Bernoulli trial, and the heuristic uses those trial results to converge as rapidly as possible to parameter values that roughly maximize the success probability. The obvious approach is to cycle through all dimensions in sequence, treating it as a one-dimensional optimization problem -- though the best way to optimize in one dimension isn't obvious to me either -- but just as with the deterministic version of optimization, I assume it's possible to do better than that. It might be fun problem to play with, but if good tools already exist then it wouldn't be very productive for me to waste time reinventing the broken wheel.
RSPSA: http://www.sztaki.hu/~szcsaba/papers/rspsa_acg.pdf Levente Kocsis, Csaba Szepesvari, Mark H.M. Winands Abstract. Most game programs have a large number of parameters that are crucial for their performance. While tuning these parameters by hand is rather di±cult, successful applications of automatic optimisation al- gorithms in game programs are known only for parameters that belong to certain components (e.g. evaluation-function parameters). The SPSA (Simultaneous Perturbation Stochastic Approximation) algorithm is an attractive choice for optimising any kind of parameters of a game pro- gram, both for its generality and its simplicity. It's disadvantage is that it can be very slow. In this article we propose several methods to speed up SPSA, in particular, the combination with RPROP, using common random numbers, antithetic variables and averaging. We test the result- ing algorithm for tuning various types of parameters in two domains, poker and LOA. From the experimental study, we conclude that using SPSA is a viable approach for optimisation in game programs, especially if no good alternative exists for the types of parameters considered. Rémi _______________________________________________ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/