OneEye Changeset - 7ef3360afbe5

Changeset - 7ef3360afbe5

Parent rev.

Child rev.

[Not reviewed]

default

0 6 0

Laman - 8 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

 import math
 ## Euclidean 2D plane point: (x,y).
 class EPoint:
 	def __init__(self,x,y):
 		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))
 	def toProjective(self):
 		return (1,self.x,self.y)
 	def dist(self,a):
 		return math.sqrt((self.x-a.x)**2+(self.y-a.y)**2)
 	def __add__(self,a):
 		return EPoint(self.x+a.x,self.y+a.y)
 	def __sub__(self,a):
 		return EPoint(self.x-a.x,self.y-a.y)
 	def __mul__(self,k):
 		return EPoint(self.x*k,self.y*k)
 	def __rmul__(self,k):
 		return self*k
 	def __truediv__(self,k):
 		return EPoint(self.x/k,self.y/k)
 	def __floordiv__(self,k):
 		return EPoint(self.x//k,self.y//k)
 	def __iadd__(self,a):
 		self.x+=a.x
 		self.y+=a.y
 		return self
 	def __isub__(self,a):
 		self.x-=a.x
 		self.y-=a.y
 		return self
 	def __imul__(self,k):
 		self.x*=k
 		self.y*=k
 		return self
 	def __itruediv__(self,k):
 		self.x/=k
 		self.y/=k
 		return self
 	def __ifloordiv__(self,k):
 		self.x//=k
 		self.y//=k
 		return self
 	def __neg__(self):
 		return EPoint(-self.x,-self.y)
 	def __str__(self): return "({0},{1})".format(round(self.x,3),round(self.y,3))
 	def __repr__(self): return "EPoint({0},{1})".format(round(self.x,3),round(self.y,3))

src/go/core.py

➞

Show inline comments

 import logging as log
 from util import EMPTY,BLACK,WHITE, colorNames,hashBoard,diffHash
 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]
 		self._record=GameRecord()
 	## Executes a move.
+	#
 	#  Doesn't check for kos. Suicide not allowed.
+	#
 	#  @param color BLACK or WHITE
 	#  @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()
 		if not self._helper.floodFill(color,r,c,EMPTY):
 			self.board[r][c]=EMPTY
 			self._freshHash=self._hashes[-1]
 			return False
 		self._record.move(color,r,c)
 		self.toMove=-1*color
 		self._hashes.append(self._freshHash)
 		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]
 	def transitionMove(self,board):
 		res=transitionMove(self.board,board)
 		if not res: return res
 		(r,c,color)=res
 		return self.doMove(color,r,c)
 	def load(self,board):
 		for (r,row) in enumerate(board):
 			for (c,x) in enumerate(row):
 				self.board[r][c]=x
 		self._freshHash=hashBoard(self.board)
 		self._hashes=[self._freshHash]
 	def hash(self):
 		return self._hashes[-1]
 	## Removes stones at coordinates marked with True in self.helper.
 	def _remove(self):
 		self._fill(EMPTY)
 	def _fill(self,filling):
 		for (r,c) in self._helper.getContinuousArea():
 			self._freshHash^=diffHash(r,c,self.board[r][c],filling)
 			self.board[r][c]=filling
 def isLegalPosition(board):
 	boardSize=len(board)
 	temp=[[None]*boardSize for x in range(boardSize)]
 	for r in range(boardSize):
 		for c in range(boardSize):
 			if board[r][c]==EMPTY: continue
 			if temp[r][c]: continue
 			if not dfs([(r,c)],board,temp): return False
 	return True
 def transitionMove(state1,state2):
 	moves=[]
 	for (r,(row1,row2)) in enumerate(zip(state1,state2)):
 		for (c,(item1,item2)) in enumerate(zip(row1,row2)):
 			if item1==EMPTY and item2!=EMPTY:
 				moves.append((r,c,item2))
 	if len(moves)==0:
 		log.info("no new stone")
 		return None
 	elif len(moves)==1:
 		log.info("new stone: %s",moves[0])
 		return moves[0]
 	else:
 		log.warning("too many new stones: %s",moves)
 		return False
 def dfs(stack,board,mask):
 	boardSize=len(board)
 	(r,c)=stack[0]
 	color=board[r][c]
 	while len(stack)>0:
 		(r,c)=stack.pop()
 		if board[r][c]==EMPTY: return True
 		elif board[r][c]!=color: continue
 		elif mask[r][c]: return True
 		mask[r][c]=True
 		for (x,y) in ((0,-1),(-1,0),(0,1),(1,0)):
 			if 0<=r+y<boardSize and 0<=c+x<boardSize:
 				stack.append((r+y,c+x))
 	return False

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):
 	def __init__(self,boardSize=19):
 		super().__init__(boardSize)
 	def listRelevantMoves(self,diff):
 		"""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 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}
 			if action!="-" and (r,c) not in res[colorKey]:
 				res[colorKey].add((r,c))
 				for (ri,ci) in self.listNeighbours(r,c): # in case a stone was played and captured. !! might want to add even more
 					res[1-colorKey].add((ri,ci))
 			# this is rather sloppy but correct. the time will show if it is effective enough
 			# just floodFill from the current intersection, add everything you find and also all the neighbours to be sure
 			if action!="+" and (r,c) not in res[colorKey] and (r,c) not in res[1-colorKey]:
 				self._helper.clear()
 				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))
 					for (rj,cj) in self.listNeighbours(ri,ci):
 						res[colorKey].add((rj,cj))
 						res[1-colorKey].add((rj,cj))
 		return res
 	def listNeighbours(self,r,c):
 		if r>0: yield (r-1,c)
 		if r+1<self.boardSize: yield (r+1,c)
 		if c>0: yield (r,c-1)
 		if c+1<self.boardSize: yield (r,c+1)
 class Engine:
 	def __init__(self,g=None):
 		self._g=g or SpecGo()
 		self._moveList=(set(),set())
 	def load(self,state1,diff):
 		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

 from util import EMPTY
 ## Utility class for finding continuous regions on a Go.board.
 class HelperBoard:
 	def __init__(self,board):
 		self._refBoard=board # Go.board, readonly
 		self._boardSize=len(board)
 		self._board=[[EMPTY]*self._boardSize for i in range(self._boardSize)]
 		self._visited=[0]*(self._boardSize**2)*2
 		self._visitedCount=0
 		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
 		if self._refBoard[r][c]==needle: return True # found something
 		if self._refBoard[r][c]!=filling:
 			if self._refBoard[r][c]==EMPTY: # remember group liberties
 				self._board[r][c]=True
 				self._libs[self._libCount*2]=r
 				self._libs[self._libCount*2+1]=c
 				self._libCount+=1
 			return False # out of area boundary
 		self._board[r][c]=True # set visited
 		self._visited[self._visitedCount*2]=r
 		self._visited[self._visitedCount*2+1]=c
 		self._visitedCount+=1
 		# check neighbors
 		return self.floodFill(filling,r,c-1,needle) or \
 			self.floodFill(filling,r,c+1,needle) or \
 			self.floodFill(filling,r-1,c,needle) or \
 			self.floodFill(filling,r+1,c,needle)
 	def getContinuousArea(self):
 		for i in range(self._visitedCount):
 			yield (self._visited[i*2],self._visited[i*2+1])
 	def getLiberties(self):
 		for i in range(self._libCount):
 			yield (self._libs[i*2],self._libs[i*2+1])
 	def clear(self):
 		for i in range(self._visitedCount):
 			(r,c)=(self._visited[i*2],self._visited[i*2+1])
 			self._board[r][c]=EMPTY
 		self._visitedCount=0
 		for i in range(self._libCount):
 			(r,c)=(self._libs[i*2],self._libs[i*2+1])
 			self._board[r][c]=EMPTY
 		self._libCount=0

src/statebag.py

➞

Show inline comments

 """Theory:
 We have a sequence S of valid board states s_1, ..., s_n.
 We search for a picked subsequence S_p of length k and m additional moves M such that:
 - S_p augmented by M forms a valid sequence of moves
 - k-m is maximal for S_p picked from S
 It is relatively cheap to add new items to S.
 User can change detector parameters, presumably in case the previous don't fit the (current) situation.
 In such a case we assume the new parameters are correct from the current position onwards.
 But the change might have been appropriate even earlier (before the user detected and fixed an error).
 So we try to find the correct crossover point like this:
 - construct a sequence S' = s'_i, ..., s'_n by reanalyzing the positions with a new set of parameters, where s_i is the point of previous user intervention or s_0
 - for each s'_j:
 	- try to append it to S[:j]
 	- try to append it to S'[:j]
 	- 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.
 def estimateDistance(diff):
 	# lot of room for improvements
 	additions=sum(1 for d in diff if d[2]=="+")
 	deletions=sum(1 for d in diff if d[2]=="-")
 	replacements=len(diff)-additions-deletions
 	if additions>0: return additions+replacements
 	elif replacements==0 and deletions>0: return 2 # take n, return 1
 	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
 	def export(self):
 		return exportBoard(self._board)
 	def exportDiff(self,s2):
 		return "vvv\n{0}\n=== {1} ===\n{2}\n^^^".format(self.export(), s2-self, s2.export())
 	def __iter__(self): return iter(self._board)
 	def __getitem__(self,key): return self._board[key]
 	def __sub__(self,x):
 		res=[]
 		for (r,(row1,row2)) in enumerate(zip(self._board,x)):
 			for (c,(item1,item2)) in enumerate(zip(row1,row2)):
 				if item1==item2: continue
 				elif item2==EMPTY: res.append((r,c,"+",item1))
 				elif item1==EMPTY: res.append((r,c,"-",item2))
 				else: res.append((r,c,"*",item1)) # ->to
 		return res
 	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):
 		self._states=[]
 	def pushState(self,board):
 		sn=BoardState(board)
 		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):
 		pass

src/tests/testEngine.py

➞

Show inline comments

 import re
 import os.path
 import logging as log
 from unittest import TestCase
 import config as cfg
 from util import BLACK as B,WHITE as W,EMPTY as _
 from go.core import Go
 from go.engine import SpecGo,Engine
 from statebag import BoardState
 _log=log.getLogger(__name__)
 _log.setLevel(log.INFO)
 _log.propagate=False
 formatter=log.Formatter("%(asctime)s %(levelname)s: %(message)s",datefmt="%Y-%m-%d %H:%M:%S")
 handler=log.FileHandler("/tmp/oneeye.log",mode="w")
 handler.setFormatter(formatter)
 _log.addHandler(handler)
 def simpleLoadSgf(filename):
 	with open(filename) as f:
 		contents=f.read()
 	g=lambda m: tuple(ord(c)-ord('a') for c in reversed(m.group(1)))
 	return [g(m) for m in re.finditer(r"\b[BW]\[([a-z]{2})\]",contents)]
 def listStates(moves):
 	g=Go()
 	res=[BoardState(g.board)]
 	for m in moves:
 		g.doMove(g.toMove,*m)
 		res.append(BoardState(g.board))
 	return res
 class TestTransitions(TestCase):
 	def testBasic(self):
 		s1=BoardState([
 			[_,_,_],
 			[_,_,_],
 			[_,_,_]
 		])
 		s2=BoardState([
 			[_,_,_],
 			[_,B,_],
 			[_,_,_]
 		])
 		g=SpecGo(3)
 		eng=Engine(g)
 		eng.load(s1,s2-s1)
 		self.assertEqual(eng.dfs(s2,1),[(1,1,1)])
 	def testCapture(self):
 		s1=BoardState([
 			[_,W,_],
 			[W,B,_],
 			[_,W,_]
 		])
 		s2=BoardState([
 			[_,W,_],
 			[W,_,W],
 			[_,W,_]
 		])
 		g=SpecGo(3)
 		g.toMove=W
 		eng=Engine(g)
 		eng.load(s1,s2-s1)
 		self.assertEqual(eng.dfs(s2,1),[(W,1,2)])
 	def testMulti(self):
 		s1=BoardState([
 			[_,_,_],
 			[_,_,_],
 			[_,_,_]
 		])
 		s2=BoardState([
 			[_,_,_],
 			[_,B,W],
 			[_,_,_]
 		])
 		g=SpecGo(3)
 		eng=Engine(g)
 		eng.load(s1,s2-s1)
 		self.assertEqual(eng.dfs(s2,2),[(W,1,2),(B,1,1)])
 	def testSnapback(self):
 		s1=BoardState([
 			[B,B,B],
 			[B,_,B],
 			[B,W,B]
 		])
 		s2=BoardState([
 			[_,_,_],
 			[_,_,_],
 			[_,W,_]
 		])
 		g=SpecGo(3)
 		eng=Engine(g)
 		eng.load(s1,s2-s1)
 		self.assertEqual(eng.dfs(s2,2),[(W,2,1),(B,1,1)])
 		s1=BoardState([
 			[_,_,_],
 			[W,B,B],
 			[_,W,W]
 		])
 		s2=BoardState([
 			[_,_,_],
 			[W,B,B],
 			[_,W,_]
 		])
 		eng.load(s1,s2-s1)
 		self.assertEqual(eng.dfs(s2,2),[(W,2,1),(B,2,0)])
 	def testReal(self):
 		files=["O-Takao-20110106.sgf","Sakai-Iyama-20110110.sgf"]
 		g=SpecGo()
 		eng=Engine(g)
 		for f in files:
 			moves=simpleLoadSgf(os.path.join(cfg.srcDir,"tests/data",f))
 			states=listStates(moves)
 			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)
 					if len(seq)!=k: _log.warning("shorter than expected transition sequence:" + msg + "\n" + str(seq))
 					toMove*=-1

0 comments (0 inline, 0 general)