пока что код не внедрен в саму игру крестики нолики пока что просто тестирую скорость
Текущий код решает полным перебором позицию за 0.68 секунды в итоге создает дерево с оценками -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 оценка(позиция, num):
if глубина>=5:
for b in адреса[num]:
if all(позиция[ind]%2==очередь and позиция[ind]>0 for ind in b):
if очередь==1:
return 10
else: return -10
if 0 not in позиция:
return 0
else:
return None
else:
return None
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!=0 else -10
if flag: return True
def перебор(позиция, hist):
if выигрыш(позиция): return
# if глубина!=9:
# if перекрытие(позиция): return
for num, b in enumerate(позиция):
if not b:
dd=позиция.copy()
dd[num]=глубина
zz=оценка(dd, num)
if zz is not None:
словарь2[tuple(hist+[num])]=zz
else: словарь[tuple(dd)]=hist+[num]
for глубина in [1,2,3,4,5,6,7,8,9]:
очередь=0 if глубина%2==0 else 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]
