Computer Chess Club Archives


Search

Terms

Messages

Subject: Hash table efficiency

Author: Miguel A. Ballicora

Date: 12:21:02 12/05/00


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
reg.games.chess.computer and their archives in www.dejanews.com 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?

Regards,
Miguel




This page took 0.13 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.