OneEye Changeset - 7ef3360afbe5

Changeset - 7ef3360afbe5

Parent rev.

Child rev.

[Not reviewed]

default

0 6 0

Laman - 7 years ago 2017-12-17 02:20:05

StateBag.pushState: linking the states together

6 files changed with 105 insertions and 64 deletions:

src/analyzer/epoint.py

src/go/core.py

src/go/engine.py

src/go/helperboard.py

src/statebag.py

src/tests/testEngine.py

0 comments (0 inline, 0 general)

src/analyzer/epoint.py

➞

Show inline comments

@@ @@ -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))

src/go/core.py

➞

Show inline comments

@@ @@ -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]

src/go/engine.py

➞

Show inline comments

-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()

src/go/helperboard.py

➞

Show inline comments

@@ @@ -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

src/statebag.py

➞

Show inline comments

@@ @@ -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):

src/tests/testEngine.py

➞

Show inline comments

@@ @@ -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)

0 comments (0 inline, 0 general)