Depth-First Proof-Number Search with Heuristic Edge Cost and Application to Chemical Synthesis Planning
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.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
A Formal Characterization of the Local Search Topology of the Gap Heuristic
The pancake puzzle is a classic optimization problem that has become a standard benchmark for heuristic search algorithms. In this paper, we provide full proofs regarding the local search topology of the gap heuristic fo…
Heuristic SearchAlphaZero-based Proof Cost Network to Aid Game Solving
In recent years, the AlphaZero algorithm has achieved super-human playing levels for many games without hand-crafted expert knowledge. Researchers have taken advantage of AlphaZero's effectiveness at learning and playing…
Board GamesMonte Carlo Tableau Proof Search
We study Monte Carlo Tree Search to guide proof search in tableau calculi. This includes proposing a number of proof-state evaluation heuristics, some of which are learnt from previous proofs. We present an implementatio…
Automated Theorem ProvingTowards solving the 7-in-a-row game
Our paper explores the game theoretic value of the 7-in-a-row game. We reduce the problem to solving a finite board game, which we target using Proof Number Search. We present a number of heuristic improvements to Proof …
On AO*, Proof Number Search and Minimax Search
We discuss the interconnections between AO*, adversarial game-searching algorithms, e.g., proof number search and minimax search. The former was developed in the context of a general AND/OR graph model, while the latter …