Fun with transposition tables
Johno
Hello there. I wonder if anyone would be so kind as to point out where I'm
being stupid:
At the moment I'm attempting to brush the cobwebs off my program
(Woodpusher) before (hopefully) taking part in the next WMCC in Paris.
While in Jakarta last year, Tom King demonstrated to me how quickly his
program Francesca searched the following famous position (Kb1!).
8| . . . . . . . . BLACK
7| k . . . . . . .
6| . . . p . . . .
5| p . . P . p . .
4| P . . P . P . .
3| . . . . . . . .
2| . . . . . . . .
1| K . . . . . . . WHITE*
+----------------
a b c d e f g h
It was very impressive, reaching a depth of 30 ply in what seemed like a
matter of seconds. Woodpusher, on the other hand, was something of an
embarrassment, getting "bogged down" and thinking "forever" at much above
20 ply. I vowed that I would sort out Woodpusher's broken transposition
tables (TT) as soon as I got back to England ..... Almost a year latter,
I'm having a go! :-)
When storing positions to the TT Woodpusher followed (follows) what I
believe to be a conventional procedure: Hash to a position in the TT, check
the depth of the position stored there and overwrite if the depth of the
position to be stored is greater/equal; if not, have 5 further tries at
other positions in the TT. When probing the TT, the 6 positions are checked
for a key match (A). Although the TT obviously works, (the search is much
slower without it), I've always thought that there had to be something
wrong because of Woodpusher's poor search depths in simple endgame
positions such as the one above.
After checking hash code distributions, hit ratios, etc, etc, without
success I gave up. Before leaving the problem however, I did one final test
to prove to myself that my re-hashing and depth based replacement was at
least better than a simple: "hash to a TT position and just overwrite
whatever was already there regardless of whether the existing information
was the result of a deeper search" (B).
Result: *MUCH* faster at simple endgames - at last Woodpusher could search
to 30-ply in the above position. Plus - Very little slow down (if any) in
middle-game test positions.
After a bit of thought I decided to try and explain this to myself by
saying that my "sensible" replacement strategy (A) was stopping some
important positions reached in a very deep search from being stored and
therefore the "mindless" algorithm (B) was better. (Even though the hit
ratio was worse!).
=> Next idea: First hash a candidate position for storing to an even
numbered TT index. If it's depth is greater than the depth already stored
there then overwrite the existing entry, otherwise, store the position at
the next index in the TT regardless of what is already there (C). I hoped
that this would give me the best of both worlds: Every position would be
stored (advantages of (B)), but deep search results (stored at the even
numbered indices) would not be overwritten by shallow search results
(advantage of (A)).
Result: Just as poor at simple endgames as the original (A) algorithm.
Question: WHY???
I'm quite happy to vary my replacement strategy depending on the game phase
(has anyone else tried this?), but I'd really like to understand why I'm
doing it. I either have bugs or I'm missing something really obvious when I
think the above results are strange.
Thanks in advance for any help / comments :-)
Best Wishes,
Johno
Robert Hyatt
Johno (jo...@chess.demon.co.uk) wrote:
: Hello there. I wonder if anyone would be so kind as to point out where I'm
: being stupid:
: Question: WHY???
: Best Wishes,
: Johno
one quick point. "faster" is not always "better". For example, it is
not uncommon for the hash table to make the search to a specific depth
take longer. *but* the result from that longer search is actually
better, due to the way things can get grafted from here to there.
If you handle the 3 cases correctly:
1. exact scores when alpha < value < beta;
2. lower-bound where value == alpha
3. upper-bound where value == beta
you are pretty well home, after you make sure the "draft" calculations
are done right so that you don't trust a search that is too shallow.
All that is left is the replacement strategy. Unfortunately this will
blow hell out of the shape of the tree, making it *very* difficult to
compare two different hash collision handlers (collision here is when
two different keys hash to the same memory address, making you take some
sort of action from the simply entry+1 you mention, to sophisticated
rehashing for second and third probes. To test hashing, you need a
*suite*, not a single position... then you will be on your way to putting
that to rest forever...
Also, reaching ply=30 in fine #70 is not necessarily a good thing. That
means that the search probably has better move ordering than you, but it
might mean the opposite too. IE by ply 30, you can force a queen in that
position, which will blow the search up badly. A program that gets to ply
25 should begin to see forced queens in some lines, which slows it down. If
the queens are not seen, the search goes way faster. But only because it
is not as "smart" as it might be... Testing will tell the tale...
brucemo
Robert Hyatt wrote:
> Also, reaching ply=30 in fine #70 is not necessarily a good thing. That
> means that the search probably has better move ordering than you, but it
> might mean the opposite too. IE by ply 30, you can force a queen in that
> position, which will blow the search up badly. A program that gets to ply
> 25 should begin to see forced queens in some lines, which slows it down. If
> the queens are not seen, the search goes way faster. But only because it
> is not as "smart" as it might be... Testing will tell the tale...
My experience with Fine 70 is that if your hash system is completely broken
you will hit a brick wall in ply 16-18.
If your hashing is working right, you will get a solution in ply 18-27,
depending upon which way the wind is blowing at the time.
It should take just a few seconds to get a solution, regardless.
The search might start to bog, with hashing that isn't broken, in the low
30's, but of course machine speed and hash table size is a consideration.
bruce
Robert Hyatt
brucemo (bru...@seanet.com) wrote:
: Robert Hyatt wrote:
:
: > Also, reaching ply=30 in fine #70 is not necessarily a good thing. That
: > means that the search probably has better move ordering than you, but it
: > might mean the opposite too. IE by ply 30, you can force a queen in that
: > position, which will blow the search up badly. A program that gets to ply
: > 25 should begin to see forced queens in some lines, which slows it down. If
: > the queens are not seen, the search goes way faster. But only because it
: > is not as "smart" as it might be... Testing will tell the tale...
: My experience with Fine 70 is that if your hash system is completely broken
: you will hit a brick wall in ply 16-18.
: If your hashing is working right, you will get a solution in ply 18-27,
: depending upon which way the wind is blowing at the time.
: It should take just a few seconds to get a solution, regardless.
: The search might start to bog, with hashing that isn't broken, in the low
: 30's, but of course machine speed and hash table size is a consideration.
: bruce
You should likely always find this by depth=23. I believe that is all that
is needed actually see the win of at least a pawn. I've always solved it
at 18 with Cray Blitz... and similar results with Crafty depending on the
size of the hash... current version with asmall hash gets +3.9 at iteration
20...
I'm not quite sure how you go beyond 30 very fast, although I've seen your
output. 30 is enough to force a queen. Actually it doesn't take 30 if
you count extensions like advancing the pawn if it is passed. But in
any case, crafty hits ply=18 in 2.1 seconds, 19 in 3.6, but 20 takes 25
seconds as it fails high on Kb1...
usually it finds it at 18, but it depends on move ordering. IN fact, you
can find it faster if you have poor move ordering. Here's what happens:
Imagine doing a 20 ply search. You play good moves, but your opponent
plays bad moves and when you reach ply=10, you reach a position where
even if your opponent plays perfectly you can still force a win by ply
20. Then you back up and try alternative moves for the opponent, for
those moves that allow the win easily. And he can put up more
resistance. But after reaching ply=20, you force the exact same
position you reached at ply=10 with lousy opponent play. And you now
notice "aha, I know how to win this, so *this* path is also a win."
If you flip=flop the move order, it won't do this, because first you
reach the deep position and have no idea it is won. Then you reach
the same position at a shallower depth and discover it is winnable,
but it is too late. A case where sloppy move ordering can be better
than optimal move ordering. :)
Probably explains why I've always gotten it at 18. Bad move ordering.
:)
Bob
Steve Maughan
Johno
How about keeping two hash tables. One for with the "Always Replace"
strategy and one with the "Intelligent Replace" strategy. I know some
programs use this technique.
Steve
Robert Hyatt
Steve Maughan (mau...@clara.net) wrote:
: Johno
: Steve
That works. It was used (first) in Belle as I recall. The problem
is that this only gives two entries, sort of like a 2-way set associative
cache. 4-way is better in you have a choice of which of the 4 to replace,
possibly overwriting something less important. 8-way is even better, but
the time factor starts becoming noticable, *unless* you use a Cray. In
Cray Blitz, we used N=8, and simply did a vector load on the primary hash
address, with a stride of N, where 0 < N < 4096, and N was extracted from
the unused part of the hash signature. Worked very well, and the extra
7 loads cost us *nothing* on that machine. We had to wait N cycles for
the first word, then the next word was available the next cycle and so
forth.
On a PC, this tends to "die" due to memory starvation, however, since there's
no way to fit a reasonable transposition table into cache.
I use the "always store" and "depth preferred" approach in Crafty for
simplicity. You always store in one table, and the entry that is being
replaced may be moved to the depth-preferred table if it is better than the
entry it would replace. The good stuff migrates to the depth-preferred
table, using the always-store table as a sort of "staging area"...
Richard A. Fowell
(I thought I'd posted this earlier, but both services I use show my
posting with no content).
Here's how five programs do on Fine #70. Interesting dispersion.
"Johno" <jo...@chess.demon.co.uk> posted this Fine #70 (per Hyatt)
8| . . . . . . . . BLACK
7| k . . . . . . .
6| . . . p . . . .
5| p . . P . p . .
4| P . . P . P . .
3| . . . . . . . .
2| . . . . . . . .
1| K . . . . . . . WHITE*
+----------------
a b c d e f g h
Here's the EPD for those who'd like it:
8/k7/3p4/p2P1p2/P2P1P2/8/8/K7 w - - bm Kb1; id "FINE.70";
...
Johno noted that his "sensible" hash algorithm stalls at about 20 ply,
whereas other programs zip through 30 ply in seconds.
Just for fun I ran this problem through a few
programs on my Mac 7600/180 (results below).
Observations:
Even though Crafty 11.14d1 didn't reach very deep, it did find the
solution in < 5 seconds (19ply). Also note that CM4000 didn't reach
great depths (or even find the solution).
Both are reasonably strong programs, so fast depth here isn't
a requirement for being a strong program.
HIARCS not only searched deep and fast - it didn't need to.
It found the solution at 2 ply!
(I spot checked 3,5,10,15 ply - it still had the solution)
This position doesn't require a lot of hash table-256K/320K was more
than ample.
(The "Anonymous" program is one of the betas I'm testing
that is still under wraps. Although it was fast,
it did take 21 ply to find the solution here. Interestingly enough, this
position is one of the sample endgame positions that come with this
program - they credited it to Lasker. This program slowed a bit in
the 30-ply range, but when I increased the hash to 5Mb or more, it
hit 40 ply in under 30 seconds).
HIARCS 6.0 Mac beta 256K hash: Solves in <1 second, hits 31 ply in 5 seconds
Anonymous 320K hash: Solves in <1 second, hits 31 ply in 5 seconds
=================================================================
Crafty 11.14d1 12M hash: Solves in 4.5 seconds, hit 25 ply at a minute
ChessMaster 4000 (?) hash: Unsolved at 1 minute , hit 21 ply at a minute
MacChess 3.0 32M hash: Unsolved at 1 minute , hit 20 ply at a minute
as Robert points out, reaching 31 ply rapidly in this position isn't
necessarily a good thing in itself. I'd still like to know how HIARCS
found the solution in 2 ply ... all other programs liked Kb2 for a long
time (actually HIARCS did like Kb2 initially, but only at ply 1).
fow...@netcom.com (Richard A. Fowell)
Tom King
In article <01bcbef6$448fd380$0100007f@king>, Johno
<jo...@chess.demon.co.uk> writes
>Hello there. I wonder if anyone would be so kind as to point out where I'm
>being stupid:
>
>At the moment I'm attempting to brush the cobwebs off my program
>(Woodpusher) before (hopefully) taking part in the next WMCC in Paris.
>
>While in Jakarta last year, Tom King demonstrated to me how quickly his
>program Francesca searched the following famous position (Kb1!).
>
>7| k . . . . . . .
>6| . . . p . . . .
>5| p . . P . p . .
>4| P . . P . P . .
>3| . . . . . . . .
>2| . . . . . . . .
>1| K . . . . . . . WHITE*
> +----------------
> a b c d e f g h
>
I've been using a two level hash table, very similar to "Two-Deep", as
described by D. Breuker et al. in an ICCA article. The idea behind the 2
level table is that you can have your cake and eat it, by using both the
"always replace" and "replace if new position has a better draft"
replacement schemes. I got the article from the Web ages ago, but I
think it appeared in the ICCA journal.
I've also found what you stated - for Fine #70, the "always replace"
scheme works well. But I think you'll find that for middle game
positions "always replace" is not as good as other schemes.
Francesca does indeed reach 30 ply very quickly on this position, but
although it plays the right move, Kb1!, it doesn't have the kind of
score I've seen on other programs. So it's possible I've got a hashing
bug here, too.
Hope to see you in Paris, John. Maybe there will be a Francesca -
Woodpusher game this time round. Not exactly clash of the titans, but it
could be fun!
--
Tom King
Tom King
In article <5vabtg$6...@juniper.cis.uab.edu>, Robert Hyatt
<hy...@crafty.cis.uab.edu> writes>: > Also, reaching ply=30 in fine #70 is not necessarily a good thing. That
>: > means that the search probably has better move ordering than you, but it
>: > might mean the opposite too. IE by ply 30, you can force a queen in that
>: > position, which will blow the search up badly. A program that gets to ply
>: > 25 should begin to see forced queens in some lines, which slows it down. If
>: > the queens are not seen, the search goes way faster. But only because it
>: > is not as "smart" as it might be... Testing will tell the tale...
>
>: you will hit a brick wall in ply 16-18.
>
>: If your hashing is working right, you will get a solution in ply 18-27,
>: depending upon which way the wind is blowing at the time.
I agree. I've seen solution depths for this problem vary from 18-24 ply,
depending on the hash replacement scheme, move ordering, evaluation,
extensions etc. etc.
>
>: It should take just a few seconds to get a solution, regardless.
>
>: The search might start to bog, with hashing that isn't broken, in the low
>: 30's, but of course machine speed and hash table size is a consideration.
>
>: bruce
>
>You should likely always find this by depth=23. I believe that is all that
>is needed actually see the win of at least a pawn. I've always solved it
>at 18 with Cray Blitz... and similar results with Crafty depending on the
>size of the hash... current version with asmall hash gets +3.9 at iteration
>20...
Francesca plays the right move at depth 21, but the score is only +2 or
something at depth 30. Something isn't right, probably. I think I have a
bug, or something weird is happening, like null moves creeping into the
search in a position where they shouldn't. Hmmm.. One to look at
sometime soon.
--
Tom King
John Stanback
Johno wrote:
>
> Hello there. I wonder if anyone would be so kind as to point out where I'm
> being stupid:
>
>
> After checking hash code distributions, hit ratios, etc, etc, without
> success I gave up. Before leaving the problem however, I did one final test
> to prove to myself that my re-hashing and depth based replacement was at
> least better than a simple: "hash to a TT position and just overwrite
> whatever was already there regardless of whether the existing information
> was the result of a deeper search" (B).
>
> Result: *MUCH* faster at simple endgames - at last Woodpusher could search
> to 30-ply in the above position. Plus - Very little slow down (if any) in
> middle-game test positions.
>
At one timeI used depth alone as my replacement strategy and Tony
Sherzer told me to try simply replacing a table entry with the current
position and sure enough, it was usually considerably faster at solving
problems. I think that this means that having "local" information
deeper in the tree is so helpful in producing cutoffs that it is more
important than getting less frequent cutoffs at shallower nodes and
having "better" scores due to storing nodes with bigger depths. My
current method is to generate 4 hash indexes and choose the one with the
least depth and replace it. Also, I won't replace positions in the
table if they are very near the root of the tree because they are
probably pretty important for move ordering (I want to at least retain
the best move after each of the ply 1 moves).
John
brucemo
Tom King wrote:
> I've been using a two level hash table, very similar to "Two-Deep", as
> described by D. Breuker et al. in an ICCA article. The idea behind the 2
> level table is that you can have your cake and eat it, by using both the
> "always replace" and "replace if new position has a better draft"
> replacement schemes. I got the article from the Web ages ago, but I
> think it appeared in the ICCA journal.
Dec 96, p. 230 :-)
> Francesca does indeed reach 30 ply very quickly on this position, but
> although it plays the right move, Kb1!, it doesn't have the kind of
> score I've seen on other programs. So it's possible I've got a hashing
> bug here, too.
You should see it taking the f5 pawn in the PV, regardless of the score.
> Hope to see you in Paris, John. Maybe there will be a Francesca -
> Woodpusher game this time round. Not exactly clash of the titans, but it
> could be fun!
If Francesca has improved as much from 96 to 97 as it did from 95 to 96, who
knows.
bruce
Tom King
In article <341B02...@seanet.com>, brucemo <bru...@seanet.com>
writes
>Tom King wrote:
>
>> I've been using a two level hash table, very similar to "Two-Deep", as
>> described by D. Breuker et al. in an ICCA article. The idea behind the 2
>> level table is that you can have your cake and eat it, by using both the
>> "always replace" and "replace if new position has a better draft"
>> replacement schemes. I got the article from the Web ages ago, but I
>> think it appeared in the ICCA journal.
>
>Dec 96, p. 230 :-)
>
>> Francesca does indeed reach 30 ply very quickly on this position, but
>> although it plays the right move, Kb1!, it doesn't have the kind of
>> score I've seen on other programs. So it's possible I've got a hashing
>> bug here, too.
>
>You should see it taking the f5 pawn in the PV, regardless of the score.
>
Yes, I get Kxf5 deep in the PV, so it looks like Francesca's seeing the
winning line. Good!
>> Hope to see you in Paris, John. Maybe there will be a Francesca -
>> Woodpusher game this time round. Not exactly clash of the titans, but it
>> could be fun!
>
>If Francesca has improved as much from 96 to 97 as it did from 95 to 96, who
>knows.
>
She's improved, but I can't determine by how much. The big improvement
from 95 to 96 was adding transposition tables, and improved move
ordering. This meant that when I turned up in Jakarta, my program was
searching depths of interest upto *10 TIMES* faster than the version of
the program that played in Paderborn. Unfortunately, I haven't squeezed
out another 10 fold improvement since Jakarta, more like 10% actually..
:-(
>bruce
Maybe see you in Paris.
--
Tom King
brucemo
Richard A. Fowell wrote:
> as Robert points out, reaching 31 ply rapidly in this position isn't
> necessarily a good thing in itself. I'd still like to know how HIARCS
> found the solution in 2 ply ... all other programs liked Kb2 for a long
> time (actually HIARCS did like Kb2 initially, but only at ply 1).
The odds of "solving" this this way are 1 in 3. I've never heard of a
program that preferred Kb1 at the start though, they all seem to want to
play Kb2. At what point did the score kick up, or show a PV that
included capture of the f5 pawn?
bruce
Peter Fendrich
There is a B.Sc thesis from 1978 by Kenneth Church at MIT, dealing with
positions like this.
The article is reprinted in "Computer Chess Compendium" by D Levy and is
called "Co-ordinate squares: A solution to many Chess Pawn Endgames".
The position is solved in a 'mathematical' way and the main theme is
to use "Distance Opposition" and the fact that all pawn are blocked.
I have seen another article about a program wich implemented the utility
and solved this position fast and easy. But I just can't remember
where i read about it. It doesn't seem to be ICCA Journal but maybee in
one of the "Advances in computer chess", I never searched there. I have
number 2, 4 and 5.
I'm sure HIARCS is using the same kind of algorithm.
Peter
Richard A. Fowell
Sorry for the confusion, but as I recently posted, HIARCS does NOT lock on
to the right solution at ply 2 and hang on to it. I had mistaken what the
output of HIARCS meant. HIARCS does select the right move at ply 3, but
at lower and higher ply searches, pickes the wrong move until ply 18 and
higher, and the eval doesn't indicate that it realizes how good the right
move is until ply 21.
Howver, I have spoken with a programmer who told me his program does
find the solution at ply 1 using the "coordinate square" type of approach.
fow...@netcom.com (Richard A. Fowell)
Dr A. N. Walker
Peter Fendrich wrote:
> I have seen another article about a program wich implemented the utility
> and solved this position fast and easy. But I just can't remember
> where i read about it. It doesn't seem to be ICCA Journal but maybee in
> one of the "Advances in computer chess", I never searched there. I have
> number 2, 4 and 5.
Perhaps "Interactive Solution of King and Pawn Endings", in
ACC5, North-Holland (1989), pp187-197, by yours truly? The program
described there can solve this position essentially instantly. But
there is less point these days, now that transposition tables with
room for hundreds of thousands of positions can do the same job for
a general-purpose program with only a modest time penalty.
--
Andy Walker, Maths Dept., Nott'm Univ., UK.
a...@maths.nott.ac.uk