chess_engine_using_python

Шахматный движок с использованием Python

Этот репозиторий содержит реализацию шахматного движка с использованием Minimax , алгоритма обрезки Alpha-Beta и поиска покоя . Блокнот Jupyter внутри Docker-контейнера используется для кодирования. Все Jupyter Notebook также доступны в виде образа докера.

Ознакомьтесь с документом проекта, чтобы увидеть подробный анализ.

Используемый внешний модуль

• Питоновые шахматы

Как запустить с помощью докера

docker pull codewithnk/chess-engine-using-python:latest

docker run -p 8888:8888 -v $( pwd ) codewithnk/chess-engine-using-python:latest

Алгоритмы шахматного движка

Минмакс

Теория

Ядро игры в шахматы в минмаксе. Minmax обычно связывает черную фигуру с MAX, а белую фигуру с MIN и всегда оценивает с точки зрения белых.

Алгоритм Minmax — это алгоритм состязательного поиска в теории игр. Он использует дерево игры и включает в себя MIN и MAX для двух игроков. Оба игрока пытаются свести на нет действия другого. Макс пытается максимизировать результат, тогда как MIN пытается его минимизировать. Оба игрока играют поочередно, при условии, что оба играют оптимально. Оптимальная игра означает, что оба игрока играют по правилу, т. е. МИН минимизирует результат, а МАКС максимизирует результат.

Алгоритм minmax использует подход поиска в глубину для поиска результата. Кроме того, он также использует возврат и рекурсию. Алгоритм пройдет до конечного узла, а затем вернется назад, сравнивая все дочерние значения. Он выберет минимальное или максимальное значение в зависимости от того, чья очередь. Затем он передаст значение обратно своему родителю. Он использует статическую функцию оценки для определения значения на каждом конечном узле. Он использует преимущества игры с нулевой суммой.

Выполнение

Шахматный движок с использованием Minmax

Временная сложность

Minmax использует поиск в глубину (DFS) в дереве игры, следовательно, временная сложность алгоритма minmax равна O(b**m) , где b — коэффициент ветвления дерева игры, а m — максимальная глубина дерева.

Космическая сложность

Пространственная сложность алгоритма minmax также аналогична DFS, которая равна O(bm) , где b — коэффициент ветвления дерева игры, а m — максимальная глубина дерева.

Полнота

Алгоритм Minmax завершен. Он обязательно найдет решение, если оно существует, в конечном дереве поиска.

Оптимальность

Алгоритм Minmax оптимален, если оба противника играют оптимально.

---

Альфа-бета обрезка

Теория

Алгоритм minmax можно оптимизировать, сократив несколько ветвей. Обрезанные ветки — это те, которые не повлияют на результат. Это улучшит временную сложность. Эта версия minmax известна как minmax с обрезкой альфа-бета. Его также называют альфа-бета-алгоритмом.
В Alpha-Beta Pruning есть два значения: Alpha и Beta. Ниже приведены несколько моментов, которые следует учитывать при выборе альфа- и бета-версии:

Кое-что об Альфе(α)

• Альфа — это наивысшее значение, найденное на пути MAX.
• Начальное значение альфа является отрицательной бесконечностью, поскольку значение альфа будет продолжать увеличиваться или оставаться неизменным с каждым ходом. Если мы выберем какое-то значение, отличное от отрицательной бесконечности, то может возникнуть сценарий, в котором все значения альфа могут быть меньше выбранного значения. Итак, нам нужно выбрать наименьшее возможное значение, а это отрицательная бесконечность.
• Альфа обновляется только игроком MAX.

Некоторые моменты о бета(β)

• Бета — это наименьшее значение, найденное на пути MIN.
• Начальное значение бета является положительной бесконечностью, поскольку значение бета будет продолжать уменьшаться или оставаться неизменным с каждым ходом. Если мы выберем какое-то значение, отличное от положительной бесконечности, может возникнуть сценарий, в котором все значения бета могут быть больше выбранного значения. Итак, нам нужно выбрать максимально возможное значение, а это положительная бесконечность.
• Бета-значение обновляется только игроком MIN.

При возврате родительскому элементу передается только значение узла, а не значения альфа и бета.

Условие обрезки альфа-бета:

 α >= β

Переместить порядок

Эффективность альфа-бета-алгоритма во многом зависит от порядка обхода. Он играет решающую роль во временной и пространственной сложности.

Худший заказ

В некоторых случаях из дерева игры не удаляется ни один узел или поддерево. В этом случае лучший ход происходит в правом поддереве Дерева игры. Это приведет к увеличению временной сложности.

Идеальный порядок

В этом случае сокращается максимальное количество узлов и поддеревьев. Лучшие ходы происходят в левом поддереве. Это уменьшит временную и пространственную сложность.

Выполнение

Chess Engine с использованием альфа-бета-обрезки

Временная сложность

Алгоритм Альфа-Бета также использует поиск в глубину (DFS) в дереве игры.

• В случае худшего порядка: O(b^m)
• В случае идеального порядка: O(b^m/2)

Космическая сложность

• В случае худшего порядка: O(bm)
• В случае идеального порядка: O(b(m/2))

Полнота

Алгоритм Альфа-Бета завершен. Он обязательно найдет решение, если оно существует, в конечном дереве поиска.

Оптимальность

Алгоритм Альфа-Бета оптимален, если оба противника играют оптимально.

---

Поиск покоя

Поиск покоя — это модификация, основанная на сокращении альфа-бета с мин-максом. Тишина означает тишина. Этот поиск оценивает только тихие ходы. Другими словами, после определенной глубины он использует только ходы захвата для расчета следующих ходов. Поиск покоя позволяет избежать эффекта горизонта.
Эффект горизонта возникает, когда мы ищем только на определенную глубину, но может случиться так, что если мы посмотрим еще на один уровень глубже, то перемещение может принести меньше очков. Поиск покоя использует только приемы захвата, чтобы предотвратить это. Поиск покоя также снижает коэффициент ветвления на разных уровнях, что приводит к быстрому алгоритму.

Временная сложность

Алгоритм поиска покоя также использует поиск в глубину (DFS) в дереве игры.

• В случае худшего порядка: O(b^m)
• В случае идеального порядка: O(b^m/2)

Космическая сложность

• В случае худшего порядка: O(bm)
• В случае идеального порядка: O(b(m/2))

Полнота

Алгоритм поиска покоя завершен. Он обязательно найдет решение, если оно существует, в конечном дереве поиска.

Оптимальность

Алгоритм поиска покоя оптимален, если оба противника играют оптимально.

---

Ключевой вывод

• Число исследуемых узлов за ход в Alpha Beta уменьшено в 10 раз по сравнению с Minmax.
• Время, затрачиваемое на поиск лучшего хода, также сокращается в 10 раз в Alpha Beta по сравнению с Minmax.
• Поиск покоя хорошо работает на большей глубине.
• Поиск покоя — самый быстрый алгоритм из всех трех.
• Поиск покоя оценивает меньше узлов.
• Поиск покоя может привести к повторным перемещениям, если не обращаться с ним должным образом.