Enhanced Transposition Table Cutoffs
Andrea Zinno
Hi Tom, I'm developed an othello (also called "reversi") program during
last year and I've tried ETC (my program uses a fail-soft MTD-Alpha-Beta
with null window, Iterative deepening and Tansposition Table plus some kind
of forward pruning).
Regarding ETC I agree with you, i have observed an increase not greater
than 4-8% on the average. My opinion is that this low value depend on how
good is the order on which the nodes are visited: if MTD converges rapidly
to the exact value (2 iterations) and if the tree is expanded in such a way
that the left branch is often the minimax-tree, then the increasing
obtained by ETC is small.
Bye.
Tom King <t...@hatbulb.demon.co.uk> wrote in article
<met5TCAo...@hatbulb.demon.co.uk>...
> Any chess programmers out there played around with Enhanced
> transposition table cutoffs? It's mentioned in a couple of papers by
> Jonathon Schaeffer, which you can grab from the Web (I don't have the
> URL's, sorry).
>
> Breifly, Enhanced Transposition Table Cutoffs (ETTC) consists of this:
>
> - in most chess programs, at any level in the search tree, if you get a
> transposition table hit, but it's not good enough to give you a cutoff,
> you search the move stored in the transposition table before any others.
> This improves the move ordering in your program, leading to a more
> efficient search.
> ......
> --
> Tom King
>
Jonathan Schaeffer
"Andrea Zinno" <a.z...@finsiel.it> writes:
>Hi Tom, I'm developed an othello (also called "reversi") program during
>last year and I've tried ETC (my program uses a fail-soft MTD-Alpha-Beta
>with null window, Iterative deepening and Tansposition Table plus some kind
>of forward pruning).
>Regarding ETC I agree with you, i have observed an increase not greater
>than 4-8% on the average. My opinion is that this low value depend on how
>good is the order on which the nodes are visited: if MTD converges rapidly
>to the exact value (2 iterations) and if the tree is expanded in such a way
>that the left branch is often the minimax-tree, then the increasing
>obtained by ETC is small.
The benefits of transposition tables in Othello (reversi) programs
is small - there just aren't a lot of transpositions. The original
ETC work shows only a small benefits for Othello. In chess and checkers,
transposition tables are a major performance enhancement: ETC
performs well there.
Many people are misinterpreting the ETC results. The ETC experiments
were done with *fixed* depth searches. This was the only fair way of
measuring the node count differential. If you use variable depth,
then there is no way to quantify how much better ETC is. Using
ETC will change the search trees in subtle ways that prevent you from
fairly measuring the improvement. For example, since ETC "transfers"
transpositions from one part of the search tree to another, you often
get the effect of having an ETC transposition giving you the result
of a deeper search than you would have had without ETC. Several exper-
iments (including those done by the Deep Blue team) show that this results
in the search discovering things sooner. For example, with variable
depth searches, the Deep Blue team reported that ETC did not reduce the
search time by much, but resulted in more positions being solved in
their standard test set (personal communication).
The bottom line is not to judge ETC by execution time alone.
Tom King
In article <5rubu3$ad2$1...@pulp.ucs.ualberta.ca>, Jonathan Schaeffer
<jona...@cs.ualberta.ca> writes
>
>The benefits of transposition tables in Othello (reversi) programs
>is small - there just aren't a lot of transpositions. The original
>ETC work shows only a small benefits for Othello. In chess and checkers,
>transposition tables are a major performance enhancement: ETC
>performs well there.
>
>Many people are misinterpreting the ETC results. The ETC experiments
>were done with *fixed* depth searches. This was the only fair way of
>measuring the node count differential. If you use variable depth,
>then there is no way to quantify how much better ETC is. Using
>ETC will change the search trees in subtle ways that prevent you from
>fairly measuring the improvement. For example, since ETC "transfers"
>transpositions from one part of the search tree to another, you often
>get the effect of having an ETC transposition giving you the result
>of a deeper search than you would have had without ETC. Several exper-
>iments (including those done by the Deep Blue team) show that this results
>in the search discovering things sooner. For example, with variable
>depth searches, the Deep Blue team reported that ETC did not reduce the
>search time by much, but resulted in more positions being solved in
>their standard test set (personal communication).
>
>The bottom line is not to judge ETC by execution time alone.
Aha! So not only can ETTC save time, but it can help choose better
moves? Yes, I can see that now. I've noticed the phenomena of finding
combinations that are "too deep" thanks to a standard hash table. ETTC
will just increase the likelyhood of finding better moves.. I don't
think I've seen any situations where this happens, but if I do, I'll
post.
Ok. So Bob has played with ETTC in Crafty. What about the other
programmers who contribute to this group? Do you use this?
--
Tom King
Robert Hyatt
Tom King (t...@hatbulb.demon.co.uk) wrote:
: In article <5rubu3$ad2$1...@pulp.ucs.ualberta.ca>, Jonathan Schaeffer
Remember, my results were based solely on performance alone, and nothing
else. IE time to a particular move at a particular ply. I noticed the
"better" move idea on fine #70, where Crafty normally solves this position
(Kb1!) at ply=18. It dropped to ply=17 when I tested it.
I plan on trying this idea again very soon (as soon as 12.7 can be called
"done" and released)... but this time I am going to "do it right" and make
a special piece of code to update the hash signature only, rather thanusing
MakeMove() which updates a bunch of stuff that was not needed for the ETC
test.
I'll provide more results, and may release 12.8 with ETC installed, even if
I don't find exceptional results, just so others can try it...
Dan Wulff
Tom King <t...@hatbulb.demon.co.uk> wrote:
>Aha! So not only can ETTC save time, but it can help choose better
>moves? Yes, I can see that now. I've noticed the phenomena of finding
>combinations that are "too deep" thanks to a standard hash table. ETTC
>will just increase the likelyhood of finding better moves.. I don't
>think I've seen any situations where this happens, but if I do, I'll
>post.
>Ok. So Bob has played with ETTC in Crafty. What about the other
>programmers who contribute to this group? Do you use this?
If you can post some theory, or where I might find some, I'll try it
in Gandalf.....
Greetings
Dan
Robert Hyatt
Dan Wulff (wu...@po.ia.dk) wrote:
: Tom King <t...@hatbulb.demon.co.uk> wrote:
: Greetings
: Dan
Here's the basic idea:
when you enter a ply, you do a lookup() on the transposition table for
the current position. If that produces a suggested best move, go for
it. If not, generate moves, and then do a quick test on each one by
updating thing hash signature and probing in the "other" hash table (for
the other side-to-move) to see if you get a hit. If so, this move would
be a good one to try.
I'm going to re-test this, because I did it in a lazy fashion before by
using MakeMove() to compute the new hash key. Unfortunately it updates a
lot of other stuff so it is slower than what is really needed.
Other questions concern whether to do this before or after the capture
search (winning captures). I'll run it in every way I can think of and
report the results before long...
Jonathan Schaeffer
hy...@crafty.cis.uab.edu (Robert Hyatt) writes:
>when you enter a ply, you do a lookup() on the transposition table for
>the current position. If that produces a suggested best move, go for
>it. If not, generate moves, and then do a quick test on each one by
>updating thing hash signature and probing in the "other" hash table (for
>the other side-to-move) to see if you get a hit. If so, this move would
>be a good one to try.
Actually, the way we implemented it is different. We did the ETC check before
searching *any* moves. i.e. your description has the TT move being searched
before doing an ETC test. We did the ETC test before doing any searching.
Robert Hyatt
Jonathan Schaeffer (jona...@cs.ualberta.ca) wrote:
: hy...@crafty.cis.uab.edu (Robert Hyatt) writes:
I think I did this too... I simply did a poor job of writing. If the
current table hit didn't cause a cutoff, I tried to seeif I could find an
ETC move that would... you are correct...
Robert Hyatt
Andrew Tridgell (Andrew....@anu.edu.au) wrote:
: Robert Hyatt wrote:
: > ...
: > I'm going to re-test this, because I did it in a lazy fashion before by
: > using MakeMove() to compute the new hash key. Unfortunately it updates a
: > lot of other stuff so it is slower than what is really needed.
: I just tried it in KnightCap (which uses MTD(f) in case that matters)
: and found a approx 5-10% speedup. To make it fast I use a simple
: function that estimates the hash keys for the new position and only
: calls the full do_move() code to confirm the hash keys if I get
: a hit with the "likely" hash key. The quick function doesn't take
: into account as many things as the full do_move() (it doesn't
: account for enpassent, castling, loss of castling privilages
: etc which all contribute to the hash key)
: If I probed by calling the full do_move() on each move then I'm
: sure it would come out as a loss.
: So far I'm only using ETTC to to try to produce a instant fail high,
: I'll try using it for move ordering soon. With MTD(f) the only
: nodes where move ordering matters is those that produce fail highs
: so I'll probe for moves where the upper/lower bounds in the hash
: entry indicate that a fail high is possible.
: Cheers, Andrew
the move ordering is one hidden benefit, because it will "draw" you toward
hashable positions, and it can produce better values than normal search
because you might not get this useful hash hit otherwise...
I'm going to test also, although forme, mtd(f) is a dead issue for the
present. It was nowhere near as fast as my PVS implementatin, *for
crafty only* of course...
Tom King
In article <5t252o$egq$1...@news.uni-c.dk>, Dan Wulff <wu...@po.ia.dk>
writes
>Tom King <t...@hatbulb.demon.co.uk> wrote:
>
>
>>Aha! So not only can ETTC save time, but it can help choose better
>>moves? Yes, I can see that now. I've noticed the phenomena of finding
>>combinations that are "too deep" thanks to a standard hash table. ETTC
>>will just increase the likelyhood of finding better moves.. I don't
>>think I've seen any situations where this happens, but if I do, I'll
>>post.
>
>>Ok. So Bob has played with ETTC in Crafty. What about the other
>>programmers who contribute to this group? Do you use this?
>
>If you can post some theory, or where I might find some, I'll try it
>in Gandalf.....
>
>Greetings
>
>Dan
>
>
Have you seen the paper(s) from J. Schaeffer? If not, they are available
on line. They explain the ideas behind ETTC, and some hints on
implementation.
I'm sorry, I don't have the URL's, but I'm sure you can find them at
Alta Vista, or somewhere. Search for "Schaeffer" and "Alberta", and you
should come up trumps.
--
Tom King
Tom King
In article <5t4ga1$i...@juniper.cis.uab.edu>, Robert Hyatt
<hy...@crafty.cis.uab.edu> writes
move ordering with ETTC? I don't understand this. Do you mean: if a move
has a successor which has a hash entry, but it isn't good enough to
cause an ETTC, the move should be searched early?
>I'm going to test also, although forme, mtd(f) is a dead issue for the
>present. It was nowhere near as fast as my PVS implementatin, *for
>crafty only* of course...
>
--
Tom King
Andrew Tridgell
Andrew Tridgell
Robert Hyatt wrote:
> ...
> I'm going to test also, although forme, mtd(f) is a dead issue for the
> present. It was nowhere near as fast as my PVS implementatin, *for
> crafty only* of course...
I think there are a couple of things that crafty doesn't have that are
essential for MTD(f).
1) you need fail soft. Otherwise it may take an age to converge
2) you need both an upper and lower bound in the hash table
Cheers, Andrew
Robert Hyatt
Andrew Tridgell (Andrew....@anu.edu.au) wrote:
: Cheers, Andrew
I did failsoft in 12.7, to test this, and then took it back out...
I didn't do the upper/lower bound idea, but I don't think that is a
critical need. It might help some. But for Crafty, mtd(f) simply
doesn't work. You need a program with a stable evaluation, that doesn't
have large speculative bonuses and an eval that doesn't do any "lazy"
exits... And when you give up all of that stuff, the penalty is high,
in Crafty.
Andrew Tridgell
Robert Hyatt wrote:
> I did failsoft in 12.7, to test this, and then took it back out...
> I didn't do the upper/lower bound idea, but I don't think that is a
> critical need. It might help some. But for Crafty, mtd(f) simply
> doesn't work. You need a program with a stable evaluation, that doesn't
> have large speculative bonuses and an eval that doesn't do any "lazy"
> exits... And when you give up all of that stuff, the penalty is high,
> in Crafty.
KnightCap has lazy eval, large positional factors (often larger
than crafty) and I'd hardly call the eval stable :-)
I did add a few tricks to the standard MTD(f) to make it work well.
In particular I added:
- a convergence test routine that sees if only one move remains
in the bisection window
- some tricks in choosing the next test value that stop it from
converging slowly in bad cases. Basically each time it fails in
one direction it increases the stride that it uses.
These tricks help, but the vanilla MTD(f) was OK.
I also think you underestimate the need for upper/lower bounds
in MTD(f). With PVS researching with different bounds in the exception
whereas with MTD(f) its the norm. To make use of the previous searches
you need to keep all the info you can in the hash tables.
Andrew
Robert Hyatt
Tom King (t...@hatbulb.demon.co.uk) wrote:
: In article <5t4ga1$i...@juniper.cis.uab.edu>, Robert Hyatt
: <hy...@crafty.cis.uab.edu> writes: >: > I'm going to re-test this, because I did it in a lazy fashion before by
: >the move ordering is one hidden benefit, because it will "draw" you toward
: >hashable positions, and it can produce better values than normal search
: >because you might not get this useful hash hit otherwise...
: >
: move ordering with ETTC? I don't understand this. Do you mean: if a move
: has a successor which has a hash entry, but it isn't good enough to
: cause an ETTC, the move should be searched early?
Possibly. Something caused that position to be stored. It *might* be
that the current move is a good one. It might mean that the current move
is a lousy one and the stored position was a refutation position. Testing
will show whether this is any good. I'm going to be "out" for a week, but
I'm taking my notebook with me. I'll try to implement ETC and get some
results...
Marcel van Kervinck
Andrew Tridgell <Andrew....@anu.edu.au> wrote:
> I did add a few tricks to the standard MTD(f) to make it work well.
> In particular I added:
> - a convergence test routine that sees if only one move remains
> in the bisection window
Plain mtd(f) doesn't do this, but it is an obvious improvement
since we only want to know the best move, not it's value. Do you
jump to the next iteration when there's only one move left?
> - some tricks in choosing the next test value that stop it from
> converging slowly in bad cases. Basically each time it fails in
> one direction it increases the stride that it uses.
How often do you typically need a research in one iteration?
I often saw it doing lots of them, each improving on the previous
by only one point. All while using fail soft.
> These tricks help, but the vanilla MTD(f) was OK.
> I also think you underestimate the need for upper/lower bounds
> in MTD(f). With PVS researching with different bounds in the exception
> whereas with MTD(f) its the norm. To make use of the previous searches
> you need to keep all the info you can in the hash tables.
I guess you're right here. I've been experimenting with it for
some time, but it never really improved on pvs. Storing two bounds,
(at least in the 'pv's) is something I wanted to try next, but
never did. Also, as Aske Plaat explained, you need to be very, very
careful when doing window-dependend things. (Like vanilla null-moves).
Marcel
BTW: I see you're posting from the ANU CS department. I visited it
about two years ago and your name sounds familiar. Is there any chance
we actually met? I have fond memories of a local programming contest
we nearly won there...
-- _ _
_| |_|_|
|_ |_ mar...@win.tue.nl
|_| Marcel van Kervinck
Vincent Diepeveen
>Tom King <t...@hatbulb.demon.co.uk> wrote:
>
>
>>Aha! So not only can ETTC save time, but it can help choose better
>>moves? Yes, I can see that now. I've noticed the phenomena of finding
>>combinations that are "too deep" thanks to a standard hash table. ETTC
>>will just increase the likelyhood of finding better moves.. I don't
>>think I've seen any situations where this happens, but if I do, I'll
>>post.
>
>>Ok. So Bob has played with ETTC in Crafty. What about the other
>>programmers who contribute to this group? Do you use this?
I use it for about 1.5 years now. Only it didn't have the Name ETTC
at that time.
>If you can post some theory, or where I might find some, I'll try it
>in Gandalf.....
For all moves, in your move ordering, make the move, look whether
it gives a cut off.
Order these moves BEFORE your transtable move. It might increase
alfa or beta, or even better, it might give a cutoff.
It saves a lot when you search deeply, several %. It doesn't bring much on
7/8 ply. So i guess it will be hard to profit with Gandalf
in tournament play with it.
Anyway, our evaluation functions are so slow, that you should use it.
Doesn't eat much systemtime.
Good luck with the experiments.
>Greetings
>Dan
--
+----------------------------------------------------+
| Vincent Diepeveen email: vdie...@cs.ruu.nl |
| http://www.students.cs.ruu.nl/~vdiepeve/ |
+----------------------------------------------------+
Andrew Tridgell
Marcel van Kervinck wrote:
> Plain mtd(f) doesn't do this, but it is an obvious improvement
> since we only want to know the best move, not it's value. Do you
> jump to the next iteration when there's only one move left?
Not exactly, I just probe the hash table. For each move I check
the hashed upper bound of the opponents position after the move,
and when only one move gives a value above alpha I know that is the
move.
> > - some tricks in choosing the next test value that stop it from
> > converging slowly in bad cases. Basically each time it fails in
> > one direction it increases the stride that it uses.
>
> How often do you typically need a research in one iteration?
> I often saw it doing lots of them, each improving on the previous
> by only one point. All while using fail soft.
Thats why I added the fast striding code, I also noticed that this
could happen (especially with null moves and eval shortcuts turned on).
Typically KnightCap does 2-4 iterations per ply, most commonly 3. The
iterations aren't equal cost tho, as the hash table ensures that
you get a very large number of cutoffs after the first iteration. Thats
why you need both upper and lower bounds in the hash table. I also
store separate depths for the lower and upper bounds which prevents
iterative deepening from wrecking previous hash values.
> BTW: I see you're posting from the ANU CS department. I visited it
> about two years ago and your name sounds familiar. Is there any chance
> we actually met? I have fond memories of a local programming contest
> we nearly won there...
Yep, I was "Judge Dread" in that one I think. Your team did pretty
well!
Cheers, Andrew