# HG changeset patch # User Laman # Date 2017-12-17 02:20:05 # Node ID 7ef3360afbe51272d3aa1248821a6bfe99897e33 # Parent 231b6d9b956192d68aa32f05f770c2e9aab5ebf2 StateBag.pushState: linking the states together diff --git a/src/analyzer/epoint.py b/src/analyzer/epoint.py --- a/src/analyzer/epoint.py +++ b/src/analyzer/epoint.py @@ -7,8 +7,7 @@ class EPoint: self.x=x self.y=y - def fromTuple(tup): return EPoint(tup[0],tup[1]) - + @staticmethod def fromProjective(point): if point.item(0)==0: return None return EPoint(point.item(1)/point.item(0),point.item(2)/point.item(0)) diff --git a/src/go/core.py b/src/go/core.py --- a/src/go/core.py +++ b/src/go/core.py @@ -5,12 +5,20 @@ from .helperboard import HelperBoard from .gamerecord import GameRecord +PASS=(99,99) + + class Go: ## Initializes self.board to a list[r][c]=EMPTY. def __init__(self,boardSize=19): self.boardSize=boardSize self.board=[[EMPTY]*boardSize for x in range(boardSize)] self.toMove=BLACK + + # utility field to allow undoing moves. but only useful right after doMove. this class doesn't need it, so it is not kept correct at other times + self.captures=[None]*4 + self.captureCount=0 + self._helper=HelperBoard(self.board) self._freshHash=hashBoard(self.board) # always reflecting current state of the board self._hashes=[self._freshHash] @@ -24,15 +32,23 @@ class Go: # @return True on success, False on failure (illegal move) def doMove(self,color,r,c): if color!=self.toMove: log.warning("move by %s out of order",colorNames[color]) + if (r,c)==PASS: + self.toMove*=-1 # pass + self._hashes.append(self._freshHash) + return True if self.board[r][c]!=EMPTY: return False self.board[r][c]=color self._freshHash^=diffHash(r,c,EMPTY,color) # capture neighbors + self.captureCount=0 for dr,dc in ((-1,0),(1,0),(0,-1),(0,1)): self._helper.clear() - if not self._helper.floodFill(-color,r+dr,c+dc,EMPTY): self._remove() + if not self._helper.floodFill(-color,r+dr,c+dc,EMPTY): + self.captures[self.captureCount]=(r+dr,c+dc) + self.captureCount+=1 + self._remove() # check for suicide and prevent it self._helper.clear() @@ -46,15 +62,16 @@ class Go: return True def undoMove(self,r,c,captures): - assert self.board[r][c]==-1*self.toMove, "{0}!={1}".format(self.board[r][c],-1*self.toMove) + if (r,c)!=PASS: + assert self.board[r][c]==-1*self.toMove, "{0}!={1}".format(self.board[r][c],-1*self.toMove) - if len(captures)>0: - self._helper.clear() - for (ri,ci) in captures: - self._helper.floodFill(EMPTY,ri,ci) - self._fill(self.toMove) + if len(captures)>0: + self._helper.clear() + for (ri,ci) in captures: + self._helper.floodFill(EMPTY,ri,ci) + self._fill(self.toMove) - self.board[r][c]=EMPTY + self.board[r][c]=EMPTY self.toMove*=-1 self._hashes.pop() self._freshHash=self._hashes[-1] diff --git a/src/go/engine.py b/src/go/engine.py --- a/src/go/engine.py +++ b/src/go/engine.py @@ -1,9 +1,14 @@ -from util import EMPTY,BLACK,WHITE +from .core import PASS from . import core -def transitionSequence(state1, state2, diff, limit=0): - return [] +## Compute move sequence from state1 to state2. +# +# @param colorIn {BLACK,WHITE}: color to start the sequence +# @param colorOut {BLACK,WHITE}: color to close the sequence +def getTransitionSequence(state1,state2,colorIn,colorOut,diff): + eng.load(state1,diff) + eng.iterativelyDeepen(state2,colorIn,colorOut) class SpecGo(core.Go): @@ -17,7 +22,7 @@ class SpecGo(core.Go): Also any non-missing stones of partially deleted (or replaced) groups had to be replayed, so add them too. Needs to handle snapback, throw-in. 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()) + res=({PASS},{PASS}) for d in diff: (r,c,action,color)=d colorKey=(1-color)>>1 # {-1,1}->{1,0} @@ -55,48 +60,46 @@ class Engine: self._g.load(state1) self._moveList=self._g.listRelevantMoves(diff) - def iterativelyDeepen(self,state2,toMove=None): - for i in range(1,10): - for color in [toMove] if toMove else [BLACK,WHITE]: - self._g.toMove=color - seq=self.dfs(state2,i) - if seq: - seq.reverse() - return seq + def iterativelyDeepen(self,state2,colorIn,colorOut): + startDepth=1 if colorIn==colorOut else 2 + self._g.toMove=colorIn + + for i in range(startDepth,10,2): + seq=self.dfs(state2,i) + if seq: + seq.reverse() + return seq def dfs(self,state2,limit): g=self._g moveSet=self._moveList[(1-g.toMove)>>1] - for (r,c) in moveSet.copy(): - if g.board[r][c]!=EMPTY: continue - neighbours=( - g.board[r-1][c] if r>0 else None, - g.board[r+1][c] if r+10 else None, - g.board[r][c+1] if c+1>1].remove(m) if g.hash()==state2.hash(): - g.undoMove(r,c,captured) - moveSet.add((r,c)) - return [(g.toMove,r,c)] + self._undoMove(m,captured) + return [(g.toMove,*m)] if limit>1: seq=self.dfs(state2,limit-1) if seq: - g.undoMove(r,c,captured) - moveSet.add((r,c)) - seq.append((g.toMove,r,c)) + self._undoMove(m,captured) + seq.append((g.toMove,*m)) return seq - g.undoMove(r,c,captured) - moveSet.add((r,c)) + self._undoMove(m,captured) return False + def _undoMove(self,move,captured): + g=self._g + g.undoMove(*move,captured) + k=(1-g.toMove)>>1 + self._moveList[k].add(move) + if move==PASS: + self._moveList[1-k].add(move) + eng=Engine() diff --git a/src/go/helperboard.py b/src/go/helperboard.py --- a/src/go/helperboard.py +++ b/src/go/helperboard.py @@ -13,6 +13,9 @@ class HelperBoard: self._libs=[0]*(self._boardSize**2)*2 self._libCount=0 + ## Performs a recursive breadth first search of a continuous area filled with filling. + # + # @return {True,False}: True on encountering needle (usually free liberty), False otherwise. def floodFill(self,filling,r,c,needle=None): if c<0 or c>=self._boardSize or r<0 or r>=self._boardSize: return False # out of range if self._board[r][c]: return False # already visited diff --git a/src/statebag.py b/src/statebag.py --- a/src/statebag.py +++ b/src/statebag.py @@ -16,8 +16,8 @@ So we try to find the correct crossover - remember the better variant - linearize the fork back by discarding s'_j-s preceding the crossover and s_j-s following the crossover """ -from util import EMPTY, hashBoard,exportBoard -from go.engine import transitionSequence +from util import EMPTY,BLACK,WHITE, hashBoard,exportBoard +from go.engine import getTransitionSequence ## Crude lower bound on edit distance between states. @@ -31,16 +31,41 @@ def estimateDistance(diff): return replacements+1 # ??? +class GameTreeNode: + def __init__(self,parent,color): + self.parent=parent + self.color=color # color closing the move sequence + self.prev=None + self.moves=[] # move sequence from prev to self + self.weight=0 + + ## Connect itself after v if it gains itself more weight. + def tryConnect(self,v,diff): + moves=getTransitionSequence(v.parent,self.parent,-1*v.color,self.color,diff) + w=v.weight+2-len(moves) # proper one move transition increases the weight by 1 + if w>self.weight: + self.moves=moves + self.prev=v + self.weight=w + + class BoardState: def __init__(self,board): self._board=tuple(tuple(x for x in row) for row in board) - self.prev=None - self._next=None - self.moves=[] - self.weight=0 + self.nodes=(GameTreeNode(self,BLACK),GameTreeNode(self,WHITE)) self.diff2Prev=None self._hash=None + def tryConnect(self,s): + diff=s-self + distEst=estimateDistance(diff) + if distEst>3: return # we couldn't find every such move sequence anyway without a clever algorithm + weightEst=s.getWeight()-distEst + if weightEst<=self.getWeight(): return + for v1 in s.nodes: + for v2 in self.nodes: + v2.tryConnect(v1,diff) + def hash(self): if self._hash is None: self._hash=hashBoard(self._board) return self._hash @@ -69,6 +94,9 @@ class BoardState: def __eq__(self,x): return self.hash()==x.hash() + def getWeight(self): + return max(v.weight for v in self.nodes) + class StateBag: def __init__(self): @@ -79,18 +107,7 @@ class StateBag: if self._states and sn==self._states[-1]: return # no change for s in reversed(self._states): - diff=sn-s - distEst=estimateDistance(diff) - if distEst>3: continue # we couldn't find every such move sequence anyway without a clever algorithm - weightEst=s.weight-distEst - if weightEst<=sn.weight: continue - moves=transitionSequence(s,sn,diff) - weight=s.weight-len(moves) - if weight<=sn.weight: continue - sn.prev=s - sn.diff2Prev=diff - sn.moves=moves - sn.weight=weight + sn.tryConnect(s) self._states.append(sn) def merge(self,branch): diff --git a/src/tests/testEngine.py b/src/tests/testEngine.py --- a/src/tests/testEngine.py +++ b/src/tests/testEngine.py @@ -125,10 +125,12 @@ class TestTransitions(TestCase): for k in range(1,4): toMove=B - for (s1,s2) in zip(states,states[k:]): + for (i,(s1,s2)) in enumerate(zip(states,states[k:])): diff=s2-s1 eng.load(s1,diff) - seq=eng.iterativelyDeepen(s2,toMove) + colorIn=W if i&1 else B + colorOut=colorIn if k&1 else 1-colorIn + seq=eng.iterativelyDeepen(s2,colorIn,colorOut) msg="\n"+s1.exportDiff(s2) self.assertIsNotNone(seq,msg) self.assertLessEqual(len(seq),k,msg)