Author: Robert Hyatt
Date: 17:28:17 05/30/00
Go up one level in this thread
On May 30, 2000 at 18:58:11, Tom Kerrigan wrote: >On May 30, 2000 at 18:01:31, Robert Hyatt wrote: > >>On May 30, 2000 at 17:57:30, Tom Kerrigan wrote: >> >>>On May 30, 2000 at 17:24:29, Gian-Carlo Pascutto wrote: >>> >>>>On May 30, 2000 at 14:54:28, Tom Kerrigan wrote: >>>> >>>>>I assume that when Bob says he expects a 25% hit rate, he means 25% of the >times that the hash table is probed, and not 25% of the nodes. >>>> >>>>Probably yes, so did I... >>>> >>>>>Which means that more work needs to be done to estimate the speedup from the >optimization that started this thread, i.e., the equation becomes: >>>>> >>>>>speedup = (% hit rate) * (% hash probes) * (% hash move cutoffs) * (% of time >>>>>spent doing move generation) >>>>> >>>>>Throwing in some extremely optimal numbers, the result is: >>>>> >>>>>0.5 * 0.2 * 0.5 * 0.2 = 1% >>>>> >>>>>So I think the best you can hope for is 1%. Seems like too much work for too >>>>>little, to me. >>>> >>>>If you do the same optimization for killer moves, how much can you hope for >>>>then ? >>>> >>>>This would be (killer move cutoffs) * (time doing move generation), right ? >>>> >>>>The second term is pretty high for me, so I'm interested to know what the >>>>first one will be. Anybody got any numbers on this ? >>>> >>>>-- >>>>GCP >>> >>>Depends on how you generate moves... >>> >>>Captures should be ordered higher than killers, so you have to generate >>>captures. For me, if you're generating captures, you might as well generate all >>>the moves while you're at it. >>> >>>Don't forget, there's also some overhead in bypassing move generation. You have >>>to keep track of which "stage" of move generation you're in. You have to make >>>sure you don't search the same move twice. And you have to test the legality of >>>hash and killer moves. Basically, this is overhead on an improvement that's >>>already small. Not worth it, in my opinion... >>> >>>-Tom >> >> >>It definitely works for me... > >What improvement does it give you? >-Tom That is complex. So how about this as a starting point: When I added killer moves in crafty, I already had the other stuff present (history, winning captures, hash move, etc.). I added killers and at the same time, started using the more complex "NextMove()" function I now use. Which behaves like this: 1. suggest hash move without a move generation, but a direct validation that the move is legal to avoid massive corruption. 2. suggest winning captures, and on the first winning capture, make a special case to cull the hash move, should it have been a capture. 3. suggest killer moves (2) before generating non-capture moves. I don't allow captures to become killers so there is no chance of duplication there, but I do make sure that the hash move also is not a killer move to avoid replication. 4. suggest up to four history moves. The first one is handled separately to screen the entire move list against moves already played so that they are not tried again. 5. rest of the moves in order in the list. this speeded me up by about 10%. When I looked at the size of the tree, it had not changed, implying killers were not making the search more efficient. What was happening was that I was avoiding move generations. If you have a specific experiment you want to suggest, I can cobble the code to do whatever you suggest and run the test...
This page took 0 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.