Го
У 2015 році компанія Deep Mind закінчила роботи над першою робочою нейромережею для гри у го. До цього моменту для цієї гри не існувало ефективних алгоритмів, а найкращі комп’ютерні програми відповідали рівню сильного аматора. Головна причина полягала в особливостях правил гри та ключових відмінностях від шахів. Гра го - це той випадок, коли декілька простих правил генерують дуже складну структуру.
Спробую змалювати процес гри “в цілому”, без усіх деталей.
Правила можна почитати у Вікі. У го гравці ходять по черзі і виставляють на перетини ліній сітки 19 x 19 чорні і білі камені.
Ключові елементи для розуміння складності створення програми для го:
Успіх комп’ютерів до появи AlphaGo були дуже помірними в основному внаслідок тотального взаємозв’язку усього, що відбувається на дошці, та проблем з перебором варіантів. Найбільших успіхів досягли Zen та Crazy Stone, що досягли рівня сильного аматора і навіть перемагали професіоналів (з форою). Основним компонентом, що дозволив досягнути такого результату, був пошук Монте-Карло по деревам (Monte Carlo tree search), однак все гальмувалося на спробах пояснити програмі, як побачити усю дошку загалом.
AlphaGo
Алгоритм AlphaGo наведено в статті в Nature [1]. Щоб не забрідати в хащі, спробую пояснити ідею простими словами. Три головних компоненти: дві згорткові нейромережі та пошук Монте-Карло по деревах. Згорткові нейромережі дозволили вирішити проблему навчання, а їх взаємодія полягає у тому, що одна відповідає за оцінку позиції, інша - за вибір можливих (перспективних) ходів. Їх об’єднує дерево позицій (для кожної точки гри вибудовується 10 мільйонів позицій, для якого алгоритм використовує метод Монте-Карло для знаходження хороших гілок - тих, що гарантують максимальну вірогідність виграшу.
Ключовим нововведенням було саме поєднання цих трьох елементів.
Матч з Лі Седолем
Лі Седоль є одним з топ-гравців (історичні графіки рейтингу) і вважається одним з найсильніших гравців за всю історію, але його пік припав на 2010 рік. Однак, і він, і інші профі випромінювали впевненість у перемозі, а загальний настрій був таким: якщо програма виграє одну партію - це буде дуже круто.
Лі
Седоль грає партію
Після першої програної партії Седоль ще посміхався та відважував компліменти - мовляв, яку гарну програму зробили. Але після другого та третього програшу посмішки ставали все більше удаваними. Бажаючі можуть знайти ютуб трансляції з докладними коментарями (на каналі DeepMind). При цьому Седоль боровся на найвищому рівні (за людськими вимірами), однак, здавалося, що слабкостей у програми просто немає. Вона чудово прораховувала варіанти, оцінювала ситуацію на всій дошці, краще рахувала територію та, навіть, застосовувала новинки у дебюті.
Кульмінація цієї драми в стилі старих майстрів настала на четвертій партії, коли долю матчу вже було вирішено (усього було заплановано 5 партій).
Лі Седоль зрозумів, що вже можна спалювати всі мости та застосував виключно ризиковану стратегію гри - він забрав територію по бокам дошки, дозволивши AlphaGo побудувати дві стінки. Територія між стінками перетворилась, таким чином, у мішок. Якщо цей мішок конвертується у вірну територію чорних, то гра стає безнадійною для білих. Загалом, приблизно так ситуацію і оцінювали коментарі. Настрій був доволі пригніченим. В цей момент Седоль зробив хід, що перевернув усю ситуацію на дошці. В го є термін тесудзі - кращого (єдиного) ходу у складній ситуації. Седоль зміг знайти мега тесудзі - це, приблизно, як знайти голку у скирті сіна (з 10 мільйонів варіантів), яку до нього вже перевірила програма.
Лі
Седоль грає білими. Трикутником позначений
“божествений хід”
Хід на малюнку відімчений трикутником - він “виламує” стіну чорних, рятує білу групу і відбирає внутрішню територію чорного мішка. Найбільш дивовижне те, що він працює. Після цього ходу AlphaGo поплила - почала робити необов’язкові ходи і через деякий час капітулювала. П’яту партію Лі Седоль програв, але в історію він себе вже вписав - як, ймовірно, остання людина, що змогла виграти у топ-програми з го (на той момент).
Якщо за цими подіями будуть знімати фільм, то це буде найліпший момент для фіналу - переможений майстер, який в битві з цифровим демоном створив шедевр усього свого життя. Він йде у захід сонця, завіса, всі плачуть. Далі все було просто і брутально. Розробники почали шукати можливості покращення програми та позбавлення її вразливостей (адже вона програла одну партію).
Цікаво, що основною проблемою виявилось попереднє навчання на партіях людей - в наступній версії вони зменшили цей елемент. Результатом стала програма AlphaGo Master, яка спочатку виграла у попередньої AlphaGo, потім зіграла (інкогніто) 60 бліц-ігор на найсильніших го-серверах tygem і FoxGo з топовими профі (виграла всі). Нарешті на саміті «Майбутнє Го» на початку 2017 AlphaGo Master виграла у поточного першого номера рейтингу Ке Цзе. Виграла без шансів, хоча Ке Цзе в першій партії і програв з мінімальною перевагою у 0.5. Контрольним пострілом у голову стала поява Alpha Zero - алгоритма, який взагалі не використовував партії людей для навчання. Alpha Zero було надано правила та обчислювальні ресурси. За три дні вона навчилась і обіграла усі попередні версії. Було оголошено, що більше матчів не буде і релізити програму DeepMind не буде (хоча потім зробили сервіс для навчання).
І правильно - бо людство може зовсім впасти в депресію (як мінімум гравці го).
Stockfish
Тепер трохи про найкращу шахову програму. Простими словами, вона складається з функції оцінки позиції на основі загальних принципів і конкретних факторів (наприклад, співвідношення матеріалу, безпека короля, контроль за клітинками, здвоєні пішаки - це, як правило, погано, тури - найкращі, коли контролюють вільні вертикалі, а слони погані, коли впираються у власних пішаків і т.д.), дебютної бази, що напрацьована людством на сьогодні, таблиці закінчень, для яких є відомий результат, та движка розрахунку комбінацій на базі оптимізованого Alpha-Beta відсічення.
Відповідно, програма не помилялась у дебюті, рахувала комбінації краще за людину, отримувала кращу позицію і перемагала. Максимальний рейтинг Магнуса Карлсена 2882, рейтинг останньої (офіційної) версії Stockfish 8 64-bit 4CPU - 3495.
Надії білкових шахістів
Але була причина, яка тішила его шахістів, а саме - позиційне мислення. За деяких умов програма оцінювала позицію гірше не дуже сильного гравця. Власне ось одна задачка 1912 року (хід білих)
Якщо завести цю позицію у шаховий движок, то він покаже вирішальну перевагу чорних. Просто без шансів. Тим не менш, білі елементарно роблять нічию і це очевидно кожному, хто хоч трохи грає. Пояснимо для інших, тим більше, що це демонструє хід думок гравця:
Після очевидної послідовності ходів Ba4+ K:a4 b3+ Kb5 c4+ Kc6 d5+ Kd7 e6+ K:d8 f5 отримуємо позицію, де тури, слон і король чорних можуть займатись чим завгодно у будь-якій послідовності - ситуація не зміниться.
Смішно, що навіть у цій позиції комп’ютер вважає, що у чорних перевага, і лише через 50 ходів знехотя визнає нічию (діє правило 50 ходів без взяття фігур і ходів пішаків - нічия). На жаль, на практиці використати цю особливість було неможливо, але певний черв’ячок сумнівів був - а все ж таки люди оцінюють такі позиції моментально.
Alpha Zero vs Stockfish
Застосування ідеї Alpha Zero до шахів і шогі описано в статті [2]. Цей матч коментували багато гросмейстерів (можете знайти на ютубі). Варто відмітити фактори, що робили протистояння нерівним (є різні думки того, як їх оцінювати):
Tore Romstad з команди Stockfish сказав, що результати не є показовими, оскільки Stockfish фактично зв’язали та позбавили її сильних сторін (зокрема дебютних баз, Stockfish також має складну систему балансування часу на хід для стандартних налаштувань часу). Те, що Alpha Zero навчалась 4 години - насправді нічого не означає, оскільки навчалась вона на декількох тисячах TPU - спеціалізованих процесорах. Тому за таких умов матч Stockfish vs AlphaZero це порівняння яблук з орангутанами (стандартна програма, яка працює на звичайному харді і спеціалізована нейромережа на кастомних процесорах).
Результатом матчу стала ніщивна поразка Stockfish - вона не виграла жодної гри і програла у 28 партіях (72 нічиї). Не зважаючи на те, що у деяких позиціях Stockfish рахувала варіанти краще, Alpha Zero просто переграла суперника, майстерно використовуючи позиційні ідеї (це, мабуть, найбільша несподіванка матчу). Шахові коментатори відмічають, що вони вперше побачили у програми настільки глибокі і людські ходи. Фактично Alpha Zero за 4 години самонавчання перевідкрила стратегічні принципи шахів, вивчила тактичні прийоми та перевідкрила дебюти (причому в одній з партій пішла на принциповий найбільш гострий варіант, який з’явився у турнірній практиці зовсім нещодавно).
Висновки
Як сказав один коментатор: “я завжди мріяв щоб якісь розвинені інопланетяни прилетіли на Землю і показали як ще можна грати в шахи. Сьогодні я це побачив.”
Основний результат власне такий: спочатку ми створили програму, яка грає як програма і грає краще за людину і ми розуміємо алгоритм її роботи. Тепер ми створили нейромережу і ми не розуміємо як вона грає, але це набагато ближче до того, як грає людина, краще, ніж грає людина, і перша програма (із зважанням на нерівність умов гри).
Другий результат - мережа взагалі не використовувала всі попередні надбання людства (дебюти, стратегію, підручники закінчень - а книжок з шахів порядку 200000 назв - sad but true) і навчалась, граючи сама з собою. Вішванатан Ананд сказав з цього приводу: “Ми 600 років грали в шахи, а вона навчилась за 4 години. Гарний жарт.”
Враховуючи, що кількість і якість даних - це ключова проблема для навчання нейромереж, жарт і дійсно гарний. Трохи обідно за людство.
Третє - Alpha Zero рахувала набагато менше варіантів ніж Stockfish, швидко відмовляючись від поганих гілок. Це свідчить про те, що програму, яку довго писали багато програмерів, можна замінити на нейромережу, яка швидко навчиться і буде робити ту ж роботу навіть швидше (тут ще багато проблем, але приклади успіхів вже є).
З відносно хороших новин: поки що область застосування цього алгоритму обмежено іграми з детерміністичними правилами (швидше за все ненадовго).
І це ще один крок до створення алгоритмів для загальних когнітивних здатностей - уміння вчитись без вчителя, розуміння і, можливо, свідомості (насправді кінцевий результат ніхто не може передбачити).
Джерела
1 Mastering the game of Go with deep neural networks and tree search
2 Mastering Chess and Shogi by Self-Play with a General Reinforcement Learning Algorithm
P.S. За наводкою Антона Сененко (завдяки якому була написана і ця стаття) додаю ще чудові статті Dmytro Mishkin тут https://goo.gl/5BNqGc і тут https://goo.gl/3QBzoZ де можна більше дізнатись про алгоритм роботи нейромереж і нерівність матчу з Stockfish.
* насправді нічия можлива в тому розумінні, що при трикратному повторенні позиції гра вважається такою, що не відбулась. Але в го, на відміну від шахів, це трапляється надзвичайно рідко.
Коментарі доступні тільки зареєстрованим користувачам
вхід / реєстрація