Author: Vincent Diepeveen
Date: 05:08:59 01/28/03
Go up one level in this thread
On January 28, 2003 at 00:10:13, Tiago Schawer wrote:
> I had a hard time fixing my transposition table's bugs, after
>that I read a few articles about them and I have lots of questions,
> Can anybody help ?
>
> I used NEW, which always replace entries on collision.
> And TWODEEP, using two tables, one table using replace if deeper or
>equal (or timestamped) and then moving the replaced entry to the second table
>if "true" or just writing the new entry on the second table if "false".
> I didn't use Minimal Windows. Just AlphaBeta. It's a checkers(brazilian)
>program, and the evaluation function used by me is *really* simple.
>
> 1) Is TWODEEP supposed to always(if not, how often ?) outperform NEW
>for any position, or do you have to run lots of tests and calculate the average
>gain to realize the difference between them ?
always replace.
but there is of course better ways to do it.
If you have a machine with DDR ram for example you will get each cache
line 64 bytes at the same time anyway. So you can also use a big
hashtables for example size = 2^n + 3
And then calculate index with hashkey&(size-4)
Now you can do a simple for loop:
for ( all entries )
determine_which_entry has smallest depth_replace;
where depth_replace is for example numberofmovesmade+depthleft
Then replace the entry with the smallest depth_replace *always*.
> 2) The History Heuristic didn't seem to help much, sometimes the results
>seemed a bit random...does it proves it's efficiency when you calculate the
>average gain ? When I turned off the Transposition Table the gains credited to
>HH were huge, but the overall result was worst, as expected. According to
>J.Schaeffer the HH is better for checkers than chess. I used only the two best
>rated moves by the HH.
HH doesn't work for my draughts program (10x10 international checkers) either.
Not in a single version of it, it worked.
It does work in some chessprograms which have a very unbalanced tree or
a very bad move ordering. Evaluation in itself is no major issue.
For my chessprogram DIEP it doesn't work either simply.
Only a local killermove works. Even the profit of a global killermove for
a realdepth x is very unsure.
> 3) If the History Heuristic is used to order moves, could this cause
>"cache misses" in the Table when using NEW, since it profits from locality ?
HH works global, not local.
> 4) I'm using two different schemes for a brazilian checkers program,
>
> A) NEW
> B) TWODEEP + History Heuristic + timestamping
>
> Using timestamping, 1 bit, but not changing the bit phisically
>on the table entries, just setting and resetting a global boolean and using
>it when storing and retrieving. The bool value was switched every turn.
well 1 bit is way too little unless your hashtable is that small that
everything gets overwritten. With a 4 probe system you should use like
16 bytes each entry and like 10 bits to replace in case people go analyse
for quite some time. I manage usually against 1000 moves to get analyzed.
> In autoplay, both systems were used for the same positions, runnign
>only in white's turn.
> I used 2^18 entries for NEW, and 2 tables with 2^17 entries for TWODEEP.
> The search depth is usually around 11 (opening, middlegame),
>and 17 (endgame) in a Pentium 200 Mhz.
> Other enhancements were disabled.
that's very little entries but i guess it is the hardware that is the problem
here.
note that SDRAM at P5-200 (MMX) is having 32 bytes each cache line but
you can go run it there at 4 probes anyway better.
4 probes always better than 2.
> Some quick tests, showed that B is usually better than A (around 15% smaller
>tree, sometimes 30% sometimes 0%). But in endgames, the searches got deeper, and
>A would reach 1 or 2 plies depper than B. Strange...
>
> Does the results look ok, am I in trouble ? Should I design better
>tests, or fix bugs ?
fixing bugs always good. idem testing ;)
> The only thing I implemented that seems to have a constant gain for
>any position was Enhaced Tranposition Cutoff.
Yes i use that too in my draughts program. It doesn't work for DIEP anymore.
Dunno why.
>
> Thanks in advance.
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.