Author: Tiago Schawer
Date: 21:10:13 01/27/03
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 ?
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.
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 ?
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.
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.
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 ?
The only thing I implemented that seems to have a constant gain for
any position was Enhaced Tranposition Cutoff.
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.