Problems with eval function

[CRoberson]

Yet again, I wish we had math symbols in this forum.

Lets get to the math. Most position evals are of the form
Sigma C(y)*X(y) where y=0 to n, C is the coefficient and X is a
boolean value for the term being triggered or not. Few seem to go
as far as having interdependent terms which increases the complexity.

So, the goal is to find an optimal set of values for all C(y). The fact
that n is typically greater than 100 means we are well into
multi-dimensional solution spaces. So, we can either hand-tune or
try one of the many mathematical or algorithmic methods for finding
near optimal solutions to multi-dimensional equations. First and second
derivative tests are not going to cut it here. This is my favorite part of
computer chess, however it can be quite time consuming.

There have been several papers written on the subject. I am not aware
of any having great results but most work to varying degrees. The
best results have come from tuning C(y) based on match
performance instead of posiiton performance, however I believe it is
possible for position performance to work as a game is a series of
positions. It will take more positions than anyone has tried to date.

The big problem with that is atleast three-fold. Firstly, there is the time to
compelete one game. Secondly, there is the number of games required
for statistical significance. Thirdly, there is overtuning to the training
set. So, you have to keep all these in mind.

There was a paper in the passed few years that claimed great results
using a Genetic Algorithm to tune the eval equation. However, they made
tuning adjustments based on 10 game intervals.

The things you might try: Genetic Algorithms, Simulated Annealers,
Pattern Walk, Neural Networks, Temporal Difference Learning ....

There is much more than that to try, but that would be a start.

[Bill Rogers]

Charles
I understand your problem with not having math sysbols. May I make a suggestion? Log onto a site that uses those symbols do your figures there and save the output to your disk and then post it here.
If people can post large pictures of events around the world then there is no reason that you can not post a sheet with all your symbols on it.
Bill

[diep]

Mind giving a proof that TD learning works?

Vincent

Yet again, I wish we had math symbols in this forum.

Lets get to the math. Most position evals are of the form
Sigma C(y)*X(y) where y=0 to n, C is the coefficient and X is a
boolean value for the term being triggered or not. Few seem to go
as far as having interdependent terms which increases the complexity.

So, the goal is to find an optimal set of values for all C(y). The fact
that n is typically greater than 100 means we are well into
multi-dimensional solution spaces. So, we can either hand-tune or
try one of the many mathematical or algorithmic methods for finding
near optimal solutions to multi-dimensional equations. First and second
derivative tests are not going to cut it here. This is my favorite part of
computer chess, however it can be quite time consuming.

There have been several papers written on the subject. I am not aware
of any having great results but most work to varying degrees. The
best results have come from tuning C(y) based on match
performance instead of posiiton performance, however I believe it is
possible for position performance to work as a game is a series of
positions. It will take more positions than anyone has tried to date.

The big problem with that is atleast three-fold. Firstly, there is the time to
compelete one game. Secondly, there is the number of games required
for statistical significance. Thirdly, there is overtuning to the training
set. So, you have to keep all these in mind.

There was a paper in the passed few years that claimed great results
using a Genetic Algorithm to tune the eval equation. However, they made
tuning adjustments based on 10 game intervals.

The things you might try: Genetic Algorithms, Simulated Annealers,
Pattern Walk, Neural Networks, Temporal Difference Learning ....

There is much more than that to try, but that would be a start.

[rjgibert]

The difficulties of tuning a chess engine run into the "global optimization" problem. To get a handle on what is involved, you might want to check out the following:

http://mathworld.wolfram.com/GlobalOptimization.html

and

http://en.wikipedia.org/wiki/Global_optimization

from which the following quote sums things up fairly well:

In real-life problems, functions of many variables have a large number of local minima and maxima. Finding an arbitrary local optimum is relatively straightforward by using local optimisation methods. Finding the global maximum or minimum of a function is a lot more challenging and has been practically impossible for many problems so far.

I'm pretty sure that most chess programmers flounder around from one local minima to another without even realizing what is really going on with both their testing and their tuning misleading them continually.

[CRoberson]

I think you are quite wrong about most chess programmers.

There is a reason Bob said that it is more Art than Science -
all research papers to date show that hand tuning is more effective
than any of the automated tuning methods. Why is that?

The usefulness of Genetic Algorithms and Simulated annealers comes
in domains where they can quantify the "goodness" of a permutation
change quickly. A good example is TSP (traveling salesman problem).
The time to compute the value of a change is measured in milliseconds.
Given that a G.A. takes about 10,000 to 100,000 iterations to converge,
a millisecond is about all you can afford.

That is a big problem in computer chess. Time to quantify the
"goodness" of a permutation change is about 8 hours. So, 10K iterations
is around 3 years, but I think it will take more iterations.

The most effective technique that I've used is to use a G.A or S.A.
and kick it in the butt with some hand tuning when it gets stuck. The
techniques that you and I mentioned always get stuck, but they
unstick themselves over time. That is the problem in computer chess:
it takes too long with only an automated approach.

That is why this area of computer chess is my favorite part - its rich
for research, because the known techniques aren't good enough.

[rjgibert]

I think you've misconstrued what I wrote. I wasn't advocating automated methods. The links I gave were meant to illustrate the difficulty of doing tuning.

Global optimization is a hard problem. It is not a solved problem.

And I still think most chess programmers don't really understand what they are up against when they do tuning.

[wgarvin]

I'm pretty sure that most chess programmers flounder around from one local minima to another without even realizing what is really going on with both their testing and their tuning misleading them continually.

That sounds very plausible to me. I think many people (including programmers) are not able to resist drawing conclusions when there is not enough evidence to truly support them. Testing will often show a correlation of some kind, but to get from there to causation usually requires an unjustified leap of reasoning.

I read somewhere a claim that about half of all the assumptions programmers make while they are debugging a program turn out to be wrong, and anecdotally I've seen lots of examples in my own debugging sessions which made me a believer of that claim. Even when you think you are being rigorous and thorough, its possible to overlook subtle relationships between things and end up with faulty reasoning. Especially in something as complex as a chess program. Between the tendency of alpha-beta to disguise bugs and occasional inaccurate evaluations, and the interactions between various search techniques, qsearch, SEE, eval, etc. it seems like a chess programmer will have many opportunities to draw incorrect conclusions.