I have a minimax game playing program that sums together different heuristics to return a value for each state of the game. I would like to implement learning. I want the program to learn weights for each heuristic. What is the most effective means of having the program learn the weights for each heuristic? Of course, it would only know if a certain weight was effective for a certain heuristic after trying it. Is the only option some kind of trial and error system?
Thank you for your help!
On
Reinforcement Learning (RL), in particual Temporal Difference (TD) methods, deal with learning weights for heuristics in non-adversarial setting. How to learn weights for heuristics in a game setting, depends on what algorithms you use to play the game. The major classes of algorithms are alpha-beta minimax and UpperConfidenceTree. For minimax, you can look at the updates to values on the tree nodes as you increase the depth of the tree. I recommend starting by learning about RL-TD, and then reading Bootstrapping from Game Tree Search by Joel Veness et. al.
I've not applied minimax much in practice - but in general its preferable to have an intrinsic measure of score/goodness/badness to base it off of. The first step would be to try and define such a score for you game - and expose that as an interface that is implemented for each supported game.
No! Genetic algorithms are popular for this kind of thing (at least among hobbyists), and can be used successfully for many problems (given sufficient time). You can find a lot of information related to this in early AI research, especially related to chess programs.
You can look up some of the research in hyperparameter optimization to find more machine learning style ways to do it. Unfortunately its not as well studied an area as it probably should be.
There are more possibilities depending on the specifics of the game being implemented / the nature of the heuristics.