OneEye Changeset - 077600f0c5f8

Changeset - 077600f0c5f8

Parent rev.

Child rev.

[Not reviewed]

default

0 4 1

Laman - 7 years ago 2017-12-12 22:59:39

engine v1 mostly finished

5 files changed with 81 insertions and 33 deletions:

src/go/core.py

src/go/engine.py

src/statebag.py

src/tests/testEngine.py

src/util.py

0 comments (0 inline, 0 general)

src/go/core.py

➞

Show inline comments

 import logging as log
 from util import EMPTY,BLACK,WHITE,colorNames
+from util import EMPTY,BLACK,WHITE, colorNames,hashBoard
 from .helperboard import HelperBoard
 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.toMove=BLACK
 		self._helper=HelperBoard(self.board)
 		self._hashes=[]
 		self._record=GameRecord()
 	def listMoves(self,diff=[]):
 		return []
 	## Executes a move.
@@ @@ -38,28 +39,35 @@ class Go: @@
 		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,color,r,c,captures):
 		self.board[r][c]=color
 	def undoMove(self,r,c,captures):
 		assert 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(-color)
 			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():

src/go/engine.py

➞

Show inline comments

 import core
 from util import EMPTY,BLACK,WHITE
 from . import core
 def transitionSequence(state1, state2, diff, limit=0):
 	return []
 class SpecGo(core.Go):
 	def __init__(self):
 		super().__init__()
 	def __init__(self,boardSize=19):
 		super().__init__(boardSize)
 	def load(self,state):
 		for (r,row) in enumerate(state):
 			for (c,x) in enumerate(row):
 				self.board[r][c]=x
@@ @@ -23,13 +24,13 @@ class SpecGo(core.Go): @@
 		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
 			colorKey=(1-color)<<1 # {-1,1}->{1,0}
 			if action!="-" and (r,c) not in res[colorKey]:
-				res[colorKey].append((r,c))
+				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():
@@ @@ -48,33 +49,48 @@ class SpecGo(core.Go): @@
 						res[colorKey].add((ri,ci+1))
 						res[1-colorKey].add((ri,ci+1))
 		return res
 class Engine:
 	def __init__(self):
 		self._g=SpecGo()
 	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: return seq
 				if seq:
 					seq.reverse()
 					return seq
 	def dfs(self,state2,limit):
 		g=self._g
 		for (r,c) in self._moveList[g.toMove]:
 		for (r,c) in self._moveList[(g.toMove-1)>>1]:
 			if g.board[r][c]!=EMPTY: continue
 			neighbours=(
 				g.board[r-1][c] if r>0 else None,
 				g.board[r+1][c] if r<g.boardSize else None,
 				g.board[r][c-1] if c>0 else None,
 				g.board[r][c+1] if c<g.boardSize else None
+			)
 			g.doMove(g.toMove,r,c)
 			if g.board==state2: return [(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:
 					seq.append((r,c))
+					seq.append((-1*g.toMove,r,c))
 					return seq
-			g.undoMove(m)
+			g.undoMove(r,c,captured)
 		return False
 eng=Engine()

src/statebag.py

➞

Show inline comments

@@ @@ -13,25 +13,15 @@ So we try to find the correct crossover @@
 - 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
 """
 import random
 from util import EMPTY
 from util import EMPTY, hashBoard
 from go.engine import transitionSequence
 rand=random.Random()
 rand.seed(361)
 zobristNums=tuple(
 	tuple(
 		tuple(rand.getrandbits(32) for i in range(3)) for c in range(19)
 	) for r in range(19)
+)
 ## Crude lower bound on edit distance between states.
 def estimateDistance(diff):
 	# lot of room for improvements
 	additions=sum(1 for d in diff if d[2]=="+")
 	deletions=sum(1 for d in diff if d[2]=="-")
@@ @@ -48,17 +38,13 @@ class BoardState: @@
 		self._next=None
 		self.moves=[]
 		self.weight=0
 		self.diff2Prev=None
 	def hash(self):
 		res=0
 		for (r,row) in enumerate(self._board):
 			for (c,item) in enumerate(row):
 				res^=zobristNums[r][c][item+1]
 		return res
 		return hashBoard(self._board)
 	def __iter__(self): return iter(self._board)
 	def __getitem__(self,key): return self._board[key]
 	def __sub__(self,x):
@@ @@ -70,14 +56,13 @@ class BoardState: @@
 				elif item2==EMPTY: res.append((r,c,"+",item1))
 				elif item1==EMPTY: res.append((r,c,"-",item2))
 				else: res.append((r,c,"*",item1)) # ->to
 		return res
 	def __eq__(self,x):
 		# might want to use hash
 		return self._board==x._board
 		return self.hash()==x.hash()
 class StateBag:
 	def __init__(self):
 		self._states=[]

src/tests/testEngine.py

➞

Show inline comments

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

src/util.py

➞

Show inline comments

 import random
 import multiprocessing
 import logging as log
 EMPTY=0
 BLACK=1
@@ @@ -31,6 +32,22 @@ class MsgQueue: @@
 			log.info(msg)
 			if msg[0]=="!kill": break
 			self._handleEvent(msg)
 	def setHandler(self,handler):
 		self._handleEvent=handler
 rand=random.Random()
 rand.seed(361)
 zobristNums=tuple(
 	tuple(
 		tuple(rand.getrandbits(32) for i in range(3)) for c in range(19)
 	) for r in range(19)
+)
 def hashBoard(board):
 	res=0
 	for (r,row) in enumerate(board):
 		for (c,item) in enumerate(row):
 			res^=zobristNums[r][c][item+1]
 	return res

0 comments (0 inline, 0 general)