Leapfrog tablebase generator
home   tablebase home

The Leapfrog Tablebase Generator

The Algorithm

Leapfrog is a tablebase generator specifically designed for generating 6-men or 7-men pawnless tablebases, or 6-men P-slices of a 7-men tablebase with a single Pawn. It uses an algorithm aimed at minimizing disk traffic, requiring the reading and writing of only 1-2 bits per position per cycle. It spends only a minor fraction of the time on seek operations, by reading and writing in contiguous chunks of 1-2MB.

Note that leapfrog generates 'one-sided' tablebases, which only resolve wins for white. There is no distinction between the various white non-wins, they can be draws or losses. To know the difference, you would have to build a tablebase with the color reversed. Normally eapfrog only generates a tablebase with winning-distances for the losing side (black) to move. The won wtm positions are only available as bitbase. There is an option, though, to store the newly-won info cycle-by cycle, although this might lead to storage problems for very long won end-games. An important limiation is that leapfrog cannot handle end-games with more than 4 black men (non-Pawns).

Leapfrog uses a decomposition of the 3-ply tree needed for retrograde generation of tablebases that splits the tree at the root into subtrees based on different sets of white moves. The different subtrees are treated in separate passes though the tablebase, slicing it up in different ways to make sure that the subtrees always fall within the current slice. It then uses the leapfrog algorithm to alternate the different slicings, requiring the data to be written to the hard disk, to be read back in another order, only once per cycle.

For 7-men tablebases, where the slices are too big to fit in memory, K-slice streaming is used to process the slices in a way that guarantees the trees fit in the memory-loaded part of the slice. The memory-loaded data set is treated by decomposing the move trees by level, treating the white moves in a different pass than the black moves. This optimizes cache utilization, making that every entry needs to loaded into the L2 cache ony 4 times per cycle.

Hardware Requirements

The hardware requirements to run leapfrog for generation of 7-men pawnless tablebases are a 32-bit computer with 2GB of DRAM, and exclusive use of an (unformatted) disk partition of 500 GB. An ordinary contiguous file of 500 GB would also do, but might be much slower due to uncontrollable overhead caused by the operating system.

Contents

For a detailed description of the algorithm, the following pages can be consulted: