Nature of Probability-Based Proof Number Search

DOI

10.2991/aisr.k.200424.075How to use a DOI?

Keywords

best first search, Probability-based Proof Number Search, Connect Four

Abstract

Probability-based Proof Number Search (PPN-Search) is a best-first search algorithm that possesses a unique nature. It combines two kinds of information from a tree structure, namely, information from visited nodes and yet to be visited nodes. Information coming from visited nodes is determined based on winning status. On the other hand, information from yet to be visited (unexplored) nodes is determined by employing play-out technique in leaf nodes. All of the information is combined into a value called probability-based proof number (PPN). In this paper, PPN-Search is employed to solve randomly generated Connect Four positions. Its results are compared to two other well-known best-first search algorithms, namely Proof Number Search and Monte-Carlo Proof Number Search. The limitation of PPN-Search related to the use of real numbers is identified based on the experiment. To increase the performance of PPN-Search while preserving its strength, an improvement technique using precision rate is introduced. Analysis from further experiments shows that the addition of the precision rate value accentuates the nature of PPN-Search, especially in its ability to combine information into PPN, which leads to increased performance. It is marked by reduced number of nodes needed to be explored up to 57% compared to implementation without precision rate.

Copyright

© 2020, the Authors. Published by Atlantis Press.

Open Access

This is an open access article distributed under the CC BY-NC license (http://creativecommons.org/licenses/by-nc/4.0/).

Download article (PDF)

TY  - CONF
AU  - Anggina PRIMANITA
AU  - Hiroyuki IIDA
PY  - 2020
DA  - 2020/05/06
TI  - Nature of Probability-Based Proof Number Search
BT  - Proceedings of the Sriwijaya International Conference on Information Technology and Its Applications (SICONIAN 2019)
PB  - Atlantis Press
SP  - 485
EP  - 491
SN  - 1951-6851
UR  - https://doi.org/10.2991/aisr.k.200424.075
DO  - 10.2991/aisr.k.200424.075
ID  - PRIMANITA2020
ER  -