# HG changeset patch # User Laman # Date 2017-12-12 22:59:39 # Node ID 077600f0c5f8d5b1211adc632a8733fc8de98c02 # Parent 4e67f9e9f027c2f605d291a2f512c07c8894a21c engine v1 mostly finished diff --git a/src/go/core.py b/src/go/core.py --- a/src/go/core.py +++ b/src/go/core.py @@ -1,6 +1,6 @@ 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 @@ -12,6 +12,7 @@ class Go: 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=[]): @@ -41,15 +42,19 @@ class Go: 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) @@ -57,6 +62,9 @@ class Go: (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) 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 @@ -import core +from util import EMPTY,BLACK,WHITE +from . import core def transitionSequence(state1, state2, diff, limit=0): @@ -6,8 +7,8 @@ def transitionSequence(state1, state2, d 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): @@ -26,7 +27,7 @@ class SpecGo(core.Go): (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() @@ -51,8 +52,8 @@ class SpecGo(core.Go): 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): @@ -61,20 +62,35 @@ class Engine: def iterativelyDeepen(self,state2): for i in range(1,10): - seq=self.dfs(state2,i) - if seq: return seq + 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 - 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 r0 else None, + g.board[r][c+1] if c1: 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() diff --git a/src/statebag.py b/src/statebag.py --- a/src/statebag.py +++ b/src/statebag.py @@ -16,19 +16,9 @@ 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 """ -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): @@ -51,11 +41,7 @@ class BoardState: 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) @@ -73,8 +59,7 @@ class BoardState: return res def __eq__(self,x): - # might want to use hash - return self._board==x._board + return self.hash()==x.hash() class StateBag: diff --git a/src/tests/testEngine.py b/src/tests/testEngine.py new file mode 100644 --- /dev/null +++ b/src/tests/testEngine.py @@ -0,0 +1,22 @@ +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)]) diff --git a/src/util.py b/src/util.py --- a/src/util.py +++ b/src/util.py @@ -1,3 +1,4 @@ +import random import multiprocessing import logging as log @@ -34,3 +35,19 @@ class MsgQueue: 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