ВИЧЕРПНИЙ ЕВРИСТИЧНИЙ ПОШУК ДЛЯ РОЗВ'ЯЗАННЯ ДЕТЕРМІНОВАНОЇ СКІНЧЕНОЇ ГРИ З НУЛЬОВОЮ СУМОЮ

Анотація

Хрестики-нулики (W3T) – це комбінаторне розширення класичної гри в хрестики-нулики, що відрізняється правилом, що гравці можуть розміщувати будь-які позначки на кожному ході. Ця додаткова гнучкість вносить значну стратегічну складність і досі залишала теоретичний результат гри невирішеним. У цьому дослідженні ми ретельно розглядаємо розв'язність W3T, побудувавши повне представлення її простору станів та всіх допустимих послідовностей ходів, використовуючи спеціально розроблену спрямовану ациклічну структуру графа, яка називається Атлас. Скінченна та детермінована природа гри дозволяє вичерпний прохід усіх допустимих позицій, що завершується повним маркуванням станів за допомогою ретроградного аналізу. Ми визначаємо та застосовуємо мітки результатів – виграш, програш або нічия – що поширюються від кінцевих позицій вгору по графу. Наша реалізація використовує потрійну схему кодування для унікального представлення станів дошки, з ефективним доступом до пам'яті та повторним використанням станів, що полегшується цілочисельними масивами. Результати демонструють, що W3T не лише розв'язується в класичному сенсі ігор з нульовою сумою з ідеальною інформацією, але й є вимушеною перемогою для першого гравця за оптимальної гри. Ця робота пропонує нову методологію для розв'язання подібних ігор зі скінченними задачами та підкреслює важливість структурної оптимізації в дослідженні простору станів. Запропонований фреймворк є прикладом форми символічного штучного інтелекту, застосованої до вичерпного міркування в просторі станів, пропонуючи прозору альтернативу статистичним підходам до навчання, які зазвичай використовуються в системах прийняття рішень для Інтернету речей.