root/04/bugfix/matchC.cc

Revision 21, 20.4 kB (checked in by ug, 5 years ago)

Import release 0.4d

Line 
1#include <Python.h>
2
3void invert(char *s) {
4  int c,i,j;
5  for (i=0,j=strlen(s)-1;i<j;i++,j--) {
6    c=s[i];
7    s[i]=s[j];
8    s[j]=c;
9  }
10}
11
12char* itoa(int n) {             // convert a non-negative integer to a char*
13  char *s = new char[15];
14  int i;
15 
16  i=0;
17  do { s[i++] = n%10+'0';
18  } while ((n/=10)>0);
19 
20  s[i]='\0';
21  invert(s);
22  return s;
23}
24
25
26bool greater(long* a, unsigned long i, unsigned long j) {
27  if (a[2*i]>a[2*j] || (a[2*i]==a[2*j] && a[2*i+1]>a[2*j+1])) return true;
28  return false;
29}
30
31void swap(long* a, unsigned long i, unsigned long j) {
32  long help1, help2;
33
34  help1 = a[2*i];
35  help2 = a[2*i+1];
36  a[2*i] = a[2*j];
37  a[2*i+1] = a[2*j+1];
38  a[2*j] = help1;
39  a[2*j+1] = help2;
40}
41
42
43void sortCArray(long* a, long l, long r) {
44
45  long left, right, li11;
46
47  long stack[250];
48  stack[0] = l;
49  stack[1] = r;
50  unsigned char stackIndex = 1;
51
52  long help1, help2;
53
54  while (stackIndex) {
55    if (r > l) {
56      if (r-l == 1) {
57        if (greater(a, l, r)) swap(a, l, r);
58       
59        stackIndex--;
60        l = stack[2*stackIndex];
61        r = stack[2*stackIndex+1];
62
63      } else {
64
65        if (greater(a, (r+l)/2, l)) {
66          if (greater(a, l, r)) li11 = l;
67          else { 
68            if (greater(a, r, (r+l)/2)) li11 = (r+l)/2;
69            else li11 = r;
70          } 
71        } else {
72          if (greater(a, (r+l)/2, r)) li11 = (r+l)/2;
73          else {
74            if (greater(a, r, l)) li11 = l;
75            else li11 = r;
76          }
77        }
78
79        swap(a, li11, r);
80        help1 = a[2*r];
81        help2 = a[2*r+1];
82       
83        left = l;
84        right = r-1;
85       
86        while (1) { 
87          while (a[2*left] < help1 || (a[2*left]==help1 && a[2*left+1]<help2)) left++;
88          while (a[2*right] > help1 || (a[2*right]==help1 && a[2*right+1]>help2)) right--;
89         
90          if (right <= left) break;
91         
92          swap(a, left, right);
93         
94          left++;
95          right--;
96        }
97
98        swap(a, left, r);
99
100        if (left-l > r-left) {
101            stack[2*stackIndex] = l;
102            stack[2*stackIndex+1] = left-1;
103            stackIndex++;
104          l = left+1;
105        } else {
106            stack[2*stackIndex] = left+1;
107            stack[2*stackIndex+1] = r;
108            stackIndex++;
109          r = left-1;
110        } 
111      }
112    } else {
113      stackIndex--;
114      l = stack[2*stackIndex];
115      r = stack[2*stackIndex+1];
116    }
117  }
118}
119
120static const int COLORSWITCH = 1024;
121
122static char flipX(char flipNO, char x, char y) {
123  if (flipNO==0) return x;
124  if (flipNO==1) return 18-x;
125  if (flipNO==2) return x;
126  if (flipNO==3) return 18-x;
127  if (flipNO==4) return y;
128  if (flipNO==5) return 18-y;
129  if (flipNO==6) return y;
130  if (flipNO==7) return 18-y;
131}
132
133static char flipY(char flipNO, char x, char y) {
134  if (flipNO==0) return y;
135  if (flipNO==1) return y;
136  if (flipNO==2) return 18-y;
137  if (flipNO==3) return 18-y;
138  if (flipNO==4) return x;
139  if (flipNO==5) return x;
140  if (flipNO==6) return 18-x;
141  if (flipNO==7) return 18-x;
142}
143
144static PyObject* match(PyObject* self, PyObject* args) {
145  int noPatterns;
146  char *Patterns;
147  char *PSize;
148  char *PInvFlips;
149  char *PColorSwitch;
150  char *PAnchors;
151  unsigned long *PBitsTable;
152  unsigned char *PBits;
153  unsigned char *fp;
154  unsigned char *mainlist;
155  unsigned long *posTable;
156
157  unsigned long *hashIndices;
158  unsigned char *hash;
159
160  char* contLabels;
161
162  int PCSlength, PAlength, PBTlength, PBlength, fplength, MLlength, PTlength, HLlength,
163    hashIlength, hashlength, contLabelsLength, contLabelsIndex,
164    showColorSwitch;
165  int moveLimit;
166  unsigned long* helplist;
167
168  PyObject *progBarUpdate;
169  PyObject *continuations;
170  PyObject *symmetries;
171  PyObject *dbData;
172  float pB_start, pB_end;
173
174  if (!PyArg_ParseTuple(args, "sss#s#s#s#s#is#s#s#s#s#s#Offs#iOOOi", &Patterns, &PSize, 
175                        &PInvFlips, &noPatterns, &PColorSwitch, &PCSlength,
176                        &PAnchors, &PAlength, &PBitsTable, &PBTlength, &PBits, &PBlength, &moveLimit,
177                        &helplist, &HLlength, &fp, &fplength, 
178                        &mainlist, &MLlength, &posTable, &PTlength,
179                        &hashIndices, &hashIlength, &hash, &hashlength,
180                        &progBarUpdate, &pB_start, &pB_end,
181                        &contLabels, &contLabelsLength, &contLabelsIndex,
182                        &continuations, &symmetries, &dbData,
183                        &showColorSwitch))
184      return NULL; 
185
186  HLlength /= sizeof(unsigned long);
187
188  int foundgamesSize = 5000;
189  int unsigned long *foundgames = PyMem_New(unsigned long, foundgamesSize);    // stored here: no. of found game
190  int foundgamesIndex=0;
191
192  PyObject *result = PyList_New(0);
193
194  int Bwins = 0;
195  int Wwins = 0;
196  int noSwitched = 0;
197  int noMatchesFinal = 0;
198
199  int patternSize = PSize[0] * PSize[1];
200
201  unsigned long* hashInd = new unsigned long[noPatterns];
202  if (hashIlength) {
203    for(int i=0; i<noPatterns; i++) hashInd[i] = hashIndices[2*i];     // set hashInd to hash_start's
204  }
205
206  for(int game=0; game < HLlength; game++) {
207
208    if (game % 600 == 0) {     
209      float percent = game * (pB_end - pB_start) / HLlength + pB_start;
210      PyObject* arglist = Py_BuildValue("(f)", percent);
211      PyEval_CallObject(progBarUpdate, arglist);
212      Py_DECREF(arglist);
213    }
214
215    unsigned long index = helplist[game];
216
217    char matchlist[13000];
218    int matchlistIndex = 0;
219
220    for(char N=0; N<noPatterns; N++) {           
221
222      if (hashIlength) {
223        while ((hashInd[N]+1<hashIndices[2*N+1]) && (index > 256*hash[hashInd[N]] + hash[hashInd[N]+1])) hashInd[N]+=2;
224        if (index < 256*hash[hashInd[N]] + hash[hashInd[N]+1]) continue;
225        if (index == 256*hash[hashInd[N]] + hash[hashInd[N]+1]) {
226          hashInd[N] += 2;
227          matchlist[matchlistIndex++] = N;
228          matchlist[matchlistIndex++] = PAnchors[4*N];
229          matchlist[matchlistIndex++] = PAnchors[4*N+1];
230        }
231      }
232      else {
233       
234        char a00 = PAnchors[4*N];
235        char a01 = PAnchors[4*N+1];
236        char a10 = PAnchors[4*N+2];
237        char a11 = PAnchors[4*N+3];
238       
239        for(char a0=a00; a0 <= a10; a0++) 
240          for(char a1=a01; a1 <= a11; a1++) {
241           
242            int matches = 1;
243           
244            int pIndex = 2*(a1%2) + (a0%2);
245            int patternBits = PBitsTable[N*4 + pIndex];
246           
247            int pbIndex = 0;
248            int fpIndex = index*150 + a1/2 + (a0/2)*10;
249           
250            for(int x=0; x < PBits[patternBits]; x++) {
251             
252              int start = PBits[patternBits + ++pbIndex];
253              int length = PBits[patternBits + ++pbIndex];
254              fpIndex += start;
255             
256              for(int y=0; y<length; y++) {
257                pbIndex++;
258               
259                if (PBits[patternBits+pbIndex] & fp[fpIndex]) {
260                  matches = 0;
261                  break;
262                }
263               
264                fpIndex++;
265              }
266              if (!matches) break;
267              fpIndex += 10 - start - length;
268             
269            }
270           
271            if (matches) { 
272              matchlist[matchlistIndex++] = N;
273              matchlist[matchlistIndex++] = a0;
274              matchlist[matchlistIndex++] = a1;
275            }
276           
277          }
278      }
279    }
280   
281    if (matchlistIndex) {    /* checkCandidate */
282
283      int noMatches = matchlistIndex/3;
284      int toBeFound = noMatches;       
285      long noCurrentResults = 0;
286      long *currentResults = new long[noMatches*2];
287 
288      char *dicts = new char[noMatches * patternSize];
289      int *dictsNO = new int[noMatches];
290         
291      int *found = new int[noMatches];
292         
293      char *Xinterv = new char[2*noMatches];
294      char *Yinterv = new char[2*noMatches];
295         
296      for(int m=0; m<noMatches; m++) {
297             
298        found[m] = -1;
299        dictsNO[m] = 0;
300             
301        int sizeX = PSize[2*matchlist[3*m]];
302        int sizeY = PSize[2*matchlist[3*m]+1];
303        int Poffset = matchlist[3*m] * patternSize;
304             
305        for(int i=0; i < sizeX; i++) {
306          for(int j=0; j < sizeY; j++) {
307            if (Patterns[Poffset + sizeY*i + j] == '.')
308              dicts[m*patternSize+i*sizeY+j] = ' ';
309            else {
310              dicts[m*patternSize+i*sizeY+j] = Patterns[Poffset + sizeY*i + j];
311              if (Patterns[Poffset + sizeY*i + j] != '*') dictsNO[m]++;
312            }                   
313          }
314        }
315       
316        Xinterv[2*m] = matchlist[3*m+1];
317        Xinterv[2*m+1] = matchlist[3*m+1] + PSize[2*matchlist[3*m]];
318        Yinterv[2*m] = matchlist[3*m+2];
319        Yinterv[2*m+1] = matchlist[3*m+2] + PSize[2*matchlist[3*m]+1];
320      }
321
322      int movelistIndex = posTable[index]+2;
323     
324      int caplistIndex = movelistIndex;
325      while (mainlist[caplistIndex] != 'z') caplistIndex++;
326      int mlLength = caplistIndex;
327     
328      if (mainlist[caplistIndex+2] == 'z') caplistIndex +=2; // caplist empty
329      else caplistIndex += 3;
330     
331      /* AB's */
332     
333      if (mainlist[movelistIndex] == 25 && mainlist[movelistIndex+1] == 3) {
334        movelistIndex += 2;
335        while (mainlist[movelistIndex] != 25) {
336          char x = mainlist[movelistIndex++];
337          char y = mainlist[movelistIndex++];
338         
339          for (int m=0; m<noMatches; m++) {
340            if (found[m] != -2) {
341              if (Xinterv[2*m] <= x && x < Xinterv[2*m+1] &&
342                  Yinterv[2*m] <= y && y < Yinterv[2*m+1]) {     /* stone played in */
343                /* relevant region */
344                if (dicts[m*patternSize+(x-matchlist[3*m+1])*PSize[2*matchlist[3*m]+1]+y-matchlist[3*m+2]]==' ') {
345                 
346                  if (!(fp[index*150 + 100 + y/4 + 5*(x/2)] & (1 << (x%2 + 2*(y%4))))) { 
347                    // this m can't become a match
348                    found[m] = -2;
349                    toBeFound--;
350                    continue;
351                  }
352                  else {
353                    dicts[m*patternSize+(x-matchlist[3*m+1])*PSize[2*matchlist[3*m]+1]+y-matchlist[3*m+2]] = '.';
354                    dictsNO[m]++;
355                  }
356                }
357                else if (dicts[m*patternSize+(x-matchlist[3*m+1])*PSize[2*matchlist[3*m]+1]
358                              +y-matchlist[3*m+2]] == 'X') {
359                  dicts[m*patternSize+(x-matchlist[3*m+1])*PSize[2*matchlist[3*m]+1]+y-matchlist[3*m+2]]=' ';
360                  dictsNO[m]--;
361                }
362              }
363            }
364          }
365        }
366      }
367     
368      /* AW's */
369     
370      if (mainlist[movelistIndex] == 25 && mainlist[movelistIndex+1] == 4) {
371        movelistIndex += 2;
372        while (mainlist[movelistIndex] != 25) {
373          char x = mainlist[movelistIndex];
374          char y = mainlist[movelistIndex+1];
375          movelistIndex += 2;
376         
377          int m;
378          for (m=0; m<noMatches; m++) {
379            if (found[m]!= -2) {
380              if (Xinterv[2*m] <= x && x < Xinterv[2*m+1] &&
381                  Yinterv[2*m] <= y && y < Yinterv[2*m+1]) {     
382                if (dicts[m*patternSize+(x-matchlist[3*m+1])*PSize[2*matchlist[3*m]+1]+y-matchlist[3*m+2]]==' ') {
383                  if (!(fp[index*150 + 100 + y/4 + 5*(x/2)] & (1 << (x%2 + 2*(y%4))))) {           
384                    // this m can't become a match
385                    found[m] = -2;
386                    toBeFound--;
387                    continue;
388                  }
389                  else {
390                    dicts[m*patternSize+(x-matchlist[3*m+1])*PSize[2*matchlist[3*m]+1]+y-matchlist[3*m+2]] = '.';
391                    dictsNO[m]++;
392                  }
393                }
394                else if (dicts[m*patternSize+(x-matchlist[3*m+1])*PSize[2*matchlist[3*m]+1]
395                              +y-matchlist[3*m+2]] == 'O') {
396                  dicts[m*patternSize+(x-matchlist[3*m+1])*PSize[2*matchlist[3*m]+1]+y-matchlist[3*m+2]]=' ';
397                  dictsNO[m]--;
398                }
399              }
400            }
401          }
402        }
403      }
404     
405      for(int m=0; m<noMatches; m++)
406        if (found[m]==-1 && !dictsNO[m]) found[m] = 0;       
407     
408      /* B's and W's */
409     
410      char co;
411     
412      if (mainlist[movelistIndex+1] == 1) co = 'B';
413      if (mainlist[movelistIndex+1] == 2) co = 'W';
414     
415      int mLimit;
416     
417      if (moveLimit == 250) mLimit = 1500 + movelistIndex;         // practically no limit
418      else mLimit = 2*moveLimit + movelistIndex;
419     
420      int counter = -1;
421      char c;
422      char cinv;
423     
424      while (movelistIndex < mlLength-2 && movelistIndex < mLimit) {
425       
426        movelistIndex += 2;
427        counter++;
428       
429        if (co == 'B') {
430          co = 'W';
431          c = 'X';
432          cinv = 'O';
433        } else {
434          co = 'B';
435          c = 'O';
436          cinv = 'X';
437        }
438       
439        char x = mainlist[movelistIndex];
440        char y = mainlist[movelistIndex+1];
441       
442        int clI = 0;
443        int clIend = 0;
444       
445        if (mainlist[caplistIndex] != 'z' && counter == 256*mainlist[caplistIndex] + mainlist[caplistIndex+1]) {
446          caplistIndex += 2;
447          clI = caplistIndex;
448          while (mainlist[caplistIndex] != 'z' && mainlist[caplistIndex] != 'y') caplistIndex++;
449          clIend = caplistIndex-1;
450          caplistIndex++;
451        } 
452       
453        for(int m=0; m<noMatches; m++) {
454
455          if (found[m] != -2) {
456
457            if (Xinterv[2*m] <= x && x < Xinterv[2*m+1] &&
458                Yinterv[2*m] <= y && y < Yinterv[2*m+1]) {
459             
460              if (found[m] > -1) {
461
462                int f = PInvFlips[matchlist[3*m]];
463                char xx = flipX(f, x, y);
464                char yy = flipY(f, x, y);
465               
466                char XX1 = flipX(f, Xinterv[2*m], Yinterv[2*m]);
467                char YY1 = flipY(f, Xinterv[2*m], Yinterv[2*m]);
468               
469                char XX2 = flipX(f, Xinterv[2*m+1]-1, Yinterv[2*m+1]-1);
470                char YY2 = flipY(f, Xinterv[2*m+1]-1, Yinterv[2*m+1]-1);
471               
472                char XX = XX1 < XX2 ? XX1 : XX2;
473                char YY = YY1 < YY2 ? YY1 : YY2;
474               
475                xx -= XX;
476                yy -= YY;
477               
478                char *cc, *wcc, *lcc, *tcc;
479                if ((PColorSwitch[matchlist[3*m]] && co == 'B') ||
480                    (!PColorSwitch[matchlist[3*m]] && co == 'W'))
481                  cc = "B";
482                else cc = "W";
483               
484                PyObject *key = Py_BuildValue("ii", xx, yy);
485                PyObject *t = PyDict_GetItem(symmetries, key);
486                Py_DECREF(key);
487
488                PyObject *xxyy = PyTuple_GetItem(t, 0);
489                long c = PyInt_AsLong(PyTuple_GetItem(t, 1));
490
491                if ((strcmp(cc, "W")==0 && !c) || (strcmp(cc, "B")==0 && c)) {
492                  cc = "W";
493                  wcc = "wW";
494                  lcc = "lW";
495                  tcc = "tW";
496                }
497                else {
498                  cc = "B";
499                  wcc = "wB";
500                  lcc = "lB";
501                  tcc = "tB";
502                }
503
504                char text;
505                PyObject* scxy;
506
507                if (scxy = PyDict_GetItem(continuations, xxyy)) {
508                  PyObject *temp = PyInt_FromLong(PyInt_AsLong(PyDict_GetItemString(scxy, cc))+1);
509                  PyDict_SetItemString(scxy, cc, temp);
510                  Py_DECREF(temp);
511                  text = PyString_AsString(PyDict_GetItemString(scxy, "N"))[0];
512                }
513                else {
514                  if (contLabelsIndex >= contLabelsLength) text = '?';
515                  else text = contLabels[contLabelsIndex++];
516                 
517                  if (strcmp(cc, "B")==0) {
518                    scxy = PyDict_New();
519                    PyObject* Py0 = PyInt_FromLong(0);
520                    PyObject *Py1 = PyInt_FromLong(1);
521                    PyDict_SetItemString(scxy, "B", Py1);
522                    PyDict_SetItemString(scxy, "W", Py0);
523                    PyDict_SetItemString(scxy, "tB", Py0);
524                    PyDict_SetItemString(scxy, "tW", Py0);
525                    PyDict_SetItemString(scxy, "wB", Py0);
526                    PyDict_SetItemString(scxy, "lB", Py0);
527                    PyDict_SetItemString(scxy, "wW", Py0);
528                    PyDict_SetItemString(scxy, "lW", Py0);
529                    PyDict_SetItemString(scxy, "N", PyString_FromStringAndSize(&text, 1));
530                    Py_DECREF(Py0);
531                    Py_DECREF(Py1);
532                    PyDict_SetItem(continuations, xxyy, scxy);
533                    Py_DECREF(scxy);
534                  }
535                  else {
536                    scxy = PyDict_New();
537                    PyObject *Py0 = PyInt_FromLong(0);
538                    PyObject *Py1 = PyInt_FromLong(1);
539                    PyDict_SetItemString(scxy, "B", Py0);
540                    PyDict_SetItemString(scxy, "W", Py1);
541                    PyDict_SetItemString(scxy, "tB", Py0);
542                    PyDict_SetItemString(scxy, "tW", Py0);
543                    PyDict_SetItemString(scxy, "wB", Py0);
544                    PyDict_SetItemString(scxy, "lB", Py0);
545                    PyDict_SetItemString(scxy, "wW", Py0);
546                    PyDict_SetItemString(scxy, "lW", Py0);
547                    PyDict_SetItemString(scxy, "N", PyString_FromStringAndSize(&text, 1));
548                    Py_DECREF(Py0);
549                    Py_DECREF(Py1);
550                    PyDict_SetItem(continuations, xxyy, scxy);
551                    Py_DECREF(scxy);
552                  }
553                }
554
555                PyObject *d1 = PyList_GetItem(dbData, index);
556
557                if (!PyTuple_Check(d1)) return NULL;
558
559                PyObject *d2 = PyTuple_GetItem(d1, 4);
560                if (!PyString_Check(d2)) return NULL;
561
562                char* winner = PyString_AsString(d2);
563
564                if (winner[0] == 'B')
565                  if (!(PColorSwitch[matchlist[3*m]] || c)) {
566                    PyObject *temp = PyInt_FromLong(PyInt_AsLong(PyDict_GetItemString(scxy, wcc))+1);
567                    PyDict_SetItemString(scxy, wcc, temp);
568                    Py_DECREF(temp);
569                    Bwins++;
570                  }
571                  else {
572                    PyObject *temp = PyInt_FromLong(PyInt_AsLong(PyDict_GetItemString(scxy, lcc))+1);
573                    PyDict_SetItemString(scxy, lcc, temp);
574                    Py_DECREF(temp);
575                    Wwins++;
576                  }
577                if (winner[0] == 'W')
578                  if (!(PColorSwitch[matchlist[