На поле размером 3×4 вместо 479 миллионов возможных комбинаций алгоритм анализирует около 1 миллиона, отсеивая остальные. Необходимо оптимизировать алгоритм для работы с более крупными игровыми полями.
Алгоритм основан на методе полного перебора с отсеиванием нерелевантных позиций. Процесс анализа включает следующие этапы
1. Проверка на выигрыш. финиш(позиция, hist) Если текущий ход принадлежит игроку и существует возможность выигрыша за один ход, позиция помечается как выигрышная. Дальнейший анализ этой ветки прекращается
2. Защита от проигрыша перекрытие(позиция, hist) проверяется возможность выигрыша соперника на следующем ходу. Если такой ход существует позиция сохраняется для предотвращения проигрыша. Остальные варианты в этой ветке не анализируются
3.Проверка на ничью if глубина==12 При достижении максимальной глубины (12 ходов) и отсутствии выигрышных позиций для обеих сторон. Позиция помечается как ничейная
4. В остальных случаях позиция сохраняется в словаре для дальнейшего анализа на большей глубине
def перебор(позиция, hist):
if финиш(позиция, hist): return
if глубина!=12:
if перекрытие(позиция, hist): return
if глубина==12:
словарь[tuple(hist+[позиция.index(0)])]=0
else:
for num, b in enumerate(позиция):
if not b:
dd=позиция.copy()
dd[num]=глубина
temp_словарь[tuple(dd)]=hist+[num]
Простой
