Alpha-Beta window in transposition tables?
Marty "c" Bochane
Hi there,
I'm having a hard time implementing transposition tables. My alpha
beta routine seems to return values that depend strongly on the
alpha-beta window. So when I find a board position in the transposition
table, the returned value is often much higher or lower than the value
that the alpha-beta routine returns for the current alpha-beta window.
I figured out that it shouldn't hurt to use the transposition table's
value, as long as the current alpha beta window lies within the
alpha beta window that was used to calculate the value.
However, my program is still giving material, and doing stupid things
now and then, and I checked every bit of the alpha beta search routine.
I have a strong feeling that it has something to do with the
transposition tables.
Does anybody know if it's ok what I'm doing with the alpha-beta check
in the transposition table lookup, or does anybody have tips to see
what's wrong?
Any help would be greatly appreciated!
--
Marty (ma...@orion.nl).
Joe Stella
"Marty \"c\" Bochane" <ma...@orion.euronet.nl> wrote:
>[...]
>I figured out that it shouldn't hurt to use the transposition table's
>value, as long as the current alpha beta window lies within the
>alpha beta window that was used to calculate the value.
>[...]
>Marty (ma...@orion.nl).
When you save the score in the transposition table, you should also
save a two-bit flag denoting "Upper Bound", "Lower Bound", or "Exact".
If the score is within the current alpha-beta window, then set the
flag to "Exact". This is an exact score, and shouldn't change if
you change alpha and beta (as long as the score is still between alpha
and beta).
If the score is below alpha, store alpha in the table (*not* the score)
and set the flag to "Upper Bound". This means that the score cannot be
greater than alpha, but could be less.
Likewise, if the score is above beta, store beta in the table along with
the "Lower Bound" flag. This denotes that the score is at least as high
as beta.
Now when you *use* the score from the table, make sure you check the
flag. Don't do anything that isn't justified; i.e. If you retrive a score
that is greater than your current beta, but the flag says "Upper Bound",
then you can't use this score to make a cutoff (the true score can be
anywhere *below* the upper bound).
Joe Stella
Valavan Manohararajah
In article <54r26g$u...@decius.ultra.net>, Joe Stella <jo...@ultranet.com> wrote:
>
> "Marty \"c\" Bochane" <ma...@orion.euronet.nl> wrote:
>
>>[...]
>>I figured out that it shouldn't hurt to use the transposition table's
>>value, as long as the current alpha beta window lies within the
>>alpha beta window that was used to calculate the value.
>>[...]
>
>>Marty (ma...@orion.nl).
>
>
>When you save the score in the transposition table, you should also
>save a two-bit flag denoting "Upper Bound", "Lower Bound", or "Exact".
>
>If the score is within the current alpha-beta window, then set the
>flag to "Exact". This is an exact score, and shouldn't change if
>you change alpha and beta (as long as the score is still between alpha
>and beta).
>
>If the score is below alpha, store alpha in the table (*not* the score)
>and set the flag to "Upper Bound". This means that the score cannot be
>greater than alpha, but could be less.
>
>Likewise, if the score is above beta, store beta in the table along with
>the "Lower Bound" flag. This denotes that the score is at least as high
>as beta.
>
This is correct for non fail-soft implementations. With fail-soft
implementations you can infact store values above alpha and beta, since with
fail-soft the search routine can return values outside the bound (which can
be used as better bounds if you wish).
>Now when you *use* the score from the table, make sure you check the
>flag. Don't do anything that isn't justified; i.e. If you retrive a score
>that is greater than your current beta, but the flag says "Upper Bound",
>then you can't use this score to make a cutoff (the true score can be
>anywhere *below* the upper bound).
>
> Joe Stella
>
>
--
-------------------------------------------------------------------------------
man...@ecf.utoronto.ca | 3rd year Comp Eng., University of Toronto
Valavan Manohararajah |
-------------------------------------------------------------------------------
Dr. Rudolf Posch
Joe Stella wrote:
>
> "Marty \"c\" Bochane" <ma...@orion.euronet.nl> wrote:
>
> >[...]
> >I figured out that it shouldn't hurt to use the transposition table's
> >value, as long as the current alpha beta window lies within the
> >alpha beta window that was used to calculate the value.
> >[...]
>
> >Marty (ma...@orion.nl).
>
> When you save the score in the transposition table, you should also
> save a two-bit flag denoting "Upper Bound", "Lower Bound", or "Exact".
>
> If the score is within the current alpha-beta window, then set the
> flag to "Exact". This is an exact score, and shouldn't change if
> you change alpha and beta (as long as the score is still between alpha
> and beta).
>
> If the score is below alpha, store alpha in the table (*not* the score)
> and set the flag to "Upper Bound". This means that the score cannot be
> greater than alpha, but could be less.
>
> Likewise, if the score is above beta, store beta in the table along with
> the "Lower Bound" flag. This denotes that the score is at least as high
> as beta.
>
> flag. Don't do anything that isn't justified; i.e. If you retrive a score
> that is greater than your current beta, but the flag says "Upper Bound",
> then you can't use this score to make a cutoff (the true score can be
> anywhere *below* the upper bound).
>
> Joe Stella
A remark to storing alpha in the transposition table instead of the score with flag "upper Bound" and Beta
instead of the score with flag "lower Bound":
When you use the "fail soft" versions of the diverse search algorithms (alpha-Beta,Aspiration window search,
NegaScout,..), which initialize the variable "score" to "-infinite" instead of to alpha, you may use the
returned score as "real" upper bound (if score < Alfa) respectively as lower bound (if score > beta) in a later
research as well as entry in the transposition table.
The problem which I have in my private chess programm is the "best move" in a situation score < Alfa.
I store in my transposition table at the end of the search of a node the flag (upper bound/exact/lower bound),
the value (score(<alpha)/ score/ score(>beta) ), the "draft" (search depth - current depth) and additionally
the "best" move in this node.
So what about the best move, when score < alpha ? The move which returned the upper bound value "score" may
have a value much lower as score (which was not calculated because of cutoff), as may have all other moves in
this node.
"upper Bound" means only "all moves are worse then score, which move is the best or which move is the worst is
not known. The only thing I know is that no move has a better value then score".
So I would be interested how other chess programmers handle this situation and what best move -if any- they put
in this case in their transposition table.
I have made tests with my chess program, storing the move, which returned the (highest) value "score" (< Alfa)
in the transposition table. When using this transposition table entry later and score < "current alpha value" I
dont know what to code at this point:
I suppose
a) I may finish the investigation of the node, because "value read from transposition entry is an upper bound
for this position and lower as the current alpha" and return the value directly.
b) I put the "best" move from the transposition table entry into the principal variation of this branch at the
current depth.
Because of a) I return often too high values (upper bounds).
Because of b) my principal variation gets longer, which should be good for an eventual research or the
iterative deeping, but with maybe "wrong" moves.
Can anybody give me hints or references on papers, where to read about this specific topic?
MfG Rudolf Posch
Robert Hyatt
Dr. Rudolf Posch (Rudolf...@siemens.at) wrote:
<SNIP>
:
: The problem which I have in my private chess programm is the "best move" in a situation score < Alfa.
: I store in my transposition table at the end of the search of a node the flag (upper bound/exact/lower bound),
: the value (score(<alpha)/ score/ score(>beta) ), the "draft" (search depth - current depth) and additionally
: the "best" move in this node.
:
: So what about the best move, when score < alpha ? The move which returned the upper bound value "score" may
: have a value much lower as score (which was not calculated because of cutoff), as may have all other moves in
: this node.
: "upper Bound" means only "all moves are worse then score, which move is the best or which move is the worst is
: not known. The only thing I know is that no move has a better value then score".
:
: So I would be interested how other chess programmers handle this situation and what best move -if any- they put
: in this case in their transposition table.
: I have made tests with my chess program, storing the move, which returned the (highest) value "score" (< Alfa)
: in the transposition table. When using this transposition table entry later and score < "current alpha value" I
: dont know what to code at this point:
: I suppose
: a) I may finish the investigation of the node, because "value read from transposition entry is an upper bound
: for this position and lower as the current alpha" and return the value directly.
: b) I put the "best" move from the transposition table entry into the principal variation of this branch at the
: current depth.
:
: Because of a) I return often too high values (upper bounds).
: Because of b) my principal variation gets longer, which should be good for an eventual research or the
: iterative deeping, but with maybe "wrong" moves.
:
:
: Can anybody give me hints or references on papers, where to read about this specific topic?
:
: MfG Rudolf Posch
I store "0" on "fail low" nodes, since we tried each and every move, and none appeared
to be any good, I do this:
when I go to Store() an entry, I obviously will replace an exact match in the table
with the new position, since they are the same position. If the replaced position
has a suggested best move, I keep it in the new entry. Otherwise, I store a 0
move and keep going. I don't have any idea how you could store anything else if
every move failed low. There's no "ranking" mechanism for a set of moves which
produce a set of scores that are simply "< alpha". There's not much to compare
to differentiate them. :)
Bob
Joe Stella
hy...@crafty.cis.uab.edu (Robert Hyatt) wrote:
>I store "0" on "fail low" nodes, since we tried each and every move, and none appeared
>to be any good, I do this:
>[...]
>Bob
In my program I use the "fail-soft" alpha-beta method, and when all
moves fail low, I store the move that has the highest upper bound. I
know that in theory this should not really work, but my program consistently
seems to perform better when I do this as opposed to storing no move at
all. It searches most positions about 15% faster using this method.
Has anyone else tried this?
Joe Stella
Valavan Manohararajah
Joe Stella wrote:
> In my program I use the "fail-soft" alpha-beta method, and when all
> moves fail low, I store the move that has the highest upper bound. I
> know that in theory this should not really work, but my program consistently
> seems to perform better when I do this as opposed to storing no move at
> all. It searches most positions about 15% faster using this method.
>
> Has anyone else tried this?
>
> Joe Stella
I used to use this stuff in my program as well.... in fail-soft you
still get a "best move" even when the search fails low. This can be
a guess as to where the best move lies. This is a pretty good
estimation too since it was also a plus in my program: but I don't
think I saw a speed up of 15%.... I think it was lower for me.
I would be curious to know how you get around the search
inconsistencies you get with the vanilla fail-soft algorithm.... in
quite a few cases I have observed the vanilla fail-soft algorithm
fail high, and then report a research value lower than the fail-high
value.
Robert Hyatt
Marcel van Kervinck (bue...@asterix.urc.tue.nl) wrote:
: Valavan Manohararajah (man...@bnr.ca) wrote:
:
: : I would be curious to know how you get around the search
: : inconsistencies you get with the vanilla fail-soft algorithm.... in
: : quite a few cases I have observed the vanilla fail-soft algorithm
: : fail high, and then report a research value lower than the fail-high
: : value.
: Again, these have nothing to do with fail-soft, but with your
: implementation of your transposition table.
:
: Marcel
: -- _ _
: _| |_|_|
: |_ |_ Marcel van Kervinck
: |_| bue...@urc.tue.nl
Not necessarily... here's one way to make this happen with *any*
alpha/beta implementation.
You search a move and in doing so, you search a position P and the
best move leading from that position results in a fail high. You
store P, plus the fail-high move, and a note that the value is
> 1.200 (for example.) Remember, that at this position P, you
know the value is > 1.200, but that's all. Also, assume that you
do all of this after a very deep search while waiting on your opponent
to make a move.
After your opponent moves, he makes something unexpected, and you
start searching again. When you encounter position P, you simply
note that this position was > 1.200, that the current beta is 1.100,
so you can safely fail high again. This gets backed up to the root
of the tree and you fail high there, and start the research. Now,
when you get to position P, you can't use this >1.200 value because
beta is now larger. You can't fail high, and you *might* not be
able to search deep enough this time to see why it would have failed
high the last time you reached P. So, you know it's better than 1.200,
but you have no idea why, and the search then fails low because it
can't see deeply enough to find it. So you see a fail high, followed
by either a fail low or a score that is < 1.200, either one of which
seems odd. But totally correct. And it's not an improper implementation
of hashing, just an anomoly that is "part" of hashing...
Bob
Marcel van Kervinck
Marcel van Kervinck
Robert Hyatt (hy...@crafty.cis.uab.edu) wrote:
> Marcel van Kervinck (bue...@asterix.urc.tue.nl) wrote:
> > > I would be curious to know how you get around the search
> > > inconsistencies you get with the vanilla fail-soft algorithm.... in
> > > quite a few cases I have observed the vanilla fail-soft algorithm
> > > fail high, and then report a research value lower than the fail-high
> > > value.
> >
> > Again, these have nothing to do with fail-soft, but with your
> > implementation of your transposition table.
> Not necessarily... here's one way to make this happen with *any*
> alpha/beta implementation.
> You search a move and in doing so, you search a position P and the
> best move leading from that position results in a fail high. You
> store P, plus the fail-high move, and a note that the value is
> > 1.200 (for example.) Remember, that at this position P, you
> know the value is > 1.200, but that's all. Also, assume that you
> do all of this after a very deep search while waiting on your opponent
> to make a move.
> After your opponent moves, he makes something unexpected, and you
> start searching again. When you encounter position P, you simply
> note that this position was > 1.200, that the current beta is 1.100,
> so you can safely fail high again. This gets backed up to the root
> of the tree and you fail high there, and start the research. Now,
> when you get to position P, you can't use this >1.200 value because
> beta is now larger. You can't fail high, and you *might* not be
> able to search deep enough this time to see why it would have failed
> high the last time you reached P. So, you know it's better than 1.200,
> but you have no idea why, and the search then fails low because it
> can't see deeply enough to find it. So you see a fail high, followed
> by either a fail low or a score that is < 1.200, either one of which
> seems odd. But totally correct. And it's not an improper implementation
> of hashing, just an anomoly that is "part" of hashing...
The way you describe this is exactly what I had in mind when I stated
that this is caused by an error in the transposition handling. I used
to see these anomalies in my previous program, but I managed to resolve
them completely in the new version. Unfortunately I have been unable
to find any literature on transposition tables that doesn't make the
same mistake. Let me try to explain what's wrong with this way of
table management:
The basic rule is this: If you trust deeper searches found in the table
and substitute them for a shallow search (what we all want to do) you have
to do this in a consistent way. Not doing so will backfire on you.
In you example above, the moment you fail low you are in error. You
should return 1.200, not less. The reason is that you *can* use the table
info, and therefore you *have* to. The table claims a deeper search
proved the value to be at least 1.200, so the shallow search should not
contradict that. The table has more 'authority' and the shallow
search should 'obey'.
Here is how to implement it, in pseudo C. The hardalpha and
hardbeta parts are new to the canonical implementation.
I only bothered to give the table reading part, as writing
remains as usual.
----------------------------------------------
struct table_entry {
int key;
int depth;
int score;
int flag;
} table[];
int search(pos *p, int alpha, int beta, int depth)
{
int hardalpha, hardbeta;
int score;
struct table_entry *tt = NULL;
hardalpha = -INF; hardbeta = +INF;
score = -INF; /* fail-soft */
'lookup position p in table and if found
point tt towards the right table_entry,
otherwise leave tt NULL'
if(tt && tt->depth >= depth) {
switch(tt->flag) {
case EXACT:
return tt->score;
break;
case LOWER:
if(tt->score >= beta)
return tt->score;
else
hardalpha = tt->score;
break;
case UPPER:
if(tt->score <= alpha)
return tt->score;
else
hardbeta = tt->score;
break;
}
}
'do your usual search here'
if(score < hardalpha)
score = hardalpha;
if(score > hardbeta)
score = hardbeta;
return score;
}
----------------------------------------------
And you inconsistensies are gone in 100 minus epsilon percent of all
cases. The remaining errors are caused by overwriting the table entry
between two hits. This doesn't hurt however, as long as it doesn't
introduce loops of repeating fail lows and highs. This can only happen
under very obscure conditions, and clearing the table and rebuilding
the hashfunction with other random numbers is the only solution in that
case. But coding that is merely a matter of pride, as you will never
live to see it being executed, I guess.
Robert Hyatt
Depends on your definition of "inconsistency." It's still there, you just
hide it (exactly like I hide it in Crafty, because when I fail high, I search
beta-1,beta+X where X is something that I think covers where the move will
fall, if it fails low, I still have the "estimate", but this does *not*
remove the inconsistency.) The problem is you do not know an *exact*
score, which can make you choose the wrong move. If another move fails high
and you get an exact score that is 1.25 for example, you will take that, when
if you searched even deeper you'd see the > +1.2 move is, in reality, +4.5...
When you store a >X or <X sort of score, that can trigger a fail high or
low, but you may not be able to search deeply enough to "see". I don't know
of any solution to this... Your trick prevents a score < new alpha, which
I also do, but it doesn't solve the problem in general...
Rudolf Posch
Joe Stella wrote:
>
> hy...@crafty.cis.uab.edu (Robert Hyatt) wrote:
>
> >I store "0" on "fail low" nodes, since we tried each and every move, and none appeared
> >to be any good, I do this:
> >[...]
> >Bob
>
> moves fail low, I store the move that has the highest upper bound. I
> know that in theory this should not really work, but my program consistently
> seems to perform better when I do this as opposed to storing no move at
> all. It searches most positions about 15% faster using this method.
>
> Has anyone else tried this?
>
> Joe Stella
I have made the same experience with my chess program.
It "seems" better to perform, although I have the "faint feeling" that with this method it picks rarely a wrong
move.
(For explanation of the unscientific expressions "seems" and "faint feeling" my private chess program search
algorithm has grown over the years to an non-transparent, impenetrable piece of code, adding everything to
search (Aspiration window with depth 0-research,Nega-Scout at depth > 0, Null move heuristic, transposition
table look up,selective deepening,complicated quiescence search interwoven with the normal search, some obscure
forward pruning, ...)).
Though I have the following argument to explain the better performance:
With good move ordering (searching very often the best moves first in a position), searching a bad position
(all moves fail low), the following occurs (for explanation I assume a position at depth 0,White to move,
variables "Best0" and "Best1" which hold the current best score of the position in depth 0 resp. 1, the
Variables Alpha1,2 and Beta1,2 and NegaMax search ):
For each move which white tries, black searches the answer moves at depth 1 with a Beta1= -Alpha0. Because of
good move ordering, the probability is high that black at depth 1 returns the best (or at least one of the
best) black move with Best1 > Beta1. In other words there is a Beta1-Cutoff at depth 1 early at searching the
depth 1-position, but this doesnt matter; in most cases there are no better moves for black after that which
caused the Beta 1 cutoff and were not searched because of cutoff.
This means at depth 0 the value Best0 (= -Best1) < Alfa0 gained for a white move is frequently the real value
of this move or not much lower. Best0 is an upper Bound, this is the only true thing, but frequently it is at
the same time the exact value or only a small quantity too low.
After searching all white moves in depth 0, Best0 (< Alfa0) contains an upper bound and the principal variation
move at depth 0 is the one which gained Best0.
Best0 is the maximum of the upper bounds (but often exact values or some "small" amount too low) of all white
moves. Quite often the move should be the real best move.
Because of the fail low condition, a research must be done with the new window (-INF,Best0+1). Using the "best
move" stored at depth 0 for move ordering in the research should have a positive effect.
The same is true for storing the "best move" with the flag "upper bound" in the transposition table entry in
depth 0 (assuming to overwrite only lower drafts and at the same draft not to overwrite "exact" or "low
bound"-enties).
When using a transposition table entry with flag "upper bound, value=Best,move,...) and Best < (current Alfa),
one can stop the search for the current node and use Best as actual (upper) bound score of the position (as
long as there will be a research later in all cases of a fail low/ fail high condition).
The move from the transposition table may be used for the principal variation with the same reasons and should
help in later researches (Null move window or aspiration window research).
The danger with storing/ using the move (at least at depth 0) is maybe with side effects of other forward
pruning measures in a complicated search routine. The move is not surely the best and may be used inadvertently
(explaining my faint feeling of unsafeness with this piece of code).
By the way I suppose the same whole story is true for "fail high nodes". For instance in the discussed case
above it makes reason to store Beta1-Cutoffs into the transposition table along with the associated black move
with the flag "lower bound" and use for later search or research, despite it isnt sure that it is the best
move.
Robert Hyatt
Rudolf Posch (Rudolf...@banyan.siemens.at) wrote:
: Joe Stella wrote:
: >
: > hy...@crafty.cis.uab.edu (Robert Hyatt) wrote:
: >
: > >I store "0" on "fail low" nodes, since we tried each and every move, and none appeared
: > >to be any good, I do this:
: > >[...]
: > >Bob
: >
: > In my program I use the "fail-soft" alpha-beta method, and when all
: > moves fail low, I store the move that has the highest upper bound. I
: > know that in theory this should not really work, but my program consistently
: > seems to perform better when I do this as opposed to storing no move at
: > all. It searches most positions about 15% faster using this method.
: >
: > Has anyone else tried this?
: >
: > Joe Stella
:
: I have made the same experience with my chess program.
: It "seems" better to perform, although I have the "faint feeling" that with this method it picks rarely a wrong
: move.
: (For explanation of the unscientific expressions "seems" and "faint feeling" my private chess program search
: algorithm has grown over the years to an non-transparent, impenetrable piece of code, adding everything to
: search (Aspiration window with depth 0-research,Nega-Scout at depth > 0, Null move heuristic, transposition
: table look up,selective deepening,complicated quiescence search interwoven with the normal search, some obscure
: forward pruning, ...)).
Personally, I have *never* had a move fail high, then fail low, and find that
the move was actually bad. I've had this inconsistency since I first started
using hash tables in 1973 or so, but each time it's happened and I've gone back
and searched the position/move with no hashing, but making it search the move
that failed high then low, it's always been a good move.
Marcel van Kervinck
Robert Hyatt (hy...@crafty.cis.uab.edu) wrote:
> Depends on your definition of "inconsistency." It's still there, you just
> hide it (exactly like I hide it in Crafty, because when I fail high, I search
> beta-1,beta+X where X is something that I think covers where the move will
> fall, if it fails low, I still have the "estimate", but this does *not*
> remove the inconsistency.) The problem is you do not know an *exact*
Allright. What is your suggestion for a formal definition of
search inconsistency? After we have settled that, we can
discuss the different techniques further.
> score, which can make you choose the wrong move. If another move fails high
> and you get an exact score that is 1.25 for example, you will take that, when
> if you searched even deeper you'd see the > +1.2 move is, in reality, +4.5...
In my opinion, the shallow search is perfectly entitled to choose
the 1.25 move over the 1.20 one. Since there is no reason to believe
or prove the 1.20 move to be +4.5. *But* it does prove it to be better
than moves in the range 1.1 - 1.2, which is exactly the range where
your search might fail and store an inferior move the next time.
> When you store a >X or <X sort of score, that can trigger a fail high or
> low, but you may not be able to search deeply enough to "see". I don't know
> of any solution to this... Your trick prevents a score < new alpha, which
> I also do, but it doesn't solve the problem in general...
I don't consider my implementation to be a 'trick', but a 'technique'.
But as said above, no need to discus this until a formal definition
of search inconsistency has been agreed upon.
Regards,
Marcel
BTW, (of topic) Your imply that you use some sort of aspiration
window search on top of pvs+tables. Is that something that has
survived from the past, or is there some quantifiable reason
for it?
Robert Hyatt
: window search on top of pvs+tables. Is that something that has
: survived from the past, or is there some quantifiable reason
: for it?
I'm doing the following: Basic search is NegaScout, right out
of the book. This searches the first root move with (alpha,beta)
and the rest of the root moves with (alpha,alpha+1) as you'd
expect. This is also done recursively, so the first successor
of the root move has its first branch searched with a wide window
and the rest searched with a null window.
I don't start with +/- infinity at the root, I start about 1/4 of
a pawn on either side of the last search value. Depending on the
version of Crafty, a fail high might increase beta by 1.000 or by
something else. In Cray Blitz, we had a three-tier faill high,
the first fail high raised the null window to the original value
of beta, the second added 1.000 to this, and the next added 8.000
more. The last fail high would take beta to +infinity. This was
good in lots of problems, in that I remember one in particular
where the goal was to win a piece, but if you let beta hit +infinity,
the search would hang because there were zillions of unforced mates
that suddenly didn't fail high or low.
however, the "aspiration" window has been used for years by me
and everyone else. I don't know of a good alternative except for
+/- infinity, which I don't want to use at the root, even with
PVS...
Bob
Komputer Korner
Robert Hyatt wrote:
>
>snipped.
>
> I don't start with +/- infinity at the root, I start about 1/4 of
> a pawn on either side of the last search value. Depending on the
> version of Crafty, a fail high might increase beta by 1.000 or by
> something else. In Cray Blitz, we had a three-tier faill high,
> the first fail high raised the null window to the original value
> of beta, the second added 1.000 to this, and the next added 8.000
> more. The last fail high would take beta to +infinity. This was
> good in lots of problems, in that I remember one in particular
> where the goal was to win a piece, but if you let beta hit +infinity,
> the search would hang because there were zillions of unforced mates
> that suddenly didn't fail high or low.
>
> however, the "aspiration" window has been used for years by me
> and everyone else. I don't know of a good alternative except for
> +/- infinity, which I don't want to use at the root, even with
> PVS...
>
> Bob
I am curious about the 1/4 pawn figure. How did you decide on 1/4 of a
pawn?
--
Komputer Korner
The komputer that couldn't keep a password safe from prying eyes and
couldn't kompute the square root of 36^n.
Robert Hyatt
Komputer Korner (kor...@netcom.ca) wrote:
:
: I am curious about the 1/4 pawn figure. How did you decide on 1/4 of a
: pawn?
From trial and error and watching. As a general rule, from one iteration
to the next, the evaluation has a built-in oscillation due to odd/even
searches either giving crafty 1 extra move, or both sides the same number
of moves (odd/even plies of course.)
The narrower you make this "window" the more efficient the search becomes,
*until* you make it too narrow. Then you get a *very* efficient search, but
the score comes back indicating that the window was too narrow (you get a
search value of alpha, meaning your lower bound is too high, or beta which
means your upper bound was too low.) In this case, you lose efficiency in
a drastic way because you have to alter the offending bound and then re-
search the position again... wasting time.
+/- 1/4 has worked well, it depends on (a) how stable your eval is; (b) how
deeply you search; and (c) how good your opponent is (the better the opponent,
the less the liklihood that he will overlook anything and make you fail high
too often.)
Bob
Komputer Korner
It is interesting that .25 of a pawn is exactly 1/2 way between the
value of 1 tempo and the value that white starts with at the start of a
game which is .16 or .17 of a pawn or 1/2 a tempo. Therefore your
window is = to 3/4 of a tempo plus 3/4 of a tempo or 1.5 tempos. There
must be some reason that this seems to work out neatly. We should
think about this some more.
Vincent Diepeveen
>Komputer Korner (kor...@netcom.ca) wrote:
>:
>: I am curious about the 1/4 pawn figure. How did you decide on 1/4 of a
>: pawn?
>From trial and error and watching. As a general rule, from one iteration
>to the next, the evaluation has a built-in oscillation due to odd/even
>searches either giving crafty 1 extra move, or both sides the same number
>of moves (odd/even plies of course.)
>The narrower you make this "window" the more efficient the search becomes,
>*until* you make it too narrow. Then you get a *very* efficient search, but
>the score comes back indicating that the window was too narrow (you get a
>search value of alpha, meaning your lower bound is too high, or beta which
>means your upper bound was too low.) In this case, you lose efficiency in
>a drastic way because you have to alter the offending bound and then re-
>search the position again... wasting time.
>
>+/- 1/4 has worked well, it depends on (a) how stable your eval is; (b) how
>deeply you search; and (c) how good your opponent is (the better the opponent,
>the less the liklihood that he will overlook anything and make you fail high
>too often.)
>
>Bob
>
These observations i share: the narrower the window, the worse the
extensions result.
For this reason i abandoned (alfa,alfa+1) window.
I now use alfabeta with a window from the root 0.1 pawn
and then ordinary alfabeta. This improved performance of Diep, but increased
the number of nodes searched.
How did i came to 0.1 pawn
First i used 0.2 pawn, then 0.19, and the better my evaluation becomes
the smaller i take the window. Currently i use 0.10
This might get 0.09 if i feel that evaluation has improved again.
It will get 0.01 (so alfa, alfa+1) as soon as i think i have a perfect
evaluation (so never, otherwise you don't need a positional search).
Still a huge problem is getting a fail low. Failing high is no problem.
Just research with a window -1.0 pawn, +1.0 pawn, and after this window
gets a fail high: -infinite,+infinite.
In the case of a fail low it first research with this -1.0 pawn and +1.0
pawn. Now a huge problem becomes the number of extensions Diep uses, which
are dependent on alfa and beta and other factors. Don't have a solution
for this other than simply allocating more time when getting a fail low.
problem transposes to: in a game where a lot of fail lows occur
Diep uses a lot of time for opening/middlegame and must play blitz in ending.
Vincent Diepeveen
vdie...@cs.ruu.nl
--
+--------------------------------------+
|| email : vdie...@cs.ruu.nl ||
|| Vincent Diepeveen ||
+======================================+
Robert Hyatt
Komputer Korner (kor...@netcom.ca) wrote:
: Robert Hyatt wrote:
: >
: > :
: > : I am curious about the 1/4 pawn figure. How did you decide on 1/4 of a
: > : pawn?
: >
: > From trial and error and watching. As a general rule, from one iteration
: > to the next, the evaluation has a built-in oscillation due to odd/even
: > searches either giving crafty 1 extra move, or both sides the same number
: > of moves (odd/even plies of course.)
: >
: > The narrower you make this "window" the more efficient the search becomes,
: > *until* you make it too narrow. Then you get a *very* efficient search, but
: > the score comes back indicating that the window was too narrow (you get a
: > search value of alpha, meaning your lower bound is too high, or beta which
: > means your upper bound was too low.) In this case, you lose efficiency in
: > a drastic way because you have to alter the offending bound and then re-
: > search the position again... wasting time.
: >
: > +/- 1/4 has worked well, it depends on (a) how stable your eval is; (b) how
: > deeply you search; and (c) how good your opponent is (the better the opponent,
: > the less the liklihood that he will overlook anything and make you fail high
: > too often.)
: >
: > Bob
: It is interesting that .25 of a pawn is exactly 1/2 way between the
: game which is .16 or .17 of a pawn or 1/2 a tempo. Therefore your
: window is = to 3/4 of a tempo plus 3/4 of a tempo or 1.5 tempos. There
: must be some reason that this seems to work out neatly. We should
: think about this some more.
: --
: Komputer Korner
: The komputer that couldn't keep a password safe from prying eyes and
: couldn't kompute the square root of 36^n.
My "methodology" for choosing this was to minimize the number of fail
high re-searches, without going too far. If you have no re-searches, that
means the search value was always in the window, which is not so efficient.
I did this sort of like the way some operating systems adjust a program's
resident set size (RSS) dynamically. If the page fault rate is > N, then
increase the RSS, if the fault rate is < M, then decrease the RSS, but
*never* drive the fault rate to zero, because the suspicion is that the
RSS is then too large. Most systems want "just enough" page faults to be
sure the RSS is not too large, while not having too many page faults which
is *very* ineficient. I used the same idea in Crafty, although it might be
time to re-evaluate since there's been many eval modifications since I set
out to test this...
to
Chris Whittington
Komputer Korner <kor...@netcom.ca> wrote:
>
> Robert Hyatt wrote:
> >
> >snipped.
> >
> > I don't start with +/- infinity at the root, I start about 1/4 of
> > a pawn on either side of the last search value. Depending on the
> > version of Crafty, a fail high might increase beta by 1.000 or by
> > something else. In Cray Blitz, we had a three-tier faill high,
> > the first fail high raised the null window to the original value
> > of beta, the second added 1.000 to this, and the next added 8.000
> > more. The last fail high would take beta to +infinity. This was
> > good in lots of problems, in that I remember one in particular
> > where the goal was to win a piece, but if you let beta hit +infinity,
> > the search would hang because there were zillions of unforced mates
> > that suddenly didn't fail high or low.
> >
> > however, the "aspiration" window has been used for years by me
> > and everyone else. I don't know of a good alternative except for
> > +/- infinity, which I don't want to use at the root, even with
> > PVS...
> >
> > Bob
>
>
> pawn?
And moses saw on the tablet of stone that god gave him, quarter
of a pawn shall be the window from which to smite your enemy.
And moses saw that the smiting was good, and he smote them craftily.
Then Korner got the tablet and it became the 7th amendment to
the 7th commandment, and Korner did claim the commandment as his
own, and god got exceedingly angry, and sent moses to do
some more smiting, and Korner's circuits were smoted severely, and
Korner did start posting garbage and .......
Chris Whittington