  This paper describes a Relevance-Zone pattern table (RZT) that can be used to
replace a traditional transposition table. An RZT stores exact game values for
patterns that are discovered during a Relevance-Zone-Based Search (RZS), which
is the current state-of-the-art in solving L&D problems in Go. Positions that
share the same pattern can reuse the same exact game value in the RZT. The
pattern matching scheme for RZTs is implemented using a radix tree, taking into
consideration patterns with different shapes. To improve the efficiency of
table lookups, we designed a heuristic that prevents redundant lookups. The
heuristic can safely skip previously queried patterns for a given position,
reducing the overhead to 10% of the original cost. We also analyze the time
complexity of the RZT both theoretically and empirically. Experiments show the
overhead of traversing the radix tree in practice during lookup remain flat
logarithmically in relation to the number of entries stored in the table.
Experiments also show that the use of an RZT instead of a traditional
transposition table significantly reduces the number of searched nodes on two
data sets of 7x7 and 19x19 L&D Go problems.
