Transcript Df-pn: Depth-first Proof Number Search

Df-pn: Depth-first Proof Number
Search
Studied by Ayumu Nagai
Surveryed by Akihiro Kishimoto
Outline of Presentation
•
•
•
•
•
Motivations
Proof Number Search
Seo’s Algorithm
Df-pn
Conclusions
Motivations
• Why do we use depth-first search?
– Dfs uses less memory than bfs in general
• O(d) v.s. O(b^d)
– Has low overhead to manage nodes
• C.f. A* needs priority queue, IDA* just needs stack
– Can behave like bfs with TT
• C.f. IDA* and A*, SSS* and MT-SSS*,
Seo and AO*
Why df-pn?
• Proof Number Search: best-first search for
AND/OR trees
• Df-pn: depth-first search
– Same behavior as pn-search
– Less expansion of interior nodes
Generally better performance than pn-search
Proof-Number Search(1/3):
Proof Numbers
• Pn- search
[Allis et.al.:94]
• Example of proof
numbers
1
– Proof numbers
• Minimum number of
leaf nodes to be
expanded to prove
– Better to select the
child with small proof
number for proving
trees
3
1
1
pn OR node
1
1
pn
1
Leaf
nodes
AND node
Proof Number Search(2/3):
Disproof Numbers
• Pn- search
[Allis et.al.:94]
• Example of disproof
numbers
1
– Disproof numbers
• Minimum number of
leaf nodes to be
expanded to disprove
– Better to select the
child with small
disproof number for
disproving trees
3
1
1
dn OR node
1
1
dn
1
AND node
Proof-Number Search (3/3)
Algorithm
1.
–
2.
3.
4.
2,2
Traverse from the root to
a leaf by choosing
Node with smallest
(dis)proof number at
(AND)OR node
Expand a leaf node
Update (Backup) pn &
dn to the root
Continue 1-3 until
proven or disproven
3,1
1,1
1,1
2,1
1,1
1,1
1,2
pn,dn OR node pn,dn AND node
Seo’s algorithm(1/4)
• Proof number as a threshold
• Transposition table
• Multiple Iterative Deepening
Seo’s algorithm(2/4):
Depth-first search
• Threshold for proof
number
• Iterative deepening
Behavior of Seo’s
algorithm
PN=1
PN=2
PN=3
Seo’s algorithm(3/4):
Transposition table
• Iterative deepening
– Re-expansion of the nodes
Save proof numbers of the nodes
previously expanded in TT
Seo’s algorithm(4/4):
Multiple iterative deepening
• Overestimation of
proof numbers at AND
nodes
– When an OR node is
proved
Behavior of Multiple
Iterative Deepening
PN=13
12
5
Iterative deepening at all
OR nodes
AND node
OR node
7
Proved
PN=8
PN=9
PN=10
Sketch of Seo’s Algorithm
• Node Selection:
– OR node: c1
– AND node: as you like
• Updating Threshold:
– OR: PN = min(pn(c2) + 1,
PN)
– AND: PN = PN + pn (c1)
– (pn(c2) + … + pn(ck))
• Returning Condition:
– PN <= pn(n)
• Others:
– Iterative deepening at OR
node as far as PN > pn(n)
• Notations:
– n: node searching
– pn(n): proof number at n
– c1,…,ck: children of n
where
pn(c1)<=…<=pn(ck)
– PN: threshold
Df-pn
• If you understand Seo’s algorithm, df-pn is
easy to understand!
– has two thresholds for proof & disproof
numbers
• C.f. Seo had only one threshold
– Iterative deepening at both OR and AND nodes
• Need to avoid overestimations of proof and disproof
numbers
– C.f. Seo avoided only the case of proof numbers
Sketch of df-pn
• Node Selection:
– Always c1
• Updating Threshold:
– OR:
– PN’= min(pn(c2) + 1, PN)
– DN’= DN – (dn(c2) + … +
dn(ck))
– AND:
– PN’= PN – (pn(c2) + … +
pn(ck))
– DN’= min(dn(c2) + 1, DN)
• Returning Condition :
– PN <= pn(n) || DN <= dn(n)
• Others:
– Iterative deepening as far as
PN > pn(n) && DN > dn(n)
• Notations:
– n: node searching
– pn(n): proof number at n
– dn(n): disproof number
at n
– c1,…,ck: children of n
where
pn(c1)<=…<=pn(ck) at
OR node n,
dn(c1)<=…<=dn(ck) at
AND node n
PN: threshold of pn
DN: threshold of dn
Conclusions
• I believe enhanced AND/OR tree search
algorithms will improve the ability of
tsumego solvers!
References
• Masahiro Seo: The C* Algorithm for AND/OR Tree
Search and its Application to a Tsume-Shogi Program,
M.Sc. Thesis, Department of Information Science,
University of Tokyo, 1995
• Ayumu Nagai and Hiroshi Imai: Proof for the Equivalence
Between Some Best-First Algorithms and Depth-First
Algorithms for AND/OR Trees, KOREA-JAPAN Joint
Workshop on Algorithms and Computation,pp. 163-170,
1999
• Ayumu Nagai: Df-pn Algorithm for Searching AND/OR
Trees and its Applications, Ph.D. Thesis, Department of
Computing Science, University of Tokyo, 2002