# HG changeset patch
# User Laman
# Date 2017-12-14 14:11:07
# Node ID f9ab2070bd69d432829f1cb08bee296bbcfa8a9b
# Parent  0cb3fbe06b5d87fe5a12a98a4d41f76f908311b3

Engine: more tests and fixes

diff --git a/src/analyzer/__init__.py b/src/analyzer/__init__.py
--- a/src/analyzer/__init__.py
+++ b/src/analyzer/__init__.py
@@ -1,8 +1,7 @@
 import logging as log
 
 from .grid import Grid
-from util import BLACK,WHITE,EMPTY
-from go.core import exportBoard
+from util import BLACK,WHITE,EMPTY, exportBoard
 
 
 class ImageAnalyzer:
diff --git a/src/go/core.py b/src/go/core.py
--- a/src/go/core.py
+++ b/src/go/core.py
@@ -15,9 +15,6 @@ class Go:
 		self._hashes=[]
 		self._record=GameRecord()
 
-	def listMoves(self,diff=[]):
-		return []
-
 	## Executes a move.
 	#
 	#  Doesn't check for kos. Suicide not allowed.
@@ -47,13 +44,15 @@ class Go:
 
 	def undoMove(self,r,c,captures):
 		assert self.board[r][c]==-1*self.toMove, "{0}!={1}".format(self.board[r][c],-1*self.toMove)
-		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)
+			for (ri,ci) in captures:
+				self._helper.floodFill(EMPTY,ri,ci)
+			self._fill(self.toMove)
+
+		self.board[r][c]=EMPTY
+		self.toMove*=-1
 		self._hashes.pop()
 
 	def transitionMove(self,board):
@@ -79,11 +78,6 @@ class Go:
 			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)]
diff --git a/src/go/engine.py b/src/go/engine.py
--- a/src/go/engine.py
+++ b/src/go/engine.py
@@ -15,7 +15,7 @@ class SpecGo(core.Go):
 		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.
+		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())
 		for d in diff:
@@ -23,7 +23,10 @@ class SpecGo(core.Go):
 			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)
@@ -31,20 +34,17 @@ class SpecGo(core.Go):
 				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))
-					if ri+1<self.boardSize:
-						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))
-					if ci+1<self.boardSize:
-						res[colorKey].add((ri,ci+1))
-						res[1-colorKey].add((ri,ci+1))
+					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):
@@ -55,9 +55,9 @@ class Engine:
 		self._g.load(state1)
 		self._moveList=self._g.listRelevantMoves(diff)
 
-	def iterativelyDeepen(self,state2):
+	def iterativelyDeepen(self,state2,toMove=None):
 		for i in range(1,10):
-			for color in [BLACK,WHITE]:
+			for color in [toMove] if toMove else [BLACK,WHITE]:
 				self._g.toMove=color
 				seq=self.dfs(state2,i)
 				if seq:
@@ -74,7 +74,7 @@ class Engine:
 				g.board[r][c-1] if c>0 else None,
 				g.board[r][c+1] if c+1<g.boardSize else None
 			)
-			g.doMove(g.toMove,r,c)
+			if not g.doMove(g.toMove,r,c): continue
 			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
diff --git a/src/statebag.py b/src/statebag.py
--- a/src/statebag.py
+++ b/src/statebag.py
@@ -16,7 +16,7 @@ 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
+from util import EMPTY, hashBoard,exportBoard
 from go.engine import transitionSequence
 
 
@@ -43,6 +43,12 @@ class BoardState:
 	def hash(self):
 		return hashBoard(self._board)
 
+	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]
diff --git a/src/tests/data/O-Takao-20110106.sgf b/src/tests/data/O-Takao-20110106.sgf
new file mode 100644
--- /dev/null
+++ b/src/tests/data/O-Takao-20110106.sgf
@@ -0,0 +1,30 @@
+(;SZ[19]FF[3]
+PW[Takao Shinji]
+WR[9d]
+PB[O Rissei]
+BR[9d]
+EV[66th Honinbo League]
+DT[2011-01-06]
+KM[6.5]
+RE[B+R]
+US[GoGoD95]
+;B[pd];W[dd];B[pq];W[dp];B[qo];W[fq];B[cj];W[qf];B[ph];W[qc];B[qd];W[pc]
+;B[od];W[rd];B[re];W[rc];B[qe];W[nc];B[jp];W[ch];B[me];W[cl];B[ej];W[eh]
+;B[gj];W[dc];B[pk];W[lp];B[nq];W[ln];B[lq];W[mp];B[mq];W[jn];B[cn];W[bp]
+;B[km];W[lm];B[kn];W[ll];B[ko];W[kl];B[jl];W[jk];B[kk];W[ok];B[kj];W[pl]
+;B[pj];W[om];B[mj];W[ql];B[rk];W[qk];B[qj];W[rl];B[rj];W[oo];B[mc];W[nb]
+;B[hd];W[el];B[ik];W[en];B[gg];W[jd];B[cf];W[dg];B[bc];W[be];B[ce];W[bd]
+;B[ef];W[df];B[lb];W[ee];B[cd];W[cc];B[hf];W[fi];B[fj];W[hh];B[gh];W[kc]
+;B[lc];W[nd];B[ne];W[hc];B[gc];W[ic];B[gb];W[if];B[ie];W[gi];B[hi];W[je]
+;B[ig];W[ih];B[jf];W[hj];B[hk];W[ii];B[ij];W[hb];B[bb];W[bf];B[jb];W[kb]
+;B[ka];W[gd];B[fd];W[ge];B[fe];W[fc];B[fb];W[ff];B[ec];W[ed];B[fc];W[gf]
+;B[db];W[cb];B[ca];W[eg];B[id];W[ha];B[ga];W[ea];B[da];W[hg];B[kf];W[ba]
+;B[aa];W[ac];B[fm];W[ad];B[jc];W[dl];B[jh];W[ji];B[ki];W[kh];B[jg];W[hi]
+;B[jj];W[fn];B[ei];W[fh];B[bk];W[bl];B[gq];W[gr];B[hq];W[hr];B[ir];W[ro]
+;B[qp];W[rn];B[ml];W[rq];B[rp];W[sp];B[rr];W[sr];B[qq];W[sq];B[fr];W[er]
+;B[fp];W[fs];B[eq];W[fr];B[rs];W[qn];B[go];W[gn];B[ep];W[dq];B[hn];W[gm]
+;B[gl];W[hm];B[po];W[pn];B[nl];W[ol];B[nj];W[lo];B[op];W[np];B[ia];W[se]
+;B[sf];W[sd];B[rf];W[jr];B[iq];W[kp];B[kq];W[is];B[hs];W[gs];B[kr];W[fl]
+;B[oc];W[ob];B[al];W[am];B[ak];W[bm];B[in];W[bi];B[lk];W[mm];B[im];W[nk]
+;B[mk]
+)
diff --git a/src/tests/data/Sakai-Iyama-20110110.sgf b/src/tests/data/Sakai-Iyama-20110110.sgf
new file mode 100644
--- /dev/null
+++ b/src/tests/data/Sakai-Iyama-20110110.sgf
@@ -0,0 +1,38 @@
+(;SZ[19]FF[3]
+PW[Iyama Yuta]
+WR[9d]
+PB[Sakai Hideyuki]
+BR[8d]
+EV[20th Ryusei]
+RO[Block B, Game 10]
+DT[2011-01-10 (Broadcast 2011-06-17)]
+KM[6.5]
+RE[W+0.5]
+US[GoGoD95]
+;B[pd];W[dd];B[pq];W[cp];B[eq];W[qo];B[pm];W[lq];B[iq];W[oo];B[np];W[op]
+;B[oq];W[nq];B[no];W[nr];B[on];W[qp];B[qq];W[rq];B[rr];W[rp];B[qs];W[or]
+;B[pr];W[nn];B[lo];W[qm];B[ql];W[pn];B[om];W[rl];B[rm];W[qn];B[lp];W[qk]
+;B[pl];W[rj];B[kq];W[kr];B[mq];W[do];B[cf];W[di];B[fc];W[df];B[cc];W[ce]
+;B[dc];W[cg];B[gp];W[nc];B[oc];W[nd];B[qe];W[jc];B[lc];W[lb];B[cr];W[fo]
+;B[dj];W[cj];B[ck];W[dk];B[ej];W[cl];B[ci];W[bk];B[bj];W[ck];B[dh];W[ei]
+;B[kb];W[fi];B[kc];W[pf];B[qf];W[pg];B[lf];W[nf];B[pp];W[po];B[rn];W[sm]
+;B[sn];W[sl];B[pj];W[sr];B[mr];W[pk];B[ok];W[qj];B[sj];W[si];B[ri];W[oj]
+;B[nm];W[nk];B[nl];W[ol];B[sh];W[rk];B[ok];W[mk];B[ll];W[ol];B[jd];W[lk]
+;B[ff];W[id];B[je];W[fd];B[gd];W[ec];B[eb];W[ed];B[gc];W[ge];B[hd];W[go]
+;B[fe];W[fq];B[gq];W[fp];B[fr];W[kl];B[gi];W[eg];B[fg];W[gh];B[fh];W[eh]
+;B[hi];W[mn];B[lm];W[ln];B[km];W[kn];B[jm];W[jn];B[im];W[jq];B[lr];W[ip]
+;B[jp];W[in];B[io];W[hm];B[ik];W[mm];B[hl];W[ml];B[jh];W[nb];B[ob];W[rg]
+;B[qg];W[qh];B[rh];W[qi];B[rf];W[fb];B[db];W[rs];B[ss];W[mo];B[mp];W[rs]
+;B[ns];W[qr];B[os];W[oa];B[pa];W[bd];B[bq];W[gb];B[he];W[cq];B[br];W[bb]
+;B[bc];W[ac];B[cd];W[be];B[ef];W[de];B[fj];W[dg];B[hb];W[gk];B[gj];W[jk]
+;B[il];W[gl];B[hk];W[kg];B[jg];W[bp];B[gm];W[fm];B[hn];W[lg];B[kf];W[ki]
+;B[mg];W[mh];B[mf];W[ng];B[fl];W[gn];B[fk];W[hp];B[hq];W[ho];B[em];W[jo]
+;B[kp];W[dq];B[dr];W[ep];B[er];W[cb];B[ga];W[da];B[fa];W[fn];B[el];W[ps]
+;B[ap];W[ao];B[aq];W[bn];B[na];W[ma];B[kh];W[lh];B[jj];W[kj];B[ji];W[oa]
+;B[pb];W[ca];B[qs];W[ea];B[fb];W[ps];B[jl];W[kk];B[qs];W[od];B[pe];W[ps]
+;B[oe];W[ne];B[qs];W[qc];B[pc];W[ps];B[of];W[og];B[qs];W[rd];B[rb];W[ps]
+;B[ab];W[aa];B[qs];W[qb];B[qa];W[ps];B[hm];W[ka];B[ja];W[ld];B[la];W[ra]
+;B[sa];W[ka];B[kd];W[qs];B[dn];W[le];B[la];W[mb];B[cn];W[cm];B[en];W[co]
+;B[ke];W[me];B[mc];W[ka];B[ad];W[ae];B[la];W[gf];B[gg];W[ka];B[na];W[la]
+;B[oa];W[sk];B[sg];W[si];B[hf];W[sj]
+)
diff --git a/src/tests/testEngine.py b/src/tests/testEngine.py
--- a/src/tests/testEngine.py
+++ b/src/tests/testEngine.py
@@ -1,20 +1,51 @@
+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([
-			[0,0,0],
-			[0,0,0],
-			[0,0,0]
+			[_,_,_],
+			[_,_,_],
+			[_,_,_]
 		])
 		s2=BoardState([
-			[0,0,0],
-			[0,1,0],
-			[0,0,0]
+			[_,_,_],
+			[_,B,_],
+			[_,_,_]
 		])
 		g=SpecGo(3)
 		eng=Engine(g)
@@ -23,33 +54,83 @@ class TestTransitions(TestCase):
 
 	def testCapture(self):
 		s1=BoardState([
-			[0,-1,0],
-			[-1,1,0],
-			[0,-1,0]
+			[_,W,_],
+			[W,B,_],
+			[_,W,_]
 		])
 		s2=BoardState([
-			[0,-1,0],
-			[-1,0,-1],
-			[0,-1,0]
+			[_,W,_],
+			[W,_,W],
+			[_,W,_]
 		])
 		g=SpecGo(3)
-		g.toMove=-1
+		g.toMove=W
 		eng=Engine(g)
 		eng.load(s1,s2-s1)
-		self.assertEqual(eng.dfs(s2,1),[(-1,1,2)])
+		self.assertEqual(eng.dfs(s2,1),[(W,1,2)])
 
 	def testMulti(self):
 		s1=BoardState([
-			[0,0,0],
-			[0,0,0],
-			[0,0,0]
+			[_,_,_],
+			[_,_,_],
+			[_,_,_]
 		])
 		s2=BoardState([
-			[0,0,0],
-			[0,1,-1],
-			[0,0,0]
+			[_,_,_],
+			[_,B,W],
+			[_,_,_]
 		])
 		g=SpecGo(3)
 		eng=Engine(g)
 		eng.load(s1,s2-s1)
-		self.assertEqual(eng.dfs(s2,2),[(-1,1,2),(1,1,1)])
+		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:]):
+					diff=s2-s1
+					eng.load(s1,diff)
+					seq=eng.iterativelyDeepen(s2,toMove)
+					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
diff --git a/src/tests/testGo.py b/src/tests/testGo.py
--- a/src/tests/testGo.py
+++ b/src/tests/testGo.py
@@ -1,26 +1,27 @@
 from unittest import TestCase
 
+from util import BLACK as B,WHITE as W,EMPTY as _
 from go.core import isLegalPosition, Go
 
 
 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]
+			[_,_,_,_,_],
+			[B,B,B,B,B],
+			[W,W,_,B,_],
+			[_,_,_,W,W],
+			[_,W,_,W,_]
 		]
 		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]
+			[_,B,_,_,_],
+			[B,W,B,_,_],
+			[_,B,_,_,_],
+			[_,_,_,_,_],
+			[_,_,_,_,_]
 		]
 		self.assertFalse(isLegalPosition(board))
 
@@ -29,19 +30,35 @@ class TestMove(TestCase):
 	def testCapture(self):
 		g=Go(3)
 		g.load([
-			[0,1,0],
-			[1,-1,0],
-			[0,1,0]
+			[_,B,_],
+			[B,W,_],
+			[_,B,_]
 		])
-		g.toMove=1
-		g.doMove(1,1,2)
+		g.toMove=B
+		g.doMove(B,1,2)
 		self.assertEqual(g.board,[
-			[0,1,0],
-			[1,0,1],
-			[0,1,0]
+			[_,B,_],
+			[B,_,B],
+			[_,B,_]
 		])
 
 		g._helper.clear()
 		for row in g._helper._board:
 			for x in row:
 				self.assertEqual(x,0)
+
+	def testUndo(self):
+		g=Go(3)
+		g.load([
+			[_,B,_],
+			[B,W,_],
+			[_,B,_]
+		])
+		g.toMove=B
+		g.doMove(B,1,2)
+		g.undoMove(1,2,((1,1),))
+		self.assertEqual(g.board,[
+			[_,B,_],
+			[B,W,_],
+			[_,B,_]
+		])
diff --git a/src/util.py b/src/util.py
--- a/src/util.py
+++ b/src/util.py
@@ -51,3 +51,8 @@ def hashBoard(board):
 		for (c,item) in enumerate(row):
 			res^=zobristNums[r][c][item+1]
 	return res
+
+
+def exportBoard(board):
+	substitutions={EMPTY:".", BLACK:"X", WHITE:"O"}
+	return "\n".join("".join(substitutions.get(x,"?") for x in row) for row in board)