Elisabeth van Aaring <Ev...@weasel.owl.de> wrote:
>When using Queen=9, Rook=5, Bishop=3, Knight=3, Pawn=1,
>there are some problems.
>[...]
>Thanks, Elisabeth
You can try Q=11, R=6, B=4, N=4, P=1.
Now a B+N = R+2P, instead of R+P.
This may create a problem where the program underestimates
the danger of a B or N sac for 2 king-protecting pawns,
but this can be compensated for with king-protection heuristics.
The fact is, any value system will have a problem. There are
some positions where a bishop is worth more than a rook (see
Fischer-Spassky 1972 match, 13th game, move 38) and there are
other positions where a bishop is worth no more than a pawn.
It's things like this that make life interesting for chess
programmers. Otherwise, it would be too easy... :-)
Joe Stella
See below.. but it is not likely a loss. It is most commonly a
draw.
: : giving R+R vs. Q+P will loose, too.
Ditto. Double the rooks on your own 2nd rank, king on the first rank
in front of the pawn... the pawn can not get through, ever. Most likely
outcome is a draw...
: : giving B vs. N will often be worse.
Depends also. If there are pawns on both wings, the B is better. IF
the pawns are all on one side, normally the knight will be better...
: :
: : What are general purpose recommendations for the piece values?
: Many programs modify these settings depending on the position or in
: general. MChess 5 for example sees R+P as "+1,xx" compared to B+N
: most of the time.
That's likely wrong. B+N vs R+P is almost always going to be a
draw. Trade one piece for the pawn, and it is nearly over, just
so you keep the other piece and king in a safe configuration so
that the resulting KR vs KN is not lost (most are draws)...
: : What are the position-depending recommendations?
: There are _many_ factors that add up to a position-depending piece value.
: And most programmers won't tell... ;-(
: ---
: Shep
: : there are some problems. For example:
: : giving B+N vs. R+P will loose in the ending.
: : giving R+R vs. Q+P will loose, too.
: : giving B vs. N will often be worse.
: : What are general purpose recommendations for the piece values?
: : What are the position-depending recommendations?
: : Thanks, Elisabeth
: It is worse than that.
: While, B > N, and B+B > B+N > N+N,
: but "good"N > "bad"B and Q+N > Q+B!
: Also B+B+N > R+R.
It's even worse than that. B+B+N is not always better than R+R... just
add a few pawns blocked on the right squares. Or have an important open file
that the 2 R's can use...
It is *all* very dynamic... :)
He's not talking about pure endings. Add a little more material
(balanced), and you see what he is getting at.
bruce
> In short, what I suggested was that many different evaluation functions should
> be written for different types of position.
>
> Then when a "leaf" position is to be evaluated in the game tree, the first task
> is to SELECT the most appropriate evaluation function. Then that eval function
> will produce a more accurate rating of the position.
I would be a little worried about doing this.
If you have one evaluation function that decides a position is about apples, and
another one that thinks that a sibling node is about oranges, how do you compare
results produced by these evaluation functions?
If you aren't able to compare two positions effectively, you get bad bugs.
A case in point is one of the games at last year's WMCCC. I watched a game where
one side had a bishop and a knight, and the other side had just a pawn. The
program absolutely would not take the pawn. This went on for a very long time, I
thought it might end up being a draw, but eventually the stronger side detected a
mate in the tree. It took the pawn, but only because it found a mate.
I speculate that what happened here is that there were two evaluation functions
involved. One counted the material, and perhaps got a bonus for being very much
ahead, maybe got a bonus for king position, a bonus for blockading the pawn,
etc., and returned a score that was large. The other one was a "helper" function
intended to allow the program to play KBNvK properly. And the scores produced by
the first evaluation function were consistently higher than those produced by the
second, hence the program wouldn't make the transition to the more easily won
endgame.
Do you have a chess program that works the way you describe? If so, have you
seen this problem, and how did you solve it?
bruce
: bruce
This is technically called a "discontinuous evaluation" and it can lead to
problems at the boundaries of the eval functions. We've known for a long time
that you can't suddenly turn something on or off, because of the edge effects
right around the point where it is switched. It seems like such an evaluation
would be laced with these sorts of problems. What you'd need to do to make this
effective is not just say "either A or B" but rather, for various positions,
let the eval be X*A+Y*B, where A and B are your two evaluation functions, and
X and Y are two numbers such that X+Y=1. And use X and Y to *slowly* increase
the value of one function or the other, while at the same time decreasing
the value of the opposite...
And even that would be difficult I'd bet...
--
http://www.demon.co.uk/oxford-soft
Graham Douglass wrote in article <5uh48p$i...@drn.zippo.com>...
> In article , "chrisw" says...
> >
> >
> >--
> >http://www.demon.co.uk/oxford-soft
> >
> >brucemo <bru...@seanet.com> wrote in article
<340AF9...@seanet.com>...
> >> Graham, Douglass wrote:
> >>
> >> > In short, what I suggested was that many different evaluation
functions
> >should
> >> > be written for different types of position.
> >> >
> >> > Then when a "leaf" position is to be evaluated in the game tree, the
> >first task
> >> > is to SELECT the most appropriate evaluation function. Then that
eval
> >function
> >> > will produce a more accurate rating of the position.
> >>
> >> I would be a little worried about doing this.
> >>
> >> If you have one evaluation function that decides a position is about
> >apples, and
> >> another one that thinks that a sibling node is about oranges, how do
you
> >compare
> >> results produced by these evaluation functions?
> >
> >Agreed. Its very dangerous to mix evaluation functions in the tree.
> >
> >What you can do (and most do) is to decide at the root (pre-processing,
KK
> >:) ) what type of position it is (or will become) and then switch in a
> >specific evaluation function for use during the upcoming search.
>
> In many cases, they probably do even less than this. I suspect they don't
select
> from a choice of functions, but rather just select (or calculate) values
to use
> within a single function.
No, several programs specifically page in certain code evaluation concepts
depending on the 'stage' fo the game. I certainly do this.
>
> I think I've seen this before in another thread, some time ago. I think
it was
> called "root evaluation".
I think you're talking about pre-processing, which is something else. It is
not the same as setting game status switches which then page in or page out
specific evaluation concepts.
>
> I think that the final consensus was that root evaluation leads to a very
quick
> tree searcher, and a computer that finds the tactics in a position very
quickly.
Other way round. If your program is very fast and only uses piece square
tables then it is imperative that the programmer implements pre-processing
knowledge else the program will appear incredibly stupid.
>
> However, as computers have become faster, and search depths have become
deeper,
> this method has become less successful.
The problem, as you correctly point out, is that the assumptions made as to
the nature of the position at the root will become increasingly incorrect
the deeper the search (eg faster processors).
>
> Fritz is reputed to be based on root evaluation. It is reputed to be very
> competitive up to about 60 Mhz, 486 PC level. Above this speed, its
> competitiveness seems to fall away.
I don't accept this. Fritz is very strong. Its strength falls away with
high speed and fast processors because the available RAM for hash tables is
exceeded. ie its a problem of processor technology outstripping RAM
availability/size/cheapness.
> Of course, root evaluation is ideal for the
> Kasparov 10 Mhz, 32 K ROM, 1 K RAM GK2100, President and Travel Champion
> computer range which is also written by Franz Morsch, and which are
tactically
> very strong for their hardware specification.
>
> I would think that the basic (and very obvious) problem with root
evaluation is
> that you can't control what moves your opponent is going to make. What if
they
> choose a move that takes you into a different type of position, where the
> evaluation function you've been using was inappropriate? The boundaries
exist
> both within the game and within the evaluation function.
>
> In the light of this, why do programmers think that it is more dangerous
to
> select an evaluation function at the nodes of the tree than it is to
select one
> at the root of the tree?
Do they ? News to me. Thought it was the other way round ?
Chris Whittington
--
http://www.demon.co.uk/oxford-soft
brucemo <bru...@seanet.com> wrote in article <340AF9...@seanet.com>...
> Graham, Douglass wrote:
>
> > In short, what I suggested was that many different evaluation functions
should
> > be written for different types of position.
> >
> > Then when a "leaf" position is to be evaluated in the game tree, the
first task
> > is to SELECT the most appropriate evaluation function. Then that eval
function
> > will produce a more accurate rating of the position.
>
> I would be a little worried about doing this.
>
> If you have one evaluation function that decides a position is about
apples, and
> another one that thinks that a sibling node is about oranges, how do you
compare
> results produced by these evaluation functions?
Agreed. Its very dangerous to mix evaluation functions in the tree.
What you can do (and most do) is to decide at the root (pre-processing, KK
:) ) what type of position it is (or will become) and then switch in a
specific evaluation function for use during the upcoming search.
Chris Whittington
: In many cases, they probably do even less than this. I suspect they don't select
: from a choice of functions, but rather just select (or calculate) values to use
: within a single function.
: I think I've seen this before in another thread, some time ago. I think it was
: called "root evaluation".
: I think that the final consensus was that root evaluation leads to a very quick
: tree searcher, and a computer that finds the tactics in a position very quickly.
: However, as computers have become faster, and search depths have become deeper,
: this method has become less successful.
: Fritz is reputed to be based on root evaluation. It is reputed to be very
: competitive up to about 60 Mhz, 486 PC level. Above this speed, its
: competitiveness seems to fall away. Of course, root evaluation is ideal for the
: Kasparov 10 Mhz, 32 K ROM, 1 K RAM GK2100, President and Travel Champion
: computer range which is also written by Franz Morsch, and which are tactically
: very strong for their hardware specification.
: I would think that the basic (and very obvious) problem with root evaluation is
: that you can't control what moves your opponent is going to make. What if they
: choose a move that takes you into a different type of position, where the
: evaluation function you've been using was inappropriate? The boundaries exist
: both within the game and within the evaluation function.
: In the light of this, why do programmers think that it is more dangerous to
: select an evaluation function at the nodes of the tree than it is to select one
: at the root of the tree?
The biggest problem is making long-term decisions at the root that become
inappropriate at the tips. For example, at the root, you notice that one
king is very exposed, and you set up piece/square tables to attract pieces
toward that king'sposition. And when you get to a tip position, 20 plies
later (after checks and captures) you are still trying to get your pieces
to that original weak king position, not noticing that the king has walked
across the board to the other corner. So you are doing your evaluation based
on attacking a king where it isn't. Ditto for weak pawns that disappear,
or most anything else that can change between the root and the tips.
4 ply searches don't have this problem, because the position can't change
enough to throw it off. 12-14 ply searches would start off in one world, and
use the rules of that world to evaluate positions that are in another world by
the time the tip positions are reached.
That's why root evaluation doesn't work well...and as hardware gets faster,
it works more poorly...
It might hit efficiency. Now you have to do two multiplications.
This is probably a small amount of time, but if you try to
stir in many evaluation functions, you start having to do
more multiplications which eats more time than simply adding up
a score for each feature you detect.
Also, the implication is that you must calculate evaluation functions
A and B, which is of course twice the effort of calculating one
evaluation function. Then you must calculate the coefficients
X and Y, also taking time.
.ac.uk. I will happily receive spam
Simon cranfield at email: feed...@whitehouse.gov
s read
Simon Read (bl...@blah.blurg.retch) wrote:
I agree. But a discontinuity, while not hurting NPS performance, will
be guaranteed to produce search artifacts that will cause problems. I've
done too many of those by accident, and got burned in the process. I will
probably do a few more before I quite writing chess programs. And I'll
kick myself when I catch it after the debugging too. :)
>GrahamDouglass wrote:
>: In many cases, they probably do even less than this. I suspect they don't select
>: from a choice of functions, but rather just select (or calculate) values to use
...
>: select an evaluation function at the nodes of the tree than it is to select one
>: at the root of the tree?
>The biggest problem is making long-term decisions at the root that become
>inappropriate at the tips. For example, at the root, you notice that one
...
>enough to throw it off. 12-14 ply searches would start off in one world, and
>use the rules of that world to evaluate positions that are in another world by
>the time the tip positions are reached.
>That's why root evaluation doesn't work well...and as hardware gets faster,
>it works more poorly...
Well, as you now I haven't done a program yet (I'm on it ), but I have
always liked the idea of type B programs. It's not quite what you're
discussing now, but it has to be with a root evaluation that discards
certain moves that seem useless. As you said, these method is poor,
but in some way I like it, maybe because it tries to reach a kind of
human playing.
Apart from this, I wanted to comment something one of you said about
multiplications. Like in Demos,etc, multiplications can be enhanced
and made quite faster by storing an array of, say, all the possible
multiplications of certain numbers. The problem is that in chess,
these numbers tend to change :-) But imagine you have aX + bY and you
now a and b will range between -10 and 10(integers). You also now that
the numbers X and Y will produce are within 0.1 and 1.0 then you can
store 10 arrays of 10 multiplications each, for example, and tell the
program that if multiplying a negative number, the result is the
number stored in the array, but negative.
: hy...@crafty.cis.uab.edu (Robert Hyatt) wrote:
: >GrahamDouglass wrote:
: >: In many cases, they probably do even less than this. I suspect they don't select
: >: from a choice of functions, but rather just select (or calculate) values to use
: ...
: >: select an evaluation function at the nodes of the tree than it is to select one
: >: at the root of the tree?
: >The biggest problem is making long-term decisions at the root that become
: >inappropriate at the tips. For example, at the root, you notice that one
: ...
: >enough to throw it off. 12-14 ply searches would start off in one world, and
: >use the rules of that world to evaluate positions that are in another world by
: >the time the tip positions are reached.
: >That's why root evaluation doesn't work well...and as hardware gets faster,
: >it works more poorly...
Wait... you mis-interpreted. I think there is possible hope for pruning
moves at the root. The topic we were discussing is "pre-processing"... IE
at the root, you notice black's king at g8 is not very safe. So you set up
all the scoring tables so that pieces are attracted toward g8 to build up
for an attack. For shallow searches this works. But for deep searches,
you are piling up on g8 while the king walks over to b8. At the tip
positions, where you simply sum up piece/square values, you are quite
happy, while the opponent's king is on the other side of the board and
you have attracted a crowd of pieces around an empty area of the board.
That is the problem with root evaluation rather than tip evaluation. Tip
evaluation would reward pieces close to the king, at the tips of the
branches, regardless of where it is. Root evaluators reward pieces for
moving toward where the king is at the root of the tree. Ditto for
other weaknesses like piling up on a backward pawn that is exchanged at
ply=2, but the evaluator keeps rewarding every piece that attacks where
it "was"...
This is different from the forward-pruning you are thinking of. Of course,
the same sort of problem can occur, but it is somewhat different in the way
it acts...
: Well, as you now I haven't done a program yet (I'm on it ), but I have
: always liked the idea of type B programs. It's not quite what you're
: discussing now, but it has to be with a root evaluation that discards
: certain moves that seem useless. As you said, these method is poor,
: but in some way I like it, maybe because it tries to reach a kind of
: human playing.
yes. Of course, there is a great debate over whether computers ought to
be doing this or not. :) (playing like a human)
: Apart from this, I wanted to comment something one of you said about
: multiplications. Like in Demos,etc, multiplications can be enhanced
: and made quite faster by storing an array of, say, all the possible
: multiplications of certain numbers. The problem is that in chess,
: these numbers tend to change :-) But imagine you have aX + bY and you
: now a and b will range between -10 and 10(integers). You also now that
: the numbers X and Y will produce are within 0.1 and 1.0 then you can
: store 10 arrays of 10 multiplications each, for example, and tell the
: program that if multiplying a negative number, the result is the
: number stored in the array, but negative.
We do this sort of stuff all the time. For example, in bitmap mobility,
the obvious way is to generate the attack bitmap for a piece and then count
the one bits. The faster way is to produce a table of counts up front at
the same time we preconstruct the table of attack bitmaps, so there is no
need to run off and do that FirstOne() which is expensive. It is easy to
compute f(x)=y, by saying y=lookup(x), just so long as "x" is not too
large. In chess, 64 is a common upper limit. And it works quite well.
[About preprocessing]
hy> Wait... you mis-interpreted. I think there is possible hope for
hy> pruning moves at the root. The topic we were discussing is
hy> "pre-processing"... IE at the root, you notice black's king at g8 is
hy> not very safe. So you set up all the scoring tables so that pieces are
hy> attracted toward g8 to build up for an attack. For shallow searches
hy> this works. But for deep searches, you are piling up on g8 while the
hy> king walks over to b8. At the tip positions, where you simply sum up
hy> piece/square values, you are quite happy, while the opponent's king is
hy> on the other side of the board and you have attracted a crowd of pieces
hy> around an empty area of the board.
hy> That is the problem with root evaluation rather than tip evaluation.
hy> Tip evaluation would reward pieces close to the king, at the tips of
hy> the branches, regardless of where it is. Root evaluators reward pieces
hy> for moving toward where the king is at the root of the tree. Ditto for
hy> other weaknesses like piling up on a backward pawn that is exchanged
hy> at ply=2, but the evaluator keeps rewarding every piece that attacks
hy> where it "was"...
What I don't understand is: why would you choose for preprocessing in the
first place? Maybe it's a only a remainder of the old days. The only reason
I can think of is that you can make the search faster. But suppose the
fastest preprocessor (Fritz) does 200.000 NPS and the fastest endnode
evaluator (Ferret or maybe Junior) does 100.000. In the first place that's
not even a ply extra, with inferior evaluation. The faster the hardware the
more inferior, so future perspectives are bad. Secondly the fact that Fritz
does incremental evaluation is not taken into account. It should in theorie
be possible to do that for endnode evaluators as well? Than the NPS gap
would be even smaller.
Are there endnode evaluators with incremental updates of the evaluation
value? And which effect would that have on NPS? But maybe it's a very tough
job unless you plan for it from the start, I don't know.
Regards,
Bas Hamstra.
--
| ME-Info Net: Bas Hamstra 67:100/400
| FidoNet : 2:281/204
| Internet : ham...@kb.xs4all.nl
|
| Standard disclaimer: The views of this user are strictly his own.
| Het Klankbord's Public Access Internet Gateway
: -=[ Quoting hy...@crafty.cis.uab.edu ]=-
: [About preprocessing]
: hy> Wait... you mis-interpreted. I think there is possible hope for
: hy> pruning moves at the root. The topic we were discussing is
: hy> "pre-processing"... IE at the root, you notice black's king at g8 is
: hy> not very safe. So you set up all the scoring tables so that pieces are
: hy> attracted toward g8 to build up for an attack. For shallow searches
: hy> this works. But for deep searches, you are piling up on g8 while the
: hy> king walks over to b8. At the tip positions, where you simply sum up
: hy> piece/square values, you are quite happy, while the opponent's king is
: hy> on the other side of the board and you have attracted a crowd of pieces
: hy> around an empty area of the board.
: hy> That is the problem with root evaluation rather than tip evaluation.
: hy> Tip evaluation would reward pieces close to the king, at the tips of
: hy> the branches, regardless of where it is. Root evaluators reward pieces
: hy> for moving toward where the king is at the root of the tree. Ditto for
: hy> other weaknesses like piling up on a backward pawn that is exchanged
: hy> at ply=2, but the evaluator keeps rewarding every piece that attacks
: hy> where it "was"...
: What I don't understand is: why would you choose for preprocessing in the
: first place?
I don't, of course. But some do... IE fritz seems to fit this
mode of operation. It lets you do a quick and dirty eval incrementally
as the search progresses. Which produces some fast search speeds, but
at a knowledge penalty...
: Maybe it's a only a remainder of the old days. The only reason
: I can think of is that you can make the search faster. But suppose the
: fastest preprocessor (Fritz) does 200.000 NPS and the fastest endnode
: evaluator (Ferret or maybe Junior) does 100.000. In the first place that's
: not even a ply extra, with inferior evaluation. The faster the hardware the
: more inferior, so future perspectives are bad. Secondly the fact that Fritz
: does incremental evaluation is not taken into account. It should in theorie
: be possible to do that for endnode evaluators as well? Than the NPS gap
: would be even smaller.
I agree. That's why I (and Ferret) do endpoint evals only.
: Are there endnode evaluators with incremental updates of the evaluation
: value? And which effect would that have on NPS? But maybe it's a very tough
: job unless you plan for it from the start, I don't know.
Probably. It is possible, but it is not so clear that the speed advantage
stays behind, because when you start evaluating piece interactions, a move
of a knight might affect the scores for other pieces. Which leads to losing
the very speed advantage you were trying to pick up..
: Regards,
hy> @MSGID: 67:100/4 00004d72
hy> From: hy...@crafty.cis.uab.edu (Robert Hyatt)
hy> Subject: Re: Optimal piece values?
hy> Organization: CIS, University of Alabama at Birmingham
hy> Bas Hamstra (ham...@kb.xs4all.nl) wrote:
hy> : -=[ Quoting hy...@crafty.cis.uab.edu ]=-
hy> : [About preprocessing]
hy> : What I don't understand is: why would you choose for preprocessing
hy> in the : first place?
hy> I don't, of course. But some do... IE fritz seems to fit this
hy> mode of operation. It lets you do a quick and dirty eval
hy> incrementally as the search progresses. Which produces some fast
hy> search speeds, but at a knowledge penalty...
hy> : Maybe it's a only a remainder of the old days. The only reason
hy> : I can think of is that you can make the search faster. But suppose
hy> the : fastest preprocessor (Fritz) does 200.000 NPS and the fastest
hy> endnode : evaluator (Ferret or maybe Junior) does 100.000. In the first
hy> place that's : not even a ply extra, with inferior evaluation. The
hy> faster the hardware the : more inferior, so future perspectives are
hy> bad. Secondly the fact that Fritz : does incremental evaluation is not
hy> taken into account. It should in theorie : be possible to do that for
hy> endnode evaluators as well? Than the NPS gap : would be even smaller.
hy> I agree. That's why I (and Ferret) do endpoint evals only.
hy> : Are there endnode evaluators with incremental updates of the
hy> evaluation : value? And which effect would that have on NPS? But maybe
hy> it's a very tough : job unless you plan for it from the start, I don't
hy> know.
hy> Probably. It is possible, but it is not so clear that the speed
hy> advantage stays behind, because when you start evaluating piece
hy> interactions, a move of a knight might affect the scores for other
hy> pieces. Which leads to losing the very speed advantage you were trying
hy> to pick up..
Yes it might be. Couldn't parts of the evaluation be hashed? Like pawn
hashing, as you do already. Suppose you make a list of more or less stable
eval characteristics that are rather costly to calculate and hash them? For
instance king safety or parts of it. Somehow it must be overkill to calcula-
te *everything* again after a3, when nearly all of it is already done.
: Yes it might be. Couldn't parts of the evaluation be hashed? Like pawn
: hashing, as you do already. Suppose you make a list of more or less stable
: eval characteristics that are rather costly to calculate and hash them? For
: instance king safety or parts of it. Somehow it must be overkill to calcula-
: te *everything* again after a3, when nearly all of it is already done.
I already hash pawn evals as you mention. *and* king safety. And yes,
there are potentially other things to hash as well. The only down-side is
that the hash signature for such things can only have a minimum amount of
"board state" in it, otherwise it becomes useless. For pawns, I only
hash the locations of all pawns and nothing else. For any other piece,
you have to hash the location of that piece, *and* the locations of any
other pieces or pawns that you include when evaluating that piece. That
tends to include lots of things...