Author: Robert Hyatt
Date: 07:52:41 05/31/00
Go up one level in this thread
On May 31, 2000 at 01:14:38, Tom Kerrigan wrote: >On May 30, 2000 at 21:50:19, Robert Hyatt wrote: > >>On May 30, 2000 at 20:45:17, Tom Kerrigan wrote: >> >>>On May 30, 2000 at 20:28:17, Robert Hyatt wrote: >>> >>>>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... >>> >>>Can you just generate all the moves at the same time and then order them? >>>-Tom >> >> >>Yes. Although I don't "order" anything except for winning captures. No need >>to order the others. Are you asking me to run with a "generate all moves first" >>change to see how it effects speed? > >Yes, that's the question at hand. >-Tom I am trying to understand what the question is supposed to be. It is clearly better to generate captures and non-captures separately, because in the q-search, non-captures are not needed. For captures, I generate and sort. For non-captures I do no sorting at all. It would seem we have to reach some sort of common point before I can write something that compares to whatever you are doing...
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.