прикреплённый файл:ttt.py к странице LecturesVMSH/2011-04-20

   1 #!/usr/bin/python
   2 # coding: utf8
   3 '''
   4 Написать непобедимую программу игру в «крестики-нолики 3x3». Условие: нельзя за одну игру вычислять выигрышность одной и той же позиции более одного раза. 
   5 '''
   6 
   7 class ttt:
   8     WINS=((0,1,2),(3,4,5),(6,7,8),(0,3,6),(1,4,7),(2,5,8),(0,4,8),(2,4,6))
   9     CACHE={}
  10     win=0
  11     @classmethod
  12     def New(self,matrix,i,v):
  13         matrix=matrix[:i]+(v,)+matrix[i+1:]
  14         return self.CACHE.setdefault(matrix,self(matrix,3-v))
  15     def __init__(self,matrix=(0,)*9,next=1):
  16         self.field=matrix
  17         self.next=next
  18         self.towin=self.win=self.who()
  19         if not self.win:
  20             self.go=[ttt.New(self.field,i,self.next) for i in xrange(9) if not self.field[i]]
  21         else:
  22             self.go=[]
  23     def who(self):
  24         if self.win: return self.win
  25         for p in self.WINS:
  26             if self.field[p[0]] and \
  27                self.field[p[0]] == self.field[p[1]] and \
  28                self.field[p[0]] == self.field[p[2]]:
  29                 return self.field[p[0]]
  30         if 0 in self.field: return 0
  31         return -1
  32     def mark(self):
  33         if self.towin: return self.towin
  34         nexts=[n.mark() for n in self.go]
  35         if not self.go: print "ERROR"
  36         if self.next in nexts: self.towin=self.next
  37         elif -1 in nexts: self.towin=-1
  38         else: self.towin=3-self.next
  39         return self.towin
  40     def __repr__(self):
  41         s="".join([" XO"[i] for i in self.field])
  42         return ''' +---+
  43 {3}|{0}|
  44 {4}|{1}|
  45  |{2}|
  46  +---+'''.format(s[:3],s[3:6],s[6:],"?12="[self.win],"?12="[self.towin])
  47 
  48 start=ttt()
  49 print len(ttt.CACHE)
  50 start.mark()
  51 me=1   # or 2
  52 s=start
  53 while not s.who():
  54     print s
  55     if s.next==me:
  56         res=s.go[0]
  57         for n in s.go:
  58             if n.towin == me:
  59                 res=n
  60                 break
  61             elif n.towin == -1:
  62                 res=n
  63     else:
  64         i=input("> ")
  65         if i not in xrange(9) or s.field[i]:
  66             print "!",i,"invalid"
  67             continue
  68         res=ttt.New(s.field,i,s.next)
  69     s=res
  70 print s
  71 if s.who()!=-1:
  72     print "=====",s.who(),"wins"
  73 else:
  74     print "===== DRAW"