Гра в стратегічні ігри з мінімаксним алгоритмом

На цьому уроці ми дослідимо популярний алгоритм, який називається мінімакс . Ми також вивчимо деякі його додаткові функції для дружнього сусідства, такі як евристичні показники , ітеративне поглиблення та альфа-бета-обрізка . Використовуючи ці методи, ми можемо створити більш гнучкий та потужний агент гри. Він зможе змагатися у багатьох викликах, включаючи стратегічну гру Isolation.

У моєму попередньому дописі Як виграти судоку, ми дізналися, як навчити комп’ютери розв’язувати головоломки судоку. Якщо ви ще не читали, продовжуйте і швидко прочитайте. Але це був насправді лише спосіб намочити ноги, перш ніж зануритися у складніші методи ігрових агентів. Особливо ті методи, які можуть робити стратегічні ходи проти суперника!

Не потрапляйте на мілину

Ізоляція (або Ізола) - це покрокова стратегічна настільна гра, коли двоє гравців намагаються укласти свого супротивника на дошку, схожу на шашку. Зрештою, вони більше не можуть зробити ходу (тим самим ізолюючи їх).

Кожен гравець має одну фігуру, якою він може рухатись як королева в шахах - вгору-вниз, вліво-вправо та по діагоналі. Є три умови, за яких шматки можна переміщати -

  1. Вони не можуть розмістити свій твір на вже відвіданій площі.
  2. Вони не можуть перетнути вже відвідані площі (стискати їх по діагоналі - це нормально).
  3. Вони не можуть перетинати шматок один одного.

На наведеному малюнку з чорних квадратиків видно, що обидва гравці розмістили свої фігури на різних частинах дошки. Але по ходу гри, це показує, що у жовтого гравця ще є три можливі ходи. Вгору і вправо, вправо один квадрат, а вправо два квадрати. Але у синього гравця немає варіантів. Отже, жовтий гравець тут переможець.

Зараз це може здатися простою грою - і, чесно кажучи, це так. Це не так, як ми граємо в покер чи Starcraft. Тим не менш, існує ще величезна кількість можливих ходів, які будь-який гравець може зробити в будь-який момент гри.

У таких загадках, як судоку, є “відповідь”, яку ми хочемо вирішити. Але відповіді на питання стратегічних ігор немає.

Ми граємо проти іншого суперника - як людина, комп’ютер чи котячий детектив. Для цього потрібна стратегія і певна думка над тим, як гра може скластись, коли вона рухається.

Такі ігри можуть розвиватися і давати абсурдну кількість можливих результатів. Тож нам потрібно подумати, як ми можемо вибрати найкращий можливий хід, не витрачаючи часу, необхідного котам для заселення Землі.

Гаразд, більше немає котів!

Могутній Мінімакс та друзі

Тепер, коли ви знаєте, як грати в Isolation, давайте подивимось, як ми можемо використовувати алгоритм minimax ; основним компонентом спільноти AI. Ми також розглянемо евристичні показники , ітеративне поглиблення та альфа-бета-обрізку . Разом із ними ми можемо створити конкурентоспроможного агента ШІ.

Мінімакс

Алгоритм мінімаксу дуже популярний для навчання агентів ШІ як грати в покрокові стратегічні ігри. Причиною є те, що вона враховує всі можливі ходи, які гравці можуть зробити в будь-який момент протягом гри. За допомогою цієї інформації він намагається мінімізувати перевагу гравця суперника, одночасно максимізуючи переваги агента на кожному кроці, який отримує агент ШІ.

Тепер, як це виглядає?

Ну, подібно до того, як агент ШІ буде грати в таку гру, як Судоку, ми можемо змоделювати наступні можливі ходи, які може зробити будь-який гравець, за допомогою дерева пошуку . Однак нам потрібно буде використовувати дерево пошуку зі змінною шириною - або іншими словами, ширину рівня дерева. Причиною є те, що кожен гравець може змінювати кількість ходів у будь-який момент протягом гри.

Дерево, показане вище, представляє наступні ходи, доступні під час гри в Ізоляцію. Він має сітку 2х3, причому нижній правий квадрат недоступний. Як бачите, двоє гравців - це синій круг і червоний хрест.

Верх дерева (кореневий вузол) ілюструє хід, зроблений червоним гравцем. Середній рівень ілюструє наступні можливі ходи синього гравця. І третій рівень ілюструє можливі ходи червоного гравця, враховуючи попередній хід синього гравця.

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

Тепер ви можете задатися питанням, який біс - ці трикутники під кожним ходом?

Вниз трикутник представляє розташування в дереві , де мінімаксне буде мінімізувати перевагу противника. Тоді як вищі трикутники - це місця, де мінімакс максимізує перевагу агента.

Але мінімакс може знати перевагу обох гравців лише в тому випадку, якщо він знає шляхи на дереві, які ведуть до перемоги будь-якого з гравців. Це означає, що мінімакс повинен проходити до самого дна дерева для кожної можливої ​​серії ходів. Далі він повинен призначити деякий бал (наприклад, +1 для перемоги та -1 для програшу) і розподілити ці цифри вгору по дереву. Таким чином, кожен ігровий стан або вузол у дереві має інформацію про те, який гравець може отримати найбільше від будь-якого потенційного ходу.

На цій картині ми можемо зробити пару спостережень. Перший мінімакс присвоює число кінцевим результатам гри на листових вузлах . Потім він поширює їх вгору по дереву, виконуючи мінімізацію та максимізацію на шляху. Як тільки мінімакс закінчить заповнення дерева, щоразу, коли настане черга агента ШІ, він буде знати, які ходи можуть призвести до виграшу або програшу.

Другий рівень після кореневого вузла показує наступні можливі ходи для синього гравця (наш агент AI). Наш агент хоче максимізувати доступні бали під час своєї черги. Таким чином, він вибирав хід, представлений у самому правому вузлі, що слідує за кореневим вузлом. Супер круто!

Але чи є сенс просто призначати +1 або -1 результатам гри? Чи не повинен цей рахунок враховувати, як вигравати гру або програвати?

Спойлер сповіщення: відповідь так!

Евристичні бали

У світі стратегічних ігор евристичний бал - це, по суті, суб’єктивна цінність, яку ми надаємо певному ігровому стану. Це значення базується на нашому розумінні того, як виграють і програють гру. Вибравши продуману евристичну оцінку, ми можемо навчити нашого агента ШІ, як найкраще обирати наступні ходи, граючи в гру Ізоляція.

Зараз існує, мабуть, необмежена кількість евристичних балів, які ми могли б придумати. Але тут ми розглянемо лише деякі з них, крім наївного балу (NS) +1 та -1.

Однією ідеєю може бути підрахунок усіх наступних можливих ходів кожного гравця в будь-який момент часу, оскільки більше можливих ходів означає менше шансів бути ізольованим. Ми будемо називати це рахунком відкритого ходу (OMS) .

Іншою ідеєю може бути використання значення, отриманого від OMS, і віднімання кількості наступних можливих ходів, які має опонент. Причиною є те, що кожен гравець хоче збільшити кількість своїх ходів, одночасно зменшуючи супротивника. Ми будемо називати це покращеною оцінкою (IS) .

Наведений вище малюнок показує коефіцієнт виграшу в багатьох модельованих іграх на ізоляцію, що проводились між агентами ШІ з використанням різних евристичних балів. Тепер ви можете побачити, наскільки різними були наші бали під час фактичної гри. Але були деякі евристичні показники, які перевершували ті, які ми придумали

Цікаво, що два найкращих місця майже однакові з покращеним балом. Ми будемо називати їх агресивними покращеними оцінками (AIS) та супер агресивними покращеними оцінками (SAIS) . Але є невелика різниця між цими балами та оригіналом. Дві верхні оцінки застосовують коефіцієнт два і три до значення, яке ви віднімаєте (кількість ходів, доступних опоненту) при обчисленні покращеного балу.

Ви можете виявити оптимальний “агресивний фактор”, який застосовуватиметься при обчисленні цього балу!

Ще одне сповіщення спойлера - існують кращі значення.

Але що, якщо ми придумаємо евристичну оцінку, для обчислення якої потрібно багато часу? Що робити, якщо дерево величезне? Чи вистачить у нашого агента ШІ часу, щоб знайти наступні найкращі ходи, при цьому залишаючись досить чуйним під час гри?

Ітеративне поглиблення

Тепер ми знаємо, що наш агент ШІ може моделювати всі можливі ходи, використовуючи дерево пошуку та відповідну евристичну оцінку його вузлів. Але, на жаль, під час гри в Isolation наше дерево буде масивним. На пошук дерева та обчислення цих значень знадобилося б більше часу, ніж пройшло років після Великого Вибуху!

Введіть ітеративне поглиблення - стратегію управління часом роботи для ігрових агентів. Використовуючи цей метод, ми можемо скоротити час обчислень та пошуку до максимального часу, який ми вибрали. Таким чином наш агент ШІ може реагувати принаймні так швидко, як це могла б людина.

Але як працює ітеративне поглиблення?

Це дозволяє мінімаксу рухатися рівень за рівнем та обчислювати евристичні оцінки до певного часового обмеження. Як тільки цей часовий ліміт досягнуто, агент ШІ змушений використовувати найкращий ход, який він виявив, рухаючись все глибше і глибше по дереву.

Тепер це дає деяке уявлення про те, наскільки це може бути складно. Створення агента ШІ, який є розумним і досить чуйним для стратегічних ігор, може бути досить складно, навіть для майстрів ШІ. Особливо, якщо такі ігри містять світ можливостей.

На жаль, кількість ходів, які може уявити собі агент ШІ вперед, обмежена. Тож можливо, він міг би прийняти рішення, яке призведе до його загибелі. Це відоме явище, яке називається ефектом горизонту . Але нам все-таки потрібно розглянути, мабуть, найефективніший алгоритм скорочення часу, який використовується при пошуку дерев.

Обрізка альфа-бета

Гаразд, це родзинки, а не чорнослив, але все ж - як це взагалі було? Я маю на увазі серйозно групу із ізюм-блюзом?

Ви вже могли здогадатися, альфа-бета обрізка не має нічого спільного з чорносливом, а також більше про зменшення розміру (обрізки) нашого дерева пошуку. Коли ми маємо дуже велике дерево пошуку, виявляється, що не завжди потрібно обходити кожен вузол, використовуючи мінімакс.

Нам потрібно надати мінімаксу можливість зупинити пошук у певній області дерева, коли він знаходить гарантований мінімум або максимум цього конкретного рівня.

Якщо ми можемо це зробити, це може значно зменшити час реакції нашого агента ШІ та покращити продуктивність.

Як працює обрізка альфа-бета?

Алгоритм мінімаксу рухається по дереву за допомогою пошуку по глибині. Це означає, що він проходить крізь дерево, рухаючись зліва направо, і завжди рухаючись найглибше, що може піти. Потім він виявляє значення, які необхідно присвоїти вузлам безпосередньо над ним, ніколи не дивлячись на інші гілки дерева.

Обрізка альфа-бета дозволяє мінімаксу приймати настільки ж якісні рішення, як мінімакс може приймати окремо, але з вищим рівнем продуктивності.

Розглянемо наступне зображення, на якому ми маємо дерево з різними оцінками, призначеними кожному вузлу. Деякі вузли затінені червоним кольором, що вказує на відсутність необхідності їх перегляду.

У нижньому лівому куті дерева мінімакс розглядає значення 5 і 6 на нижньому рівні максимуму. Він визначає, що 5 має бути призначено мінімальному рівню прямо над ним. Має сенс.

Але, оглянувши 7 та 4 правої гілки максимального рівня, він розуміє, що вищезазначеному вузлу мінімального рівня має бути присвоєно максимальне значення 4. Оскільки другий максимальний рівень прямо над першим мінімальним рівнем займе максимум від 5 до щонайбільше 4, зрозуміло, що він вибере 5. Після цього він буде продовжувати обхід дерева, виконуючи той самий набір операцій в інших гілках дерева.

Нижче наведено алгоритмічне представлення мінімаксу з альфа-бета обрізанням.

Використання цього методу забезпечує простий спосіб скоротити пошуковий простір нашого агента ШІ. Таким чином, обрізка альфа-бета дозволяє мінімаксу приймати правильні рішення, які мінімакс міг би приймати самостійно, але з більш високим рівнем продуктивності.

Ізола-тер

Ми дослідили, як створити власного агента ШІ, який зможе грати в гру Isolation на досить конкурентному рівні. Використовуючи алгоритм minmax, ми побачили, як агент ШІ може моделювати гру і приймати рішення на основі евристичної оцінки. Ми також дізналися, як визначити чітко визначену евристику для даного завдання (ізоляція).

Але ми також виявили, що пустити мінімакс на самоплив було б занадто обчислювально. Тож нам довелося використовувати такі методи, як повторне поглиблення та альфа-бета обрізка. Це змусило б нашого агента ШІ придумати наступний крок протягом розумного періоду часу. Але що, якщо ми хочемо, щоб наш агент з інтелекту мав вищий коефіцієнт виграшу, при цьому принаймні реагуючи як людина?

Ну, є й інші методи, які ми могли б вивчити, щоб збільшити виграш нашого агента, а також час відгуку. Ми торкнулися ідеї налаштування параметрів нашої евристичної оцінки (пам’ятаєте “агресивний фактор”?). Ми могли б навіть придумати евристичну оцінку, краще пристосовану для гри в Ізоляцію.

Існують також відбивні властивості, пов'язані з можливими рухами на ізоляційній платі. Це стає очевидним, коли ми аналізуємо повністю заповнене дерево пошуку, що дозволило б нам потенційно зрізати багато гілок з дерева пошуку. Крім того, якби ми оновили апаратне забезпечення, наш агент ШІ був би швидшим - і, отже, мав змогу дослідити більше можливостей.

Якщо ви хочете отримати глибокі подробиці того, як це самостійно реалізувати, подивіться на код, який я написав, щоб вирішити цю проблему для моєї наноградуси штучного інтелекту Udacity. Ви можете знайти його на моєму репозиторії GitHub.

Привіт, я Грант! Я розробник і фрілансер. Перевірте мій веб-сайт //freelancequant.com. На здоров’я!