Web   ·   Wiki   ·   Activities   ·   Blog   ·   Lists   ·   Chat   ·   Meeting   ·   Bugs   ·   Git   ·   Translate   ·   Archive   ·   People   ·   Donate
summaryrefslogtreecommitdiffstats
path: root/gogame.py
blob: 894952f9f724dde146fae543fda8328ea4d2fdae (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
# -*- coding: UTF-8 -*-
# Copyright 2007-2008 One Laptop Per Child
# Copyright 2007 Gerard J. Cerchio <www.circlesoft.com>
# Copyright 2008 Andrés Ambrois <andresambrois@gmail.com>
#
# 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; if not, write to the Free Software
# Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA

import logging
_logger = logging.getLogger('PlayGo')

from gettext import gettext as _

class GoGame:
    """ 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

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

    def __init__(self, boardSize = 19):
        self.size = boardSize
        self.status = {}
        self.undostack = []
        self.score = {'B' : 0,  'W' : 0}
        _logger.setLevel( logging.DEBUG )

    def get_score(self):
        return self.score
        
    def increase_score(self, color):
        self.score[color] = self.score[color] + 1

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

        if   x[1]== 0                :     l1 = [1]
        elif x[1]== self.size-1 :     l1 = [self.size-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 is_occupied(self, x, y):
        return  self.status.has_key((x, y))
        
    def clear(self):
        """ Clear the board """
        self.status = {}
        self.undostack=[]     
        self.score = {'B' : 0,  'W' : 0}

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

        if self.legal(pos,color): # legal move?
            self.status[pos] = color
            captures = self.get_captures(pos, color)
            if captures:
                for x in captures: 
                    del self.status[x]   # remove captured stones, if any
                    self.increase_score(color)
            self.undostack.append((pos,color,captures))   # remember move + captured stones for easy undo
            return captures
        else: 
            return 0
    
    def get_captures(self,  pos,  color):
        """Returns a list of captured stones resulting from placing a color stone at pos """
        c = [] # captured stones
        
        for x in self.neighbors(pos):
            if self.status.has_key(x) and self.status[x]==self.invert(color):
                c = c + self.hasNoLibExcP(x, self.invert(color), pos)
                
        if c:
            captures = []
            for x in c:
                if not x in captures: captures.append(x)
            return captures
            
        return 0
        
    def checkKo(self,  pos, color):
        ''' Check if a move by color at pos would be a basic Ko infraction '''
        # Basically what we need to check, is if the current play would undo
        #   all that was done by the last entry in undostack (capture what was placed
        #   and place what was captured). 
        if self.undostack:
            lastpos,  lastcolor,  lastcaptures = self.undostack[-1]
            currentcaptures = self.get_captures(pos, color)
            if lastcaptures != 0 and currentcaptures != 0:
                if lastcolor != color and lastcaptures[0] == pos and lastpos == currentcaptures[0]:
                    return 1
        return 0
        
    def legal(self, pos, color):
        """ Check if a play by color at pos would be a legal move. """
        if self.status.has_key(pos):
            return 0
            
        # If the play at pos would leave that stone without liberties, we have two possibilities: 
        # 1- It's a capturing move
        # 2- It's an illegal move
        if self.hasNoLibExcP(pos, color): 
            # Check if it would capture any stones
            if self.get_captures(pos, color):
                return 1
            # It didnt, so I guess it's illegal
            return 0
        else: return not self.checkKo(pos, color)

    def illegal(self, x, y, color):
        """ Check if a play by color at pos would be an illigal move, and return pretty errors"""
        if self.status.has_key((x, y)):
            return _('There already is a stone there!')
        if self.checkKo((x, y), color):
            return _('Ko violation!')
        
        # If the play at pos would leave that stone without liberties, we have two possibilities: 
        # 1- It's a capturing move
        # 2- It's an illegal move
        if self.hasNoLibExcP((x, y), color): 
            # Check if it would capture any stones
            if self.get_captures((x, y), color):
                return False
            # It didnt, so I guess it's illegal
            return _('Illegal move.')
        else: return False

    def hasNoLibExcP(self, pos, color, 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 not self.status.has_key(y) and y != exc and y != pos:    # found a liberty
                        return []
                    elif self.status.has_key(y) and self.status[y]==color \
                        and not y in newlyFound and not y in st: # 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 get_territories(self):
        def get_group(self, first_element, color):
            current_group = [first_element]
            for current_element in current_group:
                for x in self.neighbors(current_element):
                    if self.status.has_key(x):
                        if self.status[x] != color:
                            return None
                    elif not x in current_group:
                        current_group.append(x)   
            return set(current_group)
            
        groups = {'B':set(), 'W':set()}
        for x in self.status.keys():
            for n in self.neighbors(x):
                if not self.status.has_key(n):
                    new_group = get_group(self, n, self.status[x])
                    if new_group: 
                        groups[self.status[x]] |= new_group
        return groups

    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]
                if captures:
                    for p in captures: 
                        self.status[p] = self.invert(color)
                        self.score[color] -= 1
                return True
            else:
                return False

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