Author: Miguel A. Ballicora
Date: 10:06:46 12/18/00
Go up one level in this thread
This is a repost from some time ago.
>[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 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.