computer chess "oracle" ideas...
Robert Hyatt
I've been puzzling over a long-term aggravation that I've had in Crafty
and have not yet found a workable solution that I'd call acceptable from
various angles.
First the problem:
Development. I'd like to teach Crafty to develop its pieces. A year and one
half ago it did this quite well, but it was only searching 5 plies or so deep
in middlegames. In the endpoint Evaluate() code, I have an EvaluateDevelopment()
module that (to take a simple case) gives a penalty for an unmoved knight or
bishop. Simple idea. Which fails.
The failure:
Since I now do 8-9-10 ply searches in blitz chess, I see a white bishop at c1
that might not move for a good while, and here's why. At endpoints I penalize
positions where the bishop is unmoved. But after 10 plies, it easily has the
bishop moving in that PV. In effect, it always "promises" to move it, which
satisfies endpoint evaluation code. But it generally doesn't get around to
really moving it, until it is sometimes too late. It keeps promising, until
it finally reaches a position where it has waited too long and suddenly has to
start defending against something and doesn't get a chance to deliver on the
"promise."
The idea:
I'd like to assign a score to each root move, and have it passed down to the
endpoint to use as an initial value, rather than zero as is done now. This
would let an "oracle" say that this piece has never been moved, and any move
that takes it to a decent square gets a small bonus added, but since this is
added at the root, moving the piece at the root is slightly better than moving
it at deeper levels in the tree.
The fault:
The above fails. Let's try a simple example: Choice 1: Bf4 any Ng5. Here
the bonus is added to the position, because the move Bf4 is moving the bishop
off the back rank, at the root where the bonus was added. Choice 2:
Ng5 any Bf4. Here the bonus is not added, because the Ng5 move is not a
developing move, but is played at the root where it doesn't get the bonus.
Bf4 is played deeper in the tree, and doesn't get the bonus either.
Sounds good, *until* you remember the transposition table. Suppose that
Ng5 is searched first, and the position after Ng5 any Bf4 is stored in the
transposition table. When the PV Bf4 any Ng5 is searched, the table hit
produces the score without the hit. So the bonus is missed.
solutions:
1. for moves that have a non-zero "oracle" value at the root, I could perturb
the hash signature, so that the two paths given above don't produce the same hash
signature. This would affect hashing efficiency of course, which is not so
attractive.
2. The hash score could be stored without the "oracle" score added in, and
then hash hits could have it added if the move at the root deserves it. This
sounds "iffy" due to complexity but might be better than 1 above. It sounds
particularly bad when the value stored is a bound, because I don't think I
can logically subtract an "oracle" value from a search bound without causing
all sorts of oddball problems.
Any ideas or suggestions?
BTW I'd like to use this idea for other things besides development, but
this is the first cut...
Chris Mayer
On 1 Apr 1997 03:49:36 GMT, hy...@crafty.cis.uab.edu (Robert Hyatt)
wrote:
>Sounds good, *until* you remember the transposition table. Suppose that
>Ng5 is searched first, and the position after Ng5 any Bf4 is stored in the
>transposition table. When the PV Bf4 any Ng5 is searched, the table hit
>produces the score without the hit. So the bonus is missed.
>
>solutions:
>
>1. for moves that have a non-zero "oracle" value at the root, I could perturb
>the hash signature, so that the two paths given above don't produce the same hash
>signature. This would affect hashing efficiency of course, which is not so
>attractive.
>
>2. The hash score could be stored without the "oracle" score added in, and
>then hash hits could have it added if the move at the root deserves it. This
>sounds "iffy" due to complexity but might be better than 1 above. It sounds
>particularly bad when the value stored is a bound, because I don't think I
>can logically subtract an "oracle" value from a search bound without causing
>all sorts of oddball problems.
>
>Any ideas or suggestions?
>
>BTW I'd like to use this idea for other things besides development, but
>this is the first cut...
>
>
I remember a thread a while back on this, and I did an experiment with
path dependent bonuses. Examples are: If you're going to get a piece,
its better to get it now, if your going to drop a piece, drop it
later, castle early, develiop minor pieces, etc. My solution was to
store only the non bonus portion of the traditional eval into the hash
table. This is your #2 idea above. There are problems because most
values are bounds, and what would normally be a "hash hit and prune"
becomes a "hash hit and I still don't know" so I have to continue as
if there was a hash miss. Sometimes the hit is a bound and the bonus
score delta still allows a cutoff. This is working quite well so far,
so I've kept it. As usual, you get better play at the cost of more
time, in this case reduced valid hash hits.
Chris Mayer
Robert Hyatt
Craig Shoemaker (craig.s...@his.home) wrote:
: Hi,
: I am a super novice on this stuff. I will attempt to answer in an area
: where I am a novice.
: The question I would first ask is why do you want to teach Crafty to
: develop its pieces. Here, I would stress the word 'teach'.
: I am not a strong chess player, and when I went to chess club one night
: here is how I learned (actually it took a few games) to develop my pieces.
: I wish to point out that how I learned won't be the same way the computer
: would learn.
: Once, playing against a far better player than myself, I noticed, quite
: unfortunately, that nomatter what I tried to do he kept my development
: backward with threats, posting his pieces in the most threatening
: positions. While I did not analyse deeply, things just looked tense and
: bad for my side.
: So, I just follow the general algorithm when I play: I don't seriously get
: involved in any action unless my pieces are developed. Now, as I would
: suggest that Crafty be programmed to do the same, everyone will immediately
: yawn and say, "obviously, we know that, that was done twenty years ago."
: Nevertheless, I wish to suggest that it is a pretty damn good algorithm!
: Develope early, and don't worry about the score ten moves down the road
: because it won't pan out unless you are developed and ready to take
: advantage of opportunities.
I agree. However, it is the "doing" that is a problem... because in *your*
case, you are evaluating as you search. Crafty is evaluating at endpoints,
which is what you have to do with alpha/beta. It is not aware of "when"
something happened (when was that knight developed, for example) but it is
aware of "if* the knight has been developed, and that's the problem. I want
it done earlier, Crafty just wants it to be done.
: This implies that Crafty would need to be aware of an opening phase of the
: game. During this phase crafty initial move generator would place
: developing moves as top priority, even if their actual score wasn't so hot.
: For Crafty must learn, just as humans learn, that deep calculations without
: sound development are meaningless. The exceptions of course always exist!
: Of course, that is the fun of chess; when should Crafty not develop? when
: should Crafty break the rules? Well, that's the fun of being human, and, I
: would suggest that it becomes quite demanding to program Crafty to think
: like a human in this regard. And, of course, there is never a sure thing:
: for how would Crafty learn from his mistakes? How will Crafty know that
: some position p was not appropriate to break the rules while some position
: pp it is appropriate.
Move order doesn't affect what is played. It only affects the size of the tree.
So putting developmental moves first won't guarantee their getting played any more
than the current idea. In fact, most developmental moves do come first because
those pieces have a bad scoring value sitting on the edge of the board...
: So, I would use twenty year old chess programming technology, that is, use
: the opening book as far as you can, and when the book isn't available,
: develope; and then, if you want to get fancy, try to figure out how to
: code the algorithm Crafty would use when he decides "boy, I'll grab that
: pawn even though I realize I am breaking a basic rule of chess in the
: opening which is to develop the pieces."
: I realized, of course, Mr. Hyatt that you are the Guru of chess
: programming; so, I hope it is OK for a novice like me to speak out. I'm a
: novice, but I still like to think about these problems, though, in this
: case, I've offered no new thinking which hasn't already been around for
: decades.
Obviously not as much of a "guru" as I'd like, because I haven't found a way to
make this work. The problem is the hash table has no "path" information, just
"position" information. So hits won't reflect if a piece was developed at ply
one, or at ply 15. I want 'em out at ply 1 if possible.
Robert Hyatt
Craig Shoemaker (craig.s...@his.home) wrote:
: This is an aside, an addition to the longer post I just made.
: It just ocurred to me: what does it mean if Crafty is analyzing moves
: ahead with his Bishop undeveloped and he keeps promising to develope it but
: it turns out often that he never gets a chance to because the enemy takes
: advantage of the situation before Crafty can get it out.
: It means that the analysis function, the function which judges the value of
: the position is inaccurate, I think, right? That is, it is not as accurate
: as one would like, for if Crafty indeed is seeing every possibilty N half
: moves ahead, and "missed the good developing move" by not making it when he
: had a chance, then obviously, if you only use mini-max thinking during the
: opening phase, the positional judgement isn't keen enough.
no. think about what is going on. Crafty has two components to choose a
move. (1) the search which shuffles pieces around, captures things, and
(2) the evaluation function takes positions and produces a numeric score
reflecting whether the positions are good or bad. And that's the problem.
The evaluation doesn't know whether that knight was moved at ply 1 or at
ply 15. And even if it did, the hash table would hide this later because
the hash algorithm uses encoded positions to produce a hash match, not
encoded paths. Doing paths would work, but it would eliminate any sort
of transpositions, which is the reason for using the table.
: After all, even for humans to make refined judgements about "when is a
: piece developed" is not always simple. Here we immediately get into the
: "breaking of rules" again. Most of the time developing my Knight, let's
: say, to f3 (King's Bishop 3) is probably a pretty good move; but, no doubt,
: we have all seen chess games where the master broke the rules and played,
: let's say, Bishop to f1! Because, for that circumstance, that was a great
: "developing move" (perhaps because the master decided to redeploy the
: Bishop in a fianchetto).
: If what I say is correct, then the part of the positional algorithm, I mean
: to say, the static evaluation function, as it is called, needs to be
: refined so that it's understanding of when "pieces and pawns are maximally
: deployed" to Crafty's advantage is enhanced. [aside: of course, one
: doesn't always run around with one's pieces "maximally deployed" for the
: tension has to be released in an attack or a liquidation at the right point
: in the game].
While I agree, it is basically impossible to do. I can check the path and add
such info into the score, but the transposition table is going to apply that same
score to any similar position, regardless of the order the pieces were moved to
reach that position...
: This immediately brings about a, well, probably not so new way of thinking.
: Let's assume, for simplicity, that the computer can think about two things
: at once.
: 1) The first thing it would do is for all its possible legal moves assign
: them a score for some given depth of look ahead.
: 2) But, unlike standard thinking, these numbers are just guidelines for the
: play. The computers of the future have got to start thinking (OK, don't
: get mad at me, I don't read this group too often to know exactly what the
: state of the art in computer thinking is). And, when I say thinking, I
: mean planning. Now, I realize that the idea of people writing modules with
: micro-plans is also an old idea. But, it is critically important. In my
: opinion, the "fun", at least for the novice like me who doesn't get his
: hands dirty, the "fun concepts" of the future are to get the computer's
: thinking in terms of short and long term plans, in balancing positional
: judgements, of deciding when and where to attack, deciding how to mount an
: attack and when, and deciding when to abort an attack and regroup to try
: something new.
: Now, even if you could just get the computer to think conceptually, to come
: up with the simplest plan, wow! Think of it, the computer learns a few
: tricks (minority attack, or whatever), knows how to implement certain long
: term plans, and you combine this with a killer tactical ability and wow,
: people better start looking out, because that "do nothing strategy" will
: start to fail, and fail more frequently over time as the computer
: stockpiles more and more plans and procedures.
: Bye,
: Craig
: P.S. Please note that I am a novice on this topic, and if my writing
: doesn't say much, at least I enjoyed talking and thinking about the topic.
: Cheers.
: --------------------------------------------------------------------
: My notes on Monet and Symmetry are available for a short time from April 1
: through about April 7, 1997 at http://www.his.com/~esoteric/interests/art/
: -----
: http://www.his.com/~esoteric/ then click on the "What's New" link.
: You must visit my page to send me e-mail.
Jean-Peter Fendrich
> Ng5 is searched first, and the position after Ng5 any Bf4 is stored in the
> transposition table. When the PV Bf4 any Ng5 is searched, the table hit
> produces the score without the hit. So the bonus is missed.
>
> solutions:
>
> 1. for moves that have a non-zero "oracle" value at the root, I could perturb
> the hash signature, so that the two paths given above don't produce the same hash
> signature. This would affect hashing efficiency of course, which is not so
> attractive.
>
> 2. The hash score could be stored without the "oracle" score added in, and
> then hash hits could have it added if the move at the root deserves it. This
> sounds "iffy" due to complexity but might be better than 1 above. It sounds
> particularly bad when the value stored is a bound, because I don't think I
> can logically subtract an "oracle" value from a search bound without causing
> all sorts of oddball problems.
>
> Any ideas or suggestions?
>
> BTW I'd like to use this idea for other things besides development, but
> this is the first cut...
In my program I sort the development moves to the top at root node.
When some other move returns a better value from the search I don't
accept
that if the value doesn't exceed the current value (from a development
move)
with some certain small value. It seems to work fairly good and is easy
coded.
--
J-P Fendrich
Server Administrator
In article <5hq0kg$d...@juniper.cis.uab.edu>, Robert Hyatt (hy...@crafty.cis.uab.edu) wrote:
>
>I've been puzzling over a long-term aggravation that I've had in Crafty
>and have not yet found a workable solution that I'd call acceptable from
>various angles.
>
>First the problem:
>
>Development. I'd like to teach Crafty to develop its pieces. A year and one
>half ago it did this quite well, but it was only searching 5 plies or so deep
>in middlegames. In the endpoint Evaluate() code, I have an EvaluateDevelopment()
>module that (to take a simple case) gives a penalty for an unmoved knight or
>bishop. Simple idea. Which fails.
>
>The failure:
>
>Since I now do 8-9-10 ply searches in blitz chess, I see a white bishop at c1
>that might not move for a good while, and here's why. At endpoints I penalize
>positions where the bishop is unmoved. But after 10 plies, it easily has the
>bishop moving in that PV. In effect, it always "promises" to move it, which
>satisfies endpoint evaluation code. But it generally doesn't get around to
>really moving it, until it is sometimes too late. It keeps promising, until
>it finally reaches a position where it has waited too long and suddenly has to
>start defending against something and doesn't get a chance to deliver on the
>"promise."
My intuition is that endpoint evaluation has got to be the right
thing to do. If that's true, then if you're getting bad results it
must be because you aren't evaluating the right thing.
Why is early development good? Why is it so often better to develop
the bishop with Bf4 than to increase the knight's activity with Ng5?
It's because pieces cooperate--the N on g5 may be more active than
it was on f3, but it can't do anything by itself, it needs friends
before it can put any real pressure on the opponent.
Looked at that way, a has-this-piece-moved-yet development term
seems crude. It's the vaguest possible interpretation of "get all
the pieces working together harmoniously". A smarter evaluator
doesn't want to move pieces, it wants to DO THINGS with them; it
merely happens to discover that it usually has to move them first. :-)
So I suspect you'll eventually get more mileage out of improving
the evaluation term than out of finding a new way to apply it.
Andrew Tridgell
As I don't have an opening book in KnightCap I spent
some time getting it to develop pieces reasonably.
I get development by assigning large penalties for trapped
and "useless" pieces.
A trapped piece is one which has no moves to squares that
are controlled by that player. Thus all but the knights
start out "trapped" and get a big penalty.
A "useless" piece is one with a mobility less than 5 that
is not attacking any enemy piece or pawn. These also get
large penalties. All pieces start out "useless".
The main "trapped" and "useless" calculations are done using bit
masks built into the way the move generator works, so they
aren't too expensive.
This system seems to work reasonably, but it can mean
that sometimes KnightCap sacrifices a pawn in the
opening for superior development (not an uncommon idea
in the chess world!). Unfortunately not all the gambits
it makes up are sound :-)
Andrew
Robert Hyatt
Andrew Tridgell (Andrew....@anu.edu.au) wrote:
: As I don't have an opening book in KnightCap I spent
: Andrew
I've done similar things... but how did you convince it to develop a
piece at ply 1, rather than waiting until ply 5. Since the evaluator
doesn't see the position until (say) ply=11, and has no idea when that
knight was moved. My problem is that if you keep "promising" to develop
that knight, sooner or later, something will come up that makes you wish
you had done more than promised.
even if I knew how to evaluate the move because it was made at ply=1 rather
than at ply=5, the hash table will further hide this since it is only
position based, and not path based...
Bob
Andreas Mader
Maybe I missed the real problem but I think it has already been solved.
Nimzo is using CHE functions to handle this problem. If e.g. the knight
is on b1 then the function "goodmoves (Nb1c3, Nb1d2)" [this is NOT the
exact way CHE is used, but it gives you a good insight] is used in the
oracle and the moves Nb1-c3 and Nb1-d2 are given a bonus at ply 1 (of
course only if they are legal). It is simple to modify the move list of
the actual position on the board by adding a bonus to single moves.
If you use the CHE function "goodsquares (Knight, c3 d2)" [again this is
NOT the exact way CHE is used] in the above example, the knight gets a
bonus when it is placed on c3 or d2 regardless of the search depth.
If you use both functions "goodmoves" and "goodsquares", then you force
the program to play Nc3 or Nd2 and leave the Knight on this square.
Best wishes
Andreas Mader
Robert Hyatt
Andreas Mader (ma...@p6.gud.siemens.co.at) wrote:
We are missing something in communication however. To make the above
work, there has to be (a) some initial "bonus" that is attached to each
root move and (b) a really complicated set of hacks to the search so
that *every* score, every test for alpha and beta, and so forth also have
the root score added to them. Otherwise the values in the hash table
can't tell which of these two things you are evaluating:
Nb1-c3 any Nf3-g5
or
nf3-g5 any Nb1-c3
because they end up in the same exact position. Except that the second
pv delays the nb1 development and promises to do it at ply-3. But it
might not get to... that's the problem I'd like to solve, *without* the
really gross mechanism of having to compute all the scores without the
bonus added in, and then adding it after a lookup, before testing for a
cutoff, etc... which is ugly beyond belief...
Andreas Mader
I think I understood the problem.
You ONLY have to give (a) the initial bonus to the root move Nb1-c3 and
do not have to care about every score and alpha beta. If you care about
(b) then you provoke the problem you are complaining about.
Nb1-c3 any Nf3-g5 -> Nb1-c3 is 1.ply and gets the initial bonus
Nf3-g5 any Nb1-c3 -> Nb1-c3 is 3.ply and dosn't get the initial bonus
Therefore it is "better" for the program to play Nb1-c3 first. You
compute the evaluation for Nb1-c3 and add e.g. a score of 0.2 to it. If
there is no very good reason to play another move the program will most
likely play Nc3. Why does this extreme simple method not work?
Best wishes
Andreas Mader
John A. Gregor, Jr.
In article <5hvcik$n...@juniper.cis.uab.edu>,
Robert Hyatt <hy...@crafty.cis.uab.edu> wrote:
> My problem is that if you keep "promising" to develop
> that knight, sooner or later, something will come up that makes you wish
> you had done more than promised.
I guess the real question is why isn't the search/eval seeing that
situation and taking precautions.
Instead of making the score path-dependent, can't the eval be tweaked
to 'recognize' a less developed board (more pawns still on 2 and 7,
many back pieces still in the back, no castling, still 32 or so pieces
on the board, etc.) and give the knight and bishop development moves a
greater bonus? That way, with earlier development, the score is
higher. What should matter is board position, not path. It shouldn't
matter if both sides took out their knights, played around for 20
moves, pushed a pawn, and then put the knights back where they started,
logically it was just a pawn advance.
Disclaimer, I'm a computer chess neophyte.
-JohnG
Andrew Tridgell
Robert Hyatt wrote:
> I've done similar things... but how did you convince it to develop a
> piece at ply 1, rather than waiting until ply 5. Since the evaluator
> doesn't see the position until (say) ply=11, and has no idea when that
> that knight, sooner or later, something will come up that makes you wish
> you had done more than promised.
I understand the problem, but it doesn't seem to be very serious
in KnightCap. As our search algorithms are pretty similar I assume
the difference is something in the evaluation function.
One possability is the "board control" function in KnightCap. This
is the core of the evaluation function and is the most expensive part
of it. It calculates who controls each square on the board, as
a boolean function. If one player has control of a square then they
get a bonus, with bigger bonuses for central squares.
Its possible that this function means that the search can't find
a way to delay the development of a piece without losing out in
board control. This might provide the impetus to stop it being
put off.
Its only a guess of course, but I can try to verify if by removing
the board control function and seeing what changes. Let me
know if you think its a worthwhile experiment.
>
> even if I knew how to evaluate the move because it was made at ply=1 rather
> than at ply=5, the hash table will further hide this since it is only
> position based, and not path based...
I don't really understand why the hash table would make any difference
to this problem. I think that it could only have an effect if the
same position could occur via two different paths without either
player being able to gain more by diverting the position from one
of the paths. This would have to be pretty rare, and would mean
that the two paths really are equivalent anyway. Do you know of any
examples where this could actually occur?
There is really an inherent contradiction in there. If the program
is worse off by playing along one path than the other (which is
what I think you say is happening) then this can only be because the
opponent can "take advantage" of the delay to gain something. But
if they can take advantage of the delay then the alpha-beta search
should see this.
So it comes back to something missing in the eval function, so that
the search fails to see the significance of the detour that the
opponent can make.
I suppose with null moves in there you are searching some branches
to a lesser depth than others, so the above argument starts to fall
apart, perhaps thats another possability for the root cause of your
problem?
Hmmm, I've just thought of yet another possability. If you used an
eval function that did any pre-processing at the root (assigning
weights to squares etc) then it could get things severely wrong in
the early parts of the game, perhaps leading to two paths looking
equivalent when one in fact has the possability of the opponent
diverting the game into something better.
Cheers, Andrew
Robert Hyatt
John A. Gregor, Jr. (jgr...@engr.sgi.com) wrote:
: In article <5hvcik$n...@juniper.cis.uab.edu>,
: Robert Hyatt <hy...@crafty.cis.uab.edu> wrote:
: > My problem is that if you keep "promising" to develop
: > that knight, sooner or later, something will come up that makes you wish
: > you had done more than promised.
: I guess the real question is why isn't the search/eval seeing that
: situation and taking precautions.
: Instead of making the score path-dependent, can't the eval be tweaked
: to 'recognize' a less developed board (more pawns still on 2 and 7,
: many back pieces still in the back, no castling, still 32 or so pieces
: on the board, etc.) and give the knight and bishop development moves a
: greater bonus? That way, with earlier development, the score is
: higher. What should matter is board position, not path. It shouldn't
: matter if both sides took out their knights, played around for 20
: moves, pushed a pawn, and then put the knights back where they started,
: logically it was just a pawn advance.
Yes. But the problem is, there is a difference between developing a
piece at ply=1 and at ply=n. Because at ply=1 it gets done. at ply=n
it is a promise only. and after a deeper search, you might figure out
that "boy, wish I'd gotten that knight out when I had the chance, because
now I have to defend against this threat on d4 and don't have time to
get the knight into action."...
: Disclaimer, I'm a computer chess neophyte.
: -JohnG
Robert Hyatt
Andreas Mader (ma...@p6.gud.siemens.co.at) wrote:
: I think I understood the problem.
: You ONLY have to give (a) the initial bonus to the root move Nb1-c3 and
: do not have to care about every score and alpha beta. If you care about
: (b) then you provoke the problem you are complaining about.
: Nb1-c3 any Nf3-g5 -> Nb1-c3 is 1.ply and gets the initial bonus
: Nf3-g5 any Nb1-c3 -> Nb1-c3 is 3.ply and dosn't get the initial bonus
This is where it fails. Because after those 3 moves, you get a hash hit
and use the same score as for the first PV, because the two positions are
identical...
That's why this fails "as is" on rare occasions...
: Therefore it is "better" for the program to play Nb1-c3 first. You
Simon Read
cma...@ix.netcom.com (Chris Mayer) wrote:
BOB: hy...@crafty.cis.uab.edu (Robert Hyatt) wrote:
BOB> Any ideas or suggestions?
BOB>
BOB> BTW I'd like to use this idea for other things besides development, but
BOB> this is the first cut...
--->
You can get development before other action starts with a little
non-linearity in the evaluation function. As an example, I saw
GNUchess come unstuck once: it won a little material within about 10
moves, but it only had its queen out, nothing else developed, and its
king exposed. The other side's king was also exposed, so GNUchess
spent 20 moves fruitlessly chasing the opponent's king around. The
queen even followed the king into a sort of hole on the other side of
the board when it suddenly became apparent that it had trapped its
own queen. Suddenly its total lack of development became a major
problem, along with its imminent lack of any females in the royal
line.
The problem was GNUchess started an attack before completing its
development. You can solve this by including in the evaluation function:
(1) score for development
(2) little score for an attack
(3) more score if there is both development AND attack.
This is effectively a non-linear evaluation function, which isn't
treating development and attack separately, but realises that
the combination of the two is more valuable than the sum of either
on its own.
Simon http://www.cranfield.ac.uk/~me944p/hotlist.html
>>
>I remember a thread a while back on this, and I did an experiment with
>path dependent bonuses. Examples are: If you're going to get a piece,
>its better to get it now, if your going to drop a piece, drop it
>later, castle early, develiop minor pieces, etc. My solution was to
>store only the non bonus portion of the traditional eval into the hash
>table. This is your #2 idea above. There are problems because most
>values are bounds, and what would normally be a "hash hit and prune"
>becomes a "hash hit and I still don't know" so I have to continue as
>if there was a hash miss. Sometimes the hit is a bound and the bonus
>score delta still allows a cutoff. This is working quite well so far,
>so I've kept it. As usual, you get better play at the cost of more
>time, in this case reduced valid hash hits.
>
>Chris Mayer
>
Robert Hyatt
Simon Read (bl...@blurgh.bleah.retch) wrote:
only problem is the hash table can hide *when* a piece is developed, since
that is "path" information and is not kept in the hash table for obvious
space reasons...
Ronald de Man
hy...@crafty.cis.uab.edu (Robert Hyatt) writes:
>I've been puzzling over a long-term aggravation that I've had in Crafty
>and have not yet found a workable solution that I'd call acceptable from
>various angles.
>First the problem:
>Development. I'd like to teach Crafty to develop its pieces. A year and one
>half ago it did this quite well, but it was only searching 5 plies or so deep
>in middlegames. In the endpoint Evaluate() code, I have an EvaluateDevelopment()
>module that (to take a simple case) gives a penalty for an unmoved knight or
>bishop. Simple idea. Which fails.
>The idea:
>I'd like to assign a score to each root move, and have it passed down to the
>endpoint to use as an initial value, rather than zero as is done now. This
>would let an "oracle" say that this piece has never been moved, and any move
>that takes it to a decent square gets a small bonus added, but since this is
>added at the root, moving the piece at the root is slightly better than moving
>it at deeper levels in the tree.
>The fault:
>The above fails. Let's try a simple example: Choice 1: Bf4 any Ng5. Here
>the bonus is added to the position, because the move Bf4 is moving the bishop
>off the back rank, at the root where the bonus was added. Choice 2:
>Ng5 any Bf4. Here the bonus is not added, because the Ng5 move is not a
>developing move, but is played at the root where it doesn't get the bonus.
>Bf4 is played deeper in the tree, and doesn't get the bonus either.
>Sounds good, *until* you remember the transposition table. Suppose that
>Ng5 is searched first, and the position after Ng5 any Bf4 is stored in the
>transposition table. When the PV Bf4 any Ng5 is searched, the table hit
>produces the score without the hit. So the bonus is missed.
>Any ideas or suggestions?
>BTW I'd like to use this idea for other things besides development, but
>this is the first cut...
This is very similar to the discussion of a while back about randomization.
Let me recall the problem there. To keep a program from playing the same
moves everytime once out of book, the idea is to compute the values of
all root moves, then add a random value to each of these values, and then
play the move with the largest value. The problem here is that it is much
too expensive to compute the exact values of all moves.
My solution to this problem (and, as I understood then, I was not the first
one to have this idea) was to FIRST generate random values, and then
use these values in the root search to shift the alpha/beta windows when
searching the different root moves.
After a little thought it turns out that this causes no problems with
hash values. (Of course, you have to implement it in the right way.) Only
problem might be a slight decrease in efficiency, maybe 5% (as someone
reported then).
What does this have to do with stimulating development? Well, instead of
generating a random value for each move one takes a positive value for
developing moves, a negative value for anti-developing moves, and 0 for
other moves (or something like that). Now the move selected will be the move
that has the largest (value_returned_by_search + development_bonus), where
value_returned_by_search is the value for this root move without any
bonus. And this at almost no cost. (If decrease in efficiency really
turns out to be 5% it is of course easy to take a little more time for moves
in which these bonusses are used).
Assuming the search consists of a procedure SearchRoot() to search the
root moves and a recursive procedure Search() (that is called in SearchRoot
for each root move) it is easy to adapt the program.
As an example, let's assume we have a very simplistic search to a fixed depth.
The originally, we have something like this:
Move SearchRoot(depth) /* first */
int depth;
{
GenerateMoves();
alpha=-infinity;
for(n=0;n<numMoves;n++) {
MakeMove(move[n]);
value=-Search(-infinity,-alpha,depth);
UnMakeMove();
if(value>alpha) {
alpha=value;
bestMove=move[n];
}
}
return(bestMove);
}
So now I add in a development bonus for each move. The way I do it here
is very stupid and expensive.
Move SearchRoot(depth) /* second */
int depth;
{
GenerateMoves();
for(n=0;n<numMoves;n++)
bonus[n]=ComputeDevelopmentBonus(move[n]);
for(n=0;n<numMoves;n++) {
MakeMove(move[n]);
value[n]=-Search(-infinity,infinity,depth);
UnMakeMove();
}
for(n=0;n<numMoves;n++)
value[n]+=bonus[n];
alpha=-infinity;
for(n=0;n<numMoves;n++)
if(value[n]>alpha) {
alpha=value[n];
bestMove=move[n];
}
return(bestMove);
}
The routine above does a full search for all root moves, thus wasting
a lot of time. However, it is clear how the bonus is added.
In particular, nothing gets added at the tip nodes.
My claim is that there is a way to achieve the exact same effect
of this second routine with the efficiency of the first.
Here it goes:
Move SearchRoot(depth) /* third */
int depth;
{
GenerateMoves();
for(n=0;n<numMoves;n++)
bonus[n]=ComputeDevelopmentBonus(move[n]);
alpha=-infinity;
for(n=0;n<numMoves;n++) {
MakeMove(move[n]);
value = bonus[n]-Search(-infinity,bonus[n]-alpha,depth);
/* or for a minimal window search:
value = bonus[n]-Search(bonus[n]-alpha-1,bonus[n]-alpha,depth);
*/
UnMakeMove();
if(value>alpha) {
value=alpha;
bestMove=move[n];
}
}
return(bestMove);
}
This third procedure gives the same result as the second. Note that
Search() itself remains totally unchanged(!), and as a result, there
are NO problems with hashing.
It takes a little thought to see what is going on. The idea is: before I
start searching a move, I know that I'm only interested if its value+bonus
is bigger than the current alpha. So its value (returned by Search()) should
be bigger than alpha-bonus[n], and I search it with a window
(alpha-bonus[n],infinity), or (alpha-bonus[n],alpha-bonus[n]+1) in case
I do a minimal window search. Search() itself knows nothing about bonus[n]!
It just gets two bounds and compares these bounds with the value of the tree
it searches.
To compare this with your idea, the bonus is not passed down to the tip nodes,
but instead is added after the move is searched (which prevents hash
values from getting corrupted and is probably simpler to implement
anyway.)
There might arise some problems when the opponent allows a quick mate.
In that case a value is added to the mate value which might change a
mate in 2 to apparently a mate in 10 or maybe even -10. So it might be
safe to check for mate values so that these will be handled correctly.
Currently, I do not have such a development bonus in my program. But I
use this trick for randomizing moves a few moves out of book. I do not
see any real decrease of efficiency. Please do not think I have a simple
search like the one above.
Ronald de Man
Ronald de Man
jgr...@engr.sgi.com (John A. Gregor, Jr.) writes:
>I guess the real question is why isn't the search/eval seeing that
>situation and taking precautions.
>Instead of making the score path-dependent, can't the eval be tweaked
>to 'recognize' a less developed board (more pawns still on 2 and 7,
>many back pieces still in the back, no castling, still 32 or so pieces
>on the board, etc.) and give the knight and bishop development moves a
>greater bonus? That way, with earlier development, the score is
>higher. What should matter is board position, not path. It shouldn't
>matter if both sides took out their knights, played around for 20
>moves, pushed a pawn, and then put the knights back where they started,
>logically it was just a pawn advance.
This is exactly how it is done currently. The problem is that after a 12
ply search a currently undeveloped bishop might have moved, so that the
eval is happy, but that some moves later it turns out there is no more
time to move the bishop, because there are some threats that have to be
taken care of. So it's just safer to get that bishop out right away,
instead of at the 11th move of a 12-ply PV. In my program, I have this
problem often with castling. Sometimes it is planning to castle, then fails
high just a little and makes some different move, planning to castle the
next move. This next move, the same thing happens. And then suddenly it
discovers some threat and it has to give up castling to defend.
So not delaying castling might deserve a bonus...
Ronald de Man
chrisw
--
http://www.demon.co.uk/oxford-soft
Robert Hyatt <hy...@crafty.cis.uab.edu> wrote in article
<5i0e7r$4...@juniper.cis.uab.edu>...
> Andreas Mader (ma...@p6.gud.siemens.co.at) wrote:
>
> : I think I understood the problem.
>
> : You ONLY have to give (a) the initial bonus to the root move Nb1-c3 and
> : do not have to care about every score and alpha beta. If you care about
> : (b) then you provoke the problem you are complaining about.
>
> : Nb1-c3 any Nf3-g5 -> Nb1-c3 is 1.ply and gets the initial bonus
> : Nf3-g5 any Nb1-c3 -> Nb1-c3 is 3.ply and dosn't get the initial
bonus
>
> This is where it fails. Because after those 3 moves, you get a hash hit
> and use the same score as for the first PV, because the two positions are
> identical...
>
> That's why this fails "as is" on rare occasions...
Eeeeeerrrgggghhhhhh.
We've been through all this before.
Hyatt argues its impossible to extract the 0.20 value back out of the line
that doesn't start with Nc3. Others argued that it is.
Usenet creaks under the strain :)
Chris Whittington
Ronald de Man
Andrew Tridgell <Andrew....@anu.edu.au> writes:
>There is really an inherent contradiction in there. If the program
>is worse off by playing along one path than the other (which is
>what I think you say is happening) then this can only be because the
>opponent can "take advantage" of the delay to gain something. But
>if they can take advantage of the delay then the alpha-beta search
>should see this.
No, there's no contradiction. The opponent can really take advantage of
the delay. The computer searches only to a certain depth and regards
the moves by which the opponent takes this advantage as inferior. A few
moves later it will discover it was wrong. Happens all the time.
>So it comes back to something missing in the eval function, so that
>the search fails to see the significance of the detour that the
>opponent can make.
Of course there will always be something missing in the evaluation that
will cause the search to disregard dangers. But in this case checking
development in the search cannot solve the problem, as long as the
evaluation is path-independent.
Ronald de Man
Pete Nielsen
One place that you ought to be able to apply "Path" info without perterbing
the hash table is at the root.
If you adjusted your AB window at the root only, to favor developing moves
would that address the problem?
Andreas Mader
chrisw wrote:
>
> --
> http://www.demon.co.uk/oxford-soft
>
> Robert Hyatt <hy...@crafty.cis.uab.edu> wrote in article
> <5i0e7r$4...@juniper.cis.uab.edu>...
> > Andreas Mader (ma...@p6.gud.siemens.co.at) wrote:
> >
> > : I think I understood the problem.
> >
> > : You ONLY have to give (a) the initial bonus to the root move Nb1-c3 and
> > : do not have to care about every score and alpha beta. If you care about
> > : (b) then you provoke the problem you are complaining about.
> >
> > : Nb1-c3 any Nf3-g5 -> Nb1-c3 is 1.ply and gets the initial bonus
> > : Nf3-g5 any Nb1-c3 -> Nb1-c3 is 3.ply and dosn't get the initial
> bonus
> >
> > This is where it fails. Because after those 3 moves, you get a hash hit
> > and use the same score as for the first PV, because the two positions are
> > identical...
> >
> > That's why this fails "as is" on rare occasions...
>
> Eeeeeerrrgggghhhhhh.
>
> We've been through all this before.
>
> Hyatt argues its impossible to extract the 0.20 value back out of the line
> that doesn't start with Nc3. Others argued that it is.
>
> Usenet creaks under the strain :)
>
> Chris Whittington
Sorry, I missed the first discussion (there are so many posts in this
newsgroup that I have to read very selective).
OK, you get a hash hit after 3 plies, but the 0.20 (or whatever it is)
bonus is NOT in the "normal" evaluation, its the "root" evaluation. When
you compute the first ply, you simply add 0.20 to the "normal"
evaluation when it comes to Nc3. No need to put the "root" evaluation
bonus in the hash tables!
John A. Gregor, Jr.
In article <5i0ht9$7...@wsdw10.win.tue.nl>,
Ronald de Man <de...@wsdw10.win.tue.nl> wrote:
> This is exactly how it is done currently. The problem is that after a
> 12 ply search a currently undeveloped bishop might have moved, so that
> the eval is happy, but that some moves later it turns out there is no
> more time to move the bishop, because there are some threats that have
> to be taken care of. So it's just safer to get that bishop out right
> away, instead of at the 11th move of a 12-ply PV. In my program, I have
> this problem often with castling. Sometimes it is planning to castle,
> then fails high just a little and makes some different move, planning
> to castle the next move. This next move, the same thing happens. And
> then suddenly it discovers some threat and it has to give up castling
> to defend. So not delaying castling might deserve a bonus...
Ahh, I think I'm beginning to see the problem (give him enough
time...). So, if I'm understanding correctly, you could give any bonus
you wanted for early development, but as you search successive plys,
those values replace the earlier, inflated evaluation because a deeper
eval is more accurate as a rule. So my early bishop development might
be eval'd at +1.75 for ply1, but by ply9 it is now only evaluating as
+0.25. If a different line produces an eval of +0.26 at ply9, then my
bishop doesn't get developed. Oops.
Am I close?
So, what you really want is to somehow "take the area under the curve"
of the sequence of plys. So, if you had two lines: the first evals to
+0.50 for 7 plys while the second evals to -0.1 for the first 6 plys but
then jumps to +0.51, you would want to go with the first line as it is
only marginally worse in the long run, but much safer in the shorter
term. Conversely, you would want to choose lines that minimize your
opponent's "area". Of course, the art lies in choosing the
thresholds and how you weigh the contributions of early evals.
One possible way to do this might be in sort of a "push-down" apprach.
In addition to the static eval of the board, each ply calculates
"bonus" points. Instead of storing these bonuses as part of the board
eval, it is passed down as you recurse. It then gets added to the
eval at the next ply (and successive plys) to calculate the adjusted
evaluation of the board. Those adjusted evaluations are what is used
by the alpha-beta.
Let me guess: Been there, done that, got the t-shirt, and it doesn't
do what I think it will...
-JohnG
chrisw
--
http://www.demon.co.uk/oxford-soft
Andreas Mader <ma...@p6.gud.siemens.co.at> wrote in article
<334519...@p6.gud.siemens.co.at>...
That's what I think too. But be prepared for a heavy onslaught as to why
its not possible ....
Chris Whittington
Ronald de Man
"chrisw" <chr...@cpsoft.demon.co.uk> writes:
>Robert Hyatt <hy...@crafty.cis.uab.edu> wrote in article
>> Andreas Mader (ma...@p6.gud.siemens.co.at) wrote:
>> This is where it fails. Because after those 3 moves, you get a hash hit
>> and use the same score as for the first PV, because the two positions are
>> identical...
>> That's why this fails "as is" on rare occasions...
No, no, no!
The bonus is NOT propagated to the tip nodes. At the tips, normal evaluation
is used. Values stored in the hash are totally path-independent, hence cause
no problems.
>Eeeeeerrrgggghhhhhh.
:)
>We've been through all this before.
Yes, we have.
>Hyatt argues its impossible to extract the 0.20 value back out of the line
>that doesn't start with Nc3. Others argued that it is.
>Usenet creaks under the strain :)
>Chris Whittington
>> : Therefore it is "better" for the program to play Nb1-c3 first. You
>> : compute the evaluation for Nb1-c3 and add e.g. a score of 0.2 to it. If
>> : there is no very good reason to play another move the program will most
>> : likely play Nc3. Why does this extreme simple method not work?
Of course it works!
As you say, you add the score AFTER evaluation of the (root) move.
And to line this up with alpha/beta, you just shift the window by
the appropriate bonus value when searching the other moves.
But, I've already tried to explain this in a previous post...
>> : Best wishes
>> : Andreas Mader
Ronald de Man
Andreas Mader
chrisw wrote:
> Andreas Mader wrote:
> > OK, you get a hash hit after 3 plies, but the 0.20 (or whatever it is)
> > bonus is NOT in the "normal" evaluation, its the "root" evaluation. When
> > you compute the first ply, you simply add 0.20 to the "normal"
> > evaluation when it comes to Nc3. No need to put the "root" evaluation
> > bonus in the hash tables!
>
> That's what I think too. But be prepared for a heavy onslaught as to why
> its not possible ....
>
> Chris Whittington
Thank you, I will be prepared... :)
But I have a very good argument: Chrilly Donninger already did it in
Nimzo 3!
Best wishes
Andreas
chrisw
--
http://www.demon.co.uk/oxford-soft
Andreas Mader <ma...@p6.gud.siemens.co.at> wrote in article
<334550...@p6.gud.siemens.co.at>...
Two arguments - I did in in CSTal
Chris Whittington
>
> Best wishes
> Andreas
>
Robert Hyatt
chrisw (chr...@cpsoft.demon.co.uk) wrote:
: That's what I think too. But be prepared for a heavy onslaught as to why
: its not possible ....
: Chris Whittington
note that I've never said it is not possible, only that I don't see how to
make it work, since the hash table stores exact scores (which would be easy
to fudge) and also bounds (which don't seem so easy to fudge with.)
Robert Hyatt
: Ronald de Man <de...@wsdw10.win.tue.nl> wrote:
: > This is exactly how it is done currently. The problem is that after a
: > 12 ply search a currently undeveloped bishop might have moved, so that
: > the eval is happy, but that some moves later it turns out there is no
: > more time to move the bishop, because there are some threats that have
: > to be taken care of. So it's just safer to get that bishop out right
: > away, instead of at the 11th move of a 12-ply PV. In my program, I have
: > this problem often with castling. Sometimes it is planning to castle,
: > then fails high just a little and makes some different move, planning
: > to castle the next move. This next move, the same thing happens. And
: > then suddenly it discovers some threat and it has to give up castling
: > to defend. So not delaying castling might deserve a bonus...
: Ahh, I think I'm beginning to see the problem (give him enough
: time...). So, if I'm understanding correctly, you could give any bonus
: you wanted for early development, but as you search successive plys,
: those values replace the earlier, inflated evaluation because a deeper
: eval is more accurate as a rule. So my early bishop development might
: be eval'd at +1.75 for ply1, but by ply9 it is now only evaluating as
: +0.25. If a different line produces an eval of +0.26 at ply9, then my
: bishop doesn't get developed. Oops.
: Am I close?
: So, what you really want is to somehow "take the area under the curve"
: of the sequence of plys. So, if you had two lines: the first evals to
: +0.50 for 7 plys while the second evals to -0.1 for the first 6 plys but
: then jumps to +0.51, you would want to go with the first line as it is
: only marginally worse in the long run, but much safer in the shorter
: term. Conversely, you would want to choose lines that minimize your
: opponent's "area". Of course, the art lies in choosing the
: thresholds and how you weigh the contributions of early evals.
: One possible way to do this might be in sort of a "push-down" apprach.
: In addition to the static eval of the board, each ply calculates
: "bonus" points. Instead of storing these bonuses as part of the board
: eval, it is passed down as you recurse. It then gets added to the
: eval at the next ply (and successive plys) to calculate the adjusted
: evaluation of the board. Those adjusted evaluations are what is used
: by the alpha-beta.
: Let me guess: Been there, done that, got the t-shirt, and it doesn't
: do what I think it will...
: -JohnG
Actually, I haven't "quite been there" yet. The hash table is the confounding
part. I could keep the bonus part out of the hash table, but that introduces
some things I haven't though enough about. For example, when I get a hash hit,
I would always add the current "bonus" to the value from the hash table, if it
is an exact score. And it would then reflect the path development bonuses like
you suggest. but if the hash hit is a lower bound or upper bound, I don't
think I can add this bonus to that, because if I know the current score is
<= -.222, andmy development bonus is currently +.100, I can't add the +.100
to the hash bound, because <=-.222 might be -1.000 for example, and -1.000
+.1 is still way less than -.222...... that's the part that gives me headaches
thinking about it. :)
Jay Scott
Simon Read and I independently suggested that the difficulty is not
your "promise problem" but instead is a weakness in the evaluator.
As he put it, nonlinearity is key. As I mentioned, the issue is
that pieces cooperate with each other, so you can't evaluate their
development independently (which is the same as saying that you can't
evaluate their development linearly).
This kind of evaluator should solve the development mistakes
indirectly: with a deep search, crafty will see that it has to
develop its pieces before it can use them together to put some
pressure on, so it will develop them immediately. The crucial
word here is TOGETHER.
Personally, I have a strong intuition that trying to include any
path info in the scores is the wrong idea. You've shown that
it could potentially cure development mistakes that crafty makes,
but perhaps a different evaluator would cure them better.
Jay Scott <j...@forum.swarthmore.edu>
Machine Learning in Games:
http://forum.swarthmore.edu/~jay/learn-game/index.html
Kevin Whyte
This may well be naive, but it seems like a bad idea to force the
program to do something you know to be conceptually wrong. It may
well make it play better for now (by hiding something that's wrong),
but someday you'll probably have to go back, fix the real problem, then
undo the hack. Here's how the developement problem you describe
seems to me:
1> Crafty likes developed pieces, and so "promises" in its PV to
develope at some point.
2> This promise keeps getting pushed to the end of the PV, and so
the developing moves aren't made now.
3> The opponent developes, and eventually has threats that Crafty
sees, and must defend against rather than develope, so it never
gets to develope.
I don't think it's always correct to develope first (several GMs
suggest that it's much more important to have a plan than to randomly
develope pieces). So, what crafty is doing, namely manoevering rather
than developing - given that it sees it will be able to develope
harmoniously later, is quite possibly a good thing. The problem
comes in that crafty fails to see the threats coming until its too
late. If it saw them at the end of a PV, it would know that it had
to develope now rather than later. So, it would seem that what you
need is a term in the eval that counts "vague threats", and that is
much more worried about them when it is undeveloped. This would let
it see that if it doesn't develope now, then somewhere along the
search tree we reach a position where the opponent is well developed
and crafty isn't. If the score at this node is sufficiently bad,
crafty will stop searching that branch at that point, and won't ever
see the "phantom developemnt".
Of course, I don't really know what I'm talking about.
Kevin Whyte
kwh...@math.uchicago.edu
Robert Hyatt
Jay Scott (j...@forum.swarthmore.edu) wrote:
I obviously agree with you. However, from where I am, to where I want
to be is a *giant* step. I'm trying to take baby steps instead, because
every time I deal with giant things, there are also giant diapers, giant
messes and so forth to deal with. :)
In any case, as a human, I still do some of what I am talking about above,
because if I can play two moves in a plan, I'll likely play the developing
move first, just on general principles, so that if I've overlooked something,
I'll at least have one more piece on a decent square to help me defend against
whatever I overlooked. With hashing this is harder. For real scores I can
follow doing this with no problem. For search bounds, which is almost all
of the hits I see nowadays, it seems messier and less efficient.
: This kind of evaluator should solve the development mistakes
Stephen C
Jay Scott wrote:
>
> In article <5i0fu3$4...@juniper.cis.uab.edu>, Robert Hyatt (hy...@crafty.cis.uab.edu) wrote:
> >Simon Read (bl...@blurgh.bleah.retch) wrote:
<snip>
> >only problem is the hash table can hide *when* a piece is developed, since
> >that is "path" information and is not kept in the hash table for obvious
> >space reasons...
>
> Simon Read and I independently suggested that the difficulty is not
> your "promise problem" but instead is a weakness in the evaluator.
> As he put it, nonlinearity is key. As I mentioned, the issue is
> that pieces cooperate with each other, so you can't evaluate their
> development independently (which is the same as saying that you can't
> evaluate their development linearly).
> (snip)
>
> Personally, I have a strong intuition that trying to include any
> path info in the scores is the wrong idea. You've shown that
> it could potentially cure development mistakes that crafty makes,
> but perhaps a different evaluator would cure them better.
>
> Jay Scott <j...@forum.swarthmore.edu>
>
Have either of you considered
a) Not using hash tables and using less plys instead
b) Using a multipart evaluation function (Differing on each ply)
c) Using hash but with searchs conducted under different parms
(Time consuming yes but more effective ??)
By this I mean searching for different intents. Best offensive move,
best defensive move, best supporting move, etc, etc.
Just curious.....
Stephen C
Jean-Peter Fendrich
And now we are at least 4 saying about the same thing about this and
using it in our programs...
What does Crafty do to make it impossible or hard?
IMHO it is very easy coded with some minor drawbacks.
--
J-P Fendrich
Robert Hyatt
Jean-Peter Fendrich (j...@vd.volvo.se) wrote:
the "hard" part is efficiency. If you use PVS or negascout-like
algorithms, when I played with this last time, hash efficiency went way
down. Because shifting the window wrecked havoc with the search hits
that produce bounds only... at least in my case. That was the issue I
could not resolve cleanly, and the one I've pointed out several times.
In some endings, for example, the cost was *huge* when I tested it. I
could have had bugs... hard to say, but it didn't work as efficiently as
it did before I started "shifting the window." I generally try to find
ways to accomplish things that don't give up anything... this one had too
high a cost...
anyone doing this tried a position like (say) fine #70, and shifted each
move a random amount just for testing?
Chris Mayer
On 7 Apr 1997 01:26:29 GMT, hy...@crafty.cis.uab.edu (Robert Hyatt)
wrote:
>
>the "hard" part is efficiency. If you use PVS or negascout-like
>algorithms, when I played with this last time, hash efficiency went way
>down. Because shifting the window wrecked havoc with the search hits
>that produce bounds only... at least in my case. That was the issue I
>could not resolve cleanly, and the one I've pointed out several times.
>In some endings, for example, the cost was *huge* when I tested it. I
>could have had bugs... hard to say, but it didn't work as efficiently as
>it did before I started "shifting the window." I generally try to find
>ways to accomplish things that don't give up anything... this one had too
>high a cost...
>
>anyone doing this tried a position like (say) fine #70, and shifted each
>move a random amount just for testing?
>
>
My tinkering has come to the same conclusion. It works, but you do
pay for it with many less usable hash hits. These losses are
diminished somewhat if you take into account these path dependent
bonuses in your regular move pre-sort routine for the top ply.
Chris Mayer
Ronald de Man
kwh...@ford.uchicago.edu (Kevin Whyte) writes:
> This may well be naive, but it seems like a bad idea to force the
>program to do something you know to be conceptually wrong. It may
>well make it play better for now (by hiding something that's wrong),
>but someday you'll probably have to go back, fix the real problem, then
>undo the hack. Here's how the developement problem you describe
>seems to me:
> 1> Crafty likes developed pieces, and so "promises" in its PV to
> develope at some point.
> 2> This promise keeps getting pushed to the end of the PV, and so
> the developing moves aren't made now.
> 3> The opponent developes, and eventually has threats that Crafty
> sees, and must defend against rather than develope, so it never
> gets to develope.
Yes, this is exactly the problem.
> I don't think it's always correct to develope first (several GMs
>suggest that it's much more important to have a plan than to randomly
>develope pieces). So, what crafty is doing, namely manoevering rather
>than developing - given that it sees it will be able to develope
>harmoniously later, is quite possibly a good thing. The problem
>comes in that crafty fails to see the threats coming until its too
>late. If it saw them at the end of a PV, it would know that it had
>to develope now rather than later. So, it would seem that what you
>need is a term in the eval that counts "vague threats", and that is
>much more worried about them when it is undeveloped. This would let
>it see that if it doesn't develope now, then somewhere along the
>search tree we reach a position where the opponent is well developed
>and crafty isn't. If the score at this node is sufficiently bad,
>crafty will stop searching that branch at that point, and won't ever
>see the "phantom developemnt".
The problem is that the eval only sees the position at the end of the
say 12-ply PV. It is very well possible that the program is well
developed at that point, but that the first move of the PV is still a
non-developing move. So development is delayed, and the next move the
same thing can happen, until it is too late. Telling the eval to be
more worried about development if there are threats lurking around
won't help this: the problem is occurring when the search does not see
problems coming at the end of the PV. Because if it sees problems at
the end of the PV, the eval will evaluate the position as being bad
(because that is what it should do), and the search will choose a
different PV. Delaying development does not take place in positions
where the search sees problems. It occurs in positions where developing
is safe, and it also seems safe to delay it a little.
There is really no way to solve this problem in the eval only, without
making the eval path-dependent. As I said, the eval just looks at the
position. It doesn't know what happened before. If doesn't see that there
was first a non-developing move, followed by a developing move, and that
it possibly would be wiser to interchange these.
What you need is something that distinguishes moves made early in the PV
from moves made later. But making the evaluation path-dependent gives all
kinds of problems with hashing, and so on. Therefore that is not the
solution you would like. However, giving a bonus only to the first move
of the PV can be implemented quite efficient, and gives no problems
with hashing (if implemented right of course, which is easy).
>Kevin Whyte
> kwh...@math.uchicago.edu
Ronald de Man
Ronald de Man
hy...@crafty.cis.uab.edu (Robert Hyatt) writes:
>chrisw (chr...@cpsoft.demon.co.uk) wrote:
>: Chris Whittington
You still seem to be thinking in the wrong direction.
First of all, don't worry, it is possible. But you should not try to pass
the bonus to the tip nodes. That would indeed give hash problems. The solution
is to not change anything in your Search() procedure. That already solves
all potential hash problems. You just add the bonus AFTER Search() has
returned a value for a particular root move. So that would be done in your
SearchRoot(). What you basically do there is change every occurence of
value=-Search(-beta,-alpha,...)
in
value=bonus[n]-Search(bonus[n]-beta,bonus[n]-alpha,...)
where bonus[n] is the development bonus value for the move you are currently
searching.
It is all very natural when you think about it. You should consider
Search() as a black box. You give it some numbers alpha and beta, and
Search() gives you a number x, with the properties that, relative
to the real value v of this move,
1. If v<=alpha, then x<=alpha,
2. If v>=beta, then x>=beta,
3. If alpha<v<beta, then x=v.
If you search a move, you want to know if its real value + bonus[n] is bigger
than alpha. So you want to know if its real value is bigger than
alpha-bonus[n]. So you give Search() the bounds alpha-bonus[n] and
beta-bonus[n], and add bonus[n] to the result. And you do this in SearchRoot().
So no fudging with hash table scores whatsoever!
Of course this trick gives all kinds of possibilities. Not only can you
stimulate development, or add in some randomization. It is also easy to
solve the 'underpromotion' problem: to prevent the program from under-
promoting to a rook (in situations where the piece will probably be
captured the next move anyway), you give underpromotion moves a penalty.
Or in trivially drawn endgames like KRKR you give captures a bonus.
Or in not-so-trivially drawn endgames for which tablebases give draw values
you give moves that give away a piece (but do not change the outcome)
a penalty, hoping that the opponent will make a fatal mistake further on
in the game :-)
Ronald de Man
Andreas Mader
Very good explanation, Nimzo already does this and with CHE every user
is able to force Nimzo to follow his/her own rules! So everyone can do
experiments with e.g. the development of pieces. I've done it several
times and - Bob, believe me - it works very well!
Best wishes
Andreas Mader
Robert Hyatt
Chris Mayer (cma...@ix.netcom.com) wrote:
: On 7 Apr 1997 01:26:29 GMT, hy...@crafty.cis.uab.edu (Robert Hyatt)
: wrote:
maybe what I tried was not broken then. I suppose it is gong to resolve
into an issue of whether or not I can accomplish this in some other way.
Right now the development problem is *very* rare. But it exists. The
question is, then, will it play better "overall" or will the loss of
performance that happens everywhere offset the better play in the few
"developmental" places where I see problems?
Robert Hyatt
Ronald de Man (de...@wsdw10.win.tue.nl) wrote:
: kwh...@ford.uchicago.edu (Kevin Whyte) writes:
I agree with everything above, *except* the last statement. *IF* you are
using a PVS-like algorithm, there's an efficiency loss, because given this:
value <= alpha *or* value >= alpha
you can't prove this:
value+n <= alpha *or* value-n <= beta
except for trivial cases (n negative for example). With PVS, since alpha=
beta-1, this becomes an issue at every other ply in the tree. With perfect
ordering, you might make this work, since even plies are going to cause
alpha/beta cutoffs, while odd plies are not (except for the leftmost branch
which is odd, but still has the same problems.) if n is positive, then the
test value+n>beta would still work. If n is negative, it would not. It is
not quite so easy to do, *if* you are using a PVS (null-window) type search.
: >Kevin Whyte
: > kwh...@math.uchicago.edu
: Ronald de Man
Robert Hyatt
: >chrisw (chr...@cpsoft.demon.co.uk) wrote:
: >: That's what I think too. But be prepared for a heavy onslaught as to why
: >: its not possible ....
: >: Chris Whittington
: >note that I've never said it is not possible, only that I don't see how to
: >make it work, since the hash table stores exact scores (which would be easy
: >to fudge) and also bounds (which don't seem so easy to fudge with.)
: You still seem to be thinking in the wrong direction.
: First of all, don't worry, it is possible. But you should not try to pass
: the bonus to the tip nodes. That would indeed give hash problems. The solution
: is to not change anything in your Search() procedure. That already solves
: all potential hash problems. You just add the bonus AFTER Search() has
: returned a value for a particular root move. So that would be done in your
: SearchRoot(). What you basically do there is change every occurence of
: value=-Search(-beta,-alpha,...)
: in
: value=bonus[n]-Search(bonus[n]-beta,bonus[n]-alpha,...)
: where bonus[n] is the development bonus value for the move you are currently
: searching.
: It is all very natural when you think about it. You should consider
: Search() as a black box. You give it some numbers alpha and beta, and
: Search() gives you a number x, with the properties that, relative
: to the real value v of this move,
Pardon my thick academic head... ( :) ) but this still looks like it
is wrong. If you do the above, then at ply=3, 5, 7 the bonus is *not*
factored in, because when you factor it in to call search for ply=2, you
get:
value=-search(bonus-beta, bonus-alpha);
then at ply=2, when you call search for ply=3, you get:
value=-search(bonus-(bonus-alpha), bonus-(bonus-beta)) when the
signs are reversed. Am I overlooking something here? This means at
ply=3, 5, etc... anything stored in the hash won't have the bonus factored
in at all? Which means at odd plies this trick is "inoperative"???
Which means you are not losing efficiency at odd plies at all? Which is
why you get away with this? But it also means it is *not* working at
odd plies as well, period?
That's only the odd ply case... but before I go to the even ply case,
what have I overlooked here?
: 1. If v<=alpha, then x<=alpha,
Marcel van Kervinck
Robert Hyatt (hy...@crafty.cis.uab.edu) wrote:
> Pardon my thick academic head... ( :) ) but this still looks like it
> is wrong. If you do the above, then at ply=3, 5, 7 the bonus is *not*
> factored in, because when you factor it in to call search for ply=2, you
> get:
> value=-search(bonus-beta, bonus-alpha);
> then at ply=2, when you call search for ply=3, you get:
> value=-search(bonus-(bonus-alpha), bonus-(bonus-beta)) when the
> signs are reversed. Am I overlooking something here?
The bonus is awarded to a rootmove _only_, and _only_ search_root()
has to be enhanced to do so. If I remember correctly, this is
exactly the same discussion rgcc had a few months ago. Only the
topic at the time was 'randomizing' scores. Cleanest way to do so
is precisely what Ronald suggested.
Marcel
-- _ _
_| |_|_|
|_ |_ Marcel van Kervinck
|_| mar...@stack.nl
Dr A. N. Walker
Andreas Mader wrote:
> Ronald de Man wrote:
> Very good explanation, [...]
Seconded! And I fail to understand Bob's difficulty! But I
wanted to add something else. We get hung up about reaching good
*positions*. Alpha-beta is "all about" finding the route to the best
position, as judged by our evaluation function. But if that evaluation
were accurate, we wouldn't need deep searches -- just one ply would do
[OK, throw in the quiescence stuff if you must]. Searching deeply is
our fix -- push the errors in evaluation far enough away, and they
probably won't matter. But it's not the *only* possible fix.
Chess proceeds by *moves*; we talk about good moves, blunders,
etc. So part of every player's armoury against the uncertainties of
deep evaluation is to play good moves. If the knight has two routes
to reach a particular square, and I really can't tell which route to
take, I play the one that goes nearer the centre, or that protects a
vulnerable pawn, simply because if anything goes wrong, it's safer.
So, another fix to the evaluation problem is this path dependency that
Bob is talking about -- prefer the central route, develop pieces,
protect pawns, play early the moves you have to play and defer the
moves where you have a choice, and so on.
At the first of what became the ACC series of conferences, in
1975, I remember Hans Berliner getting very irate about the moves played
by Master. Bill Hartston and other strong players present were saying
that it didn't matter, the moves transposed into a regular opening; but
Hans's argument was that it showed that Master didn't *understand* what
it was doing -- it was merely wood-shifting into what it thought were
good positions. If computer programs were ever to play at the master
level, they had to understand the nuances of move-ordering. 22 years
later, we still haven't really solved that problem. At least, Bob
hasn't!
--
Andy Walker, Maths Dept., Nott'm Univ., UK.
a...@maths.nott.ac.uk
Robert Hyatt
Marcel van Kervinck (mar...@stack.nl) wrote:
: The bonus is awarded to a rootmove _only_, and _only_ search_root()
: has to be enhanced to do so. If I remember correctly, this is
: exactly the same discussion rgcc had a few months ago. Only the
: topic at the time was 'randomizing' scores. Cleanest way to do so
: is precisely what Ronald suggested.
So you are saying, then, that for ply = 1, you make a move, and call
search with (bonus[i]-beta,bonus[i]-alpha), which offsets the entire
alpha/beta window upward or downward, but you leave things alone elsewhere
in the tree?
This was something I tried in the "random" discussion, but it broke badly
there, because since all of the root move searches are with alpha and alpha+1
for the bounds, you shift everything either above or below, which hurt the
efficiency when I tested it. Are we still on the "same page" here???
Bob
Chris Mayer
I have a very naive question, as I am a very weak player.
Q 1: Why is it so bad to develope minor pieces early, if the computer
search shows that it maybe isn't so important?
A 1?: I can only think that this is another of those human vs computer
things, where all the experts agree after centuries of experience.
Q 2: Is it possible, however, that this old wisdom may be not so
concrete in todays world of computer opponents? Instead of attempting
to mimic the old ways by hacking our code, should we not instead allow
the computer to come up with it's own style and leave it alone at
that?
A 2?: There is not currently enough search depth to prove the old
wisdom heuristics, so we have no choice but to hack in this knowledge.
Q 3: If we now admit there exist heuristics (such as early
development) that are worth many ply, can we algorithmically
(genetically, etc.) come up with new heuristics, perhaps the computer
discovering some that humans couldn't even begin to understand?
Chris Mayer
Ronald de Man
hy...@crafty.cis.uab.edu (Robert Hyatt) writes:
>Jean-Peter Fendrich (j...@vd.volvo.se) wrote:
>: Ronald de Man wrote:
>: >
>: > "chrisw" <chr...@cpsoft.demon.co.uk> writes:
>: >
>: And now we are at least 4 saying about the same thing about this and
>: using it in our programs...
>: What does Crafty do to make it impossible or hard?
>: IMHO it is very easy coded with some minor drawbacks.
>the "hard" part is efficiency. If you use PVS or negascout-like
>algorithms, when I played with this last time, hash efficiency went way
>down. Because shifting the window wrecked havoc with the search hits
>that produce bounds only... at least in my case. That was the issue I
>could not resolve cleanly, and the one I've pointed out several times.
>In some endings, for example, the cost was *huge* when I tested it. I
>could have had bugs... hard to say, but it didn't work as efficiently as
>it did before I started "shifting the window." I generally try to find
>ways to accomplish things that don't give up anything... this one had too
>high a cost...
>anyone doing this tried a position like (say) fine #70, and shifted each
>move a random amount just for testing?
First of all, I do use PVS, minimal windows, and so on.
I don't think you should try endings, because that is not where you want
to apply a development bonus (nor add randomization).
Fine #70 in particular is a bad test, because that one is relying so
heavily on hash tables that any change in the order that things are
searched can have a big effect.
But ok, I've tried it a couple of times. On the average my program
takes longer to find Kb1.
You really should try positions where you want to apply it.
(But first make sure you implement it correctly. So only change
something in SearchRoot(), and *nothing* in Search().)
As an example, I tried the position after 1. a4 (to get my program out
of book). After 10 plies, the randomized search was faster two times out
of three. The third time it was a little slower.
Of course this certainly does not mean that randomizing will make the
search more efficient. But it is in line with my personal experience
that the cost is minimal (at least for non-endings).
Remember that changing something small in the eval can cause a fail-high
where previously there was none. And fail-highs have a bad effect
on search efficiency. But a change can also make it disappear.
We have the same situation here. Adding a bonus will cause fail-highs
in some positions, and will make them disappear in others.
Ronald de Man
Robert Hyatt
Chris Mayer (cma...@ix.netcom.com) wrote:
: I have a very naive question, as I am a very weak player.
: search shows that it maybe isn't so important?
: A 1?: I can only think that this is another of those human vs computer
: things, where all the experts agree after centuries of experience.
Someone else posted the "human" explanation for this, which was exactly
the issue I was interested in: If I have a set of moves I want to play
to achieve some goal, I'm going to play the "natural" moves first, most
likely, so that if I discover my plan won't work, I've saved the "oddest"
for last (for example g5 as black) so that if I discover it's not going
to work, I have not made a move that suddenly becomes both useless and
weakening...
: Q 2: Is it possible, however, that this old wisdom may be not so
: concrete in todays world of computer opponents? Instead of attempting
: to mimic the old ways by hacking our code, should we not instead allow
: the computer to come up with it's own style and leave it alone at
: that?
: A 2?: There is not currently enough search depth to prove the old
: wisdom heuristics, so we have no choice but to hack in this knowledge.
: Q 3: If we now admit there exist heuristics (such as early
: development) that are worth many ply, can we algorithmically
: (genetically, etc.) come up with new heuristics, perhaps the computer
: discovering some that humans couldn't even begin to understand?
It's happened in endgame databases already (KQ vs KR is one good
example where it was always considered bad to separate the king and
rook, but now we know it offers the stiffest resistance.) Who knows
what new things might show up over time...
: Chris Mayer
Robert Hyatt
don't forget my original post. "first the development problem, but
later other oracle-type ideas." I'd like to be able to do this for the
entire game, but the efficiency issue gives me pause...
: You really should try positions where you want to apply it.
: (But first make sure you implement it correctly. So only change
: something in SearchRoot(), and *nothing* in Search().)
that I did. But think about this: with PVS, the absolutely most efficient
search is for the first root move to establish alpha, and then we search
the remainder of the moves with alpha,alpha+1. If you shift the root alpha/
beta window at all, even by 1 point, suddenly 1/2 of the possible fail-
high/fail-low hash hits disappear, because of the shifted bound. That has
been my concern all along... not that it couldn't be done, but that the
efficiency issue made it unattractive.
: As an example, I tried the position after 1. a4 (to get my program out
: of book). After 10 plies, the randomized search was faster two times out
: of three. The third time it was a little slower.
: Of course this certainly does not mean that randomizing will make the
: search more efficient. But it is in line with my personal experience
: that the cost is minimal (at least for non-endings).
you can also do what I did, and modify LookUp() to precisely quantify the
loss of efficiency. If you shift the bound, when you do a lookup, you can
ask "would this cutoff on original bound" and "will it not cutoff on the
current bound" and increment a counter when the answer is yes to both. I
didn't save the data, but it was higher than I liked...
: Remember that changing something small in the eval can cause a fail-high
Marcel van Kervinck
Robert Hyatt (hy...@crafty.cis.uab.edu) wrote:
> : The bonus is awarded to a rootmove _only_, and _only_ search_root()
> : has to be enhanced to do so. If I remember correctly, this is
> : exactly the same discussion rgcc had a few months ago. Only the
> : topic at the time was 'randomizing' scores. Cleanest way to do so
> : is precisely what Ronald suggested.
> So you are saying, then, that for ply = 1, you make a move, and call
> search with (bonus[i]-beta,bonus[i]-alpha), which offsets the entire
> alpha/beta window upward or downward, but you leave things alone elsewhere
> in the tree?
Right.
> This was something I tried in the "random" discussion, but it broke badly
> there, because since all of the root move searches are with alpha and alpha+1
> for the bounds, you shift everything either above or below, which hurt the
> efficiency when I tested it. Are we still on the "same page" here???
The effect of slightly reduced table use is there, ofcourse. But
this problem can be dealt with in two ways:
-1- don't overdo the bonus
-2- finally switch to fail-soft PVS
Regards,
Ronald de Man
mar...@stack.nl (Marcel van Kervinck) writes:
>The effect of slightly reduced table use is there, ofcourse. But
>this problem can be dealt with in two ways:
>-1- don't overdo the bonus
>-2- finally switch to fail-soft PVS
I just changed my program into a fail-hard one. A few tests indicated that
this might indeed increase the randomization penalty. Maybe 5% instead of 2%.
But I only tested very few positions, so this doesn't really say anything.
What surprised me a little was the loss of efficiency in going from fail-soft
to fail-hard. In most positions this was about 10%. Again, few positions.
Ronald de Man
Simon Read
In theory at least, it all ought to be taken care of by the evaluation
function, for that is where your knowledge resides. If there ever is
a suitable evaluation function developed, the computer will understand
opening strategy and we won't need opening books at all. Then we will
see what openings look like from a purely "theoretical" point of view.
This, coupled with the position learning, will produce some really
interesting openings.
Simon s'read & cranfield'ac'uk