root/06/devel-old/abstractBoardPY.py

# file: board1.py

##   This file is part of Kombilo, a go database program
##   It contains classes implementing an abstract go board and a go
##   board displayed on the screen.

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

##   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 (gpl.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


from copy import deepcopy

class abstractBoard:
    """ This class administrates a go board.
        It keeps track of the stones currently on the board in the dictionary self.status,
        and of the moves played so far in self.undostack

        The "coordinate system" of the board is as follows:

        (0,0) ------- (self.boardsize-1,0)
          |                     |
          |                     |
        (0,bsize-1) --- (bsize-1, bsize-1)

        (this is analogous to the SGF coordinate system).

        It has methods to clear the board, play a stone, undo a move. """

    def __init__(self, boardsize = 19):
        self.status = {}
        self.undostack = []
        self.boardsize = boardsize

    def getStatus(self, x, y):
        if self.status.has_key((x, y)): return self.status[(x, y)]
        else: return ' '

    def setStatus(self, x, y, value):
        self.status[(x, y)] = value


    def copy(self):
        ab = abstractBoard(self.boardsize)
        ab.status = deepcopy(self.status)
        ab.undostack = deepcopy(self.undostack)
        return ab

    def restore(self, ab):
        self.boardsize = ab.boardsize
        self.status = ab.status
        self.undostack = ab.undostack

    def len_cap_last(self):
        """ Return number of captured stones in last move. """

        return len(self.undostack[-1][2])

    def get_cap_last(self):
        return self.undostack[-1][2]

    def undostack_pop(self):
        return self.undostack.pop()

    def undostack_append_pass(self):
        self.undostack.append(((20,20), '' ,[]))

    def len_undostack(self):
        return len(self.undostack)

    def neighbors(self,x):
        """ Returns the coordinates of the 4 (resp. 3 resp. 2 at the side / in the corner) intersections
            adjacent to the given one. """
        if   x[0]== 0                :     l0 = [1]
        elif x[0]== self.boardsize-1 :     l0 = [self.boardsize-2]
        else:                              l0 = [x[0]-1, x[0]+1]

        if   x[1]== 0                :     l1 = [1]
        elif x[1]== self.boardsize-1 :     l1 = [self.boardsize-2]
        else:                              l1 = [x[1]-1, x[1]+1]

        l = []
        for i in l0: l.append((i,x[1]))
        for j in l1: l.append((x[0],j))

        return l


    def clear(self):
        """ Clear the board """
        self.status = {}
        self.undostack=[]        




    def play(self,pos,color):
        """ This plays a color=black/white stone at pos, if that is a legal move
            (disregarding ko), and deletes stones captured by that move.
            It returns 1 if the move has been played, 0 if not. """

        if color is None: color = self.currentColor
        elif color in ['black', 'b']: color = 'B'
        elif color in ['white', 'w']: color = 'W'

        if self.getStatus(pos[0], pos[1]) != ' ':                # check if empty
            return 0

        l = self.legal(pos,color)
        if l:                                       # legal move?
            captures = l[1]
            for x in captures: del self.status[x]   # remove captured stones, if any
            self.undostack.append((pos,color,captures))   # remember move + captured stones for easy undo
            return 1
        else: return 0


    def legal(self, pos, color):
        """ Check if a play by color at pos would be a legal move. """
        c = [] # captured stones
        for x in self.neighbors(pos):
            if self.getStatus(x[0],x[1])==self.invert(color):
                c = c + self.hasNoLibExcP(x, pos)        

        self.status[pos]=color

        if c:
            captures = []
            for x in c:
                if not x in captures: captures.append(x)
            return (1, captures)

        if self.hasNoLibExcP(pos):
            del self.status[pos]
            return ()
        else: return (1, [])


    def hasNoLibExcP(self, pos, exc = None):
        """ This function checks if the string (=solidly connected) of stones containing
            the stone at pos has a liberty (resp. has a liberty besides that at exc).
            If no liberties are found, a list of all stones in the string is returned.

            The algorithm is a non-recursive  implementation of a simple flood-filling:
            starting from the stone at pos, the main while-loop looks at the intersections
            directly adjacent to the stones found so far, for liberties or other stones that belong
            to the string. Then it looks at the neighbors of those newly found stones, and so
            on, until it finds a liberty, or until it doesn't find any new stones belonging
            to the string, which means that there are no liberties.
            Once a liberty is found, the function returns immediately. """
            
        st = []            # in the end, this list will contain all stones solidly connected to the
                           # one at pos, if this string has no liberties
        newlyFound = [pos] # in the while loop, we will look at the neighbors of stones in newlyFound
        foundNew = 1
        
        while foundNew:
            foundNew = 0
            n = []         # this will contain the stones found in this iteration of the loop
            for x in newlyFound:
                for y in self.neighbors(x):
                    if self.getStatus(y[0], y[1]) == ' ' and y != exc:    # found a liberty
                        return []
                    elif self.getStatus(y[0],y[1])==self.getStatus(x[0],x[1]) \
                         and not y in st and not y in newlyFound: # found another stone of same color
                        n.append(y)
                        foundNew = 1

            st[:0] = newlyFound
            newlyFound = n

        return st     # no liberties found, return list of all stones connected to the original one


    def undo(self, no=1):
        """ Undo the last no moves. """
        for i in range(no):
            if self.undostack:
                pos, color, captures = self.undostack.pop()
                del self.status[pos]
                for p in captures: self.status[p] = self.invert(color)


    def remove(self, pos, removeFromUndostack=0):
        """Remove the stone at pos, if not removeFromUndostack, append this as capture to undostack.
        Otherwise, find the placement of this stone in undostack, and remove it from there."""
        
        if removeFromUndostack:
            for i in range(len(self.undostack), 0, -1):
                if pos == self.undostack[i-1][0]:
                    self.undostack[i-1:i] = []
        else:
            self.undostack.append(((-1,-1), self.invert(self.status[pos]), [pos]))
        del self.status[pos]


    def invert(self,color):
        if color == 'B': return 'W'
        else:            return 'B'