(AI) algorithm to optimize input parameters

Question

Background information

I am building a program that plays checkers as good as possible. It already plays pretty well but the goal is to improve it even more.

This can be done by adding new methods to evaluate how "good" a certain board-state is. I've already implemented these methods but each of the methods has a parameter by which it can be multiplied.

I already implemented the fact that I can let the program play against itself and the outcome of the game is a number that is positive if the player wins (or plays a draw with an advantage in pieces), a negative number if the player loses (or plays a draw with an advantage in pieces) or 0 if they draw and the pieces are equal.

Question

I have 3 parameters that can vary from 0 to 1. I need to find a combination of these 3 parameters that needs to be as many numbers after the comma as possible in and needs to be calculated as fast as possible.

I can let 2 different sets of parameters play against each other with an outcome that is positive if the first set of parameters has an advantage (the bigger the positive number, the bigger the advantage), negative if the second set of parameters has an advantage and 0 if they both have the same kind of advantage.

E.g.: (0.232, 1, 0.62) against (0.12345, 0.71, 0) can output 1.32987 which means that the first set of parameters has an advantage. Take into account that it takes around 2 minutes to get an output of 2 sets playing against each other!

I would like to know an algorithm/literature/keywords/explinations of how I can find the an as precise as possible set of numbers that wins against all the other set of numbers?

Statistics

I've already ran some tests and found out that probably (not sure) for each parameter the effect will be that the results will get better until they get to a peak and than they wil drop again.

Answer 1

I would recommend to try different standard algorithms for optimization of non-differentiable functions and see how well it works. Out of my head, in increasing complexity:

• hill climbing
• threshold accepting
• simulated annealing
• evolutionary algorithms

Answer 2

SMAC, Sequential Model-based Algorithm Configuration, is a relatively recent approach to this problem. It may well be overkill. It is aimed at the scenario where evaluating a particular configuration is very expensive. Many traditional parameter optimization approaches assume that evaluating a particular parameter choice is not that expensive. There is an implementation for Python.

The high-level idea of SMAC is to build up a predictive model of the performance of the algorithm for various configuration parameters (this is the "model-based" part), and to update and improve that model as new instances are evaluated (this is the "sequential" part). The predictive model allows guiding the choice of which configuration to try next so that the most information can be gained with the least amount of evaluations. Of course, it is the details of this that make SMAC.

Other work by Frank Hutter, one of the leads on SMAC, is also relevant and interesting. He has done work on earlier but still relevant related systems such as ParamILS. Also closely related but not Hutter's work is Gender-based Genetic Algorithms (GGA).

If you are very interested in using these kinds of tools, you may find Pitfalls and Best Practices in Algorithm Configuration interesting.