Computer Chess Club Archives




Subject: Re: Hash table efficiency

Author: Robert Hyatt

Date: 12:46:15 12/05/00

Go up one level in this thread

On December 05, 2000 at 15:21:02, Miguel A. Ballicora wrote:

>Before the question, a little background and an aknowledge.
>I am writing a program that plays chess mainly for fun. I started 3-4 years
>ago and I could not keep up but now I want to continue. I made it to work,
>and I can play a game against it (in fact, it plays much better
>than I would have predicted being so basic). I like to thank most of the
>people in this forum because the little I know I learned it from one chapter
>in the enciclopedia of A.I. and mainly from
> and their archives in 3-4 yrs ago.
>Most of the authors of those messages are writing here now.
>My program generates the moves using bitboards. It does what it is called
>"aspiration search" and iteration deepening,
>I sorts the move by something similar to MVV/LVA, it uses history tables, i t
>does not do "killers" yet. It has a transposition/refutation table, I use the
>store moved trying to make a cutoff first (>=beta). It has a rudimentary
>evaluation function that takes into account material, movility
>terms and rudimentary pawn structure (isolated and double pawns).
>I extend teh search when I found a check or a recapture. Also when
>It looks like there could be a perpetual. It detects draw repetition.
>I also implemented null move (I am using what I understand people call it R=2)
>The program is slow (30-40 knps in AMD K-2 400 mhz) and my "to do list"
>is huge. I am happy because it is "running" but I feel that most of
>the code should be updated, debugged, improved, modified, profiled, optimized
>etc. etc.
>(any suggestion about what my next step should be will be greatly appreciated)
>My plans now are to improve the search and the tree size.
>Too much of an introduction. My question is:
>How do you realize that your hash table is efficiently coded?
>from the initial position into ply 7 or 8 I have ~4-5% of the nodes
>hit in the hash table (position was found) but only ~10% of those hits (0.5%
>total) can be used to return a value (depth stored is >= than depth).
>Are these numbers reasonable?
>If I use two tables, one for overwriting always and the other to overwrite
>only if depth >= depth stored it does not change much.
>If the numbers are not reasonable, what would you try to change or debug?

Try this position:

/k/3p/p2P1p/P2P1P///K/ w

The solution is Kb1, and should take between 18 plies and maybe 21-22 plies
to find.  If you can't get to 18 instantly, your hashing is not working right.
For comparison, on a 550mhz single cpu machine, Crafty can reach depth 34 in
8.2 seconds...

This page took 0.06 seconds to execute

Last modified: Thu, 07 Jul 11 08:48:38 -0700

Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.