diff --git a/src/go/core.py b/src/go/core.py --- a/src/go/core.py +++ b/src/go/core.py @@ -23,7 +23,7 @@ class Go: # # @param color BLACK or WHITE # @return True on success, False on failure (illegal move) - def move(self,color,row,col): + def doMove(self,color,row,col): if color!=self.toMove: log.warning("move by %s out of order",colorNames[color]) if self.board[row][col]!=EMPTY: return False @@ -55,7 +55,7 @@ class Go: res=transitionMove(self.board,board) if not res: return res (r,c,color)=res - return self.move(color,r,c) + return self.doMove(color,r,c) ## Removes stones at coordinates marked with True in self.helper. def _remove(self): diff --git a/src/go/engine.py b/src/go/engine.py --- a/src/go/engine.py +++ b/src/go/engine.py @@ -8,7 +8,6 @@ def transitionSequence(state1, state2, d class SpecGo(core.Go): def __init__(self): super().__init__() - self._diff=[] def load(self,state): for (r,row) in enumerate(state): @@ -16,27 +15,49 @@ class SpecGo(core.Go): self.board[r][c]=x def listRelevantMoves(self,diff): - res=([],[]) + """There can be 3 different changes in the diff: additions, deletions and replacements. + Additions can be taken as relevant right away. + Deletions and replacements had to be captured, so we add their liberties. + Also any non-missing stones of partially deleted (or replaced) groups had to be replayed, so add them too. + Needs to handle: Take n, return 1. Snapback. + There's no end to what could be theoretically relevant, but such sequences are long and we will pretend they won't happen.""" + res=(set(),set()) for d in diff: (r,c,action,color)=d - colorKey=(1-color)<<1 - if action!="-": + colorKey=(1-color)<<1 # {-1,1}->{1,0} + if action!="-" and (r,c) not in res[colorKey]: res[colorKey].append((r,c)) - if action!="+": + # this is rather sloppy but correct. the time will show if it is effective enough + if action!="+" and (r,c) not in res[colorKey] and (r,c) not in res[1-colorKey]: self._helper.clear() - self._helper.floodFill(color,r,c) - res[colorKey].extend(self._helper.getLiberties()) + self._helper.floodFill(color if action=="-" else 1-color, r, c) + res[colorKey].union(self._helper.getContinuousArea()) + for (ri,ci) in self._helper.getContinuousArea(): + res[colorKey].add((ri,ci)) + res[1-colorKey].add((ri,ci)) + if ri>0: + res[colorKey].add((ri-1,ci)) + res[1-colorKey].add((ri-1,ci)) + if ri<self.boardSize: + res[colorKey].add((ri+1,ci)) + res[1-colorKey].add((ri+1,ci)) + if ci>0: + res[colorKey].add((ri,ci-1)) + res[1-colorKey].add((ri,ci-1)) + if ci<self.boardSize: + res[colorKey].add((ri,ci+1)) + res[1-colorKey].add((ri,ci+1)) return res class Engine: def __init__(self): self._g=SpecGo() - self._diff=[] + self._moveList=(set(),set()) def load(self,state1,diff): self._g.load(state1) - self._diff=diff + self._moveList=self._g.listRelevantMoves(diff) def iterativelyDeepen(self,state2): for i in range(1,10): @@ -45,13 +66,13 @@ class Engine: def dfs(self,state2,limit): g=self._g - for m in g.listRelevantMoves(): - g.doMove(m) - if g.board==state2: return m + for (r,c) in self._moveList[g.toMove]: + g.doMove(g.toMove,r,c) + if g.board==state2: return [(r,c)] if limit>1: seq=self.dfs(state2,limit-1) if seq: - seq.append(m) + seq.append((r,c)) return seq g.undoMove(m) return False