Як часто ви зустрічали новини про те, як штучний інтелект обходить гравців у шахи або ґо? Що значить для нас останнє досягнення алгоритму від DeepMind, який справився з іграми на Atari, не знаючи при цьому правил? Думаєте, що алгоритмам по плечу тільки Ms. Pac-Man? Поговоримо про те, як штучний інтелект вже навчився грати у покер, анонімно обіграв кращих гравців у StarCraft II та чому це все не просто забавки розробників.
Навіщо розробники вчать алгоритми іграм?
Може здаватися, що всі ці витрати на розробку штучного інтелекту, якого тільки що і роблять, що змушують грати в настільні та комп’ютерні ігри, є забавкою розробників, які не хочуть врешті решт навчити алгоритми нормально розпізнавати мову та перешкоди на дорозі. Однак, ігри виявилися чи не найкращим середовищем для тестування алгоритмів на їхню реакцію, здатність планувати дії та коригувати їх відповідно до дій суперника. Саме вміння штучного інтелекту обходити людей на ігровому полі вважається показником прогресу їхньої ефективності.
Складність ігор полягає не стільки в кількості можливих ходів та позицій, скільки в особливостях стратегій. Так ігри поділяють на детерміновані та недетерміновані й такі, що мають або не мають елементи невизначеності. Наприклад, всі азартні ігри є недетермінованими, оскільки тасування карт або підкидання гральних кубиків дають випадковий результат, а от ігри на кшталт китайської ґо або шахів вважаються визначеними та з повною інформацією, бо мало того, що хід гри визначається кроками гравців, так вони ще й бачать всю ситуацію на дошці. Втім, повністю вирішити яку-небудь гру з повною інформацією, ті ж шахи або хрестики нулики, алгоритмам складно, бо дерево варіантів занадто велике, щоб його можна було побудувати та проаналізувати за прийнятний час. Але це і не потрібно, щоб обіграти світового чемпіона з шахів, як це зробив вже у 1997 році алгоритм Deep Blue від IBM.
І після того, як штучний інтелект знову всіх обіграв, у тому числі й таких самих «запрограмованих» чемпіонів на полі інтелектуальних настільних ігор, розробники вирішили взятися за «недосконалі» ігри, де гравці мають вгадати, що знають їхні суперники, та врахувати фактори випадковості, що робить ігри набагато складнішими для вирішення. У покері, маджонгу та відеоіграх гравець може мати так звані “козирі в руках”, а тому ШІ варто було б навчити блефувати, думати про ходи, які тільки можуть виникнути і при цьому все одно враховувати стратегію гри в цілому. І це потрібно не тільки, щоб вигравати мільйони в казино. Така прихована інформація присутня у реальних стратегічних взаємодіях: переговори, ділові та економічні стратегії, аукціони, військова безпека.
GIPHY
Від шахів до Dota 2
Перемога алгоритму Deep Blue стала важливою віхою для штучного інтелекту, після якого алгоритми вже не переставали виходити за рамки людських можливостей. І вони освоїли не лише шахи та шашки. Останньою відкритою грою, яка не встояла перед штучним інтелектом стала вершина настільних ігор ґо, де алгоритм AlphaGo вже на 186 ході побив кращого гравця світу Лі Седоля. І це за умови, що можливих комбінацій у ґо більше, ніж атомів у видимому Всесвіті!
Після цього розробники вирішили відійти від давніх розваг і звернулися до відеоігор. Одними з перших під увагу інженерів потрапили ігри з приставки Atari 2600. Вона була випущена 1977 року і для неї розробили понад 500 ігор, що охоплюють різноманітні жанри: шутери, файтинги, головоломки та екшен-пригодницькі ігри. Atari й досі використовують для штучного інтелекту, хоч вона й набагато простіша за сучасні ігри зі складним управлінням та візуальними елементами (тут може бути ваш жарт про реалізм в Cyberpunk 2077). Вся річ у тому, що у сфері штучного інтелекту вважається моветоном як навчати, так і оцінювати алгоритм за одним і тим же набором даних, оскільки це може сильно переоцінити його ефективність. А Atari розробники вважають досяжною і разом з тим вагомою сходинкою для оцінки компетентності програм — вона забезпечує ідеальний баланс між складністю та швидкими досягненнями у навчанні та плануванні. Такі дані важко отримати у складних реальних середовищах, де непросто чи безпечно розіграти всі наслідки неправильних рішень.
Втім, це не означає, що ШІ не намагався поборотися у вправності в сучасних іграх. У 2018 розробники вирішили створити змагання алгоритмів у Minecraft, де вони мають будувати міста. Хоч реальні гравці і будують Ейфелеві вежі, Діснейленд та зірки смерті із “Зоряних воєн”, це не така вже і легка задача насправді, бо у грі є принаймні 60 мільйонів прикладів дій, які можна було б вжити в тій чи іншій ситуації. Гравці мають вивчити фізику гри, відкрити рецепти для перетворення матеріалів у ресурси чи інструменти та захищатися від монстрів. Так само і з, наприклад, Dota 2.
Бій з орками і чаклунами може здатися менш інтелектуальним, ніж шахи або ґо, але розробники OpenAI Five стверджують, що кожен з ботів його команди повинен обирати в середньому з тисячі допустимих дій кожну восьму секунди. Алгоритм вчився грати, змагаючись зі своїми клонами мільйони разів, а витрачені обчислювальні ресурси інженери порівняли з 180 роками ігрових годин. Ще одну популярну онлайн стратегію, StarCraft II, алгоритм DeepMind AlphaStar пройшов за 27 днів навчання, анонімно обійшовши 99,8 відсотка гравців з офіційного рейтингу. Причому розробники вирішили накласти обмеження на AlphaStar: він також страждає від затримок мережі, його дії за хвилину (APM) обмежені, а пікова статистика значно нижча, ніж у людей.
Місто, побудоване ШІ у Minecraft, яке у 2018 році отримало перше місце у змаганнях. Естетичність оцінили в 4.21 бала, а загалом проєкт набрав 4.38. Filip Skwarski / The GDMC Competition
Грати без правил і думати лише про винагороду
Перші перемоги над гросмейстерами, як не дивно, програмам принесли самі гросмейстери: алгоритми використовували дані про ходи гравців-людей та поєднували їх з методом Монте Карло, який допомагає обрати найбільш успішний варіант розвитку гри. По суті, цей метод дещо схожий на перебір, однак, як ми вже згадували, складні ігри і називають складними, бо кількість можливих ходів величезна. Тому алгоритми не шукають оптимальний хід з огляду на свою позицію та на можливий оптимальний хід суперника, а проводять симуляцію гри зі своєї позиції, обираючи випадкові ходи. Кожний хід оцінюється, і якщо його можна вважати успішним, то алгоритм його використовує. Звичайно, так можна втратити якийсь цікавий варіант ходу, однак це значно скорочує необхідний на обчислення час. Тож перший спосіб обіграти кращих — вивчити стратегії всіх інших кращих і на їхній основі будувати свої кроки до кінця гри. Так, майже як Бет Гармон з «Ферзевого гамбіту» візуалізувала шахівницю на стелі.
Втім, згодом розробники дійшли висновку, що для того, аби алгоритм став беззаперечним чемпіоном, вчитися у людей йому не варто, а краще покладатися на самого себе. Так AlphaGo Zero, програму-наступницю AlphaGo, яка справилася з ґо, модернізували та розробляли її на навчанні з підкріпленням без будь-якого втручання людини. Інженери розповіли AlphaGo Zero, як ходять фігури та й були такі — далі програма навчалася сама. Кроки, які вели до перемоги, заохочувалися і алгоритму вже просто не було потрібно передбачати поведінку гравця-людини, а достатньо лише думати про те, який хід частіше веде до перемоги. На кожному кроці програма також використовувала метод Монте Карло, вираховуючи найбільш ефективний хід. Тож навіщо вам знати про суперників, якщо можна вчитися у самого себе?
Далі з’ясувалося, що алгоритмам і правила не дуже потрібні, а навчання з підкріпленням може вивести ШІ на вищий рівень не лише в ґо. Тож вже за рік у AlphaGo Zero зникла приставка Go і вона навчилася так само грати і в японські шахи сьоґі, а потім змінила ім’я на MuZero та доповнила список своїх ігрових досягнень 57 іграми на приставці Atari. Причому на цьому етапі алгоритмам правил ніхто і не пояснював: програмі достатньо було знати, як виглядає ігрове поле(або екран), знати своє поточне і попереднє положення під час гри та думати лише про набрані бали. Тобто вхідними даними були не стратегії інших і не правила гри, а лише спостереження за її ходом.
GIPHY
У ґо ніхто на гроші не грає. Як щодо «реальних» ставок?
Що ж, навчання з підкріпленням, методом проб і помилок, принесло перемоги ШІ у Dota 2 і у StarCraft, де нагородою була ігрова статистика. Однак, як перейти у вищу лігу, наприклад, покер? З покером все дуже складно, адже це не просто гра з нестачею інформації та з елементами випадковості, а і гра, яка потребує справжніх психологічних навичок — постійний блеф, наприклад, буде поганою стратегією.
Протягом майже трьох тижнів алгоритм Libratus розіграв 120 000 партій у один з варіантів покеру для двох людей, техаський голдем(no-limit Texas hold'em), та обіграв професійних гравців, забравши касу з фішок на суму понад 1,7 мільйона доларів. На жаль, тут просто позитивного підкріплення алгоритму буде замало і доведеться пошкодувати про свої рішення. Libratus використовував тристоронній підхід, який включав попереднє обчислення загальної стратегії, адаптацію стратегії до реального ігрового процесу та навчання у противника. Так, щоб грати як ШІ, вам доведеться спочатку награтися самим з собою і навчитися розуміти, наскільки ви шкодуєте про попередній хід. Розроблений алгоритм використовував варіант методу Монте Карло — Monte Carlo counterfactual regret minimization (MCCFR), який показував, наскільки алгоритм шкодує, що не вибрав ту чи іншу дію в минулому. І коли під час самостійної гри він стикався з точкою прийняття рішення, його дії зумовлювалися тим, наскільки він потім пошкодує. Втім, це лише перший крок, щоб обійти професіоналів у грі з 10161 можливим рішенням. Далі потрібно розробити план дій, слідувати йому, а у разі непередбачених дій суперників, розіграти ще одну, внутрішню, гру, щоб скоригувати стратегію. Також не варто намагатися впіймати опонента на помилці, бо спроба експлуатації огріхів у стратегії суперника рано чи пізно призведе до помилки тебе. Краще навпаки слідкувати за ставками: алгоритм цілий день збирав дані про ставки гравців, вночі аналізував їх, і повертався вже з новою стратегією. Тож пошкодуйте про деякі ходи, з’ясуйте, які з них викликають найбільший жаль, розігруйте внутрішні ігри, щоб врахувати несподівані дії опонентів та слідкуйте за ставками, а не стратегіями.
Через рік наступник цього алгоритму, Pluribus, обійшов за столом вже п’ятьох професійних гравців і знову грав без правил: ядром стратегії було навчання на грі проти своїх копій, без будь-яких даних про людські або попередні надбання алгоритмів. Pluribus грав навмання і вдосконалювався, визначаючи, які дії та який розподіл ймовірності на ці дії призводять до кращих результатів порівняно з попередніми версіями його стратегії. У техаському голдемі занадто багато моментів прийняття рішень, щоб міркувати про кожний окремо. Тому алгоритм розглядає гру як абстракцію та відкидає всі «непотрібні» дії та інформацію, враховуючи лише 13 варіантів ставок, та об’єднує свої стратегії для різних розкладів, тим самим зменшуючи кількість різних ситуацій, для яких йому потрібно визначити план дій.
GIPHY
Користь від ігор
Насправді попри весь успіх алгоритмів, навіть найкращі моделі глибинного навчання не зможуть навчитися грати в 57 ігор одночасно. Так, здається, їм будь-яка гра по плечу, якщо розробники зададуться такою метою, однак, якщо ми говоримо про те, що штучний інтелект вчиться робити щось більш складне, то нам варто розглядати гру як реальну ситуацію з життя. І реальні ситуації з життя можуть бути схожими одночасно на шутер, покер і спокійну ґо, і алгоритмам доведеться вчитися швидко, одразу і для всього. Втім, це все про шахи та відеоігри не означає, що розробникам аби погратися. Так ШІ від OpenAi, наприклад, після того, як награвся в Dota 2, навчився збирати кубик Рубіка однією рукою, алгоритми після Minecraft та StarCraft краще вміють працювати в команді, а розробка DeepMind вирішила одну з головних проблем біологів.