A Local-Pattern Related Look-Up Table

Chung Chin Shih, Ting Han Wei, Ti Rong Wu, I. Chen Wu

Research output: Contribution to journalArticlepeer-review

Abstract

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 life-and-death (L&amp;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&#x0025; 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 <inline-formula><tex-math notation="LaTeX">$7 \times 7$</tex-math></inline-formula> and <inline-formula><tex-math notation="LaTeX">$19 \times 19$</tex-math></inline-formula> L&amp;D Go problems.

Original languageEnglish
Pages (from-to)1-10
Number of pages10
JournalIEEE Transactions on Games
DOIs
StateAccepted/In press - 2023

Keywords

  • Game Solving
  • Games
  • Heuristic Search
  • Kill-all Go
  • Pattern Matching
  • Pattern matching
  • Reinforcement Learning
  • Safety
  • Search problems
  • Shape
  • Table lookup
  • Time complexity

Fingerprint

Dive into the research topics of 'A Local-Pattern Related Look-Up Table'. Together they form a unique fingerprint.

Cite this