KKFChess' EGTBs holds solutions to all possible positions for a given set of pieces. File symmetry is used to reduce the size to 50% of a non-symmetrical aware one. Rank symmetry is possible (with special care when pawns are present) but not yet implemented. The EGTB's header file also contains statistical information about the number of wins, losses or draws for all the positions contained.
A 32-bit value is used for the index into the table. This index consists of groups of 6 bits, each holding the bit square value (0 to 63) a piece is on. Hence the maximum number of pieces an EGTB file can support is 5 (6*5 = 30 bits). Below is a breakdown of the bit pattern of an index:
| Bits 29-24 | Bits 23-18 | Bits 17-12 | Bits 11-6 | Bits 5-0 | Maximum positions | Pseudo valid positions | |
| Five pieces | 1st piece | 2nd piece | 3rd piece | 4th piece | 5th piece | 64 ^ 5 = 1,073,741,824 | 64! / 59! = 914,941,440 |
| Four pieces | 0 | 1st piece | 2nd piece | 3rd piece | 4th piece | 64 ^ 4 = 16,777,216 | 64! / 60! = 15,249,024 |
| Three pieces | 0 | 0 | 1st piece | 2nd piece | 3rd piece | 64 ^ 3 = 262,144 | 64! / 61! = 249,984 |
| Two pieces | 0 | 0 | 0 | 1st piece | 2nd piece | 64 ^ 2 = 4,096 | 64! / 62! = 4,032 |
Some index values are not used because they imply that two or more pieces are on the same square or a pawn on the 1st or 8th rank.
Each table entry holds a pair of distance to mate values for a position - one for white to move and the other for black to move. They are coded such that 0 indicates a drawn, positive for a winning and negative for a losing position. For majority of positions, 8-bits are enough to hold a solution but for some 16-bits are required.
KKFChess works on a non-symmetrical 16-bit data table internally and will output a symmetrical 8-bit or 16-bit EGTB file, depending on the maximum and minimum values of the solutions generated. A flag in the file header is set to indicate the data size of the table that follows. The probing code automatically adjusts to the correct data size given by this setting.
EGTB files can be compressed to save space and the probing code can handle compressed EGTB files.
The automated EGTB generator is capable of generating primary distance to mate EGTB files in the correct order - pieces first then pawns for supported chess variants. The driver is simply a nested loop that iterate over all pieces given. A (Pascal / BASIC like) pseudo 2-piece driver looks like:
begin Files Driver:
for pawns count = 0 to 2
for 1st piece = pawn to king
for 2nd piece = pawn to king
if number of pawns > pawns count then
next 2nd piece
end if
if file already exists next 2nd piece
if reversed colour file already exists then
next 2nd piece
end if
Solve by iteration
next 2nd piece
next 1st piece
next pawns count
end Files Driver
These loops will produce primary EGTB files in the sequence of:
N_N, N_B, N_R, N_Q, N_K,
B_B, B_R, B_Q, B_K,
R_R, R_Q, R_K,
Q_Q, Q_K,
K_K,
P_N, P_B, P_R, P_Q, P_K,
P_P
Of course, other checks are performed such as pieces' configuration against current chess variant. Extending the code to other piece counts was trivial.
The iterator is responsible for finding a "next move will mate" solution for all the given pieces. As its name implies it first finds all the mate in one moves, then finds the moves that leads to the these mate in one positions (mate in two), then finds the moves that leads to the mate in twos, etc., etc., until no more new solutions are available. The unsolved positions are then considered as draws.
The solutions driver is responsible for placing pieces on their squares then try to solve the position. It knows about position symmetries and will skip positions that were symmetrical to previously solved ones. Below is a pseudo code for this driver:
begin Solution Driver:
if no more pieces to be placed then
if position has not been symmetrically solved then
Solve position for white to move
Set same solutions to all symmetrical positions
Solve position for black to move
Set same solutions to all symmetrical positions
Make all symmetrical positions "solved"
end if
exit Solution Driver
else
for each square
if square is empty then
Place a piece on the square
Call Solution Driver to place next piece
end if
next square
end if
end Solution Driver
As you can see, the solutions driver is a recursive function, placing one piece at a time until no pieces left, then solves the position. It knows about symmetries such as file, rank, diagonal and rotation plus special cases when pawns are on the board. Position validation codes are not shown in the above.
Solvers are responsible for placing pieces on the board and attempt to solve by finding a move that leads to mate, using previously solved positions such as those from other EGTB files or from previous iterations. Solvers are tailor made to solve particular variants. A suicide solver will be different from an atomic solver since the game rules differ.
From V2.6.1, recently EGTB files are caches in small memory block known as cache lines. When an EGTB probe is made, the cache lines are examine to find a matching position. If one is found then it is a simple case of reading the value from memory, otherwise a cache miss is said to have occurred and the new block of information is required to be read into the cache. Each cache line is independent but non-overlapping and can map into different areas of the same file.
EGTB caching uses an "aging" replacement scheme where each cache line has an "age" that is decremented at every probe but refreshed at every successful probe. A cache miss will cause an empty or least used cache line to be filled with the required data.
There are two kinds of EGTB file caching used in KKFChess - ready-only and read-write. The ready-only cache is used for EGTB probing and the read-write one is used for caching the temporary file when generating EGTB files with the temporary file option enabled.
Another difference between the read-only and read-write cache is that the former holds data from different or the same files while the latter only holds data from one file.
V2.6.1 has 128 read-only cache lines of 262,144 (256x1024) entries and 32 read-write cache lines of user selectable total size. The enabling of the cache is under user selection.
The primary goal of caching is to speed up EGTB generation but it also speeds up EGTB probing, especially with compressed EGTB files since they can be cached also.