Оптимізація алгоритму мінімакс з альфа-бета відсіканням для систем шахового штучного інтелекту

Анотація

У роботі розглянуто підходи до навчання штучної моделі гри в шахи. Базовим методом пошуку обрано алгоритм мінімакс з альфа-бета відсіканням, реалізований мовою програмування Пайтон з відповідною шаховою бібліотекою. Альфа-бета відсікання зменшує обчислювальну складність обходу ігрового дерева, відкидаючи на ранніх етапах ті гілки, які не впливають на остаточне рішення. До базового алгоритму додано евристичні розширення: ітеративне поглиблення, таблиці транспозицій з хешуванням Зобриста, впорядкування ходів за принципом пріоритету взяття найбільш цінної фігури найменш цінним нападником, евристику вбивці та історичну евристику, а також пошук спокою для послаблення ефекту горизонту. Розроблено адаптивну оцінкову функцію, яка враховує матеріальний баланс, таблиці позиційних оцінок, безпеку короля, структуру пішаків, мобільність фігур і контроль ключових полів. Модель навчено на вибірці понад сто тисяч партій рівнів від аматорського до гросмейстерського. За результатами експериментів, поєднання альфа-бета відсікання з впорядкуванням ходів і таблицями транспозицій зменшує кількість оцінюваних вузлів у середньому у сто двадцять разів відносно стандартного мінімаксу на глибині п'яти півходів, а час прийняття рішення скорочується з дев'яноста двох цілих і чотирьох десятих секунди до нуля цілих і сорока трьох сотих секунди. У модельованих матчах проти шахового рушія модель демонструє високий відсоток перемог на початкових рівнях складності (до дев'яноста шести цілих і п'яти десятих відсотка на нульовому рівні). Як перспективний напрям подальшого розвитку запропоновано архітектуру інтеграції нейромережевого оцінювача на базі ефективно оновлюваної штучної нейронної мережі у класичне альфа-бета дерево пошуку, що дозволить поєднати інтерпретованість класичного методу з адаптивністю глибокого навчання. Запропонований підхід придатний для систем підтримки прийняття рішень у детермінованих іграх з повною інформацією та в задачах стратегічного планування.