52:
disproved in order to disprove the node. Because the goal of the tree is to prove a forced win, winning nodes are regarded as proved. Therefore, they have proof number 0 and disproof number ∞. Lost or drawn nodes are regarded as disproved. They have proof number ∞ and disproof number 0. Unknown leaf nodes have a proof and disproof number of unity. The proof number of an internal AND node is equal to the sum of its children's proof numbers, since to prove an AND node all the children have to be proved. The disproof number of an AND node is equal to the minimum of its children's disproof numbers. The disproof number of an internal OR node is equal to the sum of its children's disproof numbers, since to disprove an OR node all the children have to be disproved. Its proof number is equal to the minimum of its children's proof numbers.
55:
The procedure of selecting the most-proving node to expand is the following. We start at the root. Then, at each OR node the child with the lowest proof number is selected as successor, and at each AND node the child with the lowest disproof number is selected as successor. Finally, when a leaf node
51:
To each node of the partially expanded game tree the proof number and disproof number are associated. A proof number represents the minimum number of leaf nodes which have to be proved in order to prove the node. Analogously, a disproof number represents the minimum number of leaves which have to be
59:
The proof and disproof numbers represent lower bounds on the number of nodes to be evaluated to prove (or disprove) certain nodes. By always selecting the most proving (disproving) node to expand, an efficient search is generated.
114:
152:
48:. Maximizing nodes become OR-nodes, minimizing nodes are mapped to AND-nodes. For all nodes proof and disproof numbers are stored, and updated during the search.
63:
Some variants of proof number search like dfPN, PN, PDS-PN have been developed to address the quite big memory requirements of the algorithm.
186:
90:
80:
196:
191:
41:
133:
129:
34:
146:
108:
172:
86:
26:
45:
180:
30:
40:
Using a binary goal (e.g. first player wins the game), game trees of two-person
23:
82:
Searching for
Solutions in Games and Artificial Intelligence. PhD Thesis
167:
A. Kishimoto, M.H.M. Winands, M. Müller, and J-T. Saito (2012)
169:
Game-tree search using proof numbers: The first twenty years
56:
is reached, it is expanded and its children are evaluated.
113:: CS1 maint: bot: original URL status unknown (
128:Mark H.M. Winands, Jos W.H.M. Uiterwijk, and
8:
151:: CS1 maint: multiple names: authors list (
135:PDS-PN: A New Proof-Number Search Algorithm
95:. Archived from the original on 2004-12-04
71:
37:, but also for sub-goals during games.
144:
106:
7:
141:. Lecture Notes in Computer Science.
14:
33:, with applications mostly in
1:
187:Game artificial intelligence
213:
16:Game tree search algorithm
42:perfect-information games
85:. Ponsen & Looijen.
22:(short: PN search) is a
171:, ICGA, 35(3):131–156,
130:H. Jaap van den Herik
44:can be mapped to an
20:Proof-number search
197:Search algorithms
79:Allis, L Victor.
204:
192:Graph algorithms
157:
156:
150:
142:
140:
125:
119:
118:
112:
104:
102:
100:
76:
27:search algorithm
212:
211:
207:
206:
205:
203:
202:
201:
177:
176:
165:
163:Further reading
160:
143:
138:
127:
126:
122:
105:
98:
96:
93:
78:
77:
73:
69:
35:endgame solvers
17:
12:
11:
5:
210:
208:
200:
199:
194:
189:
179:
178:
164:
161:
159:
158:
120:
91:
70:
68:
65:
15:
13:
10:
9:
6:
4:
3:
2:
209:
198:
195:
193:
190:
188:
185:
184:
182:
175:
174:
170:
162:
154:
148:
137:
136:
131:
124:
121:
116:
110:
94:
88:
84:
83:
75:
72:
66:
64:
61:
57:
53:
49:
47:
43:
38:
36:
32:
28:
25:
21:
168:
166:
134:
123:
97:. Retrieved
92:90-9007488-0
81:
74:
62:
58:
54:
50:
39:
31:Victor Allis
29:invented by
19:
18:
46:and–or tree
181:Categories
67:References
147:cite book
109:cite book
24:game tree
132:(2003).
99:24 Oct
89:
139:(PDF)
153:link
115:link
101:2014
87:ISBN
173:pdf
183::
149:}}
145:{{
111:}}
107:{{
155:)
117:)
103:.
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.