root/06/devel-old/algosPY.py

# File: algosPY.py

##   Copyright (C) 2001-6 Ulrich Goertz (u@g0ertz.de)

##   This file is part of Kombilo 0.6, a go database program.

##   This program is free software; you can redistribute it and/or modify
##   it under the terms of the GNU General Public License as published by
##   the Free Software Foundation; either version 2 of the License, or
##   (at your option) any later version.

##   This program is distributed in the hope that it will be useful,
##   but WITHOUT ANY WARRANTY; without even the implied warranty of
##   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
##   GNU General Public License for more details.

##   You should have received a copy of the GNU General Public License
##   along with this program (see doc/license.txt); if not, write to the Free Software
##   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
##   The GNU GPL is also currently available at
##   http://www.gnu.org/copyleft/gpl.html

import os
from array import *
from string import lower, join
from copy import copy, deepcopy

class AlgoError(Exception): pass

def BW2XO(c):
    try:
        return {'B': 'X', 'W': 'O'}[c]
    except:
        return c



class Hit:
    def __init__(self, counter, labelStr, where=None):
        self.counter = counter
        self.labelStr = labelStr
        self.where = where

    def moveno(self):
        if self.where:
            # print self.where
            return self.where
        else:
            print 'no where'
            if labelStr[-1]=='-':
                return [int(labelstr[:-1])]
            else:
                return [int(labelStr)]

    def output(self):
        if not self.where: return '/' + self.labelStr
        if len(self.where) == 1: return str(self.where[0]) + self.labelStr
        m = 0
        i = 0
        while i < len(self.where):
            if i%2: m += 1
            else: m += self.where[i]
            i += 1
        return 'V' + str(m) + self.labelStr


class Algorithm: # virtual
    """
    This class is a prototype for search algorithms for Kombilo.

    Two parts:

     * processing: react to events during the processing

     * search: do a search

    Two types of algorithms (first-stage, second-stage):

    The first type builds a list of candidates, for example by using hash tables,
    or by looking at the final position of the game.

    The second type checks which of the candidates are actual hits.
    
    ... FIXME
    """

    def __init__(self, boardsize): pass

    def initialize_process(self):
        """ Start of database. """
        pass

    def newgame_process(self):
        """ New game. """
        pass
    
    def AB_process(self, x, y): pass

    def AW_process(self, x, y): pass

    def AE_process(self, x, y, removed): pass

    def endOfNode_process(self): pass

    def B_process(self, counter, x, y, cap): pass

    def W_process(self, counter, x, y, cap): pass

    def branchpoint_process(self): pass

    def endOfVariation_process(self): pass

    def endgame_process(self): pass
        
    def finalize_process(self, datap):
        """ End of database. """
        pass

    filelist = [] # List of the names of the files written to disk by this algorithm.

    # ---------------------------------------------------------------

    def search(self, patternList, options, gamelist, matchlist): pass 

# ------------------------------------------------------------------------------------------

class Algo_finalpos(Algorithm):
    """
    This algorithm decides if the current game could possibly contain the search pattern,
    by looking at the final position of the game. It then creates a list of candidates,
    i.e. pairs describing an orientation and an anchor of the search pattern such that a
    hit for that particular combination is possible in view of the final position.

    The final position is stored in a bit-array, in order to reduce the number of comparison
    needed to check for a search pattern.
    """

    def __init__(self, boardsize):
        pass

    def initialize_process(self, l):
        """ Start of database. """
        self.finalpos = array('B')

    def newgame_process(self):
        """ New game. """
        self.fp = array('B', [255] * 100)   # '20x20x2 bit-array', in the end 00 means: B, W at some time,
                                            #                                 01 = never B, but W ...

    def AB_process(self, x, y):
        self.fp[y/2 + 10*(x/2)] &= ~(1 << (2*(x%2 + 2*(y%2))))

    def AW_process(self, x, y):
        self.fp[y/2 + 10*(x/2)] &= ~(1 << (2*(x%2 + 2*(y%2))+1))

    def AE_process(self, x, y, removed):
        pass

    def endOfNode_process(self):
        pass

    def B_process(self, x, y, cap):
        self.fp[y/2 + 10*(x/2)] &= ~(1 << (2*(x%2 + 2*(y%2))))

    def W_process(self, x, y, cap):
        self.fp[y/2 + 10*(x/2)] &= ~(1 << (2*(x%2 + 2*(y%2))+1))

    def branchpoint_process(self):
        pass

    def endOfVariation_process(self):
        pass

    def endgame_process(self):
        self.finalpos.extend(self.fp)

    def finalize_process(self, datap):
        """ End of database. """

        file = open(os.path.join(datap[0], 'finalpos'+ datap[1] + '.db'), 'wb')
        self.finalpos.tofile(file)
        file.close()

    filelist = ['finalpos']

    # ---------------------------------------------------------------

    def duplicateCheck(self, sli, datapath=None):
        if datapath is None:
            if self.finalpos[sli*100:sli*100+100] == self.fp: return 1
            else: return 0

        if not self.currentDatap == datap:
            self.currentDatap = datap
            self.currentFP = array('B')
            try:
                file = open(os.path.join(datap[0], 'finalpos'+datap[1]+'.db'), 'rb')
                while 1:
                    try: self.currentFP.fromfile(file, 1000000)
                    except EOFError: break
                file.close()
            except: return 0
            
        if self.currentFP[sli*100:sli*100+100] == self.fp: return 1
        else: return 0

    # ---------------------------------------------------------------

    def retrieve_db(self, datap):
        try:
            self.finalpos = array('B')
            filelist = [(self.finalpos, 'finalpos')]
            for var, filename in filelist:
                file = open(os.path.join(datap[0], filename+datap[1]+'.db'), 'rb')
                while 1:
                    try: var.fromfile(file, 1000000)
                    except EOFError: break
                file.close()
            return 1
        except IOError:
            return 0


    def search(self, patternList, options, db, progBar, progStart, progEnd):

        print 'algo-finalpos start'
        ctr = 0

        possiblePatterns = range(patternList.size())
        index = db.start()
        counter = 0
        if not self.retrieve_db(db.datapath):
            print 'error' # FIXME
            return

        numOfMatches = 0
        numOfOccurrences = 0

        # print final position:

        # for i in range(19):
        #     for j in range(19):
        #         if not (self.finalpos[index*100 + (i/2) + 10*(j/2)] & (1 << (2*(j%2 + 2*(i%2))))):
        #             print 'X',
        #         elif not (self.finalpos[index*100 + (i/2) + 10*(j/2)] & (1 << (2*(j%2 + 2*(i%2))+1))):
        #             print 'O',
        #         else: print '.',
        #     print

        while not index is None:

            counter += 1
            if progBar and not counter % 10:
                progBar.redraw((progEnd-progStart)*counter/len(db.current) + progStart)

            matchList = []

            for N in possiblePatterns:
                       
                pattern = patternList.get(N)
                # print 'next pattern'
                # pattern.printPattern()
                # print

                # print 'N', N, pattern.left, pattern.right, pattern.top, pattern.bottom
                for a0 in range(pattern.left, pattern.right+1):
                    for a1 in range(pattern.top, pattern.bottom+1):
                        matches = 1

                        # print 'a0', a0, 'a1', a1
                                    
                        pIndex = 2*(a1%2) + (a0%2)

                        pbIndex = 0
                        fpIndex = index*100 + a1/2 + (a0/2)*10

                        for x in range(pattern.getBits(pIndex,0)):
                            start = pattern.getBits(pIndex, pbIndex+1)
                            length = pattern.getBits(pIndex, pbIndex+2)
                            # print 's', pbIndex, start, length
                            fpIndex += start
                            pbIndex += 2
                            for y in range(length):
                                pbIndex += 1
                                if (pattern.getBits(pIndex, pbIndex) & self.finalpos[fpIndex]):
                                    matches = 0
                                    break
                                fpIndex += 1
                            if not matches: break
                            fpIndex += 10 - start - length
                            
                        if matches:                       # found candidate
                            matchList.append((N,(a0,a1)))

            
            if matchList:
                db.makeCurrentCandidate(matchList)
                numOfMatches += 1
                numOfOccurrences += len(matchList)
            else: db.discardCurrent()

            index = db.next()

        print 'algo-finalpos:', numOfMatches, numOfOccurrences

# in x-coord:
ENDOFNODE = 128
BRANCHPOINT = 64          # these two flags ...
ENDOFVARIATION = 32       # ... are not combined with move coordinates

# in y-coord
REMOVE = 128
BLACK = 64
WHITE = 32

class Algo_movelist(Algorithm):
    """
    This algorithm stores the information from an SGF file in a "move list", that is a list
    of black/white moves and captures, respectively. The coordinates of the move/capture are
    appended (as two bytes) to the movelist, and the second coordinate gets a flag indicating
    what happened at this positon (BLACK/WHITE/REMOVE).

    In addition, if in the first byte the ENDOFNODE flag is set, this event is the last event
    of the current node (usually there is of course just one "event" per node, namely the
    placement of one stone, but if there are captures or AB/AW/AE tags, there may be several
    "events" per node. Of course, the search engine should only look for hits after a full node
    has been completed.

    Finally, in order to handle variations, there are the BRANCHPOINT and ENDOFVARIATION flags.
    They are stored without any move coordinates; nevertheless two bytes have to be appended ...
    i.e. BRANCHPOINT and 0, or ENDOFVARIATION and 0.

    BRANCHPOINT means that at this point several variations start. In practice this means that
    all of the current information about expected hits etc. should be pushed on a stack
    (self.branchpoints in the search method), such that we can jump back to this exact point
    later.

    ENDOFVARIATION means, as I suppose you guessed, the end of a variation; i.e. when encountering
    an ENDOFVARIATION, we jump back to the state described by the topmost entry of the
    self.branchpoints stack.

    In addition to the move list, we store some information about captures: for each intersection,
    we remember if at any point in the game a capture has occured at this position. This information
    is useful when doing a search, because when a stone is placed which "destroys" a hit, and which
    is not captured later, we don't have to follow the game any further to check for a hit at this
    position.

    For further information on how the search is actually carried out, see the search method.
    """

    def __init__(self, boardsize):
        pass


    def initialize_process(self, l):
        """ Start of database. """
        self.mainlistArr = array('B')    # here we store all the move lists of the current database
        self.posTable = array('L')       # this is a table of pointers to the beginning of the
                                         # corresponding move list
        self.finalposC = array('B')      # here we store information about captures; this should be
                                         

    def newgame_process(self):
        """ New game. """
        self.movelist = array('B')
        self.fpC = array('B', [0] * 50)     # '20x20 bit array', 0 = never captured, 1 = captured at some point
        

    def AB_process(self, x, y):
        self.movelist.append(x)
        self.movelist.append(y | BLACK)
        

    def AW_process(self, x, y):
        self.movelist.append(x)
        self.movelist.append(y | WHITE)


    def AE_process(self, x, y, removed):
        self.movelist.append(x)
        if removed == 'B':
            self.movelist.append(y | REMOVE | BLACK)
        elif removed == 'W':
            self.movelist.append(y | REMOVE | WHITE)
        else: print 'oops' # FIXME


    def endOfNode_process(self):
        if self.movelist:
            if self.movelist[-2] & ENDOFNODE: # there has been a pass or something, so we append an extra node
                self.movelist.append(ENDOFNODE)
                self.movelist.append(0)
            else:
                self.movelist[-2] |= ENDOFNODE


    def B_process(self, x, y, cap):
        if not self.movelist:                  # the game starts here, so we put an ENDOFNODE here,
            self.movelist.append(ENDOFNODE)    # to make sure that the empty board can be found 
            self.movelist.append(0)

        self.movelist.append(x)
        self.movelist.append(y | BLACK)

        for x, y in cap:
            self.movelist.append(x)
            self.movelist.append(y | REMOVE | WHITE)
            self.fpC[y/4 + 5*(x/2)] |= 1 << (x%2 + 2*(y%4))
 
                
    def W_process(self, x, y, cap):
        if not self.movelist:
            self.movelist.append(ENDOFNODE)
            self.movelist.append(0)
        
        self.movelist.append(x)
        self.movelist.append(y | WHITE)

        for x, y in cap:
            self.movelist.append(x)
            self.movelist.append(y | REMOVE | BLACK)
            self.fpC[y/4 + 5*(x/2)] |= 1 << (x%2 + 2*(y%4))


    def branchpoint_process(self):
        self.movelist.append(BRANCHPOINT)
        self.movelist.append(0)
        

    def endOfVariation_process(self):
        self.movelist.append(ENDOFVARIATION)
        self.movelist.append(0)


    def endgame_process(self):
        self.posTable.append(len(self.mainlistArr))
        self.mainlistArr.append(255)                  # FIXME: this delimiter shouldn't be needed
        self.mainlistArr.append(255)
        self.mainlistArr.extend(self.movelist)

        self.finalposC.extend(self.fpC)


    def finalize_process(self, datap):
        """ End of database. """
        
        filelist = [(self.posTable, 'posTable'), (self.mainlistArr, 'lists'),
                    (self.finalposC, 'finalposC')]
        for var, filename in filelist:
            file = open(os.path.join(datap[0], filename + datap[1] + '.db'), 'wb')
            var.tofile(file)
            file.close()


    filelist = ['posTable', 'lists', 'finalposC']

    # ---------------------------------------------------------------

    def retrieve_db(self, datap):
        try:
            self.posTable = array('L')
            self.mainlistArr = array('B')
            self.finalposC = array('B')
            filelist = [(self.mainlistArr, 'lists'), (self.posTable, 'posTable'),
                        (self.finalposC, 'finalposC')]
            for var, filename in filelist:
                file = open(os.path.join(datap[0], filename+datap[1]+'.db'), 'rb')
                while 1:
                    try: var.fromfile(file, 1000000)
                    except EOFError: break
                file.close()
            return 1
        except IOError:
            return 0
            

    def search(self, patternList, options, db, 
               continuations, contLabelsIndex, contLabels,
               progBar, progStart, progEnd):

        """
        Here we do the actual search. "Matchlists" have to be available from some "first-stage search".
        For each game, we proceed as follows: for each entry in the matchlist, we create a dictionary
        which pattern.sizeX * pattern.sizeY entries, which tell us if at position (i,j) the current
        board position coincides with the search pattern. More precisely, d[(i,j)] is 'X' if the search
        pattern has a black stone at (i,j), but the current board does not, it is 'O' if the search
        pattern has a white stone, but the current position has not, it is '.' if the search pattern
        has an empty intersection, but the current board has not, and it is '*' if the search pattern
        has a wildcard. (So initializing these dictionaries just means putting all stones in the
        search pattern in them, because on the empty board, they all are missing.)

        Then we go through the movelist, and for each entry we update the dictionaries correspondingly.
        When reaching an ENDOFNODE, we check if there are any empty dictionaries; If there are, we have
        found actual hits.

        This basic procedure is complicated (but not very much) by three things:
        - after finding a hit, we still are interested in the continuation
          thus we do not directly append the hit to the list of results and forget about it, but instead
          we create a 'found' entry in the dictionary which stores the move number when the hit was found.
          We then look for the continuation as we proceed to go through the move list.
        - possibly, we are interested in a move sequence, not just a pattern. In that case, we proceed as
          described above in order to find the initial position, and - after finding it - we set a
          'foundInitial' entry in the dictionary. Further moves in the corresponding region will only
          be accepted for this potential hit if they are in the right order, as prescribed by the contList,
          a list containing the information about the move sequence following the initial pattern.
          If we reach the end of the contList, we have indeed found a hit, and can set the 'found' entry
          (and look for the continuation play, as we go further through the move list.)
        - We also may want to search in variations. To this end, we use the information about branchpoints
          and end-of-variation points stored in the move list. At a branchpoint, we make a copy of all the
          dictionaries, and contLists, and push them in the self.branchpoints stack. When reaching the end
          of a variation, we reset the dictionaries etc. to the values stored in the topmost entry of the
          stack.
        """
        
        numOfHits = 0
        self.numOfSwitched = 0
        Bwins = 0
        Wwins = 0

        if options.has_key('movelimit'): self.movelimit = options['movelimit']
        else: self.movelimit = 1000
        if options.has_key('showcolorswap'): showColorSwap = options['showcolorswap']
        else: showColorSwap = 1

        searchInVariations = 1 # FIXME

        if not self.retrieve_db(db.datapath):
            print "error" # FIXME
            return
            
        index = db.start()
        gameCounter = 0

        while not index is None:

            gameCounter += 1
            if progBar and not gameCounter % 10:
                progBar.redraw((progEnd-progStart)*gameCounter/len(db.current) + progStart)
            
            result = []
            numOfSwitched = 0
            self.branchpoints = []

            movelist = self.mainlistArr
            movelistIndex = self.posTable[index] + 2

            endMovelist = movelistIndex
            while endMovelist < len(self.mainlistArr) and self.mainlistArr[endMovelist] != 255:
                endMovelist += 2
        
            dicts = {}
            contList = {}
            contListIndex = {}
            dictsNO = {}
            Xinterv = {}
            Yinterv = {}

            # initialize dictionaries
            
            for m in db.getCurrentMatchlist():
                d = {}
                dNO = 0
                p = patternList.get(m[0])
                for i in range(p.sizeX):
                    for j in range(p.sizeY):
                        if p.getInitial(i, j) != '.':
                            d[(i+m[1][0],j+m[1][1])] = p.getInitial(i,j)
                        if p.getInitial(i,j) in ['X', 'O']:
                            dNO += 1

                dicts[m] = d
                dictsNO[m] = dNO # no of places that are currently not correct

                contList[m] = []
                cL = p.contList.split('/')
                for t in cL:
                    if t: contList[m].append((ord(t[0])+m[1][0], ord(t[1])+m[1][1], BW2XO(t[2])))

                contListIndex[m] = 0
                Xinterv[m] = (m[1][0], m[1][0] + patternList.get(m[0]).sizeX)
                Yinterv[m] = (m[1][1], m[1][1] + patternList.get(m[0]).sizeY)

            # go through the game

            counter = 0 # counts at which move in the game we are
            whereAreWe = [0] # records the exact position in the game tree
                             # format: list [n1, m1, n2, m2, n3 ..., ni], where
                             # the current position can be reached by
                             # going forward n1 times, then choosing the m1-th variation,
                             # then going forward n2 times, then choosing the m2-th variation,
                             # etc.
                             # we have counter == sum_j nj // FIXME this cannot be correct (maybe i + sum_j nj)
            
            while movelistIndex < endMovelist and (counter <= self.movelimit or self.branchpoints):
                
                if movelist[movelistIndex] & BRANCHPOINT:
                    whereAreWeCopy = copy(whereAreWe)
                    if movelistIndex < self.posTable[index]+4 or not movelist[movelistIndex-2] & ENDOFVARIATION:
                        # whereAreWe[-1] -= 1
                        # print 'X', counter
                        whereAreWeCopy[-1] -= 1
                        whereAreWeCopy.extend([0,0])
                    self.branchpoints.append((deepcopy(dicts), deepcopy(dictsNO),
                                              deepcopy(contList), deepcopy(contListIndex), counter,
                                              whereAreWeCopy))
                    movelistIndex += 2
                    continue
                elif movelist[movelistIndex] & ENDOFVARIATION:
                    if not patternList.nextMove:
                        for m in dicts.keys():
                            if dicts[m].has_key('found') and dicts[m]['found'] <= self.movelimit:
                                if patternList.get(m[0]).colorSwitch: numOfSwitched += 1
                                if patternList.get(m[0]).colorSwitch and showColorSwap:
                                    if searchInVariations:
                                        result.append(Hit(dicts[m]['found'], '-', dicts[m]['whereAreWe']))
                                    else: result.append(Hit(dicts[m]['found'], '-'))
                                else:
                                    if searchInVariations:
                                        result.append(Hit(dicts[m]['found'], '', dicts[m]['whereAreWe']))
                                    else: result.append(Hit(dicts[m]['found'], ''))
                    dicts, dictsNO, contList, contListIndex, counter, whereAreWe = self.branchpoints.pop()
                    
                    whereAreWe[-2] += 1
                    # print 'Y'
                    # assert whereAreWe[-1] == 0
                        
                    movelistIndex += 2
                    continue

                endOfNode = movelist[movelistIndex] & ENDOFNODE

                x = movelist[movelistIndex] & 31
                y = movelist[movelistIndex+1] & 31

                if (not movelist[movelistIndex+1] & REMOVE) \
                   and movelist[movelistIndex+1] & (BLACK | WHITE):

                    if movelist[movelistIndex+1] & BLACK:
                        co, invco = 'X', 'O'    
                    else: co, invco = 'O', 'X'  
                    
                    for m in dicts.keys():
                        if Xinterv[m][0] <= x < Xinterv[m][1] and Yinterv[m][0] <= y < Yinterv[m][1]:

                            if dicts[m].has_key('found') and dicts[m]['found'] <= self.movelimit:
                                # so (x,y) is the continuation

                                hit, label, contLabelsIndex, switched =\
                                     patternList.updateContinuations(m[0], x, y, invco,
                                                                     Xinterv[m][0], Xinterv[m][1], 
                                                                     Yinterv[m][0], Yinterv[m][1],
                                                                     dicts[m]['found'], counter,
                                                                     continuations, ''.join(contLabels),
                                                                     contLabelsIndex,
                                                                     db.getCurrentWinner())
                                if not hit:
                                    del dicts[m]
                                    del dictsNO[m]
                                    continue

                                numOfSwitched += switched # FIXME: CHECK, was: patternList[m[0]].colorSwitch

                                if switched and showColorSwap:
                                    # FIXME: CHECK,was: (patternList[m[0]].colorSwitch or colorSwitch) and showColorSwap:
                                    if searchInVariations:
                                        result.append(Hit(dicts[m]['found'], label+'-', dicts[m]['whereAreWe']))
                                    else: result.append(Hit(dicts[m]['found'], label+'-'))
                                else:
                                    if searchInVariations:
                                        result.append(Hit(dicts[m]['found'], label, dicts[m]['whereAreWe']))
                                    else: result.append(Hit(dicts[m]['found'], label))
                                del dicts[m]
                                del dictsNO[m]
                                continue     # with for m in dicts.keys()

                            elif dicts[m].has_key('foundInitial'):
                                print contList[m], contListIndex[m]
                                if (x, y, co) == contList[m][contListIndex[m]]:
                                    contListIndex[m] += 1
                                    if contListIndex[m] == len(contList[m]):
                                        dicts[m]['found'] = counter
                                        dicts[m]['whereAreWe'] = copy(whereAreWe)
                                        # print 'found', counter, whereAreWe
                                        del dicts[m]['foundInitial']
                                else:
                                    if dicts[m].has_key('dontRestore'):
                                        del dicts[m]
                                        continue
                                    else:
                                        contListIndex[m] = 0
                                        del dicts[m]['foundInitial']
                    
                            if not dicts[m].has_key((x,y)):
                                if not (self.finalposC[index*50 + y/4 + 5*(x/2)] & (1 << (x%2 + 2*(y%4)))):
                                                                  # this stone won't be captured later,
                                                                  # so this cannot become a match
                                    if not contListIndex[m]:
                                        del dicts[m]
                                        continue
                                    else:
                                        dicts[m]['dontRestore'] = 1
                                else:
                                    dicts[m][(x,y)] = '.'
                                    dictsNO[m] = dictsNO[m] + 1
                            elif dicts[m][(x,y)] == lower(invco):
                                if not (self.finalposC[index*50 + y/4 + 5*(x/2)] & (1 << (x%2 + 2*(y%4)))):
                                    if not contListIndex[m]:
                                        del dicts[m]
                                        continue
                                    else:
                                        dicts[m]['dontRestore'] = 1
                                else:
                                    dictsNO[m] = dictsNO[m] + 1
                            
                            elif dicts[m][(x,y)] == co:
                                del dicts[m][(x,y)]
                                dictsNO[m] = dictsNO[m] - 1

                elif movelist[movelistIndex+1] & REMOVE:

                    if movelist[movelistIndex+1] & BLACK:
                        co = 'X'
                        invco = 'O'
                    elif movelist[movelistIndex+1] & WHITE:
                        co = 'O'
                        invco = 'X'
                    else: print 'oops' # FIXME

                    for m in dicts.keys():
                        if not dicts[m].has_key('found'):

                            if Xinterv[m][0] <= x < Xinterv[m][1] \