# HG changeset patch
# User Laman
# Date 2018-11-29 17:30:15
# Node ID 5b4c6f5a0a28a70f72814e9381344242786b434d
# Parent  5f2136fcbebdb496eb5c6e553b46641577526470

transposition table

diff --git a/src/go/engine.py b/src/go/engine.py
--- a/src/go/engine.py
+++ b/src/go/engine.py
@@ -1,4 +1,5 @@
 from .core import PASS
+from .transpositiontable import TranspositionTable
 from . import core
 
 
@@ -7,8 +8,8 @@ from . import core
 # @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)
-	return eng.iterativelyDeepen(state2,colorIn,colorOut)
+	eng.load(state1)
+	return eng.iterativelyDeepen(state2,diff,colorIn,colorOut)
 
 
 class SpecGo(core.Go):
@@ -28,8 +29,9 @@ 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))
+				if action=="*":
+					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]:
@@ -52,28 +54,38 @@ class SpecGo(core.Go):
 
 
 class Engine:
+	"""Class searching for move sequences changing one board state into another."""
 	def __init__(self,g=None):
 		self._g=g or SpecGo()
 		self._moveList=(set(),set())
+		self._transpositions=TranspositionTable()
 
-	def load(self,state1,diff):
+	def load(self,state1):
 		self._g.load(state1)
+
+	def iterativelyDeepen(self,state2,diff,colorIn,colorOut):
+		"""Search for a move sequence from the loaded state to state2. Tries progressively longer sequences."""
 		self._moveList=self._g.listRelevantMoves(diff)
-
-	def iterativelyDeepen(self,state2,colorIn,colorOut):
 		startDepth=1 if colorIn==colorOut else 2
 		self._g.toMove=colorIn
 
-		for i in range(startDepth,6,2):
-			seq=self.dfs(state2,i)
+		for i in range(startDepth,5,2):
+			seq=self._dfs(state2,i)
 			if seq:
 				seq.reverse()
 				return seq
 		return None
 
-	def dfs(self,state2,limit):
+	def _dfs(self,state2,limit):
+		"""Search for a "limit" move sequence from the loaded state to state2."""
 		g=self._g
 		moveSet=self._moveList[(1-g.toMove)>>1]
+		transKey=(g.hash()*state2.hash()*limit)&0xffffffff
+
+		transSeq=self._transpositions.get(transKey)
+		if transSeq is not None:
+			return transSeq[:] if transSeq else transSeq
+
 		for m in moveSet.copy():
 			if not g.doMove(g.toMove,*m): continue
 			captured=g.captures[:g.captureCount]
@@ -82,11 +94,13 @@ class Engine:
 				self._moveList[(1-g.toMove)>>1].remove(m)
 
 			if limit>1:
-				seq=self.dfs(state2,limit-1)
+				seq=self._dfs(state2,limit-1)
 				if seq:
 					self._undoMove(m,captured)
 					seq.append((g.toMove,*m))
+					self._transpositions.put(transKey,seq[:])
 					return seq
+				else: self._transpositions.put(transKey,False)
 
 			if limit==1 and g.hash()==state2.hash():
 				self._undoMove(m,captured)
diff --git a/src/go/transpositiontable.py b/src/go/transpositiontable.py
new file mode 100644
--- /dev/null
+++ b/src/go/transpositiontable.py
@@ -0,0 +1,13 @@
+class TranspositionTable:
+	def __init__(self,capacity=2**20):
+		self._capacity=capacity
+		self._table=[None]*capacity
+
+	def put(self,key,val):
+		self._table[key%self._capacity]=(key,val)
+
+	def get(self,key):
+		res=self._table[key%self._capacity]
+		if res is None: return None
+		elif res[0]==key: return res[1]
+		else: return None
diff --git a/src/statebag/boardstate.py b/src/statebag/boardstate.py
--- a/src/statebag/boardstate.py
+++ b/src/statebag/boardstate.py
@@ -63,15 +63,16 @@ class BoardState:
 
 	def __getitem__(self,key): return self._board[key]
 
-	def __sub__(self,x):
+	## Compute difference self-s.
+	def __sub__(self,s):
 		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
+		for (r,(row,rowS)) in enumerate(zip(self._board,s)):
+			for (c,(item,itemS)) in enumerate(zip(row,rowS)):
+				if item==itemS: continue
+				elif itemS==EMPTY: res.append((r,c,"+",item))
+				elif item==EMPTY: res.append((r,c,"-",itemS))
+				else: res.append((r,c,"*",item)) # ->to
 		return res
 
 	def __eq__(self,x):
diff --git a/src/tests/testEngine.py b/src/tests/testEngine.py
--- a/src/tests/testEngine.py
+++ b/src/tests/testEngine.py
@@ -32,8 +32,9 @@ class TestTransitions(TestCase):
 		])
 		g=SpecGo(3)
 		eng=Engine(g)
-		eng.load(s1,s2-s1)
-		self.assertEqual(eng.dfs(s2,1),[(1,1,1)])
+		eng.load(s1)
+		eng._moveList=eng._g.listRelevantMoves(s2-s1)
+		self.assertEqual(eng._dfs(s2,1),[(1,1,1)])
 
 	def testCapture(self):
 		s1=BoardState([
@@ -49,8 +50,9 @@ class TestTransitions(TestCase):
 		g=SpecGo(3)
 		g.toMove=W
 		eng=Engine(g)
-		eng.load(s1,s2-s1)
-		self.assertEqual(eng.dfs(s2,1),[(W,1,2)])
+		eng.load(s1)
+		eng._moveList=eng._g.listRelevantMoves(s2-s1)
+		self.assertEqual(eng._dfs(s2,1),[(W,1,2)])
 
 	def testMulti(self):
 		s1=BoardState([
@@ -65,8 +67,9 @@ class TestTransitions(TestCase):
 		])
 		g=SpecGo(3)
 		eng=Engine(g)
-		eng.load(s1,s2-s1)
-		self.assertEqual(eng.dfs(s2,2),[(W,1,2),(B,1,1)])
+		eng.load(s1)
+		eng._moveList=eng._g.listRelevantMoves(s2-s1)
+		self.assertEqual(eng._dfs(s2,2),[(W,1,2),(B,1,1)])
 
 	def testSnapback(self):
 		s1=BoardState([
@@ -81,8 +84,9 @@ class TestTransitions(TestCase):
 		])
 		g=SpecGo(3)
 		eng=Engine(g)
-		eng.load(s1,s2-s1)
-		self.assertEqual(eng.dfs(s2,2),[(W,2,1),(B,1,1)])
+		eng.load(s1)
+		eng._moveList=eng._g.listRelevantMoves(s2-s1)
+		self.assertEqual(eng._dfs(s2,2),[(W,2,1),(B,1,1)])
 
 		s1=BoardState([
 			[_,_,_],
@@ -94,8 +98,9 @@ class TestTransitions(TestCase):
 			[W,B,B],
 			[_,W,_]
 		])
-		eng.load(s1,s2-s1)
-		self.assertEqual(eng.dfs(s2,2),[(W,2,1),(B,2,0)])
+		eng.load(s1)
+		eng._moveList=eng._g.listRelevantMoves(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"]
@@ -109,11 +114,11 @@ class TestTransitions(TestCase):
 				toMove=B
 				for (i,(s1,s2)) in enumerate(zip(states,states[k:])):
 					diff=s2-s1
-					eng.load(s1,diff)
+					eng.load(s1)
 					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)
+					colorOut=colorIn if k&1 else -colorIn
+					seq=eng.iterativelyDeepen(s2,diff,colorIn,colorOut)
+					msg="\n>>> {0} ({1}, {2})\n>>> {3}\n".format(f,k,i,str(seq))+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))