codefool / dreid Goto Github PK

Refactor DHT to handle hash collisions.

DHT is a large unordered set container, but we need to convert it into a DQ so that it can be fed into CG for the next iteration. The purpose of DHT is so we can quickly identify duplicates, and the purpose of the DQ is to quickly process an unbounded queue. DHT checks for duplicates because its structure lends itself to a quick-ish check. DQ allows duplicates but in the CG processing this is avoided as all input to a DQ is first stored in a DHT. The output of CG is a DHT, BUT to make it as fresh input it must be converted into a DQ.

Zobrist collisions appear to happen not too often, currently 186 for 27682048. When a collision happens - flag the primary position record with that hash that there is a conflict, and then write that conflicting position in an adjacency file. When searching if a given position exists, and the conflict count is not zero, then the adjacency list is also checked for possible collisions.

Once these are available in the Position class, update the Zobrist hasher to use them.

Depends on CG-4

We can shorten some of the class names, etc. if we encapsulate all our "special" functions inside a dried namespace.

constants.h has morphed in a general header, and the name should reflect that. On that note, the chessgen project needs to be renamed to something more permanent.

This is to support Zobrist hashing. Rather than key off the entire packed position, use only the hash, which will double as the position id. As such, the key to the DHT will be only the hash, and the value will be the combined PackedPosition and PosInfo data together.

The PosInfo should remain as a separate entity until the worker logic is updated to use the hash/Position+PosInfo.

Seeing Zobrist collisions way too early in the generation process. Theory suggests that collisions shouldn't be seen until about 2^32 (4 billion) positions and we're not near that. Figure this out.

Logging is hard-coded to STDOUT. Make the target file configurable.

Rather than use the current PositionId class, use the Zobrist hash as the position id.

Right now the distance of a position is automatically assigned at ctor, but through copying this may result in inaccurate distance. Make this more reliable by removing the automatic assignment and replacing it with a deliberate assignment.

A tier is a set of positions that are of the same distance from the root position.

Also track tier statistics:

• Total number of:
  • positions in the tier
  • moves generated by all positions in the tier
  • duplicate positions
  • Zobrist collisions
  • checkmates
  • stalemates
  • captures
• Total number of
• Timestamp of first occurrence of position at tier n
• Timestamp of last occurrence of position at tier n

We will need to verify collisions when using the Zobrist hash. If a duplicate is found, the actual Position data (gi, pop, hi, lo) need to be compared and if not equal then we have a hash collision condition.

This one-way hashing algorithm apparently can reduce a board position to 64-bits with few collisions.

https://www.chessprogramming.org/Zobrist_Hashing

Zobrist hashing cannot be used for our purposes. As Zobrist is a one-way hash and is subject to collisions, it cannot be used as a back reference to parent positions (as the actual position is needed to resolve collisions.)

Archive and remove the Zobrist logic and revert back to using a sequential counter as before.

We are experiencing Zobrist collisions in tier 7. The way to fix this is to add a linked list to the dht buckets, but as the hash we use is a one-way hash, it requires lots of processing and additional code to identify the desired position in the list.

Before doing all this work, try using 128-bit hashes to see if the problem is "moved out" beyond our needs.

To complete Zobrist hash restore castle rights, en passant, and on side. This should be done after the combined Position object is ready.

Rather than have a ubiquitous Piece object, create specialized objects for each piece type (subclass of Piece) and move piece-oriented logic into the specialized classes.

Move objects are leaking
File buffers in DHT are not handled properly

This is to support Zobrist hashing. Normally, the DHT logic generates an MD5 of the key to get the bucket number. Since the Zobrist hash is the key, it is already hashed. The custom hasher for this simply returns the MSB of the hash as a two-digit hex string.