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 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.