Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: Doesn't appear to work for me (results and positions long)

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.