Control Systems and Computers, N4, 2024, Стаття 3
Novikov O.A., Yanovsky V.V. Analysis of Search and Multi-Agent Algorithms in the Pac-Man Game. Control Systems and Computers. 2024. 4. С.
УДК 004.94
А.О. Новіков, аспірант ННІ комп’ютерних наук та штучного інтелекту кафедри математичного моделювання та аналізу даних, Харківський національний університет ім. В.Н. Каразіна, пл. Свободи, 4, Харків, Україна, 61022, ORCID: https://orcid.org/0009-0004-5914-7098, artem.slick@gmail.com
В.В. Яновський, доктор фіз.-мат. наук, професор, завідувач теоретичним відділом, “Інститут монокристалів” Національної Академії наук України, просп. Науки, 60, Харків, Україна, 61001,
ORCID: https://orcid.org/0000-0003-0461-749X, yanovsky@isc.kharkov.ua
АНАЛІЗ ПОШУКОВИХ І МУЛЬТИАГЕНТНИХ АЛГОРИТМІВ У ГРІ PAC-MAN
Вступ. У даній роботі досліджується ефективність пошукових та мультиагентних алгоритмів у контексті гри Pac-Man. Гра 0 моделює завдання управління автономними системами у двовимірному середовищі, де агент стикається з динамічними перешкодами. Використання класичних пошукових алгоритмів, таких як A*, BFS, а також мультиагентних підходів, таких як Alpha-Beta, Expectimax та Monte Carlo Tree Search (MCTS), дозволяє дослідити різні стратегії для вирішення задач оптимізації шляху та ухилення від динамічних загроз (привидів).
Мета статті. Метою даного дослідження є аналіз продуктивності різних алгоритмів у різних за складністю лабіринтах, зокрема за показниками середнього балу, часу виконання та відсотка перемог. Це дослідження спрямоване на порівняння ефективності пошукових та мультиагентних алгоритмів в умовах змінного середовища.
Методи. У дослідженні використано системний підхід та метод експериментального моделювання. Ефективність алгоритмів оцінювалася шляхом проведення численних експериментів у лабіринтах з різним рівнем складності.
Результати. Отримані результати показують, що пошукові алгоритми (A* та BFS) демонструють високу продуктивність у менш динамічних середовищах, тоді як мультиагентні алгоритми (Expectimax, Alpha-Beta, MCTS) більш ефективні в складніших лабіринтах з багатьма динамічними загрозами. Expectimax продемонстрував найкращі результати в середовищах із випадковими діями супротивників, тоді як MCTS показав високу продуктивність у великих та складних середовищах.
Висновки. Дослідження виявило, що вибір алгоритму залежить від складності лабіринту та необхідності врахування дій динамічних супротивників. Пошукові алгоритми є ефективними у спрощених умовах, тоді як мультиагентні підходи є перспективними для складних середовищ з динамічними загрозами.
Ключові слова: алгоритми пошуку, мультиагентні алгоритми, Pac-Man, оптимізація шляху, Alpha-Beta, Expectimax, MCTS.
