Author: Ed Schröder
Date: 10:23:51 01/17/98
Go up one level in this thread
>Posted by Robert Hyatt on January 17, 1998 at 11:25:19: >In Reply to: Hash tables and data-cache, some programmer stuff... posted by >Ed Schröder on January 17, 1998 at 05:22:36: >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 think so. >>>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. It depends of course how you count NPS. I remember yours is different then mine. >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. Same answer. >>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. >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. You seem to have missed the point I was trying to make regarding hash tables. If you use a big hash table you will access (write or read) a wide area of memory. All of this is written to the data-cache with the risk of overwriting "more important" information (such as variables often used). Using a small hash table this risk is less. Result a higher NPS. The second point I was trying to make is the use of multiple hash tries. If you do just one probe you save the data-cache. If you do more (I do 3) this will lower the NPS because you (without realizing it) pollute the data-cache with information that is not very useful. Result a lower NPS because now in many cases information must come from normal memory and you know how slow that is :) Code-cache, data-cache it's really great but it makes programming life more difficult at least if you want to know all the why's. - Ed - >>>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.