Completeness and Diversity in Depth-First Proof-Number Search with Applications to Retrosynthesis
Completeness and Diversity in Depth-First Proof-Number Search with Applications to Retrosynthesis
Christopher Franz, Georg Mogk, Thomas Mrziglod, Kevin Schewior
Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence
Main Track. Pages 4747-4753.
https://doi.org/10.24963/ijcai.2022/658
We revisit Depth-First Proof-Number Search (DFPN), a well-known algorithm for solving two-player games. First, we consider the completeness property of the algorithm and its variants, i.e., whether they always find a winning strategy when there exists one. While it is known that the standard version is not complete, we show that the combination with the simple Threshold Controlling Algorithm is complete, solving an open problem from the area. Second, we modify DFPN to compute a diverse set of solutions rather than just a single one. Finally, we apply this new variant in Chemistry to the synthesis planning of new target molecules (Retrosynthesis). In this domain a diverse set of many solutions is desirable. We apply additional modifications from the literature to the algorithm and show that it outperforms Monte-Carlo Tree-Search, another well-known algorithm for the same problem, according to a natural diversity measure.
Keywords:
Search: Search and Machine Learning
Agent-based and Multi-agent Systems: Algorithmic Game Theory
Multidisciplinary Topics and Applications: Life Science
Planning and Scheduling: Planning Algorithms