прикреплённый файл:xoai.py к странице LecturesVMSH/Python/2014-04-11

   1 #!/usr/bin/env python
   2 # coding: utf
   3 '''
   4 Решатель для крестиков-ноликов
   5 '''
   6 
   7 import xoproto
   8 import random
   9 
  10 class Solver:
  11     def __init__(self, size, win):
  12         '''Set field size and winning combination length'''
  13         self.proto = xoproto.Proto()
  14         self.proto.INIT(size, win)
  15         self.initial = "."*size**2
  16 
  17     def next(self, board=None):
  18         '''Suggest next move'''
  19         if not board: board = self.proto.INFO().split()[4]
  20         if self.Tree[board][1]:
  21             board2 = random.choice(self.Tree[board][1])
  22             return "MOVE {},{} {}".format(*self.proto.diff(board, board2)[0])
  23         else:
  24             return "ENDGAME {}".format(self.Tree[board][0])
  25 
  26     def generate(self):
  27         '''Create gamestate table'''
  28         self.Tree={}
  29         self.Tree[self.initial]=self.select(self.initial,"X","O")
  30         self.proto.INIT(self.proto.size, self.proto.win)
  31 
  32     def select(self, board, turn, other):
  33         '''Choose best possible moves for turn'''
  34         # запомнить build по всем пустым местам
  35         gen = [self.build(k, board) for k in xrange(len(board)) if board[k]=="."]
  36         # если есть выигрыш -- выигрышные ходы
  37         ret = [turn, [b for b,g in gen if g[0]==turn]]
  38         # если есть ничья -- ничейные ходы
  39         if not ret[1]:
  40             ret = ["DRAW", [b for b,g in gen if g[0]=="DRAW"]]
  41         # иначе проигрыш
  42         if not ret[1]:
  43             ret = [other, [b for b,g in gen if g[0]==other]]
  44         #print "\n".join(board[i*self.proto.size:(i+1)*self.proto.size] for i in xrange(self.proto.size))
  45         #print turn,ret
  46         return ret
  47 
  48     def build(self, ind, oldboard):
  49         '''Create gamestate subtabel for oldboard[ind] move'''
  50         # Чей ход?
  51         turn,other = oldboard.count("X") > oldboard.count("O") and "OX" or "XO"
  52         # Сформировать новое поле
  53         board = oldboard[:ind]+turn+oldboard[ind+1:]
  54         # Если уже проверено, вернуть результат
  55         if board in self.Tree:
  56             return board, self.Tree[board]
  57         # Проверить, а не конец ли игры?
  58         x,y = ind%self.proto.size, ind/self.proto.size
  59         self.proto.SET(board, x, y)
  60         ret = self.proto.check().split()[-1]
  61         if ret in ("DRAW","X","O"):
  62             self.Tree[board] = [ret, []]
  63         # Если не конец, отсмотреть все возможные ходы
  64         else:
  65             self.Tree[board] = self.select(board, other, turn)
  66         return board, self.Tree[board]
  67 
  68 if __name__ == "__main__":
  69     import sys
  70     solver = Solver(3, 3)
  71     solver.generate()
  72     print "Solver table:",len(solver.Tree)
  73     req, ret = "VERSION", ""
  74     while req != "." and not ret.startswith("ENDGAME"):
  75         print solver.proto.command("BOARD")
  76         print solver.next()
  77         req = raw_input("> ")
  78         ret=solver.proto.command(req)
  79         print ret