Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss

Using values from transition tables.

41 views
Skip to first unread message

Tim Foden

unread,
Oct 13, 1997, 3:00:00 AM10/13/97
to

Hi.

I am finally attempting to get my transition table code to work
correctly, and I am a bit unsure exactly how to deal with
the value after a TT hit.

I want to run this by someone who knows before I start hacking
my code about and make things worse.

<I know this is wrong>
At the moment, whenever I get a value for a node, I simply
stuff it in the table. Whenever I enter a node and get
a TT hit, I compare the node's starting value to the table's
value, and if this >= beta, I perform a cutoff straigt away.
</I know this is wrong>

I plan on improving on this situation by storing in the table
whether the value is a fail low, exact, or fail high.

What I am not sure about is what to do when I enter a node
and get a TT hit.

Here is a table with my current idea:

condition | type of value from transition record
after |
TT hit | fail low | exact | fail high
|--------------------------------------------------
TTvalue >= | =>no action | =>cutoff | =>cutoff
beta | | return TTvalue | return TTvalue
-----------|--------------------------------------------------
TTvalue >= | =>no action | =>set alpha = | =>set alpha =
alpha | | TTvalue | TTvalue
-----------|--------------------------------------------------
TTvalue < | =>fail low | =>fail low | no action
alpha | return TTvalue | return TTvalue |

Do these seem to be the correct actions to take.

Yours, hoping for confirmation :-) Tim.
--
Tim Foden
http://www2.prestel.co.uk/diamond/index.html
Chess programming. Arcade gaming. Other stuff.

Robert Hyatt

unread,
Oct 13, 1997, 3:00:00 AM10/13/97
to

Tim Foden (ne...@diamond.prestel.co.uk) wrote:
: Hi.

: I am finally attempting to get my transition table code to work
: correctly, and I am a bit unsure exactly how to deal with
: the value after a TT hit.

: I want to run this by someone who knows before I start hacking
: my code about and make things worse.

Here is a "short course":

First, what to store?

When you are searching, and you decide that you can search no more at
the current ply, three cases have to be handled:

1. The current value is in the range alpha < value < beta, which means
this is an EXACT score. Store the value, the current depth below this
node (called the draft, usually), and an EXACT flag.

2. The current value is >= beta, which means that this move is a
"refutation" move and is causing a fail-high condition. Store the
current value, the current draft, and a flag LOWER, since this is
now known to be a lower bound on the search below this position (yes,
I am using new terminology to me, but it does seem clearer. :) )

3. The current value is <= alpha, which means that every move at this
node was searched and failed low. Here we store the current value,
an UPPER flag, and the current draft. We store UPPER because we know
that this is an upper bound on the search and that it is possible that
it is even worse than this.

Now, the other side of the coin. We recursively call Search() and when
we enter Search() the first thing to do is a hash table probe. If we get
a hit, the first thing to test is the draft, to see if the draft for the
table entry will satisfy our search depth requirement below this node. IE
if table_draft >= depth, we can use the result if it is worth anything. If
we make it past the draft test, we again have three cases:

1) The table says EXACT. We simply take the table value, and return it
as the correct search result, without searching any further at this node
or at any successor node. It might cause a cutoff, it might cause a best
value return, who knows.. but we do not need to search any further.

2) The table says LOWER. We know that this means that the table value is
a lower bound on the search value and the true search value could be even
higher. If the table value is >= BETA, we know that the search won't accept
a value >= beta, and the search below this point won't produce a value that
is < BETA, so we simply return the table value and accept the "fail high"
condition with no searching at this node. If the table value is < BETA,
it is of no use, although it can be used to lower BETA, if you like (using
PVS lowering BETA is of no use however since BETA=ALPHA+1).

3. The table says UPPER. We know that this means that the table value is
an upper bound on the search value and the true search value could be even
lower. If the table value is <= ALPHA, we know that the search won't accept
a value < ALPHA, so we simply return the table value and accept the "fail low"
condition with no searching at this node. If the table value is > alpha,
it is of no use, although it can be used to lower BETA, if you like (using
PVS lowering BETA is of no use however since BETA=ALPHA+1).

There are other things you can do, particularly an optimization to avoid
doing null-move searches when they likely won't work. You can find these in
the source to Crafty, module=lookup.c, with comments explaining what is
being done...


Tim Foden

unread,
Oct 13, 1997, 3:00:00 AM10/13/97
to

Robert Hyatt wrote:

]Tim Foden (ne...@diamond.prestel.co.uk) wrote:
]: Hi.
]
]: I am finally attempting to get my transition table code to work
]: correctly, and I am a bit unsure exactly how to deal with
]: the value after a TT hit.
]
]: I want to run this by someone who knows before I start hacking
]: my code about and make things worse.
]
]Here is a "short course":

[very useful explanation snipped -- thanks]

]There are other things you can do, particularly an optimization to avoid


]doing null-move searches when they likely won't work. You can find these in
]the source to Crafty, module=lookup.c, with comments explaining what is
]being done...

At the moment I am steering clear of null move. I'm just trying to make
the prog play as best as I can using a the normal full width search :-)

I think the next thing I am going to try to tackle is a static
exchange evaluator to cut down as much of the quiescence search
as possible as at the moment my prog tends to search about 10
times as many q-nodes as normal nodes. You wouldn't have any
tips for implementing such a thing, would you? (he asks innocently :-)

Cheers, Tim.

Robert Hyatt

unread,
Oct 13, 1997, 3:00:00 AM10/13/97
to

Tim Foden (ne...@diamond.prestel.co.uk) wrote:

: I think the next thing I am going to try to tackle is a static


: exchange evaluator to cut down as much of the quiescence search
: as possible as at the moment my prog tends to search about 10
: times as many q-nodes as normal nodes. You wouldn't have any
: tips for implementing such a thing, would you? (he asks innocently :-)

It is not difficult, but to make matters simple, again take a look at the
source to crafty, looking at swap.c...

I first make a list of white and black pieces bearing on the target
square, lowest to highest. The only real trick here is to make sure
that if you have a queen bearing on the target square, with a rook
behind it, that you don't allow the rook to get into the list before
the queen since that can not happen.

once you have the list, you simply play thru the captures until one side is
"out" of pieces and can't capture on the target square again... Then you
look at the material balance at this point and ask "is the side on move
happy or not, by comparing the material score after the side to move makes
a capture to the score before the side to move captures, since the side to
move can choose to not capture and shut things down...

From this point, the easiest way to understand how to minimax this value
is to look at swap.c, at the bottom...

It can be *very* fast, although it will have some inherent errors due to
not considering pins and overloaded pieces..


Joe Stella

unread,
Oct 14, 1997, 3:00:00 AM10/14/97
to

Tim Foden wrote:

>I think the next thing I am going to try to tackle is a static
>exchange evaluator to cut down as much of the quiescence search
>as possible as at the moment my prog tends to search about 10
>times as many q-nodes as normal nodes.

>[...]

There seems to be something wrong here. My program searches
about the same number of Q search nodes as main search nodes,
and I don't use an exchange evaluator at all.

You should make sure that you are doing as many cutoffs as
you can in the Q search. At the top of the routine, do

best = evaluate();
if (best > beta) return beta;
if (best > alpha) alpha = best;

The first line gets the static eval for the position. If
it's greater than beta, you can stop right there. If the
eval is greater than alpha, then increase alpha. This will
get you more cutoffs.

Then inside the loop you should do

for (all captures && !cutoff) {
make_move();
temp_score = increment_score();
if (temp_score > alpha) {
q_score = -q_search (-beta, -alpha, ...);
if (q_score > best) best = q_score;
if (q_score > beta) cutoff = 1;
if (q_score > alpha) alpha = q_score;
}
}

You only want to expand the search when the capture brings the
score above alpha. Then check the resulting score to see if
it is greater than beta for cutoff. Also make sure to increase
alpha if the new score is greater than alpha.

This should cause your program's Q search to be at most 1.5
times as large as your main search (measuring by node count).
Once you get this working, then you can bring in the exchange
resolver.

By the time you get the exchange resolver working correctly,
your program will probably be better than mine... :-)

Joe Stella


Robert Hyatt

unread,
Oct 14, 1997, 3:00:00 AM10/14/97
to

Joe Stella (NoJun...@Here.Please) wrote:

: Tim Foden wrote:

: >I think the next thing I am going to try to tackle is a static
: >exchange evaluator to cut down as much of the quiescence search
: >as possible as at the moment my prog tends to search about 10
: >times as many q-nodes as normal nodes.
: >[...]

: There seems to be something wrong here. My program searches
: about the same number of Q search nodes as main search nodes,
: and I don't use an exchange evaluator at all.

Might be a terminology issue too. IE if you count "internal", "leaf"
and "q-search" separately, you can get a small q-search. If you lump
leaf into q-search, it becomes quite large.

: You should make sure that you are doing as many cutoffs as

Joe Stella

unread,
Oct 14, 1997, 3:00:00 AM10/14/97
to

hyatt@crafty (Robert Hyatt) wrote:

>
>Might be a terminology issue too. IE if you count "internal", "leaf"
>and "q-search" separately, you can get a small q-search. If you lump
>leaf into q-search, it becomes quite large.

>[...]


Ooops...

I never considered the terminology. I count my leaf nodes as part
of my main search, not as part of the Q search.

I suppose if someone were to count them as part of the Q search,
and the same someone wasn't doing null move pruning, then they could
come up with a factor of 10 even with a good Q search (a factor of 5
between leaf nodes and the ply before it, then a doubling of this
because of the remaining Q search nodes).

Joe Stella


Vincent Diepeveen

unread,
Oct 14, 1997, 3:00:00 AM10/14/97
to

On 13 Oct 1997 14:04:31 GMT, hyatt@crafty (Robert Hyatt) wrote:

>Tim Foden (ne...@diamond.prestel.co.uk) wrote:
>: Hi.
>
>: I am finally attempting to get my transition table code to work
>: correctly, and I am a bit unsure exactly how to deal with
>: the value after a TT hit.
>
>: I want to run this by someone who knows before I start hacking
>: my code about and make things worse.
>
>Here is a "short course":
>

>First, what to store?
>
>When you are searching, and you decide that you can search no more at
>the current ply, three cases have to be handled:
>
>1. The current value is in the range alpha < value < beta, which means
>this is an EXACT score. Store the value, the current depth below this
>node (called the draft, usually), and an EXACT flag.

Bob, i know you are entirely true, and that this will help this guy
enormeously.

I also remember Kerrigan saying something. I'm not sure it was tom:

If you use alfabeta, then you NEVER get an EXACT flag.

You only get

>= beta

and

<= alfa

because if a score is : alfa < value < beta

then you improve alfa with value

thus window becomes: alfa = value < beta

So value <= alfa

If you store in a temporary variable alfa: tmp = alfa
and later check for an EXACT score of value:

tmp < value < beta
instead of

alfa < value < beta

Then you might try to store a the EXACT value.

However i just store 1 bit: score <= alfa, or score >= beta.

This only takes 1 bit out of the 80 i use for a
transpositiontable tuple. 80 is not much, and i cannot
waste any to something where Diep cannot profit from.

Vincent

Robert Hyatt

unread,
Oct 15, 1997, 3:00:00 AM10/15/97
to

Joe Stella (NoJun...@Here.Please) wrote:

: hyatt@crafty (Robert Hyatt) wrote:


: Ooops...

: Joe Stella

Yes. I count the "leaf" nodes as q-search nodes, because they are
handled in quiesce(). Which means my q-search numbers would be different
from you, even if our other code was identical...

This came to light during the big q-search node count comparison a year ago
or so. It can be confusing or misleading...

Robert Hyatt

unread,
Oct 15, 1997, 3:00:00 AM10/15/97
to

Vincent Diepeveen (di...@xs4all.nl) wrote:

: On 13 Oct 1997 14:04:31 GMT, hyatt@crafty (Robert Hyatt) wrote:

: >Tim Foden (ne...@diamond.prestel.co.uk) wrote:
: >: Hi.
: >
: >: I am finally attempting to get my transition table code to work
: >: correctly, and I am a bit unsure exactly how to deal with
: >: the value after a TT hit.
: >
: >: I want to run this by someone who knows before I start hacking
: >: my code about and make things worse.
: >
: >Here is a "short course":
: >
: >First, what to store?
: >
: >When you are searching, and you decide that you can search no more at
: >the current ply, three cases have to be handled:
: >
: >1. The current value is in the range alpha < value < beta, which means
: >this is an EXACT score. Store the value, the current depth below this
: >node (called the draft, usually), and an EXACT flag.

: Bob, i know you are entirely true, and that this will help this guy
: enormeously.

: I also remember Kerrigan saying something. I'm not sure it was tom:

: If you use alfabeta, then you NEVER get an EXACT flag.

this is incorrect, wherever it came from. IE watch crafty whisper analysis
on ICC and you will see PV's that end with <HT> which means an EXACT value
position was hit and used, and the PV stops at that point. So I'm not
quite sure what you mean here, but you can confirm that EXACT does happen.
I used to count 'em but it happens maybe 1% in the middlegame. When I went
to PVS, it dropped even further, but *not* to zero...


: You only get

: >= beta

: and
:
: <= alfa

: because if a score is : alfa < value < beta

: then you improve alfa with value

: thus window becomes: alfa = value < beta
:
: So value <= alfa

: If you store in a temporary variable alfa: tmp = alfa
: and later check for an EXACT score of value:

aha... a programming trick. Save alpha at the top of search. then,
when you store after completing the search at that ply you can tell if
alpha==original_alpha, if so this table position is UPPER_BOUND, if
not, it is EXACT...

I hope you are doing that, otherwise you miss out on some good table
hits..


: tmp < value < beta


: instead of
:
: alfa < value < beta

: Then you might try to store a the EXACT value.

: However i just store 1 bit: score <= alfa, or score >= beta.

you are missing some exact matches, particularly in endgames.

: This only takes 1 bit out of the 80 i use for a

: transpositiontable tuple. 80 is not much, and i cannot
: waste any to something where Diep cannot profit from.

You should try it before casting it out. EXACT works... you just
didn't implement it correctly.. save alpha at the top of search and
things will change...


Marcel van Kervinck

unread,
Oct 15, 1997, 3:00:00 AM10/15/97
to

Vincent Diepeveen <di...@xs4all.nl> wrote:
> You only get
> >= beta
> and
> <= alfa
> because if a score is : alfa < value < beta
> then you improve alfa with value
> thus window becomes: alfa = value < beta
> So value <= alfa
> If you store in a temporary variable alfa: tmp = alfa
> and later check for an EXACT score of value:
> tmp < value < beta
> instead of
> alfa < value < beta

You're throwing away information if you do this.

change your search declaration from:

int search (*pos, depth, alpha, beta)
{
struct table_entry *tt;

...

tt->flag = (alpha < score) - (score < beta);
return score;
}

into something like:

int search (*pos, const depth, const alpha, const beta)
{
struct table_entry *tt;

...

tt->flag = (alpha < score) - (score < beta);
return best_value;
}

and you'll be able to recognize exact scores.

Not that it really matters in PVS however...

Marcel
-- _ _
_| |_|_|
|_ |_ mar...@stack.nl
|_| Marcel van Kervinck

Robert Hyatt

unread,
Oct 15, 1997, 3:00:00 AM10/15/97
to

Marcel van Kervinck (mar...@unox.hak.nl) wrote:

: int search (*pos, const depth, const alpha, const beta)
: {
: struct table_entry *tt;

: ...

: tt->flag = (alpha < score) - (score < beta);
: return best_value;
: }

: and you'll be able to recognize exact scores.

: Not that it really matters in PVS however...

Where I find it matters most is when Crafty ponders the wrong move,
but the opponent plays the move that is second in the pondered PV,
which means the move actually played and the move being pondered
end up as a transposition of moves since both moves must be
played. I get exact scores there regularly, and answer the
question "what does the <HT> mean on the end of a PV that Crafty
whispered?" several times a day. This is caused by the above
sort of "hit" where it gets an EXACT value and returns that, which
backs on up to become the PV.

I just checked one log file and found 22 such PV's displayed, out
of about 60 moves in the game (note that I display a PV whenever
it changes so this is not a major percentage of all the PV's that
were displayed of course). however it does suggest that Vincent
is missing out. A good test is to run some position that is a
deep mate you can find. After finding the mate, you should be
able to follow the mate from move to move without having to search
any, because the next search should get an instant hash table hit
on the mate score (which I store as mate-in-N from the current ply)
and the search exits. If he doesn't get mate scores from the hash
table, he misses out on some useful info...


Tim Foden

unread,
Oct 16, 1997, 3:00:00 AM10/16/97
to

Robert Hyatt wrote:
[snip]
]It can be *very* fast, although it will have some inherent errors due to

]not considering pins and overloaded pieces..

Yes. I have implemented it now. :-) My version is to be quite a lot
slower than the one you have in Crafty though. :-(

It makes the quiescence nodes slower, but cuts out more than enough
to speed the whole process up quite considerably. I guess that
I now only search around 5 times more q-nodes than internal nodes
(yes, I count leaf nodes as q-nodes).

Again Bob, thanks for your help.

0 new messages