self._helper=HelperBoard(self.board)

		self._hashes=[]

		self._record=GameRecord()

	def listMoves(self,diff=[]):

		return []

	## 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,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._helper.clear()

			if not self._helper.floodFill(-color,row+r,col+c,EMPTY): self._remove()

		self._helper.clear()

		if not self._helper.floodFill(color,row,col,EMPTY):

			self.board[row][col]=EMPTY

			return False

		self._record.move(color,row,col)

		self.toMove=-1*color

		self._hashes.append(self.hash())

		return True

	def undoMove(self,r,c,captures):

		self.toMove*=-1

		self.board[r][c]=self.toMove

		if len(captures)>0:

			self._helper.clear()

			for (r,c) in captures:

				self._helper.floodFill(EMPTY,r,c)

			self._fill(-self.toMove)

		self._hashes.pop()

	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 hash(self):

		return hashBoard(self.board)

	## 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.board[r][c]=filling

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

from util import EMPTY,BLACK,WHITE

from . import core

def transitionSequence(state1, state2, diff, limit=0):

	return []

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.

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

		for d in diff:

			(r,c,action,color)=d

			if action!="-" and (r,c) not in res[colorKey]:

				res[colorKey].add((r,c))

			# this is rather sloppy but correct. the time will show if it is effective enough

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

					if ri>0:

						res[colorKey].add((ri-1,ci))

						res[1-colorKey].add((ri-1,ci))

						res[colorKey].add((ri+1,ci))

						res[1-colorKey].add((ri+1,ci))

					if ci>0:

						res[colorKey].add((ri,ci-1))

						res[1-colorKey].add((ri,ci-1))

						res[colorKey].add((ri,ci+1))

						res[1-colorKey].add((ri,ci+1))

		return res

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

		for i in range(1,10):

			for color in [BLACK,WHITE]:

				self._g.toMove=color

				seq=self.dfs(state2,i)

				if seq:

					seq.reverse()

					return seq

	def dfs(self,state2,limit):

		g=self._g

			if g.board[r][c]!=EMPTY: continue

			neighbours=(

				g.board[r-1][c] if r>0 else None,

				g.board[r][c-1] if c>0 else None,

			)

			g.doMove(g.toMove,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

			)

			if g.hash()==state2.hash(): return [(-1*g.toMove,r,c)]

			if limit>1:

				seq=self.dfs(state2,limit-1)

				if seq:

					return seq

			g.undoMove(r,c,captured)

		return False

eng=Engine()

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

			self._board[r][c]=EMPTY

		self._libCount=0

from unittest import TestCase

from go.engine import SpecGo,Engine

from statebag import BoardState

class TestTransitions(TestCase):

	def testBasic(self):

		s1=BoardState([

			[0,0,0],

			[0,0,0],

			[0,0,0]

		])

		s2=BoardState([

			[0,0,0],

			[0,1,0],

			[0,0,0]

		])

		g=SpecGo(3)

		eng=Engine(g)

		eng.load(s1,s2-s1)

		self.assertEqual(eng.dfs(s2,1),[(1,1,1)])

from unittest import TestCase

class TestLegal(TestCase):

	def testLegal(self):

		board=[

			[0,0,0,0,0],

			[1,1,1,1,1],

			[-1,-1,0,1,0],

			[0,0,0,-1,-1],

			[0,-1,0,-1,0]

		]

		self.assertTrue(isLegalPosition(board))

	def testIllegal(self):

		board=[

			[0,1,0,0,0],

			[1,-1,1,0,0],

			[0,1,0,0,0],

			[0,0,0,0,0],

			[0,0,0,0,0]

		]

		self.assertFalse(isLegalPosition(board))