Author: Uri Blass
Date: 03:16:37 11/22/02
Go up one level in this thread
On November 21, 2002 at 19:57:54, Uri Blass wrote:
>On November 21, 2002 at 16:46:28, Omid David Tabibi wrote:
>
>>On November 21, 2002 at 15:55:55, Uri Blass wrote:
>>
>>>On November 21, 2002 at 09:10:32, Omid David Tabibi wrote:
>>>
>>>>On November 21, 2002 at 07:18:11, Uri Blass wrote:
>>>>
>>>>>On November 21, 2002 at 06:26:16, Uri Blass wrote:
>>>>>
>>>>>>On November 21, 2002 at 06:25:17, Uri Blass wrote:
>>>>>>
>>>>>>>On November 21, 2002 at 04:52:13, Omid David Tabibi wrote:
>>>>>>>
>>>>>>>>On November 20, 2002 at 22:05:29, Robert Hyatt wrote:
>>>>>>>>
>>>>>>>>>On November 20, 2002 at 16:55:41, Gian-Carlo Pascutto wrote:
>>>>>>>>>
>>>>>>>>>>Nullmove in Deep Sjeng uses an algorithm of my own, but I can
>>>>>>>>>>switch it back to other systems easily. I did so for running
>>>>>>>>>>a few tests.
>>>>>>>>>>
>>>>>>>>>>I made a version which uses Heinz Adaptive Nullmove Pruning
>>>>>>>>>>and a version which uses your verification nullmove.
>>>>>>>>>
>>>>>>>>>This would seem to be a bit harder than at first glance. They say that
>>>>>>>>>if the normal null-move search fails high, then do a D-1 regular search
>>>>>>>>>to verify that, but while in that verification search, no further
>>>>>>>>>verification searches are done, meaning that the normal null-move search
>>>>>>>>>fail-high is treated just like we do it today..
>>>>>>>>>
>>>>>>>>>I'm going to experiment with this myself, just for fun, but it seems that you
>>>>>>>>>need to pass some sort of flag down thru the search calls indicating that
>>>>>>>>>you are either below a verification-search node or not so that recursive
>>>>>>>>>verification searches are not done...
>>>>>>>>>
>>>>>>>>
>>>>>>>>Exactly!! (finally someone read the article carefully)
>>>>>>>>
>>>>>>>>See Figure 3 for detailed implementation (the flag you mentioned which is passed
>>>>>>>>down as a parameter for search(), is called 'verify' in the pseudo-code).
>>>>>>>>
>>>>>>>>At first stage leave alone the zugzwang detection part (the piece of code at the
>>>>>>>>bottom of Figure 3). Due to instablilities, some programs might do a needless
>>>>>>>>re-search. First let the algorithm work fine in general, and then do the
>>>>>>>>zugwzang detection part.
>>>>>>>
>>>>>>>I let the algorithm to work without zugwzang detection and first results seems
>>>>>>>not to be good
>>>>>>>
>>>>>>>Some positions I get at the same depth and
>>>>>>>the only position so far in the gcp test suite that I got at smaller depth for
>>>>>>>tactical reasons is
>>>>>>>[D]5rk1/1r1qbnnp/R2p2p1/1p1Pp3/1Pp1P1N1/2P1B1NP/5QP1/5R1K w - - 0 1
>>>>>>>
>>>>>>>I am going to try it in 10 sedconds per move and get resulkts in half an hour.
>>>>>>>
>>>>>>>Uri
>>>>>>
>>>>>>should be seconds,results,position
>>>>>>I type too fast.
>>>>>>
>>>>>>Uri
>>>>>
>>>>>Here are the results of the new version:
>>>>>
>>>>>1 39 39
>>>>>2 9 48
>>>>>3 8 56
>>>>>4 11 67
>>>>>5 6 73
>>>>>6 6 79
>>>>>7 5 84
>>>>>8 4 88
>>>>>9 4 92
>>>>>10 2 94
>>>>>
>>>>>results of the old version seem better:
>>>>>
>>>>>1 40 40
>>>>>2 17 57
>>>>>3 8 65
>>>>>4 7 72
>>>>>5 6 78
>>>>>6 4 82
>>>>>7 8 90
>>>>>8 2 92
>>>>>9 3 95
>>>>>10 1 96
>>>>>
>>>>>Remember also that I tested the olf version at more than 10 seconds per move so
>>>>>if it changed it's mind after 20 seconds from the right move to the wrong move
>>>>>the position is counted as a failure.
>>>>>
>>>>>Uri
>>>>
>>>>Did you use the exact implementation I described in Figure 3?
>>>>
>>>>BTW, you have to compare the algorithms at deeper searches. A fixed 10 ply depth
>>>>will be fine.
>>>
>>>Some notes:
>>>
>>>I do not the exact implementation in figure 3.
>>>Differences:
>>>
>>>1)I do not use null move pruning at depth=1 because I have other pruning and I
>>>did not change it.
>>>null move pruning is used by movei only when the depth is at least 2.
>>>
>>>2)I did use research so I have not varaible to tell me about fail high and after
>>>fail high, I trust the result of normal search(verify=false) with depth
>>>that is reduced by 1.
>>>
>>>3)I already tested it at 300 seconds per move(still without research) and I
>>>expect to have results tommorow.
>>>
>>>I am going to compare it with results of my previous version(null move pruning
>>>R=3)
>>>I use also other pruning ideas that I did not change.
>>>
>>>Uri
>>
>>I'm afraid that all these differences might result in a totally different
>>structure. I strongly recommend you to try my exact implemenation first.
>
>I am interested in the question if verification search can help movei to be
>better so I compare time to get the solution and try first minimal changes.
>
>1)If the target is to have something that is clearly superior to R=2 then I
>believe that I already have it and not only because of R=3.
>
>It means that I do not expect to do movei significantly better by removing
>pruning.
>
>2)I am going to try later the following changes:
>
>a)Replace depth>1 by (!verify||depth>1)
>b)Maybe some changes of my pruning rules to try to make a) productive
>c)Add research
>
>Uri
I promised to post today results and it seems that the difference at long time
control is small and there are some positions when verification search without
research solves faster
Total results and some positions:
Results with verification search(no research):
Sec Solved Total
---- ------ ------
1 37 37
2 9 46
3 8 54
4 9 63
5 6 69
6 7 76
7 5 81
8 3 84
9 4 88
10 2 90
11 1 91
12 2 93
13 4 97
14 2 99
15 0 99
16 2 101
17 0 101
18 0 101
19 0 101
20 0 101
21 1 102
22 3 105
23 2 107
24 1 108
25 1 109
26 1 110
27 1 111
28 0 111
29 2 113
30 0 113
31 1 114
32 1 115
33 2 117
34 0 117
35 1 118
36 0 118
37 0 118
38 0 118
39 0 118
40 0 118
41 1 119
42 0 119
43 0 119
44 0 119
45 0 119
46 0 119
47 1 120
48 0 120
49 0 120
50 2 122
51 0 122
52 0 122
53 0 122
54 0 122
55 1 123
56 0 123
57 0 123
58 1 124
59 0 124
60 0 124
61 0 124
62 0 124
63 3 127
64 1 128
65 0 128
66 1 129
67 0 129
68 0 129
69 0 129
70 0 129
71 1 130
72 0 130
73 0 130
74 0 130
75 1 131
76 0 131
77 0 131
78 0 131
79 0 131
80 1 132
81 0 132
82 0 132
83 0 132
84 0 132
85 0 132
86 0 132
87 0 132
88 0 132
89 0 132
90 0 132
91 0 132
92 1 133
93 0 133
94 1 134
95 0 134
96 0 134
97 0 134
98 0 134
99 0 134
100 0 134
101 0 134
102 0 134
103 0 134
104 0 134
105 0 134
106 0 134
107 0 134
108 0 134
109 0 134
110 0 134
111 0 134
112 0 134
113 0 134
114 0 134
115 0 134
116 0 134
117 0 134
118 0 134
119 0 134
120 0 134
121 0 134
122 0 134
123 1 135
124 1 136
125 0 136
126 0 136
127 0 136
128 1 137
129 0 137
130 0 137
131 0 137
132 0 137
133 0 137
134 0 137
135 0 137
136 0 137
137 0 137
138 0 137
139 0 137
140 0 137
141 0 137
142 1 138
143 0 138
144 0 138
145 0 138
146 0 138
147 0 138
148 0 138
149 0 138
150 1 139
151 0 139
152 0 139
153 0 139
154 0 139
155 1 140
156 0 140
157 0 140
158 0 140
159 0 140
160 0 140
161 0 140
162 0 140
163 0 140
164 0 140
165 1 141
166 0 141
167 0 141
168 0 141
169 0 141
170 1 142
171 0 142
172 0 142
173 0 142
174 1 143
175 0 143
176 0 143
177 0 143
178 0 143
179 0 143
180 0 143
181 0 143
182 0 143
183 0 143
184 0 143
185 0 143
186 1 144
187 0 144
188 0 144
189 0 144
190 0 144
191 0 144
192 0 144
193 0 144
194 0 144
195 0 144
196 0 144
197 0 144
198 0 144
199 0 144
200 0 144
201 0 144
202 1 145
203 0 145
204 1 146
205 0 146
206 0 146
207 0 146
208 0 146
209 0 146
210 0 146
211 0 146
212 0 146
213 0 146
214 0 146
215 0 146
216 0 146
217 0 146
218 0 146
219 0 146
220 0 146
221 0 146
222 0 146
223 0 146
224 0 146
225 0 146
226 0 146
227 0 146
228 0 146
229 0 146
230 0 146
231 0 146
232 0 146
233 0 146
234 0 146
235 0 146
236 0 146
237 0 146
238 0 146
239 0 146
240 0 146
241 0 146
242 0 146
243 0 146
244 0 146
245 0 146
246 1 147
247 0 147
248 0 147
249 0 147
250 0 147
251 0 147
252 1 148
253 0 148
254 0 148
255 0 148
256 0 148
257 0 148
258 0 148
259 0 148
260 0 148
261 0 148
262 0 148
263 0 148
264 0 148
265 0 148
266 0 148
267 0 148
268 0 148
269 0 148
270 0 148
271 0 148
272 0 148
273 0 148
274 0 148
275 0 148
276 0 148
277 0 148
278 1 149
149 problems solved.
34 problems unsolved.
Without verification search
1 40 40
2 17 57
3 8 65
4 7 72
5 6 78
6 4 82
7 8 90
8 2 92
9 3 95
10 1 96
11 3 99
12 3 102
13 1 103
14 1 104
15 2 106
16 2 108
17 1 109
18 2 111
19 2 113
20 0 113
21 1 114
22 2 116
23 0 116
24 0 116
25 1 117
26 1 118
27 0 118
28 1 119
29 1 120
30 0 120
31 0 120
32 1 121
33 0 121
34 1 122
35 0 122
36 0 122
37 0 122
38 1 123
39 0 123
40 0 123
41 0 123
42 0 123
43 0 123
44 0 123
45 0 123
46 1 124
47 1 125
48 1 126
49 0 126
50 0 126
51 0 126
52 0 126
53 0 126
54 0 126
55 0 126
56 1 127
57 0 127
58 0 127
59 0 127
60 0 127
61 0 127
62 0 127
63 0 127
64 0 127
65 0 127
66 0 127
67 0 127
68 1 128
69 0 128
70 0 128
71 1 129
72 2 131
73 0 131
74 0 131
75 2 133
76 0 133
77 0 133
78 0 133
79 0 133
80 0 133
81 0 133
82 1 134
83 0 134
84 0 134
85 0 134
86 0 134
87 0 134
88 0 134
89 0 134
90 0 134
91 1 135
92 0 135
93 0 135
94 0 135
95 0 135
96 0 135
97 0 135
98 0 135
99 0 135
100 0 135
101 0 135
102 0 135
103 0 135
104 0 135
105 0 135
106 0 135
107 0 135
108 0 135
109 0 135
110 0 135
111 0 135
112 0 135
113 0 135
114 0 135
115 0 135
116 0 135
117 0 135
118 0 135
119 0 135
120 0 135
121 0 135
122 1 136
123 0 136
124 2 138
125 0 138
126 0 138
127 0 138
128 0 138
129 0 138
130 0 138
131 0 138
132 0 138
133 0 138
134 0 138
135 0 138
136 1 139
137 0 139
138 1 140
139 0 140
140 0 140
141 0 140
142 0 140
143 0 140
144 0 140
145 0 140
146 0 140
147 0 140
148 0 140
149 0 140
150 0 140
151 1 141
152 0 141
153 0 141
154 0 141
155 0 141
156 0 141
157 0 141
158 0 141
159 0 141
160 0 141
161 0 141
162 0 141
163 0 141
164 0 141
165 0 141
166 0 141
167 0 141
168 0 141
169 1 142
170 1 143
171 0 143
172 0 143
173 0 143
174 0 143
175 0 143
176 0 143
177 0 143
178 0 143
179 0 143
180 0 143
181 1 144
182 0 144
183 0 144
184 0 144
185 0 144
186 0 144
187 1 145
188 0 145
189 0 145
190 0 145
191 0 145
192 0 145
193 0 145
194 0 145
195 0 145
196 0 145
197 0 145
198 0 145
199 0 145
200 0 145
201 0 145
202 0 145
203 0 145
204 0 145
205 0 145
206 0 145
207 0 145
208 0 145
209 0 145
210 0 145
211 0 145
212 0 145
213 0 145
214 1 146
215 0 146
216 0 146
217 0 146
218 0 146
219 0 146
220 0 146
221 0 146
222 0 146
223 0 146
224 0 146
225 0 146
226 0 146
227 0 146
228 0 146
229 0 146
230 0 146
231 0 146
232 0 146
233 0 146
234 0 146
235 0 146
236 0 146
237 0 146
238 1 147
239 0 147
240 1 148
241 0 148
242 0 148
243 1 149
244 0 149
245 0 149
246 0 149
247 0 149
248 0 149
249 0 149
250 0 149
251 0 149
252 0 149
253 0 149
254 0 149
255 0 149
256 0 149
257 0 149
258 0 149
259 0 149
260 0 149
261 0 149
262 0 149
263 0 149
264 0 149
265 0 149
266 0 149
267 0 149
268 1 150
269 0 150
270 0 150
271 0 150
272 0 150
273 0 150
274 0 150
275 0 150
276 0 150
277 0 150
278 0 150
279 1 151
Some positions and analysis at depth>=10:
Id: ECM.1080
[D]b3r3/q2B2k1/3Q2p1/1p5p/3pP3/5P2/1p4PP/5RK1 b - - 0 1
Bm: d3+
no 10 148860 +48 24297294 e8g8 d7e6 g8f8 f1b1 f8f6 d6d7 a7d7 e6d7
a8c6 d7c6 f6c6 b1b2
yes 10 169680 +49 27935805 d4d3
yes 10 191190 +133 31488237 d4d3 g1h1 a7f2 d6d3 a8e4 f3e4 f2f1 d3f1
e8a8 d7g4 a8a1 g4d1 b2b1q
yes 10 205320 +133 34125942 d4d3 g1h1 a7f2 d6d3 a8e4 f3e4 f2f1 d3f1
e8a8 d7g4 a8a1 g4d1 b2b1q
yes 11 251670 +227 41842250 d4d3 g1h1 a7f2 f1d1 f2c2 d6d4 g7g8 d4g1
e8e5 d1b1 h5h4 g1d1 a8b7
yes 11 293100 +227 49861568 d4d3 g1h1 a7f2 f1d1 f2c2 d6d4 g7g8 d4g1
e8e5 d1b1 h5h4 g1d1 a8b7
Result: Success
Found in: 169680 ms (00:02:49.680)
Without verification search
Id: ECM.1080
Fen: b3r3/q2B2k1/3Q2p1/1p5p/3pP3/5P2/1p4PP/5RK1 b - - 0 1
Bm: d3+
no 10 71230 +50 11483702 e8f8 d7b5 f8b8 b5d3 b8b3 d3b1 g7f7 g1h1
b3c3 e4e5 331 494576
no 10 95520 +50 15678430 e8f8 d7b5 f8b8 b5d3 b8b3 d3b1 g7f7 g1h1
b3c3 e4e5 420 708299
no 11 289030 +68 47066642 e8f8 h2h4 b5b4 d7b5 b4b3 b5c4 f8b8 d6e6
a7b6 e6e7 g7h8 e7e5 h8h7 e5e7 h7h6 1181
1842263
Result: Failure
Movei needed depth 11 and slightly more than 5 minutes to find d3
without verifications.
Another example
Id: ECM.1295
[D]r3r1k1/4pp1p/b5pB/q1pP4/3b4/2N4P/PP4P1/R2RQ2K w - - 0 1
Bm: Rxd4
no 10 20660 -3 3312889 h6e3 e7e5 c3e4 a5e1 d1e1 e8b8 e3d4 c5d4
e4f6 g8g7 f6d7 b8b2 d7e5
no 10 53400 -3 8501736 h6e3 e7e5 c3e4 a5e1 d1e1 e8b8 e3d4 c5d4
e4f6 g8g7 f6d7 b8b2 d7e5
no 11 94520 -17 15056680 h6e3 e7e5 c3e4 a5e1 d1e1 e8b8 e3d4 c5d4
b2b3 a6b7 e4f6 g8g7 f6d7 b8d8 d7b6
yes 11 277690 -16 43921712 d1d4
Result: Success
Found in: 277690 ms (00:04:37.690)
Movei needs almost 5 minutes to solve the fail high now(it seems that in the
test it ran slightly slower so it did not got it and it can finish depth 11 few
seconds later
depth=11 +0.13 d1d4 c5d4 e1e5 f7f6 e5e6 g8h8 a1e1 a6e2 e6f7 e8g8 f7e7 a8a6 e7e2
d4c3 b2c3 a5c3
Nodes: 48414119 NPS: 159914
Time: 00:05:02.75
without verification search movei can get depth 12 but see nothing
Id: ECM.1295
Fen: r3r1k1/4pp1p/b5pB/q1pP4/3b4/2N4P/PP4P1/R2RQ2K w - - 0 1
Bm: Rxd4
no 10 13730 +2 2116792 h6e3 e7e5 c3e4 a5e1 d1e1 e8b8 e3d4 c5d4
b2b3 b8b6 d5d6 a6b7 e4f6 g8h8 164 216173
no 10 23150 +2 3600940 h6e3 e7e5 c3e4 a5e1 d1e1 e8b8 e3d4 c5d4
b2b3 b8b6 d5d6 a6b7 e4f6 g8h8 275 354437
no 11 55030 -19 8532899 h6e3 e7e5 c3e4 a5e1 d1e1 e8b8 e3d4 c5d4
b2b3 b8d8 h1g1 a6b7 e4f6 g8g7 f6g4 b7d5
g4e5 666 714624
no 11 200200 -19 30666318 h6e3 e7e5 c3e4 a5e1 d1e1 e8b8 e3d4 c5d4
b2b3 b8d8 h1g1 a6b7 e4f6 g8g7 f6g4 b7d5
g4e5 2250 2485690
no 12 273040 -26 41961239 h6e3 e7e5 c3e4 a5e1 d1e1 e8b8 e3d4 c5d4
b2b3 b8d8 e4f6 g8g7 f6g4 a6b7 h1g1 b7d5
g4e5 3007 3298307
Here is comparison of another position and if the solution is correct movei
without verifying detection solves it for the wrong reason
Movei with no verification
Id: ECM.1304
[D]2rbr2k/1pq2ppp/p3bn2/4p1B1/P3P3/2N3Q1/1PP1B1PP/3R1R1K w - - 0 1
Bm: Rxd8
no 10 54620 +2 7938770 g3e3 f6g4 e2g4 e6g4 d1d8 e8d8 g5d8 c8d8
e3g5 g4e6 g2g4
no 10 112520 +2 16728627 g3e3 f6g4 e2g4 e6g4 d1d8 e8d8 g5d8 c8d8
e3g5 g4e6 g2g4
no 11 141190 -6 21063683 g3e3 f6g4 e2g4 e6g4 g5d8 e8d8 d1d8 c8d8
c3d5 c7c4 f1f7 c4c2 f7b7 c2a4
Result: Failure
without verification:
2rbr2k/1pq2ppp/p3bn2/4p1B1/P3P3/2N3Q1/1PP1B1PP/3R1R1K w - - 0 1
Bm: Rxd8
no 10 47380 +2 6646151 g3e3 f6g4 e2g4 e6g4 d1d8 e8d8 g5d8 c8d8
e3g5 g4e6 g2g4 340 861950
no 10 96790 +3 13756903 g3h4
no 10 108240 +2 15433644 g3e3 f6g4 e2g4 e6g4 d1d8 e8d8 g5d8 c8d8
e3g5 g4e6 g2g4 728 2160916
no 11 113490 -6 16225840 g3e3 f6g4 e2g4 e6g4 g5d8 e8d8 d1d8 c8d8
c3d5 c7c4 f1f7 c4c2 f7b7 c2a4 813 2268570
no 11 146850 -5 21240829 h2h3
no 11 157960 +0 22863612 h2h3 c7b6 d1d8 b6d8 g3h4 d8b6 g5f6 g7f6
h4f6 h8g8 f6g5 g8f8 g5h6 f8g8 h6g5 1407
3172121
yes 11 237800 +1 34792125 d1d8
yes 11 241930 +10 35431668 d1d8 c7d8 g3h4 e8g8 f1f6 d8b6 f6e6 f7e6
g5c1 g8f8 h4g5 b6f2 2181 4906295
yes 11 269290 +10 39396996 d1d8 c7d8 g3h4 e8g8 f1f6 d8b6 f6e6 f7e6
g5c1 g8f8 h4g5 b6f2 2299 5510667
yes 12 277430 -2 40659065 d1d8 c7d8 g3h4 h8g8 f1f6 d8b6 h4g3 b6b2
g5h6 g7g6 c3d5 c8c2 2360 5662183
Result: Success
Found in: 237800 ms (00:03:57.800)
When I continue the analysis without verification search I get and movei
changes it's mind at depth 13.
12 -2 88661 127124253 d1d8 c7d8 g3h4 h8g8 f1f6 d8b6 h4g3 b6b2 g5h6 g7g6 c3d5
c8c2
13 -16 91412 131430103 d1d8 c7d8 g3h4 h8g8 f1f6 d8b6 h4g3 b6b2 c3d5 e6d5 e4d5
c8c3 g3g4 c3c2
13 -15 125647 180460345 h2h3
13 0 204584 295468093 h2h3 d8e7 g3h4 c8d8 d1d8 e8d8 g5f6 e7f6 f1f6 g7f6 h4f6
h8g8 f6g5 g8h8 g5f6
Uri
This page took 0.02 seconds to execute
Last modified: Thu, 07 Jul 11 08:48:38 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.