root/06/devel-old/patternPY.py

Revision 174, 18.3 kB (checked in by ug, 2 years ago)

Worked some more on pattern.cc ... not done yet, though.

Line 
1 # File: patternPY.py
2
3 ##   Copyright (C) 2001-6 Ulrich Goertz (u@g0ertz.de)
4
5 ##   This file is part of Kombilo 0.6, 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 from string import join
24 from array import *
25
26 class Pattern:
27     """
28     A pattern on the go board, which is basically a matrix with coefficients in
29     { 'X', 'O', '.', '*', 'x', 'o' } (black, white, empty, wildcards), plus an 'anchor
30     rectangle', given by the top left and bottom right points.
31
32     left, right, top, bottom: "anchor rectangle"
33     sizeX, sizeY: size of pattern
34     initialData: initial position                                            FIXME
35     contList, lenContList: move sequence data in the following format: ...!
36     moveOne: ?
37     """
38
39
40     def __cmp__(self, p):                    # never returns -1, so this works only for
41                                              # testing for equality
42         if self.sizeX != p.sizeX or self.sizeY != p.sizeY: return 1
43         if self.left != p.left or self.right != p.right or self.top != p.top or self.bottom != p.bottom: return 1
44         if self.moveOne != p.moveOne: return 1
45         for i in range(self.sizeX*self.sizeY):
46             if self.initialPos[i] != p.initialPos[i]: return 1
47         if self.contList != p.contList: return 1
48         return 0
49
50
51 ##     def __repr__(self):
52 ##         """ final position!!! (FIXME?)"""
53 ##         return join(self.data, '')
54
55
56     def BW2XO(self, c):
57         try:
58             return {'B': 'X', 'W': 'O'}[c]
59         except:
60             return c
61
62     def getInitial(self, i, j):
63         return self.initialPos[i + self.sizeX * j]
64
65     def getFinal(self, i, j):
66         return self.finalPos[i + self.sizeX * j]
67        
68
69     def printPattern(self):
70         d = []
71         for j in range(self.sizeY):
72             for i in range(self.sizeX):
73                 d.append(self.initialPos[i+j*self.sizeX])
74             d.append('\n')
75         print join(d, '')
76         print
77         if self.contList:
78             d = []
79             for j in range(self.sizeY):
80                 for i in range(self.sizeX):
81                     d.append(self.finalPos[i+j*self.sizeX])
82                 d.append('\n')
83             print join(d, '')
84             print self.contList
85
86        
87     def getBits(self, b, i):
88         return self.bits[b][i]
89            
90     def __init__(self,
91                  left, right, top, bottom, sizeX, sizeY,
92                  initialPos, contList, lenContList, moveOne):
93         self.flip = 0
94         self.colorSwitch = 0
95         if moveOne in ['B', 'X']: self.moveOne = 'X'
96         else: self.moveOne = 'O'
97         if self.moveOne == 'X': self.moveTwo = 'O'
98         else: self.moveTwo = 'X'
99
100         self.left = left
101         self.top = top
102         self.right = right
103         self.bottom = bottom
104         # self.anchors = [(left, top), (right, bottom)]
105         # self.anchors.sort()               # important for __cmp__ (but already sorted ...)
106
107         self.sizeX = sizeX
108         self.sizeY = sizeY
109
110         self.initialPos = initialPos
111         helpFinalPos = list(initialPos)
112
113         for t in contList.split('/'):
114             if t and ord(t[0]) < sizeX and ord(t[1]) < sizeY:
115                 if t[2] in ['B', 'W']:
116                     # print ord(t[0]), ord(t[1]), t[2]
117                     helpFinalPos[ord(t[0]) + sizeX*ord(t[1])] = self.BW2XO(t[2])
118                 else:
119                     helpFinalPos[ord(t[0]) + sizeX*ord(t[1])] = '.'
120         self.finalPos = join(helpFinalPos, '')
121
122         self.contList = contList
123         self.lenContList = lenContList
124         # self.printPattern()
125         self.bits = [] # list of 4 bit-patterns
126
127         for i in range(2):
128             for j in range(2):
129                 xBlocks = (self.sizeY+i+1)/2
130                 yBlocks = (self.sizeX+j+1)/2
131                 nextBlock = array('B', [yBlocks])
132                 for k1 in range(yBlocks):
133                     nlist = []
134                    
135                     for k2 in range(xBlocks):
136                         n = 0
137                         for x in range(2):
138                             for y in range(2):
139                                 indexX = k1 * 2 + y - j
140                                 indexY = k2 * 2 + x - i
141                                 if 0 <= indexX < self.sizeX and \
142                                    0 <= indexY < self.sizeY:
143                                     if self.getFinal(indexX,indexY)=='X':
144                                         n |= 1 << (2*(2*x+y))
145                                     elif self.getFinal(indexX,indexY)=='O':
146                                         n |= 1 << (2*(2*x+y)+1)
147                         nlist.append(n)
148                        
149                     start, end = 0, len(nlist)
150                     while start < end and not nlist[start]: start += 1
151                     while end > start and not nlist[end-1]: end -= 1
152
153                     nextBlock.append(start)
154                     nextBlock.append(end-start)
155                     for current in range(start, end): nextBlock.append(nlist[current])
156
157                 self.bits.append(nextBlock)
158
159         # self.printPattern()
160
161     flips = []
162     flips.append(lambda x,y, XX, YY: (x,y))
163     flips.append(lambda x,y, XX, YY: (XX-x,y))
164     flips.append(lambda x,y, XX, YY: (x,YY-y))
165     flips.append(lambda x,y, XX, YY: (XX-x,YY-y))
166     flips.append(lambda x,y, XX, YY: (y,x))
167     flips.append(lambda x,y, XX, YY: (YY-y,x))
168     flips.append(lambda x,y, XX, YY: (y,XX-x))
169     flips.append(lambda x,y, XX, YY: (YY-y,XX-x))
170
171
172 def PatternInvFlip(i):
173     return [0,1,2,3,4,6,5,7][i]
174
175
176 class PatternList:
177
178     def __init__(self, pattern, fixedColor, nextMove, boardsize):
179         self.pattern = pattern
180         self.fixedColor = fixedColor
181         self.nextMove = nextMove
182         self.boardsize = boardsize
183         self.data = self.patternList()
184
185
186        
187     def invertColor(self,co):
188         try:
189             return {'X': 'O', 'x': 'o', 'O': 'X', 'o': 'x', '.': '.', '*': '*', 'B':'W', 'W':'B', '-':'-'}[co]
190         except:
191             print 'oops invertColor', co # FIXME
192             return co
193
194        
195     def patternList(self):                     
196        
197         l = []
198         lCS = []
199         symmetries = []
200        
201         special = -1
202        
203         for ii in range(len(Pattern.flips)):
204             f = Pattern.flips[ii]
205             finv = Pattern.flips[PatternInvFlip(ii)]
206            
207 ##             newA = []
208
209 ##             a = [(self.pattern.anchors[0][0],self.pattern.anchors[0][1]),
210 ##                  (self.pattern.anchors[1][0],self.pattern.anchors[0][1]),
211 ##                  (self.pattern.anchors[1][0],self.pattern.anchors[1][1]),
212 ##                  (self.pattern.anchors[0][0],self.pattern.anchors[1][1])]
213             
214 ##             for anchor in a:
215 ##                 extr = [ f(anchor[0], anchor[1], self.boardsize-1, self.boardsize-1),
216 ##                          f(anchor[0]+self.pattern.sizeX-1, anchor[1], self.boardsize-1, self.boardsize-1),
217 ##                          f(anchor[0], anchor[1]+self.pattern.sizeY-1, self.boardsize-1, self.boardsize-1),
218 ##                          f(anchor[0]+self.pattern.sizeX-1, anchor[1]+self.pattern.sizeY-1,
219 ##                            self.boardsize-1, self.boardsize-1) ]
220
221 ##                 extr.sort()
222 ##                 newA.append(extr[0])
223                 
224 ##             newA.sort()
225 ##             newAnchors = [newA[0], newA[3]]
226             
227 ##             newSizeL = [ f(0,0,1,1), f(0,1,1,1) ]
228 ##             newSizeL.sort()
229 ##             if newSizeL[1][0] == newSizeL[0][0]:
230 ##                 newSizeX = self.pattern.sizeX
231 ##                 newSizeY = self.pattern.sizeY
232 ##             else:
233 ##                 newSizeX = self.pattern.sizeY
234 ##                 newSizeY = self.pattern.sizeX
235
236
237             newSizeX = max(f(0,0,self.pattern.sizeX,self.pattern.sizeY)[0],
238                            f(self.pattern.sizeX,self.pattern.sizeY,self.pattern.sizeX,self.pattern.sizeY)[0]);
239             newSizeY = max(f(0,0,self.pattern.sizeX,self.pattern.sizeY)[1],
240                            f(self.pattern.sizeX,self.pattern.sizeY,self.pattern.sizeX,self.pattern.sizeY)[1]);
241
242             newLeft = min(f(self.pattern.left,self.pattern.top,self.boardsize-1,self.boardsize-1)[0],
243                           f(self.pattern.right+self.pattern.sizeX-1,self.pattern.bottom+self.pattern.sizeY-1,
244                             self.boardsize-1,self.boardsize-1)[0])
245             newRight = max(f(self.pattern.left,self.pattern.top,self.boardsize-1,self.boardsize-1)[0],
246                            f(self.pattern.right+self.pattern.sizeX-1,self.pattern.bottom+self.pattern.sizeY-1,
247                              self.boardsize-1,self.boardsize-1)[0]) - (newSizeX-1)
248             newTop = min(f(self.pattern.left,self.pattern.top,self.boardsize-1,self.boardsize-1)[1],
249                          f(self.pattern.right+self.pattern.sizeX-1,self.pattern.bottom+self.pattern.sizeY-1,
250                            self.boardsize-1,self.boardsize-1)[1])
251             newBottom = max(f(self.pattern.left,self.pattern.top,self.boardsize-1,self.boardsize-1)[1],
252                             f(self.pattern.right+self.pattern.sizeX-1,self.pattern.bottom+self.pattern.sizeY-1,
253                               self.boardsize-1,self.boardsize-1)[1]) - (newSizeY - 1)
254
255             # print self.pattern.sizeX, self.pattern.sizeY, newSizeX, newSizeY
256
257             newPd = {}
258            
259             for i in range(self.pattern.sizeX):
260                 for j in range(self.pattern.sizeY):
261                     newPd[f(i,j, self.pattern.sizeX-1, self.pattern.sizeY-1)] = self.pattern.getInitial(i, j)
262
263             cl = self.pattern.contList.split('/')
264             # for c in cl:
265             #     if c: print ord(c[0]), ord(c[1]), c[2]
266             ncl =[chr(f(ord(t[0]),ord(t[1]),self.pattern.sizeX-1,self.pattern.sizeY-1)[0]) +\
267                   chr(f(ord(t[0]),ord(t[1]),self.pattern.sizeX-1,self.pattern.sizeY-1)[1]) + t[2] + '/'\
268                   for t in cl if t]
269             # for c in ncl:
270             #     if c: print ord(c[0]), ord(c[1]), c[2]
271             newContList = join(ncl, '')
272
273             npdl = []
274
275             for j in range(newSizeY):
276                 for i in range(newSizeX):
277                     npdl.append(newPd[(i,j)])
278             newPdString = join(npdl, '')
279                              
280             pNew = Pattern(newLeft, newRight, newTop, newBottom,
281                            newSizeX, newSizeY,
282                            newPdString, newContList, self.pattern.lenContList, self.pattern.moveOne)
283             pNew.flip = ii
284
285             if not pNew in l:
286                 l.append(pNew)
287                 # print 'ACCEPTED'
288             if pNew == self.pattern: symmetries.append((ii,0))
289  
290             if self.nextMove or not self.fixedColor:
291                 newPd1 = {}
292                 for i in range(self.pattern.sizeX):
293                     for j in range(self.pattern.sizeY):
294                         newPd1[f(i,j, self.pattern.sizeX-1, self.pattern.sizeY-1)] \
295                                       = self.invertColor(self.pattern.getInitial(i, j))
296                 npdl = []
297
298                 for j in range(newSizeY):
299                     for i in range(newSizeX):
300                         npdl.append(newPd1[(i,j)])
301                 newPd1String = join(npdl, '')
302                        
303                 newContList1 = join([t[0]+t[1]+self.invertColor(t[2])+'/' for t in ncl], '')
304                
305                 pNew1 = Pattern(newLeft, newRight, newTop, newBottom,
306                                 newSizeX, newSizeY,
307                                 newPd1String, newContList1, self.pattern.lenContList, self.pattern.moveTwo)
308                 pNew1.flip = ii
309                 pNew1.colorSwitch = 1
310
311                 if not self.fixedColor and not pNew1 in lCS:
312                     lCS.append(pNew1)
313                     # print 'ACCEPTED CS'
314                 if pNew1 == self.pattern:
315                     if not self.fixedColor: symmetries.append((ii,1))
316                     if self.nextMove: special = ii
317                    
318         for p in lCS:
319             if not p in l: l.append(p)
320        
321         # compute symmetries
322         
323         symm = {}
324         for i in range(self.pattern.sizeX):
325             for j in range(self.pattern.sizeY):
326                 symm[(i,j)] = ((i,j),0)   
327
328         for s, c in symmetries:
329             symm1 = {}
330             for i in range(self.pattern.sizeX):
331                 for j in range(self.pattern.sizeY):
332                     if (i,j) != Pattern.flips[s](i,j,self.pattern.sizeX-1,self.pattern.sizeY-1) \
333                        and not symm1.has_key(Pattern.flips[s](i,j,self.pattern.sizeX-1,self.pattern.sizeY-1)):
334                         symm1[(i,j)] = (Pattern.flips[s](i,j,self.pattern.sizeX-1,self.pattern.sizeY-1), c)
335  
336             for k in symm.keys():
337                 if symm1.has_key(symm[k][0]):
338                     if (symm1[symm[k][0]][1] or symm[k][1]) and \
339                        not (symm1[symm[k][0]][1] and symm[k][1]):
340                         cs = 1
341                     else: cs = 0
342                     symm[k] = symm1[symm[k][0]][0], cs
343
344         if special == -1:
345             symm[-1] = -1
346         else:
347             symm[-1] = PatternInvFlip(special)
348             # if there is a flip f such that color_swap(f(pattern)) == pattern,
349             # then this is stored as symm[-1]
350             # this is needed to get the continuation symmetries right when the
351             # color of the next move is fixed
352
353         self.symmetries = symm
354         return l
355
356
357     def get(self, i):
358         """ return final pattern of move sequence"""
359         return self.data[i]
360
361
362     def size(self):
363         return len(self.data)
364
365
366     def updateContinuations(self, index, x, y, co, Xint0, Xint1, Yint0, Yint1,
367                             foundWhere, counter,
368                             continuations, contLabels, contLabelsIndex,
369                             winner):
370
371         xx, yy = Pattern.flips[PatternInvFlip(self.data[index].flip)](x, y, self.boardsize-1, self.boardsize-1)
372                                
373         XX1, YY1 = Pattern.flips[PatternInvFlip(self.data[index].flip)](Xint0, Yint0,
374                                                                         self.boardsize-1, self.boardsize-1)
375         XX2, YY2 = Pattern.flips[PatternInvFlip(self.data[index].flip)](Xint1-1, Yint1-1,
376                                                                         self.boardsize-1, self.boardsize-1)
377         XX = min(XX1, XX2)
378         YY = min(YY1, YY2)
379                                
380         xx -= XX
381         yy -= YY
382                      
383         if (self.data[index].colorSwitch and co == 'X') or \
384            (not self.data[index].colorSwitch and co == 'O'):
385             cc = 'B'
386         else: cc = 'W'
387
388         (xx, yy), cSymm = self.symmetries[(xx,yy)]
389
390         if (cc == 'B' and not cSymm) or (cc=='W' and cSymm): cc = 'B'
391         else: cc = 'W'
392
393         if self.nextMove:
394             if ((self.nextMove == 2 and cc == 'B') \
395                 or (self.nextMove == 1 and cc == 'W')):
396                 if self.symmetries[-1] != -1 and not self.fixedColor:
397
398                     if cc == 'B': cc='W'
399                     else: cc = 'B'
400        
401                     xx += XX
402                     yy += YY
403
404                     xx, yy = Pattern.flips[self.symmetries[-1]](xx, yy, self.boardsize-1, self.boardsize-1)
405                                    
406                     XX1, YY1 = Pattern.flips[self.symmetries[-1]](XX1, YY1,self.boardsize-1, self.boardsize-1)
407                     XX2, YY2 = Pattern.flips[self.symmetries[-1]](XX2, YY2,self.boardsize-1, self.boardsize-1)
408
409                     XX = min(XX1, XX2)
410                     YY = min(YY1, YY2)
411
412                     xx -= XX
413                     yy -= YY                                   
414                                    
415                     (xx1, yy1), cSymm1 = self.symmetries[(xx,yy)]
416                     if not cSymm1:
417                         xx, yy = xx1, yy1
418
419                     colorSwitch = 1-cSymm
420                     # if colorSwitch: numOfSwitched += 1
421                 else:
422                     return 0,0,0,0 # not a hit!
423             else:
424                 colorSwitch = cSymm
425                 # if colorSwitch: numOfSwitched += 1
426         else:
427             colorSwitch = cSymm
428
429         if continuations.has_key((xx, yy)):
430             continuations[(xx,yy)][cc] = continuations[(xx,yy)][cc]+1
431         else:
432             if contLabelsIndex >= len(contLabels): text = '?'
433             else:
434                 text = contLabels[contLabelsIndex]
435                 contLabelsIndex += 1
436             if cc == 'B':
437                 continuations[(xx,yy)] = {'B':1, 'W':0,       # B/W continuations at this point
438                                           'tB':0, 'tW':0,     # tenukis among the above
439                                           'wB':0,'lB':0,'wW':0,'lW':0, # B wins/losses among BW continuations
440                                           'N': text}
441             else:
442                 continuations[(xx,yy)] = {'B':0, 'W':1, 'tB':0, 'tW':0, 'wB':0, 'lB':0,
443                                           'wW':0, 'lW':0, 'N': text}
444                          
445             if not foundWhere in [counter, counter+1]:
446                 continuations[(xx,yy)]['t'+cc] += 1
447
448             if winner == 'B':
449                 if not (self.data[index].colorSwitch or colorSwitch):
450                     continuations[(xx,yy)]['w'+cc] += 1
451                 else:
452                     continuations[(xx,yy)]['l'+cc] += 1
453             elif winner == 'W':
454                 if not (self.data[index].colorSwitch or colorSwitch):
455                     continuations[(xx,yy)]['l'+cc] += 1
456                 else:
457                     continuations[(xx,yy)]['w'+cc] += 1
458
459         return 1, continuations[(xx,yy)]['N'], contLabelsIndex, (self.data[index].colorSwitch or colorSwitch)
460    
Note: See TracBrowser for help on using the browser.