Incoporating chess knowledge in chess programs
MANOHARARAJAH VALAVAN
start up a discussion of chess knowledge and thir incoporation into chess
programs.
As I am not a good player (rating around 1400), my chess program doesn't have
that good of an evaluation function:
- detects doubled, backward, and isolated pawns. For each of the doubled,
backward, and isolated pawns some points are taken away if the opponent
attacks them. A small bonus is assigned for connected pawns. Passed
pawns are given a large bonus depending on the rank they are on.
which of these types of pawns is the worst to have? I currently
discourage doubled pawns greatly.
- detects knight outposts and assigns a bonus for that.
- bonus for having both bishops. Also takes into account bad/good bishops.
- detects doubled rooks on open/semi-open files. Also handles single rooks
on open/semi-open files. A bonus is assigned if rook is on the seventh
rank.
- king safety detection is pretty simple: bonus for pawn cover and
discourages allowing the opponent to attack squares near king.
- mobility of all pieces are considered.
- a bonus is given if a side exchanges pieces when ahead in material.
Obviously quite a bit of knowledge is missing here... I would like to get
opinions on other chess knowledge that can be easily added to a chess program.
--
-------------------------------------------------------------------------------
man...@ecf.utoronto.ca | 3rd year Comp Eng., University of Toronto
Valavan Manohararajah |
-------------------------------------------------------------------------------
Robert Hyatt
: Chris mentioned that a lot of guys were "speed demon" programmers, so lets
: start up a discussion of chess knowledge and thir incoporation into chess
: programs.
<snip>
:
: Obviously quite a bit of knowledge is missing here... I would like to get
: opinions on other chess knowledge that can be easily added to a chess program.
:
For my input, rather than a long post here, get the latest Crafty source
and look at evaluate.c... I've tried to include comments for everything I
do so it can be "read". It's not complete by anybody's standard, but it
does have a lot of simple-to-implement ideas, and a few difficult-to-imple-
ment ideas.
Chris Whittington
You might start by analysing the knowledge that is *not* in the
evaluation function of various programs.
1. You'ld be surprised.
2. You start asking questions about how do they 'know' what
they do know, and thus get a handle of the evaluation-search
interaction process.
3. You can start to think about what could fruitfully go into
the evaluation function.
Chris Whittington
Chris Whittington
>
> Chris mentioned that a lot of guys were "speed demon" programmers, so lets
> start up a discussion of chess knowledge and thir incoporation into chess
> programs.
>
> that good of an evaluation function:
>
> - detects doubled, backward, and isolated pawns. For each of the doubled,
> backward, and isolated pawns some points are taken away if the opponent
> attacks them. A small bonus is assigned for connected pawns. Passed
> pawns are given a large bonus depending on the rank they are on.
>
> which of these types of pawns is the worst to have? I currently
> discourage doubled pawns greatly.
>
> - detects knight outposts and assigns a bonus for that.
>
> - bonus for having both bishops. Also takes into account bad/good bishops.
>
> - detects doubled rooks on open/semi-open files. Also handles single rooks
> on open/semi-open files. A bonus is assigned if rook is on the seventh
> rank.
>
Yes, you'll need all this - its fairly trivial stuff and most programs
that run at less than 30,000 nodes per second (p100) will have it.
Faster ones will have a variant generated by pre-processing at the root.
> - king safety detection is pretty simple: bonus for pawn cover and
> discourages allowing the opponent to attack squares near king.
>
Well I'm glad you think so (simple that is) :)
Most programs keep it simple because to do it 'properly' is a
massive undertaking, and, even then, there'll be holes everywhere.
> - mobility of all pieces are considered.
standard, you need some variant on mobility.
>
> - a bonus is given if a side exchanges pieces when ahead in material.
>
also standard
> Obviously quite a bit of knowledge is missing here... I would like to get
> opinions on other chess knowledge that can be easily added to a chess program.
>
It is *not* easy adding chess knowledge beyond a relatively trivial base.
The interactions are horrendous.
Factors needed for one position will kill your program in another.
If you are 1400, as you say, you'll need a good chess player, who
is prepared, as a labour of love, to spend literally months and months
(or years) playing, analysing, studying your program, communicating to
you.
The requirement for the good chess player is even worse. Most chess
players are semi-insane, utterly appaling at human-human interaction,
and lost interest in anything other than their own navels at birth.
You face an impossible task.
Join the club.
Chris Whittington
Bruce Moreland
chr...@cpsoft.demon.co.uk says...
>
>You might start by analysing the knowledge that is *not* in the
>evaluation function of various programs.
>
>1. You'ld be surprised.
>
>2. You start asking questions about how do they 'know' what
>they do know, and thus get a handle of the evaluation-search
>interaction process.
>
>3. You can start to think about what could fruitfully go into
>the evaluation function.
At the WMCCC last year David Levy walked by my game and tried to
understand a move that my program had just made. He made some
comment to the effect that the program must be trying to increase
the mobility of the piece. I told him, "My program has no
mobility term of any sort." He seemed surprised.
I don't have any numbers to support anything I say in the rest of
this post, it is all purely speculation, so filter as you wish.
In some cases I think a mobility function might help, but in other
cases it can lead to erroneous leaf evals via some conceptual
bugs. In the middlegame you'd rather your king not have eight
squares mobility, for rooks I would be more interested in vertical
mobility than horizontal mobility, unless the rook was on the 7th,
for the queen it might help a little as long as you kept it from
coming to the center on move 3, and for knights it might not
matter much at all, as you can usually relate knight mobility to
proximity to the center, which is easier to compute.
The piece it might really matter for is the bishop. For a long
time my program was as happy having a bishop on g2 that could go
all the way to a8, as it was with a bishop on g2 that bit directly
into a pawn ram on f3/f4. But there may be easier ways to
evaluate bishops than full mobility computation, as well.
Once you've implemented a mobility term you could justify its
existence whenever your program cramps someone to death, but my
program does this just fine without such a term. I'm not
convinced that you need to be explicit about all of your terms,
some of the terms can synthesize from a combination of simpler
terms plus search -- this is what I believe Don Beal's recent
experiments with a "random" evaluation function show: that ANY
evaluation function will synthesize a mobility term because with
more moves to choose from, chances are increased that the program
will determine (correctly or not) that one of the positions it can
force is good. So it will tend to gravitate to lines where it has
increased mobility somewhere above the tip nodes. An off the wall
thought is that it might even be possible that an eval function
that penalized mobility could cause a program to play for
increased mobility if it searched deeply enough.
I believe that increased search depth not only increases tactical
competence, but will tend to improve positional play, through
synthesis of evaluation terms that aren't actually in the
evaluation function, and that these terms will be better than
terms that you can write in the evaluation function, since they
are terms that relate directly to the position being searched. My
conclusion: search depth is a good thing to increase, even when
you feel that you are tactically sufficient, because that extra
plies function effectively as an improved evaluation function.
My feeling about eval functions is that they should be fast, so as
not to impede the search, and that they should contain bonuses and
penalties for small things that you think are usually good or bad,
but that you don't have to try to resolve tactical situations in
the eval function, hopefully if you keep your pieces on good
squares, and avoid static weaknesses, you can avoid tactical
pitfalls a few plies above the leaf nodes.
bruce
Robert Hyatt
: In article <83597811...@cpsoft.demon.co.uk>,
For anyone following Crafty, if you read the comments that explain
each version, you'll note that the very first eval was mobility only,
because it's trivial with bitmaps. With the rotated bitmaps, it's
even better than trivial.
If you read further, you'll find where mobility was slowly removed
from all pieces other than bishops. Rook mobility is not just a simple
"how many squares does it attack", but, rather, how many *important*
squares does it attack. Such as squares on the 7th rank. Squares on
an open file, as opposed to squares on your own back rank. I used to
think that mobility was useful, and after reading several papers, it
seemed even more important. I recall one paper by Dap Hartman and
someone else where they measured mobility and plotted it for the winner
and loser of many games, with the result that the winner's mobility was
always higher. I now question the concept and openly wonder whether the
increased mobility was a *cause* of winning, or an *effect* of winning.
That is, does increasing mobility guarantee winning? Of course it
doesn't. If you do rook scoring right (not moving a rook to a rank where
it is cut off from reaching an open file, for example), then "right" will
naturally improve mobility as the game progresses, even without counting
it. If you do count mobility, you'd likely not want to check for open
files as it's sort of redundant. And you'd likely move a rook to a wrong
file with more mobility.
:
: Once you've implemented a mobility term you could justify its
:
MANOHARARAJAH VALAVAN
>At the WMCCC last year David Levy walked by my game and tried to
>understand a move that my program had just made. He made some
>comment to the effect that the program must be trying to increase
>the mobility of the piece. I told him, "My program has no
>mobility term of any sort." He seemed surprised.
>
>I don't have any numbers to support anything I say in the rest of
>this post, it is all purely speculation, so filter as you wish.
>
>In some cases I think a mobility function might help, but in other
>cases it can lead to erroneous leaf evals via some conceptual
>bugs. In the middlegame you'd rather your king not have eight
>squares mobility, for rooks I would be more interested in vertical
>mobility than horizontal mobility, unless the rook was on the 7th,
>for the queen it might help a little as long as you kept it from
>coming to the center on move 3, and for knights it might not
>matter much at all, as you can usually relate knight mobility to
>proximity to the center, which is easier to compute.
what if the knights every possible move was biting into its own color pawns?
Aren't you taking a big risk in saying that as long as knight is in the center
it is good?
>
>The piece it might really matter for is the bishop. For a long
>time my program was as happy having a bishop on g2 that could go
>all the way to a8, as it was with a bishop on g2 that bit directly
>into a pawn ram on f3/f4. But there may be easier ways to
>evaluate bishops than full mobility computation, as well.
>
As both Bob and Ed S. mentioned, mobility will kill 2 birds with one stone
for the bishop (or is it three birds). It will take care of mobility,
bad/good bishops and will assign bonus for having both bishops.
Peter W. Gillgasch
> In article <83597811...@cpsoft.demon.co.uk>,
> chr...@cpsoft.demon.co.uk says...
> >
> >You might start by analysing the knowledge that is *not* in the
> >evaluation function of various programs.
> >
> >1. You'ld be surprised.
> >
> >2. You start asking questions about how do they 'know' what
> >they do know, and thus get a handle of the evaluation-search
> >interaction process.
> >
> >3. You can start to think about what could fruitfully go into
> >the evaluation function.
Or you can think about what can be fruitfully be removed as Bruce has
pointed out.
> At the WMCCC last year David Levy walked by my game and tried to
> understand a move that my program had just made. He made some
> comment to the effect that the program must be trying to increase
> the mobility of the piece. I told him, "My program has no
> mobility term of any sort." He seemed surprised.
Without additional data it is very hard to explain *why* a program makes
a certain move. If it wins material or checkmates then it is obvious but
if it plays in an even position it is basically impossible most of the
time to explain which component of the evaluation was responsible for
the move. The absence of some terms can be deduced by certain moves, but
not their presence.
> I don't have any numbers to support anything I say in the rest of
> this post, it is all purely speculation, so filter as you wish.
I could produce some numbers but I am too lazy. What I am saying is
based on experience with about 3 1/2 chess engines but of course it is
somewhat speculative as well.
> In some cases I think a mobility function might help, but in other
> cases it can lead to erroneous leaf evals via some conceptual
> bugs.
If you choose a naive implementation that rewards pseudo legal mobility
for all pieces this is obviously true.
> In the middlegame you'd rather your king not have eight
> squares mobility,
If you do mobility evaluation I think that it makes sense to partition
the evaluation into at least three classes:
(a) king mobility - used in the endgame only
(b) pawn mobility - I don't know if this is useful at all,
maybe it helps in certain endgames.
(c) other pieces - those could be treated sepearately for
all piece classes.
> for rooks I would be more interested in vertical
> mobility than horizontal mobility, unless the rook was on the 7th,
> for the queen it might help a little as long as you kept it from
> coming to the center on move 3, and for knights it might not
> matter much at all, as you can usually relate knight mobility to
> proximity to the center, which is easier to compute.
I agree. I have never observed that knight mobility in the leaf node
eval helps. Of course positions can be constructed in which it helps but
those positions are so rare that it makes no sense to detect them during
search time.
> The piece it might really matter for is the bishop. For a long
> time my program was as happy having a bishop on g2 that could go
> all the way to a8, as it was with a bishop on g2 that bit directly
> into a pawn ram on f3/f4. But there may be easier ways to
> evaluate bishops than full mobility computation, as well.
I agree here as well. The bishop is the hardest piece to evaluate
especially if the pawn structure is highly flexible. As I started chess
programming I often saw my program play pawn moves that excluded a
bishop from the rest of the game. As I added mobility and some other
stuff to DarkThought in the fall of 94 this problem vanished.
> Once you've implemented a mobility term you could justify its
> existence whenever your program cramps someone to death, but my
> program does this just fine without such a term.
I *believe* that some form of mobility evaluation is potentially useful
in all programs. After having written my first chess engine I
experimented quite a lot with mobility. It is a win in terms of playing
strength if execution time does not matter. If execution time does
matter then it depends solely on your implementation. If it is fast it
is a win. If it is slow it decreases the strength of the program. I
believe that with respect to mobility (and probably with respect to most
evaluation features) there are 3 classes of chess programs:
(A) - programs that are too slow for the additional term.
the term destroys the tactical sufficiency of the
program.
(B) - programs that have enough speed to play well with
the additional term and the additional term does not
cost you an arm and a leg.
(C) - programs that are so damned wickedly fast that you
loose more strength by adding the term due to slowdown
than you gain due to knowledge.
Of course you could "stuff" a class C program with so much knowledge
that it falls back into class B but this is a matter of belief.
> I'm not
> convinced that you need to be explicit about all of your terms,
> some of the terms can synthesize from a combination of simpler
> terms plus search -- this is what I believe Don Beal's recent
> experiments with a "random" evaluation function show: that ANY
> evaluation function will synthesize a mobility term because with
> more moves to choose from, chances are increased that the program
> will determine (correctly or not) that one of the positions it can
> force is good. So it will tend to gravitate to lines where it has
> increased mobility somewhere above the tip nodes.
Good point.
> An off the wall
> thought is that it might even be possible that an eval function
> that penalized mobility could cause a program to play for
> increased mobility if it searched deeply enough.
This is not intuitively understandable to me. Of course it depends on
the weights of the other terms. Are you saying that you can imagine that
if you do material evaluation plus mobility *penalty* as evaluation
function with nothing else added that a deep search would favour open
positions? I don't think so.
> I believe that increased search depth not only increases tactical
> competence, but will tend to improve positional play, through
> synthesis of evaluation terms that aren't actually in the
> evaluation function, and that these terms will be better than
> terms that you can write in the evaluation function, since they
> are terms that relate directly to the position being searched. My
> conclusion: search depth is a good thing to increase, even when
> you feel that you are tactically sufficient, because that extra
> plies function effectively as an improved evaluation function.
I agree 100%. As soon as your evaluation function has reached a certain
knowledge content the search depth becomes more important again.
Certainly there are pieces of knowledge that are very helpful because
the interact only little with other pieces of knowledge even if you
search quite deeply. A trivial example are doubled pawns. They interact
little with other things and if there is no loss of material ahead most
programs would accept it too easily if the programmer did not tell the
program explicitely about it.
Other pieces of knowledge are completely reduntant, e.g. rewarding the
defense of a weak pawn or blocking the advance of a passed pawn
because there are enough components in a usual evaluation function that
are sensitive to this features as well.
> My feeling about eval functions is that they should be fast, so as
> not to impede the search, and that they should contain bonuses and
> penalties for small things that you think are usually good or bad,
> but that you don't have to try to resolve tactical situations in
> the eval function, hopefully if you keep your pieces on good
> squares, and avoid static weaknesses, you can avoid tactical
> pitfalls a few plies above the leaf nodes.
Likewise.
-- Peter
Tom Kerrigan
obvious but very insightful observation: increase the search depth and you're
increasing the program's knowledge. He uses the example of a fork. A 1 ply search
will not detect a fork, but a 2 ply search will have this "knowledge".
I use this observation to explain certain behavior in my program. I don't notice a
problem with a bishop on g2 blocked by a friendly pawn on f3. I think this is
because I have a serious bonus for the bishop being in the very center of the
board, and the search expands on this term (as mentioned above) by formulating
paths for the bishop to reach the center. Sometimes such formulation makes it look
for all the world like I have a mobility term.
Cheers,
Tom
_______________________________________________________________________________
Tom Kerrigan kerr...@frii.com O-
If at first you don't succeed, redefine success.
Bruce Moreland
In article <199606291628273486441@[194.121.104.139]>, gil...@ilk.com
says...
>Bruce Moreland <brucemo> wrote:
>> An off the wall
>> thought is that it might even be possible that an eval function
>> that penalized mobility could cause a program to play for
>> increased mobility if it searched deeply enough.
>
>This is not intuitively understandable to me. Of course it depends on
>the weights of the other terms. Are you saying that you can imagine that
>if you do material evaluation plus mobility *penalty* as evaluation
>function with nothing else added that a deep search would favour open
>positions? I don't think so.
This was just a goofy idea. There might be some truth in it, but it is
more likely that it is wrong but still interesting.
Consider a twenty-ply search that is trying to minimize mobility. Break
this up in an unorthodox manner -- make an eval function that does a
fifteen-ply search, and stick a five-ply search on top of that. My
suggestion is that perhaps if you treated this eval function as a black
box you could conclude that it was trying to maximize mobility, because it
might help you minimize mobility at the tips if you have a lot of paths to
choose from closer to the root. See what I mean? I'm just suggesting
that a term synthesized from search might dominate a contrary term in the
eval function, if the search has long enough to work.
Of course I have no evidence for this.
bruce
Bruce Moreland
In article <DtrMI...@ecf.toronto.edu>, man...@ecf.toronto.edu says...
>what if the knights every possible move was biting into its own color pawns?
>Aren't you taking a big risk in saying that as long as knight is in the center
>it is good?
If people drove as conservatively as they write chess programs, the speed limit
on US interstates would be five miles per hour, and even at those speeds cars
would all have roll cages.
Of course there is risk, there is also reward. I contend that the risk is
miniscule, and that the reward is not.
bruce
Bruce Moreland
In article <4r5fsn$i...@europa.frii.com>, kerr...@frii.com says...
>
>In the CHESS 4.x article in the Man and Machine book, Slate makes a seemingly
>obvious but very insightful observation: increase the search depth and you're
>increasing the program's knowledge. He uses the example of a fork. A 1 ply
search
>will not detect a fork, but a 2 ply search will have this "knowledge".
>
>I use this observation to explain certain behavior in my program. I don't notice
a
>problem with a bishop on g2 blocked by a friendly pawn on f3. I think this is
>because I have a serious bonus for the bishop being in the very center of the
>board, and the search expands on this term (as mentioned above) by formulating
>paths for the bishop to reach the center. Sometimes such formulation makes it
look
>for all the world like I have a mobility term.
I think you will see this if you look harder. You don't often get a ram on
f3/f4, but you might see a program play d5 when it has a nice bishop on c4, or
play c4 when it has a bishop on b3. Also if you watch slower time control games
with very good players, you will see them take advantage of bad bishops all the
time.
bruce
Peter W. Gillgasch
Bruce Moreland <brucemo> wrote:
> In article <DtrMI...@ecf.toronto.edu>, man...@ecf.toronto.edu says...
>
> >what if the knights every possible move was biting into its own color
> >pawns? Aren't you taking a big risk in saying that as long as knight is
> >in the center it is good?
>
> If people drove as conservatively as they write chess programs, the speed
> limit on US interstates would be five miles per hour, and even at those
> speeds cars would all have roll cages.
I love that post :)
> Of course there is risk, there is also reward. I contend that the risk is
> miniscule, and that the reward is not.
Agree. If you take a look at the root node and detect such situations if
they are already there (e.g. lots of pawn rams that cannot be resolved
without one player loosing material that restrict the knight moves on a
given square) then you are *very* safe and you still can drive 55...
Of course this is not exact knowledge but I bet that the difference will
not influence the outcome of your search in 99.9% of the cases if you
look carefully.
Another point is how likely your program will like to play into such a
situation during the tree search. I'd say that it is quite unlikely for
most programs since most programs are equipped with evaluation functions
that steer into open positions.
-- Peter
Robert Hyatt
Peter W. Gillgasch (gil...@ilk.de) wrote:
: Bruce Moreland <brucemo> wrote:
:
: > In article <DtrMI...@ecf.toronto.edu>, man...@ecf.toronto.edu says...
: >
: > >what if the knights every possible move was biting into its own color
: > >pawns? Aren't you taking a big risk in saying that as long as knight is
: > >in the center it is good?
: >
: > If people drove as conservatively as they write chess programs, the speed
: > limit on US interstates would be five miles per hour, and even at those
: > speeds cars would all have roll cages.
:
: I love that post :)
I hate to disagree with Bruce, but if I drove like I write code in Crafty,
I'd be doing Mach 1.5, and have about 400 pedestrian carcasses stuck to my
windshield. :)
Bruce Moreland
In article <4rb5hc$l...@juniper.cis.uab.edu>, hy...@crafty.cis.uab.edu says...
>
>Peter W. Gillgasch (gil...@ilk.de) wrote:
>: Bruce Moreland <brucemo> wrote:
>:
>: > In article <DtrMI...@ecf.toronto.edu>, man...@ecf.toronto.edu says...
>: >
>: > >what if the knights every possible move was biting into its own color
>: > >pawns? Aren't you taking a big risk in saying that as long as knight is
>: > >in the center it is good?
>: >
>: > If people drove as conservatively as they write chess programs, the speed
>: > limit on US interstates would be five miles per hour, and even at those
>: > speeds cars would all have roll cages.
>:
>: I love that post :)
>
>I hate to disagree with Bruce, but if I drove like I write code in Crafty,
>I'd be doing Mach 1.5, and have about 400 pedestrian carcasses stuck to my
>windshield. :)
So where is the point of disagreement? :-)
bruce