SHARE
TWEET

Untitled

a guest Dec 14th, 2019 97 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. tree = {}
  2.  
  3.  
  4. def is_winner(state):
  5.     if state[:3] == '111' or state[3:6] == '111' or state[6:9] == '111' or state[:7:3] == '111' or state[1:8:3] == '111' or state[2:9:3] == '111' or state[:9:4] == '111' or state[2:7:2] == '111':
  6.         return -1
  7.     if state[:3] == '222' or state[3:6] == '222' or state[6:9] == '222' or state[:7:3] == '222' or state[1:8:3] == '222' or state[2:9:3] == '222' or state[:9:4] == '222' or state[2:7:2] == '222':
  8.         return 1
  9.     return 0
  10.  
  11.  
  12. def fill_tree(state, num, step):
  13.     global tree
  14.     winner = is_winner(state)
  15.     if winner == -1 or winner == 1 or step == 0:
  16.         tree[state] = [winner]
  17.         return
  18.     tree[state] = []
  19.     for i in range(9):
  20.         if state[i] == '0':
  21.             newstate = state[:i]+num+state[i+1:]
  22.             tree[state].append([newstate, 0])
  23.             if num == '1':
  24.                 fill_tree(newstate, '2', step-1)
  25.             else:
  26.                 fill_tree(newstate, '1', step-1)
  27.  
  28.  
  29. def count_tree(state, step):
  30.     global tree
  31.     if len(tree[state]) == 1 and tree[state][0] in [-1, 1, 0]:
  32.         if step == 9:
  33.             return tree[state][0]
  34.         sum = 9-step
  35.         cstep = 9-step
  36.         while cstep > 1:
  37.             cstep-=1
  38.             sum*=cstep
  39.         sum*=tree[state][0]
  40.         return sum
  41.     for v in tree[state]:
  42.         res = count_tree(v[0], step+1)
  43.         v[1] = res
  44.     sum = 0
  45.     if step % 2 == 1:
  46.         flag = 0
  47.         for v in tree[state]:
  48.             if v[1] < 0:
  49.                 continue
  50.             sum += v[1]
  51.             flag = 1
  52.         if flag == 0:
  53.             sum = -1
  54.     else:
  55.         for v in tree[state]:
  56.             if v[1] < 0:
  57.                 sum = -1
  58.                 break
  59.             sum += v[1]
  60.     return sum
  61.  
  62.  
  63. ans = {}
  64. def build_json(state):
  65.     global ans
  66.     ans[state] = []
  67.     try:
  68.         if len(tree[state]) == 1 and type(tree[state][0]) is int:
  69.             if tree[state][0] == 1:
  70.                 ans[state].append(('smth','smth'))                 # бот победил
  71.             else:
  72.                 ans[state].append(('smth', 'smth'))                # бот дошел до ничьи
  73.             return
  74.     except KeyError:
  75.         pass
  76.     for c in tree[state]:
  77.         if type(tree[c[0]][0]) is int:
  78.             ans[state].append((c[0],'draw'))           # ничья, c[0] - ход человека, привел к ничье
  79.         else:
  80.             maxvalue = -1000000000
  81.             maxstate = ''
  82.             for pc in tree[c[0]]:
  83.                 try:
  84.                     if len(tree[pc[0]]) == 1 and type(tree[pc[0]][0]) is int and tree[pc[0]][0] > 0:
  85.                         maxstate = pc[0]
  86.                         break
  87.                     if pc[1] > maxvalue:
  88.                         maxvalue = pc[1]
  89.                         maxstate = pc[0]
  90.                 except IndexError:
  91.                     pass
  92.             if maxstate == '':
  93.                 pass
  94.             ans[state].append((c[0], maxstate))
  95.             build_json(maxstate)
  96.  
  97.  
  98. fill_tree('000000000', '1', 9)
  99. count_tree('000000000', 0)
  100. build_json('000000000')
  101. # print(ans)
  102. print(tree)
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top