mcostalba/Stockfish — pull request #243 by Britvich (2014-06-17 09:46:37+00:00)
Title: Packed like sardines TT

`tt_sardines` supports 50% more entries for a given sized transposition table (`TT`). Under tournament-style hash pressure, Elo is increased (+7.68 ± 2) as fewer time-consuming position evaluations are needed:

![image](https://cloud.githubusercontent.com/assets/7193012/3298436/8a70433a-f601-11e3-82f6-90f9a32cd9b2.png)

`tt_sardines` passed both STC (with 4MB hash) and LTC (with 16MB hash) easily. Also, at STC with no hash pressure (with 128MB hash), the `TT` performs at least as good as it did before:

![image](https://cloud.githubusercontent.com/assets/7193012/3298449/b16fef30-f601-11e3-8d79-fd34ce8a2dc8.png)

The old `TT` used 64-byte clusters, with each cluster containing 4 14-byte entries. `tt_sardines` uses 32-byte clusters, with each cluster containing 3 10-byte entries.

To reduce each entry from 14 to 10 bytes, some fields in the `TTEntry` structure have been condensed:

* The key field (32-bits) is now just 16-bits.
* The generation (8-bits) and bound (8-bits) fields have been combined into a single 8-bit field with 6-bits used for the generation and 2-bits for the bound.
* The depth field (16-bits) is now just 8-bits with the depth stored as an offset from the minimum depth `DEPTH_NONE` (which has been adjusted from -254 to -12). In this way, all depths can be stored as positive `uint8` values.

Since only a partial key is stored with each entry, the same entry used to store information about one position might be used to store information about a different position. This produces occasional type-2 errors during probes, where a probe returns information for a wrong position. These rare, but possible, type-2 errant probes are automatically detected with the same logic that detects corrupted entries generated during unsafe threaded access to the `TT`.

To improve speed, several optimizations have been made:

* The number of entries in each cluster has been reduced from 4 to 3.
* `first_entry` only uses 2 machine instructions and no longer uses a multiply.
* The `probe` loop has been unrolled.
* `store` writes the key only when necessary. It also evaluates only the second and third entries as potentially better replacement candidates, since the first entry starts as the best replacement candidate.