Timezone: »

Depth-First Proof-Number Search with Heuristic Edge Cost and Application to Chemical Synthesis Planning
Akihiro Kishimoto · Beat Buesser · Bei Chen · Adi Botea

Thu Dec 12 10:45 AM -- 12:45 PM (PST) @ East Exhibition Hall B + C #214

Search techniques, such as Monte Carlo Tree Search (MCTS) and Proof-Number Search (PNS), are effective in playing and solving games. However, the understanding of their performance in industrial applications is still limited. We investigate MCTS and Depth-First Proof-Number (DFPN) Search, a PNS variant, in the domain of Retrosynthetic Analysis (RA). We find that DFPN's strengths, that justify its success in games, have limited value in RA, and that an enhanced MCTS variant by Segler et al. significantly outperforms DFPN. We address this disadvantage of DFPN in RA with a novel approach to combine DFPN with Heuristic Edge Initialization. Our new search algorithm DFPN-E outperforms the enhanced MCTS in search time by a factor of 3 on average, with comparable success rates.

Author Information

Akihiro Kishimoto (IBM Research)
Beat Buesser (IBM Research)
Bei Chen (IBM Research)
Adi Botea (IBM Research)

More from the Same Authors