Го

У 2015 році компанія Deep Mind закінчила роботи над першою робочою нейромережею для гри у го. До цього моменту для цієї гри не існувало ефективних алгоритмів, а найкращі комп'ютерні програми відповідали рівню сильного аматора. Головна причина полягала в особливостях правил гри та ключових відмінностях від шахів. Гра го — це той випадок, коли декілька простих правил генерують дуже складну структуру.

Спробую змалювати процес гри «в цілому», без усіх деталей.

Правила можна почитати у Вікі. У го гравці ходять по черзі і виставляють на перетини ліній сітки 19 x 19 чорні і білі камені.

Ключові елементи для розуміння складності створення програми для го:

1. Величезна кількість варіантів, починаючи з першого ходу — 361 можливий хід чорних (у го першими ходять чорні), 360 можливих ходів білих - 129960 можливих позицій після першого ходу. Для порівняння — у шахах 20 можливих перших ходів білих (та чорних) та 400 позицій. Одним з наслідків цього є відмінність в «дебюті» (в го приблизною аналогією є джосекі та фусекі - послідовність розіграшу ходів у кутку дошки та загальний вибір таких послідовностей, що враховує загальну ситуацію, відповідно), що в шахах розроблений в деяких началах аж до переходу в ендшпіль і часто є шляхом в один бік (з кількома розгалудженнями) - відхилення від канонічної послідовності карається миттєвим програшем. У го існують певні принципи та ідеї плюс конкретні послідовності, що вважаються оптимальними для сторін, однак в цілому відомі ходи швидко закінчуються, а відхилення часто не мають миттєвого ефекту.
2. Го — це боротьба за територію. У кого в кінці гри її буде більше — той і переміг. Територію можна отримати або створюючи вцілілі групи (вони називаються фортецями, тоді територія — це пункти всередині), або вбиваючи (це з китайською політкоректністю називається «взяти у полон») камінчики суперника — кожен камінь рахується за один пункт території. При цьому нічия неможлива, оскільки на поатку гри чорні дають білим «плату» за перший хід (спочатку віддавали 4.5, нині 6.5 та, навіть, 7.5)*. Це створює декілька стратегій гри: можна надійно будувати фортеці, можна охоплювати більшу територію у надії її відстояти, можна вдиратися у територію супротивника і намагатися будувати там фортецю, можна, нарешті, полювати за великими групами, які ще не гарантували собі життя (вони називаються драконами). В будь-якому випадку, в кінці гри на дошці залишаються вцілілі групи та відбувається підрахунок території. Особливість у тому, що гравці оцінюють територію на кожному ходу з початку гри — і це ймовірністна оцінка (моя територія, моя ймовірна територія, моя можлива територія). Ця оцінка змінюється з кожним ходом і часто хід на одному боці дошки впливає на ситуацію на іншому. Одночасно потрібно добре прораховувати конкретні варіанти. Однак професіонали виконують це настільки добре, що в будь-який момент гри вони розуміють, хто виграє і скільки (+- декілька очок похибки). Цікавий момент - партії, що завершуються з мінімальною перевагою у 0.5 очка, часто, насправді, не означають рівності гри. Просто іноді профі отримують велику перевагу, прораховують можливі ходи, а потім дозволяють супернику наблизитися до мінімального програшу — така собі демонстрація у кого го крутіше. Звісно, це вимагає ювелірної точності та техніки.
3. Взаємозв'язок усього, що відбувається на дошці. Особливість го ще й у тому, що завдяки «сходам» хід на одному боці дошки може змінити усю ситуацію на іншому. Оскільки зазвичай починають ходити у кути дошки (це найбільш цінні ходи з точки зору території), потім по сторонах, то часто стається ситуація, коли кілька слабких груп намагаються втекти у центр. Гравець при цьому має постійно оцінювати статус своїх груп (живі — мертві) і вплив на цей статус майбутніх ходів. Тому, до речі, важкістю для програмування є факт, що одна й та ж послідовність ходів має різну цінність у різний час. Наприклад, можна залишити напівживу групу з невизначеним статусом і ходити у іншому місці дошки, якщо хід може принести там більше очок. А за кілька ходів, коли цінність будь-якого іншого ходу на дошці зменшиться - повернутися до цього питання.

Успіх комп'ютерів до появи 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 року (хід білих)

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

1. Своїх пішаків брати не можна, тому якщо поставити білих пішаків на білі поля - це заблокує позицію (оскільки у чорних немає білопольного слона і коней). В результаті фігури чорних не зможуть ні перетнути ні зруйнувати ці «велику стіну» пішаків. Це наша мета, тепер будемо думати, як ми можемо її досягти.
2. Звідси випливає конкретна ідея — потрібно ставити пішаків з шахом, інакше чорні сунуть своїх пішаків і створять пролом для прориву своїх фігур. Завдяки білому слону у тилу чорних чорний король обмежений у рухах, але комбінація з с4+ не проходить — після її закінчення залишається два пішака, які потрібно переставити на білі поля і тільки один хід.
3. Отже тактичне рішення — жертва слона на полі a4, щоб заманити туди ворожого короля.

Після очевидної послідовності ходів Ba4+ K:a4 b3+ Kb5 c4+ Kc6 d5+ Kd7 e6+ K:d8 f5 отримуємо позицію, де тури, слон і король чорних можуть займатись чим завгодно у будь-якій послідовності - ситуація не зміниться.

Смішно, що навіть у цій позиції комп'ютер вважає, що у чорних перевага, і лише через 50 ходів знехотя визнає нічию (діє правило 50 ходів без взяття фігур і ходів пішаків - нічия). На жаль, на практиці використати цю особливість було неможливо, але певний черв'ячок сумнівів був — а все ж таки люди оцінюють такі позиції моментально.

Alpha Zero vs Stockfish

Застосування ідеїAlpha Zero до шахів і шогі описано в статті [2].Цей матч коментували багато гросмейстерів (можете знайти на ютубі). Варто відмітити фактори, що робили протистояння нерівним (є різні думки того, як їх оцінювати):

1. Програми використовували різні обчислювальні ресурси.
2. Stockfish заборонили користуватись дебютними базами та таблицями закінчень.
3. Stockfish обмежили в оперативній пам'яті.
4. Налаштування часу були дуже незвичні — час на 1 хід було обмежено 1 хвилиною.

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.

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