# 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+1<g.boardSize else None,
- g.board[r][c-1] if c>0 else None,
- g.board[r][c+1] if c+1<g.boardSize else None
- )
- if not g.doMove(g.toMove,r,c): continue
- moveSet.remove((r,c))
- captured=tuple(
- coords for (i,coords) in enumerate(((r-1,c),(r+1,c),(r,c-1),(r,c+1)))
- if neighbours[i] is not None and neighbours[i]!=EMPTY and g.board[coords[0]][coords[1]]==EMPTY
- )
+ for m in moveSet.copy():
+ if not g.doMove(g.toMove,*m): continue
+ captured=g.captures[:g.captureCount]
+ moveSet.remove(m)
+ if m==PASS: # no reason for both players to pass
+ self._moveList[(1-g.toMove)>>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)