I'm making a Connect Four game where my engine uses Minimax with Alpha-Beta pruning to search. Since Alpha-Beta pruning is much more effective when it looks at the best moves first (since then it can prune branches of poor moves), I'm trying to come up with a set of heuristics that can rank moves from best to worst. These heuristics obviously aren't guaranteed to always work, but my goal is that they'll often allow my engine to look at the best moves first. An example of such heuristics would be as follows:
- Closeness of a move to the centre column of the board - weight 3.
- How many pieces surround a move - weight 2.
- How low, horizontally, a move is to the bottom of the board - weight 1.
However, I have no idea what the best set of weight values are for each attribute of a move. The weights I listed above are just my estimates, and can obviously be improved. I can think of two ways of improving them:
1) Evolution. I can let my engine think while my heuristics try to guess which move will be chosen as best by the engine, and I'll see the success score of my heuristics (something like x% guessed correctly). Then, I'll make a pseudo-random change/mutation to the heuristics (by randomly adjusting one of the weight values by a certain amount), and see how the heuristics do then. If it guesses better, then that will be my new set of heuristics. Note that when my engine thinks, it considers thousands of different positions in its calculations, so there will be enough data to average out how good my heuristics are at prediction.
2) Generate thousands of different heuristics with different weight values from the start. Then, let them all try to guess which move my engine will favor when it thinks. The set of heuristics that scores best should be kept.
I'm not sure which strategy is better here. Strategy #1 (evolution) seems like it could take a long time to run, since every time I let my engine think it takes about 1 second. This means testing each new pseudo-random mutation will take a second. Meanwhile, Strategy #2 seems faster, but I could be missing out on a great set of heuristics if I myself didn't include them.