root/05/release-0.5g/matchC.cc

Revision 1, 23.3 kB (checked in by ugz, 5 years ago)

Initial repository layout

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