Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: Hash table efficiency (some tests and results)

Author: Miguel A. Ballicora

Date: 20:02:00 12/10/00

Go up one level in this thread


On December 06, 2000 at 10:34:59, Robert Hyatt wrote:


>[D]8/k7/3p4/p2P1p2/P2P1P2/8/8/K7 w - - 0 1

When I ran FINE70 problem, as suggested by R.Hyatt to
check the hash tables, I found that my program took too
long to find the solution (Kb1!!).
Apparently there was no other bug in the "code", but the
problem was mainly a combination of two things that might
interest some other beginner like meLet :
1) the evaluation function I used was only material.
  I thought that doing this I would analyze only the properties
  of the hashing system. I was wrong!
2) I use a very simple hash table that overwrites an entry if
   new draft > old draft.

I did the following tests combining different things.
I tried two hashing systems with three
different evaluations functions.

Evaluation 1: only a bonus for Pa5 or Pc5 captured so
              I realized when the program sees is winning
           2: (1) + bonus if the king is in the 2nd rank rather
              than the first, better in the third, fourth and
              so on. It will drive the king towards the opponent field.
           3: (1) + a bonus if the king is closer to an opponent pawn
              I hard coded it for this particular example.
              i. e. b5 is -1, c4 is -2, b3, c3 d3 are -3 etc.
              It will drive the king towards the pawns.

Hashing    1. Single table, overwritten when a new entry has a draft higher
              than the one stored
           2. Two tables (same size). First one is overwritten in the same
              way as the previous one. If it cannot overwrite, it is always
              stored in the second one.
              This procedure was suggested by Ken Thompson according to a
              message by B. Moreland 3 years ago in usenet, thanks! (I am glad
              that I printed and kept quite a few messages since Dejanews is
              not working on very old articles now).I think that Crafty uses
              something similar according to some messages I read.

These are the results

 Table    Evaluation   Ply to see   Nodes needed to    Hash efficiency
(entries)  function     Kb1 wins    find Kb1 wins       transp. hits (%)

  2M      1 (material)    22         379 knodes            38.5
  2M      2 (rank)        22         237                   46.3
  2M      3 (closeness)   20         458                   30.0

 2x1M     1 (material)    24          56 knodes            47.9
 2x1M     2 (row)         25          80                   55.5
 2x1M     3 (closeness)   21          45                   61.5

  2k      1 (material)    22        2302 knodes            20.6
  2k      2 (rank)        22         496                   32.8
  2k      3 (closeness)   20         321                   27.6

 2x1k     1 (material)    24          64 knodes            50.8
 2x1k     2 (row)         25          67                   55.8
 2x1k     3 (closeness)   21          96                   55.3


It is obvious that that the two-table (2x) system is clearly
much better than the single one, particularly when the table size
is small (2k or 2x1k entries). The evaluation function does not
seem to be too critical, except when the hashing is bad (single table,
small size). In that case, a good evaluation function seems to
"drive" the search. The best search is when the size is bigger,
table is split, and the best evaluation is used. That gives, the fewest
nodes and of course the best % in table hits (hits that find
a transposition with enough depth/ attempts ).

Suprinsingly, the number of plies needed to find the solution
don't correlate with all this!
Why? I think that the explanation is that the table is
also filled with "wrong data" from the repetition draw values.
Somehow, this need to be overwritten or another path has to be found.
Is that possible?

For instance, using evaluation (1) and a single table, the number of nodes
needed to find the solution depends on the size of the table in the following
manner:
Size     Plies    nodes (x1000)
0.5k      20       1900
1k        20        592
2k        21 !     2300 !
4k        21       2280
8k        21        688
16k       21        519
32k       22 !      594 !
64k       22        550
128k      22        521
256k      22        521
512k      22        379
1M        22        379
2M        22        379

Has anybody experienced something similar? Any comments?

Regards,
Miguel






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