Author: Robert Hyatt
Date: 07:20:36 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 ? Think about it. "NEW" is a lot like a direct-mapped cache. "TWODEEP" is a lot like a 3-way set associative cache. It should be better in almost all cases (TWODEEP). > > 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. It works for most that try it, but that might not mean it works for _everybody_. You should dump the top few plies of the tree and make sure that you are actually using history moves as you think. > > 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 ? possibly, but not likely since the history idea is "local" as well.. > > 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... Yes, that is 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.