Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: move_generation + hash

Author: Tom Kerrigan

Date: 22:14:38 05/30/00

Go up one level in this thread


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



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.