KKFChess uses several hash tables for the chess variants:
| Normal / Wild | Suicide | Atomic | Crazyhouse | Losers | |
| Positional hash tables | Yes | Yes | Yes | Yes | Yes |
| Pawn structure hash table | Yes | No | Yes | Yes | Yes |
| Mating position hash tables | Yes | Yes | Yes | Yes | Yes |
| King safety hash table1 | Yes | No | Yes | Yes | No |
| Piece mobility hash table1 | No | Yes | No | No | Yes |
| Principle variation hash table | Yes | Yes | Yes | Yes | Yes |
| Learning hash table | Yes | Yes | Yes | Yes | Yes |
For those who wonder why KKFChess uses a lot of memory, you've found part of the answer!
1. The memory area for king safety and piece mobility is shared hence their use are mutually exclusive.
KKFChess uses 64-bit hash keys to represent chess positions. Key values are obtained by using the Zobrist hashing method and are derived from the pieces' position. Some keys also include the colour to move, castling rights and the en passant square.
This key is reduced to an index into the hash table according to the size of the hash table being accessed.
Indexing collision occurs when two hash values maps into the same index (64-bits to 32-bits mapping). When this occurs, KKFChess adds a fixed prime number to the index and try again until the collision limit has reached or a non-colliding slot is found. This technique eliminates the need to have prime number of entries in the hash tables.
The positional key is derived from all the pieces' positions, castling rights and en passant square and the side to move. Each record store the evaluation of the position, the search depth and how to interpret the stored value (exact, fail high or fail low ). There are two replacement schemes used on this table - odd keyed entries are always replaced while even keyed entries (0 is even to me) are depth and age based.
During a search, before any nodes are expanded, the hash table is probed to find a score that was recorded earlier and used if it is acceptable; otherwise the search continues.
Positional hash table have no key collision detection mechanisms. The table size is user adjustable.
As its name suggests, the pawn structure hash table holds information about the pawn structure in a position and nothing else. The pawn structure is indifference to colour hence no side to move information is stored.
Information stored in the hash table includes passed pawns, backward pawns, isolated pawns, outposts, game phase and the pawn structure's score. The hash table is accessed when a static position evaluation is performed.
Since pawns are fairly static pieces, this table helps to speed up the position evaluation process. The table uses key collision detection code and a always replace scheme. The table size is user configurable.
The mating position hash table holds positions that are win or lose only. This table is particularly useful for suicide chess where multiple transpositions can lead to the same mating position.
This table has collision resolution and uses an always replace scheme. The table size is not user adjustable.
King safety evaluation can be complex and slow. This table is used in a similar fashion to the pawn structure hash table but stores previous king safety evaluations. The table size is not user configurable.
Besides the normal implementation of the principle variation (by a 2 dimensional array; actually a "triangular" 2d array), a hash table is used to save the PVs of previous searches. The hash key of this hash table is derived form the normal positional hash key and the fifty moves counter.
The purpose of this table is for recovering PVs that had been hidden by positional hash table hits. It has no collision detection and uses an always replace scheme. This table was implemented when recovering from the main positional hash table was found to be unsatisfactory during early program development.
Another use of this table is to aid the search by finding a PV move that was stored and try that move first. This helps move ordering and can speed up the search if the PV move causes a cut-off and there will be no need to generate any moves.
The table size is not user configurable.
From V2.6.0 onwards, a dummy one dimensional PV array is used; only the best root move is stored and the rest of the PV moves are recovered entirely from the PV hash table. This saves some memory by not having the full 2 dimensional array.
This table holds information about how mobile the pieces are in a given position. It is only used for suicide and losers chess and reuses the same memory area as the king safety hash table (suicide and losers chess don't need king safety).
These tables (one for each colour to move) holds the evaluation information of positions from previous games. Before any nodes are searched, a check is made against this table (along with other hashing tables) to see if it worth expanding the current node. The learning hash table is updated automatically if the learning feature is enabled.
Besides the above, hashing is used for opening books, learned files and the compression/decompression routines. EGTB files do not use this hashing scheme - it is perfect keying by the position of pieces.