OneEye Changeset - 5b4c6f5a0a28

Changeset - 5b4c6f5a0a28

Parent rev.

Child rev.

[Not reviewed]

default

0 3 1

Laman - 6 years ago 2018-11-29 17:30:15

transposition table

4 files changed with 65 insertions and 32 deletions:

src/go/engine.py

src/go/transpositiontable.py

src/statebag/boardstate.py

src/tests/testEngine.py

0 comments (0 inline, 0 general)

src/go/engine.py

➞

Show inline comments

 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)

src/go/transpositiontable.py

➞

Show inline comments

@@ new file 100644 @@
 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

src/statebag/boardstate.py

➞

Show inline comments

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

src/tests/testEngine.py

➞

Show inline comments

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

0 comments (0 inline, 0 general)