Transposition table

Often the same position can occur after several differing move sequences, an example is the Tiger opening which can begin with f5-d6-c3-d3-c4 or f5-d6-c4-d3-c3, both sequences resulting in the same position. This is called a transposition. To avoid searching a position several times, Zebra stores most positions it has encountered during its search in a transposition table (implemented as the data structure hash table). For each position, Zebra's assessment and the best move found during the search is stored. In the midgame phase of the game, this typically reduces the time for a deep search by 20 - 50%. In the endgame, where transpositions are much more common, the gain can be much higher.