(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.

• quintumnia: I kindly request you to post this same question here Cross Validated,check it out,it's with in the stack exchange sites.
• Stan Callewaert: Thank you for the advice, I will post the question there!
• Doc Brown: Note the SE network has a strict "no-crossposts" policy, so if you want to post it on another SE site, delete it here beforehand. However, I think the question can stay here.
• Neil Slater: You have cross-posted this exact same question to 4 sites (SO, AI, Stats are the other ones)! Please pick one at a time and be patient. Posting it to multiple sites wastes other peoples' time.
• Doc Brown: @StanCallewaert, please be nice, follow the rules of the site and delete the crossposts. Thanks.

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

• Stan Callewaert: Thank you so much for the answer, very short and gives me a lot to read about!
• quintumnia: @StanCallewaert It's not the right answer,and can those who up vote tell us why.
• Doc Brown: @quintumnia: if you think this answer is not correct, shouldn't you tell us why, first?
• Stan Callewaert: @quintumnia I've investigated the evolutionary/genetic algorithms a bit and I am going to implement it this way. It's a perfect answer to my case
• quintumnia: @StanCallewaert alright.

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.

• Stan Callewaert: the performance of 2 sets of parameters playing against each other doesn't vary that much when the parameters are changed. Maybe the game can stop earlier if you play with a bad opponent against a good one (because the bad one will lose early on). But bad players always need to be picked however to get out of local minima. I will however read up on the posted links but don't think the algorithm will be a big improvement compared to an evolutionary/genetic algorithm.
• Doc Brown: Very interesting, +1