Optimization of generating a complete game tree

Hello! There is a task to generate a full tree for N-dimensional noughts and crosses. While this problem solves this code:

class GameTree: evaled = 0 # кол-во просчитанных листьев def __init__(self, players, points, cp=0, level=0): # players - list(list(list(int))) - список игроков, # каждый игрок - список его ходов, # каждый ход - список его координат # points - list(list(int)) - список ходов, # каждый ход - список его координат # cp - int - индекс игрока, который сейчас ходит # level - int - номер хода в партии (используется для вывода) GameTree.evaled += 1 players = slist(deepcopy(players)) # чтобы не дать изменять исходный список points = slist(deepcopy(points)) if cp == len(players): # если сходил последний cp = 0 self.children = [] for i in players: # если кто-то уже выиграл if won(i): self.children = None return if points == []: # если нет ходов self.children = None return me = players[cp] enemies = players.without(players[cp]) if len(me)>=2: # если уже можно выиграть for i in points: me_ = me + [i] if won(me_): # если можно выиграть, сделав ход i players[cp].append(i) self.children = GameTree(n, players, points.without(i), cp+1, level=level+1) # нужно совершить ход i return blocked = False for i in points: for en in enemies: en_ = en + [i] if won(en_): # если кто-то из противников может выиграть, совершив ход i buff = deepcopy(players) players[cp].append(i) self.children.append(GameTree(players, points.without(i), cp+1, level=level+1)) # нужно попробовать ему помешать players = buff blocked = True if blocked: # если кто-то мог выиграть return for i in points: # для каждого возможного хода buff = deepcopy(players) players[cp].append(i) self.children.append(GameTree(n, players, points.without(i), cp+1, level=level+1)) # попробовать, что получится players = buff 

And everything seems to be fine, but for three dimensions and two players, a tree is generated indecently long. But, since it is possible to come to the same state of the field in many different ways, now the tree looks like in fig. 1. It would be great to turn it into rice. 2. (sorry, I can't explain it with words)

For this was born such a monster:

 if str(players) in list(GameTree.nodes.keys()): # если есть в уже рассчитанных листьях, есть такое состояние поля self.children.append(GameTree.node[players]) # 'соединить' его с текущим return else: new = GameTree(players, points.without(i), cp+1, level=level+1) # рассчитать GameTree.nodes[str(players)] = new # запомнить self.children.append(new) 

With it, the code takes the form:

 class GameTree: evaled = 0 nodes = {} def __init__(self, players, points, cp=0, level=0): GameTree.evaled += 1 players = slist(deepcopy(players)) points = slist(deepcopy(points)) if cp == len(players): cp = 0 self.children = [] for i in players: if won(i): self.children = None return if points == []: self.children = None return me = players[cp] enemies = players.without(players[cp]) if len(me)>=2: for i in points: me_ = me + [i] if won(me_): players[cp].append(i) if str(players) in list(GameTree.nodes.keys()): self.children.append(GameTree.node[players]) else: new = GameTree(players, points.without(i), cp+1, level=level+1) GameTree.nodes[str(players)] = new self.children.append(new) return blocked = False for i in points: for en in enemies: en_ = en + [i] if won(en_): buff = deepcopy(players) players[cp].append(i) if str(players) in list(GameTree.nodes.keys()): self.children.append(GameTree.node[players]) return else: new = GameTree(players, points.without(i), cp+1, level=level+1) GameTree.nodes[str(players)] = new self.children.append(new) players = buff blocked = True if blocked: return for i in points: buff = deepcopy(players) players[cp].append(i) if str(players) in list(GameTree.nodes.keys()): self.children.append(GameTree.node[str(players)]) return else: new = GameTree(players, points.without(i), cp+1, level=level+1) GameTree.nodes[str(players)] = new self.children.append(new) players = buff 

Not only is the code terrible, it still does not work. Could you help me? Here is the whole code, if you need it (there are still a lot of ugly places, if someone tells you how to improve it in terms of style (and maybe even performance), I will be very grateful):

 from copy import deepcopy from time import time from threading import Thread from math import factorial point_class = lambda a: a.count(0) class slist(list): def without(self, x): b = self[:] b.remove(x) return b def to_ter_arr(i): if i<3: return [i] return to_ter_arr(i // 3) + [i%3] def gen(n): ret = slist() for i in range(pow(3, n)): buff = to_ter_arr(i) buff = [0]*(n-len(buff))+buff buff = list(map(lambda a: a-1, buff)) ret.append(buff) return ret def three(a, b, c): if a == [] or b == [] or c== []: return False for i in range(len(a)): s = [a[i], b[i], c[i]] if not s in [[1,1,1], [-1,-1,-1], [0,0,0], [1,0,-1], [-1,0,1]]: return False return True and a!=b and a!=c and b!=c def won(pl): for a in pl: for b in pl: for c in pl: if three(a, b, c): return True return False def output(s): f.write(s+'\n') class GameTree: evaled = 0 def __init__(self, players, points, cp=0, level=0): GameTree.evaled += 1 players = slist(deepcopy(players)) points = slist(deepcopy(points)) if cp == len(players): cp = 0 self.children = [] for i in players: if won(i): output('{}{} won {}'.format(' '*level, level, players.index(i))) self.children = None return if points == []: output('{}{} draw'.format(' '*level, level, 'draw')) self.children = None return me = players[cp] enemies = players.without(players[cp]) if len(me)>=2: for i in points: me_ = me + [i] if won(me_): players[cp].append(i) output('{}{} {} {} next - win'.format(' '*level, level, cp, i)) self.children = GameTree(players, points.without(i), cp+1, level=level+1) return blocked = False for i in points: for en in enemies: en_ = en + [i] if won(en_): buff = deepcopy(players) players[cp].append(i) output('{}{} {} {} blocking {}'.format(' '*level, level, cp, i, players.index(en))) self.children.append(GameTree(players, points.without(i), cp+1, level=level+1)) players = buff blocked = True if blocked: return for i in points: buff = deepcopy(players) players[cp].append(i) output('{}{} {} {} try'.format(' '*level, level, cp, i)) self.children.append(GameTree(players, points.without(i), cp+1, level=level+1)) players = buff def progress(): global aprox, game, start while game.is_alive(): print('\r{} / {}, {} s'.format(GameTree.evaled, aprox, time()-start), end='') n = int(input('N = ')) points = gen(n) aprox = factorial(len(points)) pc = int(input('Количество игроков: ')) center = slist([0 for i in range(n)]) players = slist([[center]]+[[] for i in range(pc-1)]) file_name = input('Имя файла: ') f = open(file_name, 'w') show = input('Показывать прогресс (Д\Н, Д по умолчанию)') if show == 'H' or show == 'н': show = False elif show == 'Д' or show == 'д' or show == '': show = True else: print('Ошибка!!!') exit(1) print('\nCenter =', center) print('Players =', players) print('Points =', points) print('Aproximate number of leaves:', aprox) start = time() output('0 0 [0, 0] root') game = Thread(target = GameTree, kwargs = {'players': players, 'points': points.without(center), 'cp': 1, 'level': 1}) prog = Thread(target = progress) game.start() if show: prog.start() else: game.join() print(time()-start, 's')