пока что код не внедрен в саму игру крестики нолики пока что просто тестирую скорость
Текущий код решает полным перебором позицию за 0.45 секунды в итоге создает дерево с оценками -10 проигрыш 0 ничья 10 выигрыш всего получается 55648 комбинаций. Нужно еще ускорить чтобы можно было решать крестики нолики на большом поле.
x=[0, 0, 0, 0, 0, 0, 0, 0, 0]
адреса={0:[[0,1,2],[0,4,8],[0,3,6]], 1:[[0,1,2],[1,4,7]], 2:[[0,1,2],[2,4,6],[2,5,8]],
3:[[0,3,6],[3,4,5]], 4:[[0,3,6],[1,4,7],[0,4,8],[2,4,6],[3,4,5]], 5:[[2,5,8],[3,4,5]],
6:[[0,3,6],[2,4,6],[6,7,8]], 7:[[6,7,8],[1,4,7]], 8:[[6,7,8],[0,4,8],[2,5,8]]}
словарь={}
словарь2={}
def выигрыш(i):
flag=False
for num, k in enumerate(i):
if not k:
cop=i.copy()
cop[num]=глубина
for b in адреса[num]:
if all(cop[ind]%2==очередь and cop[ind] for ind in b):
flag=True
словарь2[tuple(словарь[tuple(i)]+[num])]=10 if очередь%2 else -10
if flag: return True
def перебор(позиция, hist):
if выигрыш(позиция): return
# if глубина!=9:
# if перекрытие(позиция): return
if глубина==9:
for num, b in enumerate(позиция):
if not b:словарь2[tuple(hist+[num])]=0
else:
for num, b in enumerate(позиция):
if not b:
dd=позиция.copy()
dd[num]=глубина
словарь[tuple(dd)]=hist+[num]
for глубина in [1,2,3,4,5,6,7,8,9]:
очередь = глубина & 1
if глубина==1:
for num, b in enumerate(x):
if not b:
xx=x.copy()
xx[num]=глубина
словарь[tuple(xx)]=[num]
else:
for z,z1 in {**словарь}.items():
перебор(list(z), z1)
del словарь[z]
