I am developing a chess program. And have made use of an alpha beta algorithm and a static evaluation function. I have successfully implemented both but I want to improve the evaluation function by automatically tuning the weights assigned to its features. At this point am totally confused about the policy suitable for updating the weights of the function. One policy I have in mind is to check whether a move is good or bad before updating weights but I don't really know how to implement it. Thus I need ideas and pseudo code please.
In Chess, you use SPSA and CLOP. Those are the algorithms used by Stockfish in Fishtest to tune its parameter. The algorithm worked so well that it made Stockfish be the strongest engine in the world.
Please note that the algorithms are very complicated mathematically. One could write a PHD thesis on this topic. In SPSA, you start from a best guess from the value. Then play games, use those games to derive a better gradient for the next series of parameters.
The maths is very hard, but it all boils down to some statistics - you play games, and use those games to derive a distribution to update the parameters you want to tune.
I might approach this via genetic algorithm.
- Each param in the gene represents one weight you use for tuning.
- Have a fairly large test suite of positions + moves made by grandmasters (randomly over many middle game positions).
- Create a random initial population of genes to be used in competition. You can include any feature weights you already believe to be good as well.
- For each gene, for each position, do a shallow search based on how much training time you want to take.
- For every position where your program produces the same move as a grandmaster, add one to a total associated with a gene. This total is what the GA should try to maximize.
- Random pairing for mating rights competition based on above score, and breed the results using standard GA techniques.
- Run until convergence.
Whatever final weight you get becomes your feature weight.