Author: Robert Hyatt
Date: 21:25:29 05/29/00
Go up one level in this thread
On May 28, 2000 at 19:44:05, Tom Kerrigan wrote:
>On May 28, 2000 at 10:02:05, Georg v. Zimmermann wrote:
>
>>Hi,
>>
>>today I realized that the program I'm toying around with does in its search()
>>
>>1.) generate all moves
>>2.) order the moves and put hash move if available to 1st position
>>3.) do the recursive search
>>
>>I thought that I could increase its speed by testing the hash move first and
>>only if not >= beta do the move generation and the rest.
>>
>>From my tests it shows that it sticks with the hash-move about 50% of the time.
>>Should this number be higher ?
>>
>>I was very dissapointed when I didn't notice any speedup after my changes. What
>>speedup should I expect ? Something like 0.5-1% or more like 1ply ?
>
>You can forget about 1 ply. Your program needs to go ~4x faster for it to search
>1 ply deeper. Which means that your move generator must be taking ~400% of the
>execution time, which is clearly impossible.
His effective branching factor might be different than yours. Mine is at about
3.0... I have seen some higher and some a bit lower.
>
>Here's what you have to consider when calculating your speedup:
>
>1) How many moves you get from the hash table. I just ran some random position
>and got a 1.75% "hit rate."
That sounds horribly low. I'd be concerned of something serious if it drops
below 10%. I just ran the 24 kopec problems for 30 secs each, on my PII/400
notebook, and got the following: The first number is overall hash table hits
(exact signature matches, whether the draft was sufficient or not doesn't
matter). Many of those are just hits that do nothing other than provide a good
move to search first. Most are like this in fact.
hashing-> trans/ref=39% pawn=97% used=78%
hashing-> trans/ref=42% pawn=97% used=1%
hashing-> trans/ref=39% pawn=98% used=28%
hashing-> trans/ref=63% pawn=95% used=6%
hashing-> trans/ref=52% pawn=97% used=1%
hashing-> trans/ref=39% pawn=99% used=61%
hashing-> trans/ref=39% pawn=98% used=14%
hashing-> trans/ref=29% pawn=97% used=70%
hashing-> trans/ref=36% pawn=95% used=1%
hashing-> trans/ref=34% pawn=97% used=60%
hashing-> trans/ref=37% pawn=96% used=7%
hashing-> trans/ref=24% pawn=97% used=9%
hashing-> trans/ref=40% pawn=98% used=5%
hashing-> trans/ref=27% pawn=97% used=67%
hashing-> trans/ref=42% pawn=98% used=60%
I deleted a couple as they are "in crafty's opening book" and get solved
with no searching.
If you want to compare hashing over some well-known positions, I'll post
data from my code. I generally expect to see 25% and up... Which means that
in say 30% of the positions, I find a position match, but in these mostly
middlegame positions, the "EXACT" hits are rare. So most of these end up as a
position where the hash move likely will be the best move, and the time saved
by avoiding the move generation can add up quickly. I would estimate this at
10%. At least it was the last time I looked. And my move generator is nowhere
near 20% of the total search time. GenerateCaptures() is the most common piece
of my code and over many position tests, it takes about 7% of overall search
time.
>
>2) How many times your optimization will be effective. You said 50%.
This is probably the right number. Fail-high positions will like the hash
move. But for every fail high position, there is a following fail-low position
and it won't be helped by the hash move at all..
>
>3) How much time your move generator takes. Let's just say 20%.
>
>So, I bet your speedup is somewhere around 0.175%, which is probably why you
>didn't notice it.
>
>-Tom
This page took 0.01 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.