OneEye Changeset - 3cce3db6d4cc

Changeset - 3cce3db6d4cc

Parent rev.

Child rev.

[Not reviewed]

default

0 2 0

Laman - 7 years ago 2017-12-03 11:45:58

work on StateBag

2 files changed with 80 insertions and 1 deletions:

src/go.py

src/statebag.py

0 comments (0 inline, 0 general)

src/go.py

➞

Show inline comments

 import logging as log
 from util import EMPTY,BLACK,WHITE,colorNames
 from gamerecord import GameRecord
 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._temp=[[EMPTY]*boardSize for x in range(boardSize)]
 		self.toMove=BLACK
 		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 move(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
 		self.board[row][col]=color
 		# capture neighbors
 		for r,c in ((-1,0),(1,0),(0,-1),(0,1)):
 			self._clearTemp()
 			if not self._floodFill(-color,row+r,col+c): self._remove()
 		# check for suicide
 		self._clearTemp()
 		if not self._floodFill(color,row,col):
 			self.board[row][col]=EMPTY
 			return False
 		self._record.move(color,row,col)
 		self.toMove=-1*color
 		return True
 	def transitionMove(self,board):
 		res=transitionMove(self.board,board)
 		if not res: return res
 		(r,c,color)=res
 		return self.move(color,r,c)
 	## Checks for liberties of a stone at given coordinates.
+	#
 	#  The stone's group is marked with True in self.temp, ready for capture if needed. Recursively called for stone's neighbors.
+	#
 	#  @return True if alive, False if captured
 	def _floodFill(self,color,row,col):
 		if col<0 or col>=self.boardSize or row<0 or row>=self.boardSize: return False # out of range
 		if self._temp[row][col]: return False # already visited
 		if self.board[row][col]==EMPTY: return True # found a liberty
 		if self.board[row][col]!=color: return False # opponent's stone
 		self._temp[row][col]=True # set visited
 		return self._floodFill(color,row,col-1) or self._floodFill(color,row,col+1) or self._floodFill(color,row-1,col) or self._floodFill(color,row+1,col) # check neighbors
 	## Removes stones at coordinates marked with True in self.temp.
 	def _remove(self):
 		for r in range(self.boardSize):
 			for c in range(self.boardSize):
 				if self._temp[r][c]: self.board[r][c]=EMPTY
 	def _clearTemp(self):
 		for i in range(self.boardSize):
 			for j in range(self.boardSize):
 				self._temp[i][j]=EMPTY
 def exportBoard(board):
 	substitutions={EMPTY:".", BLACK:"X", WHITE:"O"}
 	return "\n".join("".join(substitutions.get(x,"?") for x in row) for row in board)
 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 transitionSequence(state1,state2,diff):
 	return []
 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/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 BLACK,WHITE,EMPTY
 from go import transitionSequence
 ## Crude lower bound on edit distance between states.
 def estimateDistance(diff):
 	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 # ???
 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.diff2Prev=None
 	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,item2,item1)) # from->to
 		return res
 class StateBag:
 	def __init__(self):
 		self._states=[]
 	def pushState(self,board):
 		self._states.append(board)
 		sn=BoardState(board)
 		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
 		self._states.append(sn)
 	def merge(self,branch):
 		pass

0 comments (0 inline, 0 general)