Determining evaluation by a genetic algorithm

[mvanthoor]

Because of all the posts about NNUE, evaluation and related things in the last few weeks, I was thinking about something. Basically, an evaluation term is a fixed or calculated number that is added to the base value (or subtracted if the number is negative).

We call such a number BISHOP_PAIR_BONUS, but it could have also been called X.

Would it be worthwhile to write a chess engine with an evaluation function that just adds.. say... 50 numbers to the base value (determined by material count)? In the beginning those numbers would be random between -50 and +50, and they could be tuned by a genetic algorithm.

I have little experience with neural networks, but enough experience with genetic algorithms to be able to write such a thing. I haven't put any research into this yet... so I may have been done already, and found to be sub-par when compared to something such as Texel tuning... any idea's about this?

[mmt]

I think that after many years of classical eval chess programs and with competition between them and with tuning frameworks, manually crafted features like BISHOP_PAIR_BONUS have their values pretty well tuned, so they will be hard to beat. The advantage of NNs is that they can come up with new functions that nobody has thought of yet. It would be interesting to try to interpret the NNs and maybe come up with some human-understandable rules of thumb and see where it gets you. You could train a net to find the function to represent just the delta compared to the classical eval function - that may be easier to interpret. Then you can write a chess book with insights

[Tony P.]

Go for it!! You don't even have to limit yourself to a linear model: GAs are a valid way of training NNs too that rivals gradient descent, especially when it comes to neural architecture search. The field that studies training with GAs and EAs is called neuroevolution. See e.g. a review published in Nature Machine Intelligence last year; or another survey from this year.

[Tony P.]

Also, NNs are, of course, not the only type of nonlinear classifiers. I've just done a quick search and found an experimental library that trains decision tree (DT) ensembles with EAs - EvaBoost, described in a conference paper (also available as an arXiv preprint). It's slower than the classical algorithms for DT induction but sometimes more accurate.

That said, DNNs tend to outperform 'shallow' learning methods when there's cheap access to large samples of structured data, which is the case in chess.

[Ferdy]

We had a fun experiment on GA with stegemma.

There are also optimizers at nevergrad on GA.

[Hrvoje Horvatic]

Because of all the posts about NNUE, evaluation and related things in the last few weeks, I was thinking about something. Basically, an evaluation term is a fixed or calculated number that is added to the base value (or subtracted if the number is negative).

We call such a number BISHOP_PAIR_BONUS, but it could have also been called X.

Would it be worthwhile to write a chess engine with an evaluation function that just adds.. say... 50 numbers to the base value (determined by material count)? In the beginning those numbers would be random between -50 and +50, and they could be tuned by a genetic algorithm.

I have little experience with neural networks, but enough experience with genetic algorithms to be able to write such a thing. I haven't put any research into this yet... so I may have been done already, and found to be sub-par when compared to something such as Texel tuning... any idea's about this?

If GAs are your thing, go for it... there have been at least 20 papers that show tuning eval Fn with GA works, and there have been several engines, most notably iCE (with PBIL) that confirmed this in practice... but Texel tuning (and it's variants) is MUCH faster... several orders of magnitude faster... you don't have to play games, as in GA case, you just loop through positions and propagate error...

As already mentioned, the advantage of ANNs is that they construct new (micro-)features, they don't tune existing eval...

OTOH, if you used Genetic Programming (GP instead of GA) to construct NEW features, now THAT would be something!