Nonlinearity in evaluation
David Eppstein
I think most programs for chess and similar games have evaluation
functions that are linear: sums of various terms that are computed
pretty much independently of each other, including material and
positional terms. But in the program I've been working on
(for fanorona, not chess, but I think it doesn't matter) I've been
finding that I want my eval to be nonlinear, to handle rules like
trading down only when ahead on material (sometimes such a trade is good
even if the material imbalance becomes smaller) or being more likely to
sacrifice for positional improvement when ahead on material.
I think the "correct" solution is to develop a function that takes as
input various material and positional terms, and combines these numbers
into an estimate of the probability of winning; there are all kinds of
sophisticated statistical regression techniques for learning such
estimates, not all of which give you something linear. But I'm too lazy
to go through all that, and instead have been coming up with simple
formulas that sort of work for a given rule of thumb. Like, to handle
the trade-down rule above, I add a term to my eval proportional to
+-(max(a,b)/min(a,b)-1) where a and b are the two material values; the
-1 part is to make it continuous, because I've discovered that big jumps
in the eval lead to the program making big mistakes to force a jump to happen.
But, I'm not entirely satisfied with such hacks, so I wonder how other
programs are dealing with this sort of nonlinearity.
--
David Eppstein UC Irvine Dept. of Information & Computer Science
epps...@ics.uci.edu http://www.ics.uci.edu/~eppstein/
Robert Hyatt
David Eppstein (epps...@euclid.ics.uci.edu) wrote:
: I think most programs for chess and similar games have evaluation
The best solution is not have discontinuities. For tradeup/down, simply
factor it in from the beginning. The only minor problem this causes is
that if you want the bonus to be significant, by the time you reach a K and
P vs K ending, the bonus will be very large. So you end up with an eval
of +2, when it should be +1. It causes *no* problems in Crafty, but it
would likely send KK into a catatonic state. :)
Tim Mirabile
hy...@crafty.cis.uab.edu (Robert Hyatt) wrote:
>So you end up with an eval
>of +2, when it should be +1. It causes *no* problems in Crafty, but it
>would likely send KK into a catatonic state. :)
KK should consider this:
There are only three correct evaluations in chess - won, lost, and drawn.
Anything else is just an approximation. :)
So all this discussion about a few hundredths of a pawn is pretty silly.
--
Long Island chess -> http://www.webcom.com/timm/ TimM on ICC and A-FICS
Webmaster, tech support - Your Move Chess & Games: http://www.icdchess.com/
David Eppstein
In <3429591a...@snews2.zippo.com> t...@mail.htp.com (Tim Mirabile) writes:
>There are only three correct evaluations in chess - won, lost, and drawn.
>Anything else is just an approximation. :)
This is only true if your opponent is perfect (i.e. never). If your
opponent is imperfect, I think correct evaluations should be the
expected score, taking into account the probability of an opponent
mistake. Anything else may be an approximation, but this is what it
should be an approximation of.
Komputer Korner
I guess that Tim doesn't believe in the THEORY OF PROBABILITY.
--
- -
Komputer Korner
The inkompetent komputer
If you see a 1 in my email address, take it out before replying.
Please do not email both me and the r.g.c.c. at the same time. I read all
the postings on r.g.c.c.
Tim Mirabile <t...@mail.htp.com> wrote in article
<3429591a...@snews2.zippo.com>...
> hy...@crafty.cis.uab.edu (Robert Hyatt) wrote:
>
> >So you end up with an eval
> >of +2, when it should be +1. It causes *no* problems in Crafty, but it
> >would likely send KK into a catatonic state. :)
>
>
> KK should consider this:
>
> There are only three correct evaluations in chess - won, lost, and drawn.
> Anything else is just an approximation. :)
>
Komputer Korner
None of what you have said contradicts the 10 Commandments of Opening
Theory.
--
- -
Komputer Korner
The inkompetent komputer
If you see a 1 in my email address, take it out before replying.
Please do not email both me and the r.g.c.c. at the same time. I read all
the postings on r.g.c.c.
Tim Mirabile <t...@mail.htp.com> wrote in article
<3428622c...@snews2.zippo.com>...
>
> I was being extreme to make a point, but I will bite...
>
> I have to disagree here, since I am talking about objective evaluations,
and
> what you are discussing is how to choose a move to maximise the expected
result
> against a given opponent.
>
> If you had a perfect evaluator and a method of estimating the
probabilities of
> the opponent selecting a each move in a position, then you could easily
modify
> standard search techniques to choose the best move to play against that
> opponent.
>
> If you want to find the expected score in a given position where it is
the
> opponent's move, just sum up the expected score of the position resulting
from
> each legal move times the probability of that move being played. The
deeper you
> search in this way, the more potential opponent mistakes you are taking
into
> account.
>
> This type of search could have the strange effect where a losing move can
give a
> higher expected score than a drawing one if the losing move results in
more
> error provoking position.
Tim Mirabile
epps...@euclid.ics.uci.edu (David Eppstein) wrote:
>In <3429591a...@snews2.zippo.com> t...@mail.htp.com (Tim Mirabile) writes:
>>There are only three correct evaluations in chess - won, lost, and drawn.
>>Anything else is just an approximation. :)
>This is only true if your opponent is perfect (i.e. never). If your
>opponent is imperfect, I think correct evaluations should be the
>expected score, taking into account the probability of an opponent
>mistake. Anything else may be an approximation, but this is what it
>should be an approximation of.
I was being extreme to make a point, but I will bite...
Tim Mirabile
"Komputer Korner" <kor...@netcom.ca> wrote:
>None of what you have said contradicts the 10 Commandments of Opening
>Theory.
Thank you, I was worried about that. :)
"Komputer Korner" <kor...@netcom.ca> wrote:
>I guess that Tim doesn't believe in the THEORY OF PROBABILITY.
I'm not sure what you mean by this. If something depends on chance it makes
sense to calculate probabilities, and sometimes these probabilities can be
calculated exactly, without approximation.
If you calculate the probability of getting two heads on two flips of a fair
coin at %25, then you do the flips and two heads come up, you don't go back and
say "gee, maybe my calculation was wrong." But if you evaluate a chess position
and the result turns out differently, and you can't find any errors, you may
want to go back and rethink your evaluation.