Source Code for Module MeatEngine.AI.mtdf

  1   
  2  """MTD(f) 
  3   
  4  from http://www.cs.vu.nl/~aske/mtdf.html 
  5   
  6  The name of the algorithm is short for MTD(n, f), which stands for 
  7  something like Memory-enhanced Test Driver with node n and value f. 
  8  """ 
  9   
 10  import boardRep 
 11   
 12   
 13   
 14  POSINFINITY=99999 
 15  NEGINFINITY=-99999 
 16   
 17  AIPLAYER=1 
 18   
 19 -class TranspositionTableEntry: 
 20 -    def __init__(self): 
 21          self.lowerBound = NEGINFINITY 
 22          self.upperBound = POSINFINITY 
 23          self.bestMove = None 
 24          self.furthestDepthSearched = -1 
 25          self.isTerminal = False 
 26   
 27 -class TranspositionTable: 
 28 -    def __init__(self): 
 29          self.cache={} 
 30           
 31 -    def lookup(self, node, depth): 
 32          ttn=self.cache.get(node,None) 
 33          if ttn is None: 
 34              return ttn 
 35          if depth<=ttn.furthestDepthSearched: 
 36              return ttn 
 37          if ttn.isTerminal: 
 38              return ttn 
 39          del self.cache[node] 
 40          return None 
 41   
 42 -    def storeLowerBound(self, node, value): 
 43          t=self.cache.get(node, TranspositionTableEntry()) 
 44          t.lowerBound=max(value,t.lowerBound) 
 45          self.cache[node]=t 
 46   
 47 -    def storeUpperBound(self, node, value): 
 48          t=self.cache.get(node, TranspositionTableEntry()) 
 49          t.upperBound=min(value,t.upperBound) 
 50          self.cache[node]=t 
 51   
 52 -    def storeDepth(self, node, value): 
 53          t=self.cache.get(node, TranspositionTableEntry()) 
 54          t.furthestDepthSearched = value 
 55          self.cache[node]=t 
 56   
 57 -    def storeBestMove(self, node, value): 
 58          t=self.cache.get(node, TranspositionTableEntry()) 
 59          t.bestMove = value 
 60          self.cache[node]=t 
 61   
 62 -    def setTerminal(self, node, value): 
 63          t=self.cache.get(node, TranspositionTableEntry()) 
 64          t.isTerminal = value 
 65          self.cache[node]=t 
 66   
 67           
 68   
 69       
 70   
 71  transTable=TranspositionTable() 
 72   
 73   
 74 -def mtdf(node, f, depth): 
 75      #print "in MTD(f) with node %d, firstGuess %d, depth %d"%(node, f, depth) 
 76      g=f 
 77      upperBound=POSINFINITY 
 78      lowerBound=NEGINFINITY 
 79      while lowerBound<upperBound: 
 80          if g==lowerBound: 
 81              beta = g+1 
 82          else: 
 83              beta = g 
 84          g = alphaBetaWithMemory(node, beta-1, beta, depth, depth) 
 85          if g< beta: 
 86              upperBound=g 
 87          else: 
 88              lowerBound=g 
 89      return g 
 90   
 91   
 92 -def alphaBetaWithMemory(node, alpha, beta, depth, printDepth): 
 93      indent=printDepth-depth 
 94      indentString="    "*indent 
 95      #print indentString,"in ABwM(node=%d, alpha=%d, beta=%d, depth=%d)"%(node,alpha,beta,depth) 
 96      transTableInfo=transTable.lookup(node, depth) 
 97   
 98      if transTableInfo: 
 99          #print indentString,"got transTableInfo: [%d, %d] depth: %d"%(transTableInfo.lowerBound, 
100          #                                                             transTableInfo.upperBound, 
101          #                                                             transTableInfo.furthestDepthSearched) 
102          if transTableInfo.lowerBound >= beta: 
103              return transTableInfo.lowerBound 
104          if transTableInfo.upperBound <= alpha: 
105              return transTableInfo.upperBound 
106          alpha = max(alpha, transTableInfo.lowerBound) 
107          beta = min(beta, transTableInfo.upperBound) 
108   
109      terminal=isTerminal(node) 
110      if depth==0 or terminal: 
111          g=evaluate(node, AIPLAYER) 
112          #print indentString,"evaluating [%d] got %d"%(node,g) 
113      elif isMaximizing(node): 
114          g = NEGINFINITY 
115          a = alpha 
116          for c in getChildren(node): 
117              if g >= beta: 
118                  break 
119              g=max(g,alphaBetaWithMemory(c, a, beta, depth-1, printDepth)) 
120              a=max(a,g) 
121      else: 
122          g = POSINFINITY 
123          b = beta 
124          for c in getChildren(node): 
125              if g <= alpha: 
126                  break 
127              g = min(g,alphaBetaWithMemory(c, alpha, b, depth-1, printDepth)) 
128              b = min(b,g) 
129   
130      if g <= alpha: 
131          transTable.storeUpperBound(node,g) 
132      elif g > alpha and g < beta: 
133          transTable.storeLowerBound(node,g) 
134          transTable.storeUpperBound(node,g) 
135          raise "never happens" 
136      else: 
137          transTable.storeLowerBound(node,g) 
138      transTable.storeDepth(node, depth) 
139      transTable.setTerminal(node, terminal) 
140      return g 
141   
142                     
143 -def iterativeDeepening(node): 
144      #print "in iterative deepening of node", node 
145      firstGuess=0 
146      for d in range(1,12): 
147          firstGuess=mtdf(node, firstGuess,d) 
148          #print "first guess after depth %d is %d"%(d,firstGuess) 
149          #print "I would check the time here" 
150      return firstGuess 
151   
152 -def isMaximizing(node): 
153      board=boardRep.TicTacToeBoard(node) 
154      return board.whoseTurn()==AIPLAYER 
155       
156 -def isTerminal(node): 
157      board=boardRep.TicTacToeBoard(node) 
158      return board.isOver() 
159   
160 -def getChildren(node): 
161      board=boardRep.TicTacToeBoard(node) 
162      sm=board.successorMap() 
163      return sm.values() 
164   
165 -def evaluate(node, player, verbose=0): 
166      board=boardRep.TicTacToeBoard(node) 
167      return board.evaluate(player, verbose) 
168       
169 -def getBestMoves(node, depth, guess=0): 
170      board=boardRep.TicTacToeBoard(node) 
171      bestMoves=set() 
172      if board.isOver(): 
173          return bestMoves 
174      sm=board.successorMap() 
175      nodeValue=mtdf(node, guess, depth) 
176      for move in sm.keys(): 
177          child=sm[move] 
178          childValue=iterativeDeepening(child) 
179          if childValue == nodeValue: 
180              bestMoves.add(move) 
181      return bestMoves 
182   
183  if __name__=="__main__": 
184      f=file("boardDescs.txt") 
185      fLines=f.readlines() 
186      f.close() 
187   
188      for boardIndex in range(len(fLines)): 
189          splitLine=fLines[boardIndex].split(',') 
190          boardHash=int(splitLine[0]) 
191   
192          v=iterativeDeepening(boardHash) 
193   
194          print boardHash,v,getBestMoves(boardHash, 10, v) 
195