Automatic evaluation parameters tuning

Discussion of chess software programming and technical issues.

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Post Reply
Ratta

Automatic evaluation parameters tuning

Post by Ratta » Thu Oct 04, 2007 11:37 pm

hi,
i have written a chess engine (RattateChess, GPL'd opensource, see WBEC) with a decent serch function and an evaluation function with many evaluation parameters that need to be tuned (and i am too lazy to do so by hand).

Is there any algorithm to automatically tune positional evaluation?
Do they work IN PRACTICE?

I heard something about the TDLeaf(lambda) algorithm used by knightcap, was it used in any other moder chess engine? Or is there is anything better?

Thanks and best regards!

Dann Corbit
Posts: 10207
Joined: Wed Mar 08, 2006 7:57 pm
Location: Redmond, WA USA
Contact:

Re: Automatic evaluation parameters tuning

Post by Dann Corbit » Thu Oct 04, 2007 11:41 pm

There are many ways to tune evaluation parameters automatically.

You can use TD-lamda or TD-leaf

You can use a parabolic fit through a pile of data

None of these methods work well in practice (I believe that a hand-tuned eval function is still better).

I don't know why that is. It's counter intuitive that guessing values would be better than actually computing them.

Ratta

Re: Automatic evaluation parameters tuning

Post by Ratta » Fri Oct 05, 2007 12:19 am

Thanks for your anser.
Actually this is a very strange thing, maybe it is just very difficult to do because of the huge number of side effects.

For instance i found that making two different versions of my engine play each other to test the search function was almost useless because of the untuned evaluation function (soon one of them found do a blatant stategical error that was putting it in a lost position, no matter what).

User avatar
Bill Rogers
Posts: 3562
Joined: Thu Mar 09, 2006 2:54 am
Location: San Jose, California

Re: Automatic evaluation parameters tuning

Post by Bill Rogers » Fri Oct 05, 2007 2:36 am

Sounds like a good way for find a major weakness in your program and to fix it. After it is fixed then you can play some more until you find something else that needs ajusting. I used the same way of testing my engine, except I only work with one variable at a time, ie like center control or king protection. Care must be taken as one of more items are changed sometime it upsets all the rest of the items and you have to start all over again.
Bill

Tony

Re: Automatic evaluation parameters tuning

Post by Tony » Fri Oct 05, 2007 1:10 pm

Ratta wrote:hi,
i have written a chess engine (RattateChess, GPL'd opensource, see WBEC) with a decent serch function and an evaluation function with many evaluation parameters that need to be tuned (and i am too lazy to do so by hand).

Is there any algorithm to automatically tune positional evaluation?
Do they work IN PRACTICE?

I heard something about the TDLeaf(lambda) algorithm used by knightcap, was it used in any other moder chess engine? Or is there is anything better?

Thanks and best regards!
I've wasted about a year on this. Well, wasted, I did learn.

The problem with learning IMO is that your evaluation patterns are related, making the scores go to extremes, or leaving to much different combinations. Maybe evetually it is possible to have the scores settle, but I never managed ( ie worse than handtuned)

fe In XiniX, I have piece square evaluation, mobility and safe mobility.

A knight on A1 will have a bad psq score, it can never have high mobility and therefor never high safe mobility so the knight gets punished 3 times.

Most likely this knight will not attack opponent king, undefended pawns etc.

Learning doesn't seem to grasp this.

Tony

Mangar

Re: Automatic evaluation parameters tuning

Post by Mangar » Mon Oct 22, 2007 3:27 pm

Hi,

there is one algorithm that work on a small amount of very relevant parameters, like the piece-values. Sadfully there is no one that works on real life chess engines.

The optimiziation idea is to treat a set of parameters as a "chess-engine-gene". Say you have got 100 parameters. A set of 100 values for these parameters is a gene.
First generate randomly a set of for example 200 genes: your population.

Repeat until the end of days (whatever it is for your population)

Randomly take two genes from your population and let them play a game.
Give the winner one point and remove one point from the looser.
Once a gene has -10 points remove it from the population (kill it).
Once a gene has + 10 points let him have childs with another gene that has many points too. If he has +20 points let him have another child. Kill him if he is too old (has played for example 50 games).
Build a child by copying random parts of each gene to a new gene (don´t let those parts be too small). Add some mutation by randomly changing one value. Use this sparsely.
Take care that your population does not die or grow too large.

After several games take a winner from the population.

You can see that you need a huge amount of games to have a resut.

200 * 50 = 10000 games is really a verry low bound. You can start by only using the material values to have a faster result.

You wouldn´t get a strong chess engine, but an automatic optimisation compared to a random function. Its fun! Your own chess playing population :-)

You can improve algorithm this if you preset ranges for each value.

Greetings Volker

Hart

Re: Automatic evaluation parameters tuning

Post by Hart » Mon Oct 22, 2007 9:34 pm

I am far from being a competent computer chess programmer but I might start with something like this:

Take (say) 1000 different positions from as may engine and GM games as you can find on the internet, preferably played by higher rated engines/GMs of comparable strength. Compute the scores for each position, p[0,...,1,000]. Then with your engine running to a depth of 2-4 or for a time of (say) 5-20 milliseconds, compute the scores in e[0,...,1,000]. From this take the difference of these scores, for example, d=p-e.
Add up the square of all elements in d, for variable S, and now you can see how good your evaluation is at predicting actual winning chances. Obviously, the smaller S, the better your evaluation predicts actual winning chances, which would result in your engine being able to find better moves (I am assuming). You could conceivably write a program that could automate this whole process and in the course of a few minutes, fine tune your evaluation function. It could also tell you which parameters of your evaluation function could be discarded for having no bearing on being able to find better moves or more accurately score positions relative to each other.

Maybe this has been tested and failed, I don't know. But to me, it sounds like a good starting point.

User avatar
michiguel
Posts: 6389
Joined: Thu Mar 09, 2006 7:30 pm
Location: Chicago, Illinois, USA
Contact:

Re: Automatic evaluation parameters tuning

Post by michiguel » Mon Oct 29, 2007 8:58 pm

Hart wrote:I am far from being a competent computer chess programmer but I might start with something like this:

Take (say) 1000 different positions from as may engine and GM games as you can find on the internet, preferably played by higher rated engines/GMs of comparable strength. Compute the scores for each position, p[0,...,1,000]. Then with your engine running to a depth of 2-4 or for a time of (say) 5-20 milliseconds, compute the scores in e[0,...,1,000]. From this take the difference of these scores, for example, d=p-e.
Add up the square of all elements in d, for variable S, and now you can see how good your evaluation is at predicting actual winning chances. Obviously, the smaller S, the better your evaluation predicts actual winning chances, which would result in your engine being able to find better moves (I am assuming). You could conceivably write a program that could automate this whole process and in the course of a few minutes, fine tune your evaluation function. It could also tell you which parameters of your evaluation function could be discarded for having no bearing on being able to find better moves or more accurately score positions relative to each other.

Maybe this has been tested and failed, I don't know. But to me, it sounds like a good starting point.


That is exactly what I am doing. Well, what I intend to do :-)

I started 1.5 years ago and I stalled because I have been busy with other stuff (work). To me it seems like a good idea but...

Miguel

Post Reply