文章基本信息

标题：Characterizing the Nature of Probability-Based Proof Number Search: A Case Study in the Othello and Connect Four Games
本地全文：下载
作者：Anggina Primanita ; Mohd Nor Akmal Khalid ; Hiroyuki Iida 等
期刊名称：Information
电子版ISSN：2078-2489
出版年度：2020
卷号：11
期号：5
DOI：10.3390/info11050264
出版社：MDPI Publishing
摘要：Variants of best-first search algorithms and their expansions have continuously been introduced to solve challenging problems. The probability-based proof number search (PPNS) is a best-first search algorithm that can be used to solve positions in AND/OR game tree structures. It combines information from explored (based on winning status) and unexplored (through Monte Carlo simulation) nodes from a game tree using an indicator called the probability-based proof number (PPN). In this study, PPNS is employed to solve randomly generated positions in Connect Four and Othello, in which the results are compared with the two well-known best-first search algorithms (proof number search (PNS) and Monte Carlo proof number search). Adopting a simple improvement parameter in PPNS reduces the number of nodes that need to be explored by up to 57%. Moreover, further observation showed the varying importance of information from explored and unexplored nodes in which PPNS relies critically on the combination of such information in earlier stages of the Othello game. Discussion and insights from these findings are provided where the potential future works are briefly described.
关键词：best;first search; probability;based proof number search; Connect Four; Othello best;first search ; probability;based proof number search ; Connect Four ; Othello