AlphaGo на пальцях

Отже, поки наші нові володарі відпочивають, давайте я спробую розповісти як працює AlphaGo. Пост передбачає деяке знайомство читача з предметом — потрібно знати, чим відрізняється Fan Hui від Lee Sedol і поверхово представляти, як працюють нейромережі.

Disclaimer: пост написаний на основі неабияк відредагованих лог чату closedcircles.com, звідси і стиль викладу, та наявність уточнюючих запитань

Як всі знають, комп'ютери погано грали в Го тому, що там дуже багато можливих ходів і простір пошуку настільки велике, що прямий перебір допомагає мало.
Кращі програми використовують так званий Monte Carlo Tree Search — пошук по дереву з оцінкою нодів через так звані rollouts, тобто швидкі симуляції результату гри з позиції в ноді.

AlphaGo доповнює цей пошук по дереву оцінними функціями на основі deep learning, щоб оптимізувати простір перебору. Стаття спочатку з'явилася в Nature (і вона там за пейволлом), але в інтернетах її можна знайти. Наприклад тут — https://gogameguru.com/i/2016/03/deepmind-mastering-go.pdf

Спочатку поговоримо про складові шматочки, а потім як вони комбінуються
Крок 1: тренуємо нейромережа, яка навчається передбачати ходи людей — SL-policy network
Беремо 160K доступних в онлайні ігор гравців досить високого рівня і тренуємо нейромережа, яка передбачає за позиції наступний хід людини.
Архітектура мережі — просто 12 рівнів convolution layers з нелінійністю та softmax на кожну клітину в кінці. Така глибина загалом порівнянна з мережами для обробки зображень минулого покоління (гуглівський Inception-v1, VGG, всі ці справи)
Важливий момент — що нейромережі дається на вхід:

image

Для кожної клітини на вхід дається 48 фіч, вони всі є в таблиці (кожне вимірювання — це бінарна фіча)
Набір цікавий. На перший погляд здається, мережі потрібно давати тільки є в клітці камінь і якщо є, то який. Але фіг там!
Є і тривіально вычисляющиеся фічі типу "кількість ступенів свободи каменю", або "кількість каменів, які будуть взяті цим ходом"
Є і формально неважливі фічі типу "як давно було зроблено хід"
І навіть спеціальна фіча для частого явища "ladder capture/ladder escape" — потенційно довгої послідовності вимушених ходів.

а що за "1" і "завжди 0"?
Вони просто щоб добити кількість фіч до кратного 4-му, мені здається.

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

Передбачення цієї натренованого SL-policy (SL — supervised learning) вже рве всі минулі програми Го, без всяких дерев і переборів.

Зокрема DeepForest Фейсбуку?
З нею не порівнювали, незрозуміло.

Окремо від SL-policy, тренують fast rollout policy — дуже швидку стратегію, яка є просто лінійним класифікатором.
Їй на вхід дають ще більше заготовлених фіч
image
Тобто, їй дають фічі у вигляді заздалегідь заготовлених шаблонів
Вона набагато гірше, ніж модель з глибокої мережею, але зате над-швидка. Як вона використовується — буде зрозуміло далі

Крок 2: тренуємо policy ще краще через гру з собою (reinforcement learning) — RL-policy network
Вибираємо противника з пулу минулих версій мережі випадково (щоб не оверфитить на саму себе), граємо з ним партію до кінця просто вибираючи найбільш ймовірний хід передбачення мережі, знову ж таки без всякого перебору.

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

(для допитливих — там трохи більш тонко і градієнт множиться на різницю між результатом і оцінкою позиції через value network)

І ось повторюємо і повторюємо цей процес — після цього RL-policy значно сильніше SL-policy з першого кроку.

Цікава деталь! В оригінальній статті пишеться, що цей процес робився всього 1 день (решта тренування — тижні).

Крок 3: натренируем мережа, яка "з одного погляду" на розстановку говорить нам, які у нас шанси виграти! — Value network
Тобто передбачає лише одне значення від -1 до 1.
У неї рівно та ж архітектура, що і у policy network (є один зайвий convolution layer, здається) + природно fully connected layer в кінці.

тобто у неї ті ж фічі?
value network дають ще одну фічу — грає гравець чорними чи ні (policy network передають "свій-чужий" камінь, а не колір). Я так розумію, це щоб вона могла врахувати комі — додаткові очки білим, за те що вони ходять другими

Виявляється, що її не можна тренувати на всіх позиціях з ігор людей — так як багато позицій належить грі з тим же результатом, що така мережа починає оверфитить — тобто запам'ятовувати, яка це партія, замість того, щоб оцінювати позицію.
Тому її навчають на синтетичних даних — роблять N ходів через SL network, потім роблять випадковий легальний хід, потім дограють через RL-network щоб дізнатися результат, і навчають на час N+2 (!) — тільки на одну позицію за згенеровану гру.

Отже, ось є у нас ці навчені цеглинки. Як ми з їх допомогою граємо?
Увага, картинко!
image

Отже, у нас є дерево позицій, в руті — поточна. Для кожної позиції є якесь значення Q, яка означає наскільки вона веде до перемоги.
Ми на цьому дереві паралельно проводимо велику кількість симуляцій.

Кожна симуляція йде по дереву туди, де більше Q + m(P). m(P) — це спеціальна добавка, яка стимулює exporation. Вона більше, якщо policy network вважає, що у цього ходу велика ймовірність і менше, якщо по цьому шляху вже багато ходили
(це варіація стандартної техніки multi-armed bandit)

Коли симуляція дійшла по дереву до листа, і хоче походити далі, де нічого ще немає…
Новий створений нод дерева оцінюється двома способами

  • по-перше, через описаний вище value network
  • по-друге, грається до кінця з допомогою супер-швидкою моделі з Кроку 1 (це і називається rollout)
Результати цих двох оцінок змішуються з певним вагою (в релізі він натурально 0.5), і отриманий score записується всім нодам дерева, через які пройшла симуляція, а Q в кожному ноде апдейтится як середнє від всіх score для проходів через цю ноду.
(там зовсім трохи складніше, але можна знехтувати)
Тобто кожна симуляція біжить по дереву в найбільш перспективну область (з урахуванням exploration), знаходить нову позицію, оцінює її, записує результат вгору по всіх ходах, які до неї призвели. А потім Q в кожному ноде обчислюється як усереднення по всіх симуляциям, які через нього втекли.

Власне, все. Кращим ходом оголошується нод, через який бігали найчастіше (виявляється, це трохи стабільніше ніж цей Q-score). AlphaGo здається, якщо у всіх ходів Q-score < -0.8, тобто ймовірність виграти менше 10%.

TL;DR: Policy network пророкує ймовірні ходи щоб зменшити ширину перебору (менше можливих ходів у ноде), value network пророкує наскільки виграшна позиція, щоб зменшити необхідну глибину перебору

Цікава деталь! У пейпере для початкових ймовірностей ходів P використовувалася не RL-policy, а більш слабка SL-policy.
Емпірично виявилося, що так трохи краще (можливо, до матчу з Lee Sedol вже не виявилося, але от з Fan Hui грали так), тобто reinforcement learning потрібен був тільки для того, щоб навчити value network

Наостанок, що можна сказати про те, що версія AlphaGo, яка грала з Fan Hui (і була описана в статті), відрізнялася від версії, яка грає з Lee Sedol:

  • Кластер став більше — 176 GPUs проти 280 GPUs
  • Схоже, стала більше витрачати часу на хід (у статті все естімейти дані для 2 секунд на хід) + додався якийсь ML на тему менеджменту часу
  • Було більше часу на тренування мереж. Моє особисте підозра — принципово те, що більше часу на reinforcement learning. 1 день в початковій статті це якось навіть не смішно.
Мабуть, все. Чекаємо 5:0!

Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.