Transcript ppt

CN and PN Tree Search Algorithms
Like B*, the “Conspiracy Number” (CN) and “Proof Number” (PN) algorithms
•Expand one node at a time, at any point on the fringe of a game tree,
•Generate all child nodes - consider all moves - as part of node expansion.
 Selective node expansion  Selective move generation
http://csiweb.ucd.ie/Staff/acater/comp4031.html
Artificial Intelligence for Games and Puzzles
1
CN and PN Tree Search Algorithms
Like B*, the “Conspiracy Number” (CN) and “Proof Number” (PN) algorithms
•Expand one node at a time, at any point on the fringe of a game tree,
•Generate all child nodes - consider all moves - as part of node expansion.
 Selective node expansion  Selective move generation
1st
http://csiweb.ucd.ie/Staff/acater/comp4031.html
Artificial Intelligence for Games and Puzzles
2
CN and PN Tree Search Algorithms
Like B*, the “Conspiracy Number” (CN) and “Proof Number” (PN) algorithms
•Expand one node at a time, at any point on the fringe of a game tree,
•Generate all child nodes - consider all moves - as part of node expansion.
 Selective node expansion  Selective move generation
1st
2nd
http://csiweb.ucd.ie/Staff/acater/comp4031.html
Artificial Intelligence for Games and Puzzles
3
CN and PN Tree Search Algorithms
Like B*, the “Conspiracy Number” (CN) and “Proof Number” (PN) algorithms
•Expand one node at a time, at any point on the fringe of a game tree,
•Generate all child nodes - consider all moves - as part of node expansion.
 Selective node expansion  Selective move generation
1st
2nd
3rd
http://csiweb.ucd.ie/Staff/acater/comp4031.html
Artificial Intelligence for Games and Puzzles
4
CN and PN Tree Search Algorithms
Like B*, the “Conspiracy Number” (CN) and “Proof Number” (PN) algorithms
•Expand one node at a time, at any point on the fringe of a game tree,
•Generate all child nodes - consider all moves - as part of node expansion.
 Selective node expansion  Selective move generation
1st
4th
2nd
3rd
http://csiweb.ucd.ie/Staff/acater/comp4031.html
Artificial Intelligence for Games and Puzzles
5
CN and PN Tree Search Algorithms
Like B*, the “Conspiracy Number” (CN) and “Proof Number” (PN) algorithms
•Expand one node at a time, at any point on the fringe of a game tree,
•Generate all child nodes - consider all moves - as part of node expansion.
 Selective node expansion  Selective move generation
1st
4th
2nd
3rd
5th
http://csiweb.ucd.ie/Staff/acater/comp4031.html
Artificial Intelligence for Games and Puzzles
6
CN and PN Tree Search Algorithms
Like B*, the “Conspiracy Number” (CN) and “Proof Number” (PN) algorithms
•Expand one node at a time, at any point on the fringe of a game tree,
•Generate all child nodes - consider all moves - as part of node expansion.
 Selective node expansion  Selective move generation
1st
2nd
4th
6th
3rd
5th
http://csiweb.ucd.ie/Staff/acater/comp4031.html
Artificial Intelligence for Games and Puzzles
7
Deeper Search gives better results
•Experience with computer chess shows that deeper search gives better play.
•Programs that can search one extra ply of game tree do gain advantage from it.
•A static evaluator gives an estimate of a position’s worth.
•Evaluation of a parent node should not be very unlike the backed-up minimax
evaluation of child nodes: the correlation should be good.
http://csiweb.ucd.ie/Staff/acater/comp4031.html
Artificial Intelligence for Games and Puzzles
8
Deeper Search gives better results
•Experience with computer chess shows that deeper search gives better play.
•Programs that can search one extra ply of game tree do gain advantage from it.
•A static evaluator gives an estimate of a position’s worth.
•Evaluation of a parent node should not be very unlike the backed-up minimax
evaluation of child nodes: the correlation should be good.
•But the child nodes will be a little closer to the game’s end,
•A static evaluator gets to see the resulting position(s) of playing out any
immediate threat(s)
http://csiweb.ucd.ie/Staff/acater/comp4031.html
Artificial Intelligence for Games and Puzzles
9
Deeper Search gives better results
•Experience with computer chess shows that deeper search gives better play.
•Programs that can search one extra ply of game tree do gain advantage from it.
•A static evaluator gives an estimate of a position’s worth.
•Evaluation of a parent node should not be very unlike the backed-up minimax
evaluation of child nodes: the correlation should be good.
•But the child nodes will be a little closer to the game’s end,
•A static evaluator gets to see the resulting position(s) of playing out any
immediate threat(s)
• Minimaxing one or more levels of game subtree can and frequently does
give a result different to static evaluation of the node at the root of the
subtree.
• That is of course why search and minimaxing are performed!
http://csiweb.ucd.ie/Staff/acater/comp4031.html
Artificial Intelligence for Games and Puzzles
10
Conspiracy Numbers
•An interior node of a game tree derives its current value from minimax of the
part of the game tree beneath it.
• The subtree beneath an interior node need not be expanded to uniform
depth: alpha-beta, null-move quiescence, B* … all expand trees
nonuniformly.
•If a leaf node is expanded, its backed-up minimax value might not be the same
as its statically evaluated value.
• i.e. its value might change
• … and if its value does change, that might or might not be enough to cause a
change of its parent’s value, and so on up the tree.
•So: how many leaf nodes would have to change together - have to conspire - to
cause the value of an interior node to change to some particular other value?
http://csiweb.ucd.ie/Staff/acater/comp4031.html
Artificial Intelligence for Games and Puzzles
11
Conspiracy Numbers - Simple Case
A: (max) 4
B: (min) 4
D: (max) 7
C: (min) 2
E: (max) 4
F: (max) 2
G: (max) 3
•For A to get the value 5 6 or 7, just 1 node - E - would have to change.
http://csiweb.ucd.ie/Staff/acater/comp4031.html
Artificial Intelligence for Games and Puzzles
12
Conspiracy Numbers - Simple Case
A: (max) 4
B: (min) 4
D: (max) 7
C: (min) 2
E: (max) 4
F: (max) 2
G: (max) 3
•For A to get the value 5 6 or 7, just 1 node - E - would have to change.
•For A to get the value 8 (… +), requires conspiracy of size 2: D&E, or F&G.
http://csiweb.ucd.ie/Staff/acater/comp4031.html
Artificial Intelligence for Games and Puzzles
13
Conspiracy Numbers - Simple Case
A: (max) 4
B: (min) 4
D: (max) 7
C: (min) 2
E: (max) 4
F: (max) 2
G: (max) 3
•For A to get the value 5 6 or 7, just 1 node - E - would have to change.
•For A to get the value 8 (… +), requires conspiracy of size 2: D&E, or F&G.
•For A to get the value 4, 0 nodes have to change.
http://csiweb.ucd.ie/Staff/acater/comp4031.html
Artificial Intelligence for Games and Puzzles
14
Conspiracy Numbers - Simple Case
A: (max) 4
B: (min) 4
D: (max) 7
C: (min) 2
E: (max) 4
F: (max) 2
G: (max) 3
•For A to get the value 5 6 or 7, just 1 node - E - would have to change.
•For A to get the value 8 (… +), requires conspiracy of size 2: D&E, or F&G.
•For A to get the value 4, 0 nodes have to change.
•For A to get the value 1 (… -), 2 nodes (D or E, & F or G) have to change.
http://csiweb.ucd.ie/Staff/acater/comp4031.html
Artificial Intelligence for Games and Puzzles
15
Range of likely values
For a root node, and indeed for any interior node generally,
• possible values increasingly greater than the current value require
progressively larger conspiracies
likewise,
• possible values increasingly less than the current value require progressively
larger conspiracies
• With a limit on the size of conspiracy, there follow bounds on the range of
values that the root node could have.
• Conspiracies beyond a certain size may be regarded as not likely.
http://csiweb.ucd.ie/Staff/acater/comp4031.html
Artificial Intelligence for Games and Puzzles
16
Conspiracies of unlikely size
Max-ing level
B:+2
E:+3
F:+2
Min-ing level
G:+4
H:+0
A:+2
C:+0
I:+2
D:+1
J:+2
K:+1
L:+2
M:+2
Values for A of less than 1, or more than 3, require two or more conspirators.
Values for A of less than 0, or more than 4, require three or more conspirators.
For a given threshold, we derive bounds on the range of likely values for A.
http://csiweb.ucd.ie/Staff/acater/comp4031.html
Artificial Intelligence for Games and Puzzles
17
CN Tree Growth Procedure
• Pick a desired accuracy, , to limit the accepted range (VMAX-VMIN) of likely
values of the root node; The smaller , the bigger the tree will get.
• Pick a conspiracy threshold, NT, to determine what size of conspiracies are
deemed sufficiently likely; The greater NT, the bigger the tree will get.
The procedure seeks to narrow the range of sufficiently-likely values of the root
until that range has the desired accuracy.
This can be attempted
• By ruling out the largest of the current likely values, VMAX
• Or by ruling out the smallest of the current likely values, VMIN
Nondeterministically, select any node in (one of) the minimal conspiracy set(s)
for ruling out either VMAX or VMIN, whichever is further from current value V.
http://csiweb.ucd.ie/Staff/acater/comp4031.html
Artificial Intelligence for Games and Puzzles
18
How big is the minimal conspiracy set?
Upsize (node, target)
if node.value ≥ target
then return 0
elseif [node is terminal in the game]
then return +
elseif [node is leaf node]
then return 1
elseif [node is maxing node]
then return [min value of
Upsize(child, target)
where child in node.children]
else return [sum values of
Upsize(child, target)
where child in node.children]
http://csiweb.ucd.ie/Staff/acater/comp4031.html
Artificial Intelligence for Games and Puzzles
19
How big is the minimal conspiracy set?
Downsize (node, target)
if node.value ≤ target
then return 0
elseif [node is terminal in the game]
then return +
elseif [node is leaf node]
then return 1
elseif [node is mining node]
then return [min value of Downsize(child, target)
where child in node.children]
else return [sum values of Downsize(child, target)
where child in node.children]
http://csiweb.ucd.ie/Staff/acater/comp4031.html
Artificial Intelligence for Games and Puzzles
20
Any node in a minimal conspiracy set will do.
Consider trying to rule out VMAX, which must be greater than
current V.
MIN-LEAF(node,Vmax)
if [node is a leaf node]
then Return node
elseif [node is a MAX-ing node]
then [Return MIN-LEAF(c,Vmax)
where c is child minimising
Upsize(child, Vmax)]
else [Quals := children of node with Value<Vmax;
pick one, call it C1;
Return MIN-LEAF(C1,Vmax)]
http://csiweb.ucd.ie/Staff/acater/comp4031.html
Artificial Intelligence for Games and Puzzles
21
Any node in a minimal conspiracy set will do.
Consider trying to rule out VMIN, which must be less than current V.
MAX-LEAF(node,Vmin)
if [node is a leaf node]
then Return node
elseif [node is a MIN-ing node]
then [Return MAX-LEAF(c,Vmin)
where c is child minimising Downsize(child, Vmin)]
else [Quals := children of node with Value>Vmin;
pick one, call it C1;
Return MAX-LEAF(C1,Vmin)]
http://csiweb.ucd.ie/Staff/acater/comp4031.html
Artificial Intelligence for Games and Puzzles
22
Tree Growth example: =0 NT=2
max-ing
name
A0
[0..]
http://csiweb.ucd.ie/Staff/acater/comp4031.html
Artificial Intelligence for Games and Puzzles
23
Tree Growth example: =0 NT=2
max-ing
B1
name
A 1 (0)
[0..]
min-ing
http://csiweb.ucd.ie/Staff/acater/comp4031.html
Static evaluation score
C0
D0
Artificial Intelligence for Games and Puzzles
24
Tree Growth example: =0 NT=2
A 0 (0)
[0..]
max-ing
B 0 (1)
[-..1]
E0
F1
min-ing
Static evaluation score
C0
D0
G1
http://csiweb.ucd.ie/Staff/acater/comp4031.html
Artificial Intelligence for Games and Puzzles
25
Tree Growth example: =0 NT=2
A 0 (0)
[-1..+1]
max-ing
B 0 (1)
[-..1]
E0
F1
min-ing
G1
H -1
http://csiweb.ucd.ie/Staff/acater/comp4031.html
Static evaluation score
C -1(0)
[-..0]
J0
D 0 (0)
[-..0]
K0
L0
M0
Artificial Intelligence for Games and Puzzles
N0
26
Tree Growth example: =0 NT=2
A 0 (0)
[-1..+1]
max-ing
B 0 (1)
[-..1]
E0
F1
min-ing
G1
H -1
Static evaluation score
C -1(0)
[-..0]
J0
D 0 (0)
[-..0]
K0
L0
M0
N0
Bringing any of {E F G} and any of {L M N} to -1 or less
would bring B & D to -1 or less, and A to -1
Raising E to 1 or more would bring B & A to 1
http://csiweb.ucd.ie/Staff/acater/comp4031.html
Artificial Intelligence for Games and Puzzles
27
Tree Growth example: =0 NT=2
A 0 (0)
[-1..+1]
max-ing
B 0 (1)
[-..1]
E0
F1
min-ing
G1
H -1
Static evaluation score
C -1(0)
[-..0]
J0
D 0 (0)
[-..0]
K0
L0
M0
N0
When range.max and range.min are equally far from
current value, arbitrarily pick range.min to rule out next.
http://csiweb.ucd.ie/Staff/acater/comp4031.html
Artificial Intelligence for Games and Puzzles
28
Tree Growth example: =0 NT=2
A 1 (0)
[-1..3]
max-ing
B 1 (1)
[-..3]
E 3 (0)
[0…]
O3
min-ing
F1
G1
P0
Q0
H -1
http://csiweb.ucd.ie/Staff/acater/comp4031.html
Static evaluation score
C -1(0)
[-..0]
J0
D 0 (0)
[-..0]
K0
L0
M0
Artificial Intelligence for Games and Puzzles
N0
29
Tree Growth example: =0 NT=2
A 1 (0)
[-1..3]
max-ing
B 1 (1)
[-..3]
E 3 (0)
[0…]
F 2 (1)
[1…]
min-ing
G1
H -1
R2
O3
P0
Static evaluation score
C -1(0)
[-..0]
J0
S1
D 0 (0)
[-..0]
K0
L0
M0
N0
T1
Q0
http://csiweb.ucd.ie/Staff/acater/comp4031.html
Artificial Intelligence for Games and Puzzles
30
Tree Growth example: =0 NT=2
A 1 (0)
[0..3]
max-ing
B 1 (1)
[0..3]
E 3 (0)
[0…]
F 2 (1)
[1…]
min-ing
G 1 (1)
[1..]
H -1
Static evaluation score
C -1(0)
[-..0]
J0
D 0 (0)
[-..0]
K0
L0
U1
R2
O3
P0
S1
M0
V1
N0
W1
T1
Q0
http://csiweb.ucd.ie/Staff/acater/comp4031.html
Artificial Intelligence for Games and Puzzles
31
Tree Growth example: =0 NT=2
A 1 (0)
[0..3]
max-ing
B 1 (1)
[0..3]
E 3 (0)
[0…]
F 2 (1)
[1…]
min-ing
G 1 (1)
[1..]
H -1
Static evaluation score
C -1(0)
[-..0]
J0
D 0 (0)
[-..0]
K0
L0
U1
R2
O3
P0
Q0
S1
M0
V1
N0
W1
T1
Raising any of {R S T} and any of {U V W} to 3
or beyond allows max value 3 for A
Reducing to 0 or beyond allows min value 0 for A
http://csiweb.ucd.ie/Staff/acater/comp4031.html
Artificial Intelligence for Games and Puzzles
32
Tree Growth example: =0 NT=2
A 1 (0)
[0..3]
max-ing
B 1 (1)
[0..3]
E 3 (0)
[0…]
O3
min-ing
F 2 (1)
[1…]
G 1 (1)
[1..]
P0
Q0
H -1
R2
http://csiweb.ucd.ie/Staff/acater/comp4031.html
Static evaluation score
C -1(0)
[-..0]
J0
S1
D 0 (0)
[-..0]
K0
T1
L0
U1
M0
V1
Artificial Intelligence for Games and Puzzles
N0
W1
33
Tree Growth example: =0 NT=2
A 1 (0)
[1..1]
max-ing
B 1 (1)
[..]
E 3 (0)
[…]
O3
min-ing
F 2 (1)
[…]
G 1 (1)
[..]
P0
Q0
H -1
R2
C -1(0)
[-..]
J0
S1
D 0 (0)
[..]
K0
T1
L0
U1
M0
V1
N0
W1
The tree grows non-uniformly until
eventually the range of likely values at
the root node is -or-less in width
http://csiweb.ucd.ie/Staff/acater/comp4031.html
Artificial Intelligence for Games and Puzzles
34
Calculating ranges of likely values
Each node in an expanded tree is either
• A Game-Terminal node, whose value cannot be changed
• A Non-Game-Terminal node (hereinafter a NGT node), which is either
 an expanded interior node, whose value could be changed by a
conspiracy among nodes in its subtree
 an unexpanded leaf node, whose value could be changed without limit
by expanding the node and finding the value of just one child.
NGT nodes can be associated with two bounds sequences:
• An ascending bounds sequence,
• being a sequence of nondecreasing limiting values which could be achieved
with successively larger conspiracies, starting at the node’s current value and
going perhaps to infinity
•A descending bounds sequence, … nonincreasing … minus infinity
http://csiweb.ucd.ie/Staff/acater/comp4031.html
Artificial Intelligence for Games and Puzzles
35
Bounds Sequences contain descendant node values & perhaps ±
•A NGT leaf node, whether a max or a min node, with current value V0,
• needs no conspiracy to achieve its current value V0,
• needs only itself to change to have value + itself
• its ascending bounds sequence is therefore {V0, +}
•A NGT interior node, if a max node with current value V0,
• needs no conspiracy to achieve its current value V0, (which must be the
current value of at least one of the children)
• can achieve any greater value that any of its child nodes may achieve with
the same conspiracy as that child node needs
• its ascending bounds sequence {V0, V1 … Vn} consists of those Vj which are
maximal for its children’s ascending bounds sequences, or Vj-1 if greater
http://csiweb.ucd.ie/Staff/acater/comp4031.html
Artificial Intelligence for Games and Puzzles
36
Bounds Sequences contain descendant node values & perhaps ±
•A NGT interior node, if a min node with current value V0,
• needs no conspiracy to achieve its current value V0, (which must be the
current value of at least one of the children)
• can achieve any greater value that any of its child nodes may achieve only
when all its child nodes have achieved at least that value
• its ascending bounds sequence {V0, V1 … Vn} consists of all Vj which are
elements of its children’s ascending bounds sequences, sorted into ascending
order, with duplicates retained, but stopping at the lowest maximum value.
•A game terminal node with current value V0, cannot have any other value
• its ascending bounds sequence is {V0}
•Descending bounds sequences can be calculated in very similar fashion
• greater  lesser, min  max, +  +, ascending  descending
http://csiweb.ucd.ie/Staff/acater/comp4031.html
Artificial Intelligence for Games and Puzzles
37
Calculating ascending bounds sequences (top-down)
(defun AscSeq (node)
(cond
((GameTerminalP node)
(list (NodeValue node)))
((UnExpandedP node)
(list (NodeValue node) +))
((MaxP node)
(AscSeqMax
(NodeValue node)
(mapcar #’AscSeq (NodeChildren node))))
((MinP node)
(AscSeqMin
(NodeValue node)
(mapcar #’AscSeq (NodeChildren node))))))
http://csiweb.ucd.ie/Staff/acater/comp4031.html
Artificial Intelligence for Games and Puzzles
38
Calculating ascending bounds sequences (top-down)
(defun AscSeq (node)
(cond (defun AscSeqMax (minimum sequences)
(when sequences
((GameTerminalP
node)
(let ((new (reduce #’max
(list (NodeValue node)))
(mapcar #’first sequences)
((UnExpandedP node)
:initial-value minimum)))
(cons newnode) +))
(list (NodeValue
(AscSeqMax new
((MaxP node)
(remove nil (mapcar #’rest sequences)))))))
(AscSeqMax
(NodeValue node)
(mapcar #’AscSeq (NodeChildren node))))
((MinP node)
(AscSeqMin
(NodeValue node)
(mapcar #’AscSeq (NodeChildren node))))))
http://csiweb.ucd.ie/Staff/acater/comp4031.html
Artificial Intelligence for Games and Puzzles
39
Calculating ascending bounds sequences (top-down)
(defun AscSeq (node)
(cond (defun AscSeqMin (maximum sequences)
(let ((leastbest (reduce #'min
((GameTerminalP node)
(mapcar #'(lambda (seq)
(apply #'max seq))
(list (NodeValue node)))
sequences)
((UnExpandedP node)
:initial-value maximum)))
(list (NodeValue
(sort #'< node) +))
(cons maximum
((MaxP node)
(mapcan #'(lambda (seq)
(AscSeqMax
(remove leastbest seq
(NodeValue node)
:test #'>))
sequences)))))
(mapcar #’AscSeq (NodeChildren
node))))
((MinP node)
(AscSeqMin
(NodeValue node)
(mapcar #’AscSeq (NodeChildren node))))))
http://csiweb.ucd.ie/Staff/acater/comp4031.html
Artificial Intelligence for Games and Puzzles
40
Conspiracy Numbers: Summary
Search can terminate without a value for the root node being fully determined:
therefore, more cheaply.
Game trees are grown selectively, in such a way as to maximise the size of
conspiracy necessary to change the root node’s value. The trees often turn out to
be deep and narrow.
Node values (derived from static evaluator results) may be real numbers.
A related algorithm, Proof Number Search, to be dealt with next, is useful in
situations where an evaluator returns boolean values rather than numeric ones.
Reference: McAllester, D.A. Conspiracy Numbers for Min-Max Search
Artificial Intelligence 35 (1988) 287-310
http://csiweb.ucd.ie/Staff/acater/comp4031.html
Artificial Intelligence for Games and Puzzles
41
CN and PN Tree Search Algorithms
Reprise
Like B*, the “Conspiracy Number” (CN) and “Proof
“Proof Number”
Number” (PN)
(PN) algorithms
algorithms
•Expand one node at a time, at any point on the fringe of a game tree,
•Generate all child nodes - consider all moves - as part of node expansion.
 Selective node expansion  Selective move generation
1st
2nd
4th
6th
3rd
5th
http://csiweb.ucd.ie/Staff/acater/comp4031.html
Artificial Intelligence for Games and Puzzles
42
Deeper Search gives better results
•Experience with computer chess shows that deeper search gives better play.
•Programs that can search one extra ply of game tree do gain advantage from it.
•A static evaluator gives an estimate of a position’s worth.
But game trees with numeric valuations are not the only game trees in town:
There are also AND-OR trees with boolean valuations.
These might be used in chess, for example to determine whether opponent Queen
can be captured for less than the cost of Rook+Pawn;
Or in Go, to determine for example whether a group can be given two eyes in
fewer than 15 moves.
http://csiweb.ucd.ie/Staff/acater/comp4031.html
Artificial Intelligence for Games and Puzzles
43
And/Or Tree - Simple Case
A: (or) T
B: (and) T
D: (or) T
red indicates a
leaf node
whose value
can be known
directly
C: (and) ?
E: (or) T
H: (and) F
J: (or) F
F: (or) T
I: (and) T
K: (or) ?
http://csiweb.ucd.ie/Staff/acater/comp4031.html
G: (or) ?
If all children of a parent
AND node are true,
then the parent is true.
If any child of a parent OR
node is true,
then the parent is true.
Artificial Intelligence for Games and Puzzles
44
Adaptation of Conspiracy Number Search
The essential purpose of conspiracy number search is to reduce the search effort
necessary to establish the value of a root node. It does this by
1. selectively expanding leaf nodes at the frontier of a game tree
• focusing effort on those nodes most likely to make a difference
• therefore not necessarily expanding some or all other nodes at a level
2. optionally, allowing some uncertainty in the value computed
•
Proof number search adapts the first of these to the boolean-value case:
•
Selectively expanding those leaf nodes likely to give an answer most
cheaply
http://csiweb.ucd.ie/Staff/acater/comp4031.html
Artificial Intelligence for Games and Puzzles
45
Proof and Disproof numbers
Each node in an and/or tree is adorned with two numbers:
its proof number
• the minimum number of dominated leaf nodes that would have to be
evaluated to provide the value true
• A node already known to have value true needs 0 more leaf nodes evaluated
to be shown to be true: its proof number is therefore 0
• A node already known to have value false cannot be shown to be true no
matter how many leaf nodes are evaluated: its proof number is therefore 
its disproof number
• the minimum number of dominated leaf nodes that would have to be
evaluated to provide the value false
• similarly, already-false nodes have disproof number 0
• already-true nodes have disproof number 
http://csiweb.ucd.ie/Staff/acater/comp4031.html
Artificial Intelligence for Games and Puzzles
46
Calculating proof & disproof numbers
For a leaf node:
if the value is known to be true, then its P# := 0 D# := 
if the value is known to be false, then its P# :=  D# := 0
if the value is not known, then its P# := 1 D# := 1
http://csiweb.ucd.ie/Staff/acater/comp4031.html
Artificial Intelligence for Games and Puzzles
47
Calculating proof & disproof numbers
For a leaf node:
if the value is known to be true, then its P# := 0 D# := 
if the value is known to be false, then its P# :=  D# := 0
if the value is not known, then its P# := 1 D# := 1
For an interior AND node:
its P# := sum of its children’s P#s
its D# := min of its children’s D#s
http://csiweb.ucd.ie/Staff/acater/comp4031.html
Artificial Intelligence for Games and Puzzles
48
Calculating proof & disproof numbers
For a leaf node:
if the value is known to be true, then its P# := 0 D# := 
if the value is known to be false, then its P# :=  D# := 0
if the value is not known, then its P# := 1 D# := 1
For an interior AND node:
its P# := sum of its children’s P#s
its D# := min of its children’s D#s
http://csiweb.ucd.ie/Staff/acater/comp4031.html
For an interior OR node:
its P# := min of its children’s P#s
its D# := sum of its children’s D#s
Artificial Intelligence for Games and Puzzles
49
Calculating proof & disproof numbers
For a leaf node:
if the value is known to be true, then its P# := 0 D# := 
if the value is known to be false, then its P# :=  D# := 0
if the value is not known, then its P# := 1 D# := 1
For an interior AND node:
its P# := sum of its children’s P#s
its D# := min of its children’s D#s
For an interior OR node:
its P# := min of its children’s P#s
its D# := sum of its children’s D#s
When a leaf node with unknown value is expanded,
1.
calculate its new P# and D# according to the above
2.
recursively, when a node’s P# or D# changes, recompute its parent’s
P# and/or D# too.
http://csiweb.ucd.ie/Staff/acater/comp4031.html
Artificial Intelligence for Games and Puzzles
50
Most Proving Node
The simplest game tree contains just an unexpanded root node, either AND or
OR, with P#=D#=1.
“Proof” proceeds by repeatedly picking the ‘most proving node’ in the tree - the
leaf node that offers prospect of contributing to a proof (/disproof) most quickly.
• At an interior AND node, pick the child with least D#
• At an interior OR node, pick the child with least P#
• When a leaf node has been expanded (and so has become an interior node),
changes to its P# and D# may ripple up the tree.
• At any ancestor where P# and D# do not change, the rippling stops.
• The most proving node for the next iteration will be found in the subtree
dominated by such an ancestor (or the root if no such ancestor)
http://csiweb.ucd.ie/Staff/acater/comp4031.html
Artificial Intelligence for Games and Puzzles
51
The cost of the savings
Proof Number Search aims to achieve fast solutions in boolean-valued game
trees, by concentrating effort on parts of the tree where the number of nodes
needing to be expanded is likely to be least.
• As with other selective game-tree search algorithms, “jumping around the
tree” may require the repeated reconstruction of interior nodes of the tree.
• The computational cost of this may outweigh the savings from expanding
and evaluating a lesser number of distinct nodes.
• Handling transpositions in PN search is a difficulty
Reference:
Allis, van der Meulen, van den Herik (1994). Proof-Number Search. Artificial
Intelligence v.66 no.1 pp91-124
http://fragrieu.free.fr/SearchingForSolutions.pdf (Allis’s PhD thesis)
http://csiweb.ucd.ie/Staff/acater/comp4031.html
Artificial Intelligence for Games and Puzzles
52