Author: Robert Hyatt
Date: 08:25:19 01/17/98
Go up one level in this thread
On January 17, 1998 at 05:22:36, Ed Schröder wrote: >>Posted by Bruce Moreland on January 17, 1998 at 03:25:31: > >>In Reply to: Re: Computer(CPU)benchmark for chessprograms posted by Ed >>Schröder on January 17, 1998 at 02:21:54: > >>On January 17, 1998 at 02:21:54, Ed Schröder wrote: > >>>Every programmer has his own view how to program the hash table. Typical >>>for Rebel is that it stores and uses the q-search results in the hash >>>table (most programs don't do that, true?). Another typical Rebel hash >>>table behavior is that it doesn't store positions in the hash table that >>>have no "best move". The latter speed up Rebel a little. this I don't quite follow. *every* node that "fails low" fits into this category, because if you search every node and each move fails low, you have no idea which move was best. If you don't store this, then when you reach this same position again, at the same depth, you get to search it again. I will look this up, find that it failed low before, and simply fail low here with no searching. Are we talking the same kind of "no best move"??? > >>I don't do this q-search thing because our searches are probably a lot >>different. I wouldn't have much use for it the way I do things. > >>But I haven't spent much time trying to figure out how to make the most >>efficient use of hash memory. I use the Thompson dual-table scheme >>described numerous places, which has always worked fine for me. > >>I like the idea of not storing elements that don't have a "best" move >>attached. You lose the ability to fail low on a node based upon the >>value in the hash table, but a little bit of statistical collection >>seems to indicate that this is pretty rare. I just ran a couple of tests. You should run this on fine #70, which is the most friendly of all positions to the hash table. Eliminating the fail low return slows it terribly. IE I got to depth=27 in 3 seconds normally, but removing the fail low let me reach depth 24 in 12 seconds. > >Ok, some programmer stuff... > >The reason for the "little" speedup in Rebel (leaving entries with no >best-move out the hash table) is that it saves entries in the Pc >"data-cache". Of course this may not work in every program but I also >can imagine you can speedup a chess program with 5-15% for free. And >there is no risk. > >A few years ago I re-wrote a very time consuming part in Rebel's >evaluation function. Instead of massive code I pre-calculated all >possibilities and stored the results in 4 Mb memory. Then a simple >table loop replaced all the massive code. > >I expected a huge speedup of 30-35% but it didn't happen. >In fact it was a little bit slower. > >The reason is the limited Pc data cache. I assume lots of useful >data (normally kept) now simply disappeared in the Pc data-cache >due to all the extensive 4 Mb table lookup's. I have no other >explanation. > >So besides all the "pro's" and "contra's" about different hash table >approaches I think one should also take into account the machine's >data-cache behavior too for a final judgement. > >If I test Rebel with 512 kb hash and the same position with 28 Mb hash >then the "average NPS" with 512 Kb is obvious higher. It's not because >less code has to be examined by the program but because of important >data loss in the Pc data-cache. there is another important explanation for going faster. As you add hash entries, you improve the ability for information to flow across different parts of the tree. Specifically, as the hash table becomes bigger, it produces more hits, and a hash hit will lower your NPS because you update the board, recursively call search, and invest all that work only to return with a score or bound immediately. If you didn't get a hit, you would search after investing in the preliminary setup work, and see your NPS go up a little. I've noticed this behavior for years, even in Cray Blitz. And the Cray XMP/YMP/C90 don't have *any* sort of data cache at all. So it couldn't be a cache issue on those machines. > >End of programmer stuff... > >Of course using 28 Mb hash will give much faster results then using >a hash table of 512 Kb but that's another story. > >- Ed - > even more important at times is it gives much better *results*. IE if you try fine #70, it is *impossible* to solve with a 19 ply search, because there is no way to win a pawn within 19 plies. But the hash table lets info flow from searches where the opponent plays badly, to searches where the opponent plays well, and you get the correct result plies quicker. I don't have the book, but I believe this position is either 23 or 26 plies deep, based on the analysis Monty Newborn did in his king and pawn - only endgame program written many years ago. So you really can't compare NPS with big/little hash tables, you can't compare time-to-depth either. Because most of the time you get deeper quicker, but at times you get deeper slower, because you are getting a better result at the same depth you got without the hash table. > > >>For those who don't know what you mean, the idea here is that a hash >>entry is good for two things: > >>1) Cutting off based upon the bound or score contained in it. >>2) Remembering the best move in the position so you can search it first >>next iteration. > >>This second reason is the most important one in almost every case. A >>lot of times, you are not going to *have* a best move to store in your >>hash element, since you fail low when you search this node. So in these >>cases, you get less benefit from hashing this node, and you might get >>more from leaving what was there before alone. I don't agree here. The best move is important for ordering. But that is a secondary effect. The fact that you failed low in an identical position at the same depth eliminates a lot more work than simply trying the best move first will. Because when you flip from one iteration to the next, the best move won't help when you are at a node that is supposed to fail low. But not searching below that point can certainly help. > >>Thompson's dual table method would make this optimization a little hard, >>since you write into your table in order to remember repetitions, but >>perhaps it can be salvaged. I don't use the hash table for repetitions. I have a simple repetition list that I search. Since Crafty implements the 50-move rule, this counter tells you how far you have to go back in the repetition list. I tried the hash approach, but it was no faster for me. And with internal iterative deepening (what I do when I search a non-fail-low position and there is no hash table entry, such as what happens after the root move fails high and has to be re-searched) the "open position" idea to detect draws became more complicated. > >>>The story: take 40 chess programs and you will notice 40 different hash >>>table behaviors. > >>No kidding. > >>bruce
This page took 0.01 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.