Source Code for Module MeatEngine.AI.boardRep

  1   
  2   
  3 -class TicTacToeBoard: 
  4 -    def __init__(self, hashVal=0): 
  5          self.squares=[0]*9 
  6          if hashVal!=0: 
  7              for i in range(9): 
  8                  v=hashVal%3 
  9                  hashVal/=3 
 10                  self.squares[i]=v 
 11   
 12 -    def countNum(self,num): 
 13          c=0 
 14          for i in range(9): 
 15              if self.squares[i]==num: 
 16                  c+=1 
 17          return c 
 18           
 19 -    def countX(self): 
 20          return self.countNum(1) 
 21       
 22 -    def countO(self): 
 23          return self.countNum(2) 
 24   
 25 -    def countEmpty(self): 
 26          return self.countNum(0) 
 27   
 28 -    def hashVal(self): 
 29          s=0 
 30          for i in range(9): 
 31              s += self.squares[i] * 3**i 
 32          return s 
 33   
 34 -    def getCanonicalHash(self): 
 35          perm,boardCopy=self.getCanonicalCopy() 
 36          return boardCopy.hashVal() 
 37   
 38 -    def getCanonicalCopy(self): 
 39          maps=[[0,1,2, 
 40                 3,4,5, 
 41                 6,7,8], 
 42                [2,5,8, 
 43                 1,4,7, 
 44                 0,3,6], 
 45                [8,7,6, 
 46                 5,4,3, 
 47                 2,1,0], 
 48                [6,3,0, 
 49                 7,4,1, 
 50                 8,5,2], 
 51                [2,1,0, 
 52                 5,4,3, 
 53                 8,7,6], 
 54                [8,5,2, 
 55                 7,4,1, 
 56                 6,3,0], 
 57                [6,7,8, 
 58                 3,4,5, 
 59                 0,1,2], 
 60                [0,3,6, 
 61                 1,4,7, 
 62                 2,5,8]] 
 63   
 64          bestVal=-1 
 65          bestMap=-1 
 66          for i in range(len(maps)): 
 67              m=maps[i] 
 68              thisVal=0 
 69              for si in range(9): 
 70                  thisVal+=self.squares[m[si]] * 3**si 
 71              if bestVal==-1 or bestVal>thisVal: 
 72                  bestVal=thisVal 
 73                  bestMap=i 
 74          newBoard=TicTacToeBoard() 
 75          bm=maps[bestMap] 
 76          for i in range(9): 
 77              newBoard.squares[i]=self.squares[bm[i]] 
 78   
 79          return bestMap,newBoard 
 80   
 81 -    def whoseTurn(self): 
 82          nX=self.countX() 
 83          nO=self.countO() 
 84          if nX==nO: 
 85              return 1 
 86          if nX-1==nO: 
 87              return 2 
 88          raise "not a valid turn" 
 89          return 0 
 90       
 91 -    def successorMap(self): 
 92          if self.isOver(): 
 93              return None 
 94          if not self.anyMoves(): 
 95              return None 
 96          m={} 
 97          wt=self.whoseTurn() 
 98          for x in range(3): 
 99              for y in range(3): 
100                  p=3*y+x 
101                  perm,bc=self.getCanonicalCopy() 
102                  if bc.isLegalMove(x,y,wt): 
103                      bc.move(x,y,wt) 
104                      v=bc.getCanonicalHash() 
105                      m[p]=v 
106          return m 
107   
108 -    def display(self): 
109          for i in range(3): 
110              for j in range(3): 
111                  p=3*i+j 
112                  print self.squares[p]," ", 
113              print 
114   
115 -    def move(self,x,y,p): 
116          pos=3*y+x 
117          self.squares[pos]=p 
118   
119 -    def isLegalMove(self, x,y,p): 
120          pos=y*3+x 
121          return self.squares[pos]==0 
122   
123 -    def anyMoves(self): 
124          return 0 in self.squares 
125   
126 -    def getWinner(self): 
127          """ 
128          returns 1 if p1 won, 2 if p2 won, 
129          -1 for a draw,  
130          or 0 if game is still ongoing 
131          """ 
132   
133          #print "in getWinner" 
134          patterns=[[0,1,2], 
135                    [3,4,5], 
136                    [6,7,8], 
137                    [0,3,6], 
138                    [1,4,7], 
139                    [2,5,8], 
140                    [0,4,8], 
141                    [2,4,6]] 
142   
143          for p in patterns: 
144              #print "testing pattern",p 
145              isPatGood=True 
146              for si in p: 
147                  #print "testing square index",si 
148                  isPatGood = (isPatGood and (self.squares[si] and self.squares[si]==self.squares[p[0]])) 
149                  #print "isPatGood=",isPatGood 
150              if isPatGood: 
151                  return self.squares[p[0]] 
152   
153          if self.anyMoves(): 
154              return 0 
155          return -1 
156       
157           
158   
159 -    def isOver(self): 
160          w=self.getWinner() 
161          return w!=0 
162   
163 -    def evaluate(self, player, verbose=0): 
164          if self.isOver(): 
165              w=self.getWinner() 
166              if w==player: 
167                  # I win 
168                  return 1000 
169              if w==-1: 
170                  # draw 
171                  return 0 
172              else: 
173                  # I lose 
174                  return -1000 
175               
176               
177          patterns=[[0,1,2], 
178                    [3,4,5], 
179                    [6,7,8], 
180                    [0,3,6], 
181                    [1,4,7], 
182                    [2,5,8], 
183                    [0,4,8], 
184                    [2,4,6]] 
185   
186          v=0 
187   
188          if verbose: 
189              print "evaluating",self.squares 
190          for p in patterns: 
191              if verbose: 
192                  print "pattern",p 
193              vals=[self.squares[x] for x in p] 
194   
195              countMine=0 
196              countEmpty=0 
197              countEnemy=0 
198              for i in range(3): 
199                  if vals[i]==player: 
200                      countMine += 1 
201                  elif vals[i]==0: 
202                      countEmpty += 1 
203                  else: 
204                      countEnemy += 1 
205   
206              if verbose: 
207                  print "countMine",countMine 
208                  print "countEmpty",countEmpty 
209                  print "countEnemy",countEnemy 
210   
211              if countMine==3: 
212                  v+=100 
213              if countMine==2 and countEmpty==1: 
214                  v+=10 
215              if countMine==1 and countEmpty==2: 
216                  v+=1 
217              if countEnemy==3: 
218                  v-=100 
219              if countEnemy==2 and countEmpty==1: 
220                  v-=10 
221              if countEnemy==1 and countEmpty==2: 
222                  v-=1 
223          if verbose: 
224              print "returning",v 
225          return v 
226               
227   
228   
229  if __name__=="__main__": 
230      b=TicTacToeBoard() 
231   
232      b.display() 
233   
234      b.move(0,0,1) 
235      b.move(0,1,2) 
236   
237      b.display() 
238   
239      print b.isOver()         
240   
241      b.move(1,0,1) 
242      b.move(2,0,1) 
243   
244      b.display() 
245      print b.isOver() 
246   
247      totalBoards=3**9 
248   
249      validBoards={} 
250       
251      for i in xrange(totalBoards): 
252          b=TicTacToeBoard(i) 
253          numX=b.countX() 
254          numO=b.countO() 
255          if ((numO==numX or 
256               numO==numX-1)and 
257              b.getCanonicalHash()==i): 
258              numMoves=numX+numO 
259              vb=validBoards.get(numMoves,[]) 
260              vb.append(i) 
261              validBoards[numMoves]=vb 
262   
263      tot=0 
264      vbk=validBoards.keys() 
265      vbk.sort() 
266   
267      f=file("tictactoeboards.txt","wt") 
268      for i in vbk: 
269          print i,len(validBoards[i]) 
270          tot+=len(validBoards[i]) 
271   
272          boards=validBoards[i][:] 
273          boards.sort() 
274          for b in boards: 
275              f.write(`b`) 
276              f.write("\n") 
277      print "total:",tot 
278   
279      openList=[0] 
280      closedList=[] 
281   
282      stateDescs=[] 
283   
284      while openList: 
285          hv=openList.pop() 
286          b=TicTacToeBoard(hv) 
287          succ=b.successorMap() 
288          if hv not in closedList: 
289              closedList.append(hv) 
290              stateDescs.append((9-b.countEmpty(), hv, succ)) 
291          if not succ is None: 
292              for move in succ: 
293                  nextState=succ[move] 
294                  if ((nextState not in openList) and 
295                      (nextState not in closedList)): 
296                      openList.append(nextState) 
297      print "having generated only legal moves," 
298      print "the number of legal moves are:",len(closedList) 
299   
300      """ 
301      stateDescs.sort() 
302   
303      f=file("boardDescs.txt","wt") 
304      for sd in stateDescs: 
305          f.write("%6d, "%sd[1]) 
306          if sd[2]: 
307              for move in sd[2]: 
308                  succState=sd[2][move] 
309                  f.write("%6d, "%succState) 
310          f.write("\n") 
311      f.close() 
312      """ 
313                   
314      countPieces={} 
315   
316      for sd in stateDescs: 
317          pieceCount=sd[0] 
318          oldCount=countPieces.get(pieceCount,0) 
319          countPieces[pieceCount]=oldCount+1 
320   
321      keys=countPieces.keys() 
322      keys.sort() 
323   
324      for k in keys: 
325          print k, countPieces[k] 
326