My "official" request to top engine programmers

[hgm]

I don't get Olivers point. Interfering with the replacement strategy is the whole purpose; you don't want entries of positions you will return to during the analysis replaced, as they normally would.

That the inability to declare anything useless fills up the hash table for 100% is just a fact of life.

[Rodolfo Leoni]

I don't get Olivers point. Interfering with the replacement strategy is the whole purpose; you don't want entries of positions you will return to during the analysis replaced, as they normally would.

That the inability to declare anything useless fills up the hash table for 100% is just a fact of life.

I don't see any practical difference about hashes. When trying to understand, it's my "translation" of both versions:

- Daniel's change

Go home
If it's sunny then go walking


- Oliver's patch

If it's sunny then
Go walking
Else
Go home
EndIf

[hgm]

So the patch is that generation8 (which seems to be the search number) is set to a fixed number (4) in the case of an analysis search. I don't understand why this is helpful. If it is to age any TT content left over from a previous search that was not an analysis search, it doesn't seem to do the job: how would you know that generation8 was not 4 to begin with? I agree it could be slightly better to only suppress incrementing the search number if both the current and the previous search where analysis. Or increment it after a non-analysis search, rather than before. But this seems a moot point; mixing analysis and other tasks is not how people typically use engines.

Also note that Stockfish seems to have a very simplistic replacement strategy: it just deducts the age (times a factor) from the depth before replacing the entry with the lowest of these 'corrected depths'. So incrementing the search number is no guarantee at all that the 'empty' part of the hash table (i.e. 100% - hashfull) is not full of stuff that is difficult to replace (because even after the age deduction the depth is still high). It just makes it somewhat easier to replace that.

It seems better to just rely on the user to press 'Clear Hash' before starting a new analysis. Or not use the engine for anything else before starting the analysis. (Which is what people usually do anyway.)

[Rodolfo Leoni]

Are we both talking about this one from Jeremy Bernstein?

http://www.open-chess.org/viewtopic.php?f=7&t=2663

The download-link given in that posting even works still

I gave a deeper look at this build. A jewel! I report Jeremy Bernstein's "About PH" readme file. I think it can inspire.

--------------------------------------------------------------------------------------
About Persistent Hash (Stockfish-DD-PA_GTB Release Notes)
============================================================

INTRODUCTION:

The basic idea of Persistent Hash is that (some) engine analysis is retained from session to session, rather than being dumped every time the program is restarted. The version of Stockfish in your hot grubby little hands has a fairly simple (but effective) implementation of persistent hash. "Interesting" positions are written to a disk file (called 'stockfish.hsh' by default, referred to as PH file below). Any positions in this file are loaded into the hash at the start of a new search. This mechanism allows previous analysis to influence present analysis without over-manipulating the way that Stockfish deals with hash entries (and the decision to preserve or overwrite them). New positions are written to the PH file between iteration depths (so if you are analyzing at depth 29, all interesting positions from the depth 28 search are in the file, but none of your depth 29 analysis).

HOW TO USE IT:

Please Enable Persistent Hash (see below, UCI Options) and use the engine as normal. You probably don't want Persistent Hash enabled during games at very fast time controls, since the reading and writing of takes a little, but measurable amount of time.

KNOWN ISSUES:

The contents of the PH file are loaded into the hash table at search start. When the PH file is very large, this can take a moment and the engine will appear to stop responding (although usually this takes less than a second, even with PH files of many MB). I haven't really checked with HUGE PH files. Anyway, it's kind of unavoidable and known.

RELEASE NOTES:

vDD
- update to the Don Dailey memorial release of the Stockfish upstream master branch

v4-002
- update to the tip of the Stockfish upstream master branch

v4-001
- update to the tip of the Stockfish upstream master branch (now at v4)

v3-008
- fix a regression in v3-007 with Persistent Hash

v3-007
- update to the tip of the Stockfish upstream master branch

v3-006
- Persistent Hash:
- reduced record size
- rewritten to use new database format (Kyoto Cabinet), with automatic translation from old format (QDBM)
- added new "importepd" feature, see below
- added new "Persistent Hash As Book Depth" UCI option, see below
- pruning the PH file creates/appends to a "stockfish_pruned.hsh" backup of the discarded records
- further 3x repetition checking improvements
- update to the tip of the Stockfish upstream master branch

v3-005 (changes since v004):
- Persistent Hash implementation
- non-main threads can publish their currmovenumber
- 3x repetition is checked all the time
- update to the tip of the Stockfish upstream master branch

FURTHER INFO:

What makes a position interesting?
- the score is exact, not a fail-high or fail-low
- the search depth is equal or above a certain value (UCI option "Persistent Hash Depth"), 24 being the default
- the score is not the result of an Endgame Tablebase hit
- the score is still in the hash table at the end of the present iteration

These criteria are fairly straightforward, although the last one is admittedly potentially problematic, since important information might get lost. Practically, I don't think it matters (PH is just a hint to the search, and none of the information in the PH file can't be reconstructed via a normal search) -- if the score is that important and has a high enough depth, it will still be there.

Additionally, the Persistent Hash record distinguishes from Root node analysis and non-Root PV node analysis. In general, non-Root node analysis cannot overwrite that of Root nodes. Root node analysis will overwrite non-Root node analysis at the same depth or higher. This is an internal detail, but is relevant for the new "Persistent Hash As Book Depth" UCI option.

COMMAND LINE OPTIONS:
- "importepd": typing 'importepd <filename.epd>' will attempt to import positions and analysis from EPD files. The EPD files must contain the following fields for each record: 'bm' (best move), 'ce' (centipawn evaluation) and 'acd' (analysis count depth). A final argument of 'noce' can be used to indicate that 'ce' fields may not be present -- if they are missing for a particular record, the record will be scored "Wins" for the side to move. EPD moves are always imported as Root node analysis.

UCI OPTIONS:

As mentioned above, there are a few UCI options to control the PH operation.

- "Use Persistent Hash": set this to true to enable the PH feature (default: false)
- "Persistent Hash File": this defaults to the file "stockfish.hsh" in the engine's working directory. You can change the name or set an absolute path to a different location, such as on an SSD if you like.
- "Clear Persistent Hash": deletes _all_ of the analysis in the PH file.
- "Persistent Hash Depth": the minimum depth at which analysis is stored in the PH file. (default: 24). The default was determined empirically to balance usefulness with file size. The lower the depth, the larger the file.
- "Persistent Hash Size": desired maximum size of the PH file when Pruning.
- "Prune Persistent Hash": starting at the current Persistent Hash Depth, iterate through the PH file and delete all records at that depth level and below. If the file is still above the "Persistent Hash Size", increase the depth and repeat until the file is either below the requested size or no further records can be found to delete.
- "Persistent Hash Merge File": the file to merge _from_ when "Merge Persistent Hash" is used. This defaults to the file "stockfish_merge.hsh" in the engine's working directory. You can change the name or set an absolute path to a different location.
- "Merge Persistent Hash": if the file specified in "Persistent Hash Merge File" is found and vallid, any entries in the file which are a) at the "Persistent Hash Depth" or higher and b) are _deeper_ than existing entries in your current PH file (same depth is ignored) will be merged into your current PH file.
- "Persistent Hash As Book Depth": Root node records in the PH file at this depth or higher will be used as book moves (if "Use Persistent Hash" is enabled, of course). Non-Root node records are not eligible as book moves. The default is 0 (disabled).

FILE SIZE:

You may have noticed that there is a file size option. This option is not used at runtime, but rather in conjunction with the "Prune Persistent Hash" button to manually keep your PH file below a desired size. When writing, there is currently no way to limit the file size of the PH file (for tech-interested, the file is in Kyoto Cabinet format, an open-source fast, small database implementation [http://fallabs.com/kyotocabinet/]). It will basically grow to fill your hard drive, if you let it, albeit very slowly. For now, don't worry about it too much. Let's see who gets to 1GB first -- the entries are very compact (8 byte key + 11 bytes data + indexing entries) and shouldn't explode too quickly. Maybe it's worth calling "Prune" when closing Stockfish, but I've left that out for now.

[corres]

After Jeremy joined to Komodo team he ceased his project.
I think if persistent hash were a very good idea Komodo team would build into Komodo yet.

[peter]

Komodo has the UCI- option Save Hash to File. Cause that didn't work as expectd in Fritz- GUI I had some emails with Mark Lefler about komodo's way of hash- handling last year.
As far as I remember and understood, a kind of persistent hash as Rodolfo would like to have is just the opposite of Mark's and komodo's way of dealing with hash- renewing and hash- aging.

"Keep Hash Tables" as it is called by Stefan Meyer- Kahlen for his Shredder, is an option to be switched off too, so I think, even Stefan doesn't see it without any disadvantage neither at some circumstances.

A learning file, that Shredder had up to version 12 always (Houdini too till version 4, Hiarcs as far as I know as the only one having that still as for the last version too), is something very special of its own, so I was glad to have that with SF PA- GTB.

Maybe somebody yet would try to continue that again for SF or any other leading engine, I guess it would be aprreciated not only by Rodolfo and me.

[Rodolfo Leoni]

..... is something very special of its own, so I was glad to have that with SF PA- GTB.

Maybe somebody yet would try to continue that again for SF or any other leading engine, I guess it would be aprreciated not only by Rodolfo and me.

Stockfish PA GTB system is a state of the art one. Almost perfect. As for the pruning hash option it would be nice to introduce a tuneable score limit (nobody wants +700 cp positions...) and a tuneable material limit (PHs are almost useless on ending positions, but the user should have the opportunity to tune this limit).

About someone who could continue this work, it would be enough if these procedures are applied on official Stockfish versions, when they are released. To follow stockfish developements would mean too much work, I guess. I'd be really happy to see a Stockfish 8 with such feature, and a Stockfish 9 when it'll be released. And Peter is right, not only we, but millions of chess players (if only they know it exists).

[BeyondCritics]

There is much confusion created now, partly because of a mistake from me. I try to cleanup:

1) The original patch leaves "generation8" as it is in analysis mode. Since it starts out as zero, it stays zero, if the user switches immediately to analysis mode after starting the engine. Unfortunately the method "hashfull" now wrongly deduces, that the hash table is full upfront. This is a minor issue, but still an issue. I see the difference clearly, when i load the engines into scidb.

2) In preparing my post, i studied this code (https://github.com/official-stockfish/S ... tt.cpp#L95) closely and in the process, i got confused. Maybe i forgot the first loop in this method. My apologies for that.
You get only to these loop, if all cluster entries are used. In this case, the age difference is identical under both solutions and in both cases the entry with the lowest depth is replaced always.

3) I hinted, that the first patch introduced a new, never seen before use case, namely that "generation8==0" holds during search. This makes the code a little bit less maintainable. I still defend that point.

Due to 1) and 3), i prefer my patch. My apologies for 2).

Am i allowed to peck back?

Also note that Stockfish seems to have a very simplistic replacement strategy: it just deducts the age (times a factor) from the depth before replacing the entry with the lowest of these 'corrected depths'.

Code: Select all

 // Due to our packed storage format for generation and its cyclic
      // nature we add 259 (256 is the modulus plus 3 to keep the lowest
      // two bound bits from affecting the result) to calculate the entry
      // age correctly even after generation8 overflows into the next cycle.
      if (  replace->depth8 - ((259 + generation8 - replace->genBound8) & 0xFC) * 2
          >   tte[i].depth8 - ((259 + generation8 -   tte[i].genBound8) & 0xFC) * 2)
          replace = &tte[i];

Code: Select all

  uint8_t generation8;

Note that generation8 is unsigned (and depth8, genBound8 have conversion rank not greater than int). Therefore in any arithmetic subexpression above, any argument gets finally promoted/converted to "unsigned int". That means, that if one of the subtractions of scaled age from depth "underflows", you might get unexpected results. Specifically:
a) If for both entries depth >= 8*age, then keep the entry x, where x.depth-8*x.age is biggest.
b) If for exactly one entry x, x.depth <8*x.age, keep always this entry.
c) If for both entries depth < 8*age, prefer the entry x, where 8*x.age-x.depth is smallest.

I feel this is to complicated to be right. But the funny thing is, this is very well tested. It must get something right, that is needed and that the more simpler version misses.

[corres]

You are right, Stockfish-TCEC6-PA-GTB is a good program. It is only ~100 Elo weaker than Stockfish 8. I think its code is sophisticated and its compilation is rather complicated in particular for Windows. This is the main reason that it has no man to continue it. Moreover relatively a few peoples use it - from open-chess.org were only about 4000 downloading from 2014...

[hgm]

If both underflow, it would not change the order. (Both get 4G added by the underflow.) But when some of the entries underflow, and others don't, those underflowing (i.e. having the lowest depth) will be protected.

This seems totally wrong. Are you sure it is tested at all? I thought Stockfish was tested only under "no-replacement" conditions, so that it basically doesn't matter how crappy the replacement algorithm is.

After your explanation I understand the problem of the hashfull of a table with all uninitialized entries. The probing code is rather fishy too. Why exclude signature = 0 for being accepted as a hit? There should many positions that have this, and they could never be found back in the table. Or does Stockfish make an attempt to keep the upper 16 bits of the key non-zero? In any case it seems a waste of time to do this extra test. If the signature you are looking for is non-zero, the second test would reject empty entries. If you are looking for a signature zero you can either stop looking without actually probing, or just accept empty entries as hits. (These will also have d=0, and possibly unusable bound type, so the search cannot use them anyway. And after some time they are no longer around. Only 1 in 64K probes will need signature = 0 anyway, while the probability for false hits with other signatures after the table is full is also 1 in 2^16.)