Author: Dieter Buerssner
Date: 09:50:13 07/21/01
Go up one level in this thread
On July 21, 2001 at 06:07:56, Ulrich Tuerke wrote:
>On July 20, 2001 at 19:25:00, John Merlino wrote:
>>>>>> 8/k7/3p4/p2P1p2/P2P1P2/8/8/K7 w - - 0 1
[...]
>>Amazing what 1MB of [hash table] memory can do, eh?
Yes ...
>Far less is sufficient here. I remember very well, that the old DOS comet on a
>386 confined to a total max of 640 K memory (without DOS extender) solved this
>already in a few seconds in iteration 18. I think that the search tree is very
>small, accounting for transpositions.
Yes, this certainly must be the case.
>For positions of this kind (only kings and mainly blocked pawns), a hash table
>of size 64 K will already help a lot.
Out of curiosity, I tried this again. For Yace, even 600 hash table entries
(7200 bytes) help a lot in this position. Without any hash, Yace cannot find the
solution in one hour.
hash entr. depth Kb1 nodes score d. 24 nodes 1) score p/f 2)
600 17 30020 0.98 4.001M 2.40 0.470
1000 18 38457 0.92 1.440M 2.40 0.475
3000 19 38753 2.06 0.235M 2.62 0.872
3000000 18 32676 2.06 0.102M 2.74 0.920
1) nodes needed to finish the search at depth 24.
2) ratio between probes to the hash table, and found positions in the hash table
after the search at depth 24 finished.
This position is also interesting for an unrelated reason. After about 1 minute
(with say 30M hash), Yace gets a fail high (score >= ~3.8), that never comes
back, when it opens the window immediately to +infinity. When the window is
gradually opened (first adding 100 cp, then 500 cp to the previous beta),
however the search progresses quite nicely, and at depth 41 I get a score of
about 9.5.
Few other hints to Adam for solving hash problems. I think, when starting to
implement the hash tables, one really should not only check for collisions, by
checking the stored move, but just store the whole position in the hashtable,
possibly including castling rights, ep square and side to move. Sure, this will
be very inefficient in terms of time and memory usage, but it might be able to
pinpoint a problem early. For every hit while probing, the positions can be
compared.
When updating hash values incrementally (in makemove, unmakemove), I think, a
debugmode, that calculates the hash value also from scratch, can be very useful.
An idea of Stefan Knappe: Use the easiest position possible. Just 2 Ks on the
board. Here many more easy checking can be done. For this of course, some "not
enough mating material code" must be disabled. The maximum search depth should
be reached in no time. Essentially, any probe to the hash table should be
successful. You should have about 7000 entries used (I forgot the correct
number, but it is easy to calculate). That really all positions are seen by the
search, I had to disable beta-cutoff in the search. It seems, that the
alpha-beta search can prove, that the score is 0 without visiting all possible
positions otherwise. I cannot remember, if I also had to disable search tree
cutoffs due to repetition of position. But I remember, that I got the expected
number, and also, even without beta cutoffs, the maximum search depth was
reached very fast.
If problems arise here, a second hash table with 2*64*64 entries can be used,
that does not work with the Zobrist scheme, but is rather indexed by the squares
of the Ks and the side to move (much like EGTBs). The index could be calculated
by 128*square_of_black_king + 2*square_of_white_king + side_to_move
(Assuming your squares are from 0 to 63). Now both hash tables must have the
exact same info at any time.
One final note. In the above position, ep captures will never be possible. So,
also positions with ep possibilities should be tested.
Regards,
Dieter
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.