АльфаЗеро проти всіх
Нещодавно AlphaZero — нейросітка від DeepMind виграла у трьох найкращих алгоритмів гри у шахи, го та сьоґі — StockFish, AlphaGoZero та Elmo відповідно.
Я спробую розповісти, яка загальна ідея , чому це круто, а також спростувати деякі хайпи навколо :) В кінці посту я приблизно опишу як саме працює АльфаЗеро.
Ідея АльфаЗеро дуже проста:
1. Ми жорстко описуємо лише правила відповідної гри.
2. Входом в алгоритм є поточна ситуація на дошці. Виходом є хід.
3. Поточна версія алгоритму грає сама із собою. Ваги нейросітки, що призвели до виграшних ходів, підсилюються, інші — послаблюються.
4. Жодних евристик, ендшпільних чи дебютних таблиць. Сітка вчиться вигравати, всі проміжні ситуації на дошці не мають значення.
Один й той самий алгоритм, з одними й тими ж початковими параметрами далі вчиться грати у будь-яку задану гру і через деякий, час перевершує все, що було придумано до цього часу :)
Чому це круто.
По-перше, тому що не потребує щодних знань “що таке добре, що таке погане” від людини. Все що, потрібно — лише задати правила гри і умови виграшу.
По-друге, таким чином можна покращувати якість гри нескінченно, точніше, до теоретичного ліміту даної гри.
По-третє, хоча це потребує досить немаленької обчислювальної потужності, по сучасним міркам, це не захмарні речі. Будь-яка середня компанія має такі ресурси, а через пару років, скоріше за все, це можна буде реалізувати і дома. І це я маю на увазі лише тренування.
Які в АльфаЗеро обмеження
1. Чітка заданість правил гри і умов перемоги. Життя — не гра, тому алгоритм АльфаЗеро не підходить для чогось, де ми не можемо ввести хороший KPI чи чітко визначити ціль. Більш того, якщо ми визначимо ціль неправильно, це як загадувати бажання у злого джина: вам дадуть саме те, що ви попросили, а не те, що мали на увазі.
2. Умовно велика кількість необхідних ігор для тренування. Для тренування АльфаЗеро було проведено 20–40 млн ігор. Це можлво лише для дешевих та швидких процесів в реальномі світі, або для віртуальних симуляцій. Якщо ж вартість спроби велика в сенсі часу чи грошей, то….
Як працює АльфаЗеро (спрощено)
Двома наріжними каменями алгоритму є нейросітки та Монте-Карло пошук на дереві.
Гра.
Отримавши нову позицію на дошці, АльфаЗеро робить наступне:
- Генерує ймовірність для вибору кожного можливого ходу у поточній ситуації за допомогою нейросітки. Ймовірність базується на вивченій в процесі гри корисності кожного ходу. На початку навчання, вірогідності є випадковими.
- Для найвірогідніших ходів, за допомогою другої половини нейросітки оцінює вірогідність виграшу, “хорошість позиції”. Хорошість — також вивчена нейросіткою, на початку навчання — випадкова.
3. Поки є час на хід, повторює все це далі для обраних ходів, тобто тобто на 1,2,3,… ходів вперед. Кількість оцінених позицій — на порядки менша, ніж у конкурентів
4. Для остаточного ходу обирається той, що веде для найкраще оціненої позиції.
Навчання
Після того, як зіграна деяка кількість партій, ситуації на дошці використовуються для навчання наступної ітерації алгоритму, а саме функцій оцінки и пропонування ходів. Ті, що оцінили правильно — підсилюються, ті, що неправильно — послаблюються.
Відповіді на популярні питання
П: У AlphaZero більший бюджет обчислень.
В: Можливо, це важко порівнювати через занадто різні архітектури. 4 спеціалізованих TPU чіпа для АльфаЗеро проти 64 поточного CPU із 1Гб кешу для StochFish. Остання дійно більш ефективна для менших бюджетів, в статті приведений графік:
П: Стокфіш грав без дебютних та ендшпільних таблиць, а АльфаЗеро напрацював свої.
В: Це лише максимум наполовину вірно. Я не знайшов в оригінальній статті чіткого визначення, чи використовував СтокФіш таблиці, чи ні. А АльфаЗеро не має жодних таблиць у тому сенсі, що будь-яку позицію він обробляє таким самим чином, як і іншу, жодних “підглядань як сходити”. ІМХО це і є, вміння гри, а не автоматичне запам’ятовування “якщо так, то так”.
П: Був використаний Стокфіш не останньої версії з не оптимальними налаштуваннями. Shannar de Kassal
В: Можливо. Самі DeepMind відмовляються від коментарів до публікації статті в рецензованому журналі, а там обіцяють навести все-все. Моя думка:
1) Якщо це так, то це, звісно, дуже некрасиво.
2)На результаті це б відбилося мінімально. Звичайно, можливо, що правильно налаштований Стокфіш грає дуже близько до оптимуму і велику перевагу отримати не можливо в принципі. Але мені здається, що таки ні і що лишивши АльфаЗеро грати саму із собою ще пару тижнів, можна показати той самий розгром, що і зараз.
3) А чому ніхто не порівнює кількість оцінених позицій для одного ходу — 70 млн. у Стокфіш проти 40 тис. у АльфаЗеро. Чи це чесно — робити більший перебір?
P.S. Голова DeepMind у своїй доповіді навів декілька прикладів “нетипової” для людини чи шахового алгоритму гри. Так, АльфаЗеро пожертвував слоном та не намагався його відіграти. Завів ферзя у кут(!) , тощо. Але всі ці незрозумілі на перших погляд ход, у решті решт призвели до перемоги.
