Computer Chess Club Archives




Subject: Re: History Heuristic on its own

Author: Robert Hyatt

Date: 13:45:55 01/20/99

Go up one level in this thread

On January 20, 1999 at 11:47:38, Will Singleton wrote:

>On January 20, 1999 at 10:17:40, Robert Hyatt wrote:
>>On January 19, 1999 at 22:38:30, Will Singleton wrote:
>>>On January 16, 1999 at 23:19:04, Chris Moreton wrote:
>>>>Cutoffs in the full width triggers a history entry which adds a value which is 2
>>>>to power Depth to the from-to array.  When a history entry reaches a certain
>>>>value, all the values are halved.
>>>Here's the results for my program on your HH question.  Sorry it took so long,
>>>but I had to get a block of time to do it.
>>>Amateur 0.9g
>>>PVS Search - 7 ply
>>>Results are average nodes from a small test suite.
>>>No enhancements                  23,000,000
>>>HH only                           9,000,000
>>>TT only                           6,700,000
>>>HH + TT                           3,000,000
>>>HH + TT + killers                 2,150,000
>>>HH + TT + killers + caps          1,860,000
>>>HH + TT + killers + caps + null     635,000
>>>all except HH                     1,100,000
>>>all except TT                     1,700,000
>>>So it appears that the HH is significant both by itself, and in combination with
>>>the others.  This is PVS as opposed to plain AB, but I don't think that should
>>>make a lot of difference.
>>>The fact that you don't get a reduction when using HH by itself is troublesome.
>>>I would guess that you might have a bug somewhere.  Try looking at the move list
>>>in the debugger for various positions, seeing if it looks reasonable.  You also
>>>might try not storing HH values when depth <= 2.  And using depth * 2 might be
>>>faster than 2 to the depth.
>>>Good luck.
>>Just a note that using _all_ of those should not continuously drop your
>>node count.  Remember that at some nodes we search _all_ moves and ordering
>>is worthless there.  And at other nodes we want to fail high after 1 move.
>>I added killers, not because they made the tree smaller (since they are just
>>a special case of history) but because I can try those two non-capture moves
>>before generating any non-capture moves (which saves time, not nodes).
>>I would suspect that you may still have some move ordering issues to clean up
>>based on your numbers, because I can take out either history or killer and
>>my node count doesn't shoot way up (unless I remove both)...
>Yes, I'm sure I have some ordering issues to work out.  It's actually a miracle
>it works at all.  And the above numbers were from a small sample.
>I use killers a little differently than others.  I try them after good caps, and
>maintain a list of 4 best.  So it's rather more like a mini-HH than killers.

I do this:

hash move
winning captures
even exchanges
killer moves (2)
history moves (no more than 4)
remaining moves in order generated.

adding killers didn't help my tree size after I already had history moves,
but it sped me up by maybe 10% since I don't generate moves before trying them,
and if they cause a cutoff, I avoid that work totally...

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.