Генетические алгоритмы поиска в шахматных программах и нейросетях
Альфа-бета алгоритм
В шахматном программировании царит альфа-бета алгоритм поиска лучшего хода. Это оптимизированный перебор для двух сторон на некоторую глубину. Этот алгоритм дает возможность построить шахматную программу базового уровня. Для достижения уровня 1 разряда, мастера и гросса этого мало. Мало потому что дерево поиска растет экспоненциально и чтобы сосчитать поглубже, до 10-12-14 полуходов, нужны эвристики оптимизации поиска.
Недействительное перемещение.
Ключевой эвристикой конца прошлого века стало Недействительное перемещение. Если сторона пропускает ход то это засчитывается как минимум и если минимум уже больше лучшей оценки противника, то дальше можно не продолжать.
Программа Альфа Шахматы
Программа Альфа Шахматы использовала нейросети для оценки позиции, и метод Монте-Карло поиска матовых окончаний. Каждому ходу присваивается оценка для сортировки - случайное число в диапазоне до некоторого значения, выдаваемого нейросетью, ведающей безопасностью короля. Так сделано в Вяленой Рыбе, нынешнем чемпионе.
Генетические алгоритмы
Кроме того, существуют генетические алгоритмы оптимизации поиска где дальше просчитываются только лучшие ходы что повышает вероятность при достижении глубины поиска 12-14 полуходов что программа будет играть в силу гросса.
Кроме того, в глубоких нейросетях совершенно необязательно прогонять все коэффициенты по всем слоям. Можно сокращать немного дельта обучения для условно худших. Это нужно для скорости и для обобщения данных.
FANTOM CHESS.
fantom
Предлагаю вашему вниманию учебный движок с генетическим алгоритмом. Протокол winboard. Программа скомпилирована для Линукс 64 Дебиан 12 и Windows. Т е нужен дистрибутив Линукс где компилятор gcc версии такой же или более новый. Мой линукс 2022 года.
Запуск для Linux:
sudo apt install xboard
chmod +x fantom
xboard -fcp ./fantom
Запуск для Windows:
start.cmd
Ссылка для скачивания:
Вопросы пожелания по адресу:
evgeniy-korniloff@yandex.ru