Pull to refresh

Comments 46

Собственно, все. Лучшим ходом объявляется нод, через который бегали чаще всех (оказывается, это чуть стабильнее чем этот Q-score). AlphaGo сдается, если у всех ходов Q-score < -0.8, т.е. вероятность выиграть меньше 10%.

Мне кажется, это лазейка, чтобы подловить AlphaGo. Очередность ходов имеет значение. Есть камни, которые рано или поздно должны быть поставлены, но поставленные слишком рано они приносят не столько пользы, сколько поставленные в свое время.
Ммм, следующий ход выбирается только из непосредственных детей рута. Т.е. это ближайший ход из возможных, через который чаще всего бегала симуляция.
Т.е. частота это просто счетчик того, насколько детально анализировалась позиция (кол-во просмотренных (до конца?) дочерних подпозиций, грубо говоря)? Т.е. расчет делается на то, что чем более перспективный оказывается ход, тем более детально он рассматривается.
В некотором смысле да, но я уточню.
Так как вероятность просмотра напрямую зависит от того, какой у позиции Q-score (симуляция выбирает ходы с максимумом Q + m(P)), то он очень коррелирует с тем, насколько выгодны позиции дерева за ним. Теоретически, можно выбирать и по максимуму Q-score напрямую, но вот они обнаружили, что по количеству чуть стабильнее.
У них в финальной версии даже есть эвристика, что если эти две метрики не сочетаются, надо прогнать дополнительные симуляции.
Воодушевляет, что они собрали довольно известные методы, очень грамотно их настроили-объединили и получили такой скачок в результатах.

Что интересно, можно ли получить существенный прогресс, добавив туда expert knowledge, в духе классические шаги завершения комбинаций или локальные-глобальные стратегии?
В некотором смысле, где есть feature engineering, там есть и expert knowledge. Часть системы — линейный классификатор на основе заранее заданных фич, что попадает в эту категорию. Возможно, если есть какие-то еще инсайты, можно добавить их к оценке нода.

Но все равно похоже они должны быть заданы так, чтобы модель можно было обучать. Иначе не получится адаптировать это для стратегии, которая эволюционирует через reinforcement learning.
Похоже, что уже нет. Майкл Редмонд (очень сильный профессионал, который комментирует матчи) характеризует некоторые ходы AlphaGo как странные, и только дальше по ходу матча выясняется, какая от этих ходов польза.

Кроме того, человеческая стратегия отличается от компьютерной, и похоже что это одна из причин, которая позволяет AlphaGo показывать такой хороший результат. Например, AlphaGo не пытается нарастить своё преимущество. Выигрыш на камень с вероятностью 90% для неё лучше выигрыша на пять камней с вероятностью 89%. Человек обычно пытается выиграть с некоторым запасом.
Второе, кстати, прямое следствие выбранного алгоритма — так как все метрики оперируют бинарным reward (победил или нет), то максимальным score будет обладать ветка, которая максимизирует именно это, а не margin.
Вообще говоря, можно натренировать версию, которая будет стремиться именно подавлять оппонента разгромным счетом :)
Пожалуй стоит добавить в статью эту ссылку, энтузиасты начали воссоздавать ИИ AlphaGo на основе публикации и выложили это на гитхаб: AlphaGoReplication.
По-моему, они выложили раньше, чем начали что-то воссоздавать. Ткнулся в десяток случайных файлов — все либо пустые, либо без какого-то внятного содержимого.
Интересно, насколько ухудшится уровень, если запустить этот ИИ на обычно компьютере? И можно ли его так оптимизировать, чтобы его можно было перенести на обычный компьютер практически без ухудшения качества расчета. Просто Deep Blue, обыгравший Каспарова, тоже был суперкомпьютером, а сейчас даже с обычным компьютером практически бесполезно соревноваться. Понятно, что с тех времен мощности сильно выросли, но все же интересно, можно ли это сделать в теории с очень хитрыми и мощными эвристиками или же все упирается в вычислительную способность?
В статье в Nature подробно описывают, как изменяется сила алгоритма игры измеренная рейтингом ELO при различных вычислительных ресурсам
см. страницу 11
https://gogameguru.com/i/2016/03/deepmind-mastering-go.pdf
Как пишут сами авторы по сравнению с Deep Blue, анализируется на 3 порядка меньше комбинаций:
AlphaGo evaluated thousands of times fewer positions than Deep Blue did in its chess match against Kasparov
Правда, насколько я понимаю, в этой оценке они ни учитывают стадию rollouts
Теоретически если бы нейросети были натренированы лучше, то необходимое количество ресурсов становится радикально меньше. Весь вопрос — можно ли лучше натренировать? Никаких теоретических оценок или ограничений нет, в других задачах получается находить архитектуры и решения все точнее и точнее.
Глядишь и тут будет прогресс.
Мне кажется, что все ресурсы в основном уходят на перебор вариантов в Monte Carlo Tree Search. А с учетом этого:

Предсказание этой натренированной SL-policy (SL — supervised learning) уже рвет все прошлые программы Го, без всяких деревьев и переборов.

Походу на обычном компьютере или даже на планшете AlphaGo будет играть очень неплохо.
О, про это есть немного информации в статье. Проход по дереву выполняется всего на одной машине, кластер из 280 GPUs и 1500 чтоли CPU занимается исключительно вычислением policy и value networks + rollouts для новых годов дерева. Т.е. основная нагрузка перебора — это именно нейросети. Если бы они сужали перебор лучше, нужно было бы меньше перебирать.

Про второе — ну да, будет играть неплохо даже просто с SL-policy, но Lee Sedol не выиграет :)
Кстати, в продолжение разговора —

Distributed version is only ~75% win rate against single machine version! Using distributed for match but single machine AG very strong also
https://twitter.com/demishassabis/status/708489093676568576

Даже на одной машине с ней могут соревноваться не больше 100 человек в мире поди
В переводе не нашел информации, сколько весят нейронные сети в общем и по отдельности. И что означает
+ добавился некий ML на тему менеджмента времени.

В каком переводе?.. То что у меня — это скорее вольное изложение :)

Про время — это что AlphaGo нужно принимать решение, сколько дозволенного времени тратить на ход. В статье про это было написано очень расплывчато, а потом Demis Hassabis в каком-то интервью сказал, что они обучили для этого какую-то модель
И даже в этом направлении идёт прогресс, следите за публикациями!
Пока только научились с помощью LSTM "изучить" Linux kernel и на основе этой информации генерить нечто бредовое, но очень похожее. Важным в этом контексте являются Neural Turing Machines. Если это все как то хитрым способом скомбинировать, то наверное что то получится.
Спасибо Семён! Я статью из Nature распечатал ещё тогда и просмотрел по диагонали, но не изучил. Ты пишешь очень доходчиво.

По делу — с точки зрения отличия от "настоящего" AI у меня к AlphaGo две претензии / предложения, попроще и посложнее:

попроще: было бы интересно узнать, во сколько раз больше вычислительных ресурсов потребовалось бы, чтобы натренировать сети до такого же отличного уровня игры чисто через игры с самой собой, без обучения на большой базе игр экспертов (ты про этот аспект написал, кстати? вроде не вижу...);

посложнее: параметры системы (картинки-таблицы в твоей статье: топология сетей и параметры MCTS) тоже люди же подбирали, не само выросло... Вот эти дела чтобы самовыводились, это интересная (и гораздо более ресурсоёмкая) задача. Ты читал / слышал про General Game World Championships? http://www.general-game-playing.de/ (почему-то с 2011 года соревнования не проводились... Но сайт обновляется!)
Очень странная разметка у тебя :)
Насколько я понимаю, про успехи тотального reinforcement learning ничего не понятно. Демис из Deepmind только несколько раз упоминал, что прикольно было бы сделать без бутстрапа с человеческими партиями (он описан в Шаге 1 в этом посте).

Выбирать оптимальные гиперпараметры (это не только параметры сети, их в любом процессе много) — это отдельная специальная наука. Наиболее перспективны на сейчас — так называемые Gaussian Processes. Грозятся, что с некоторыми допущениями получается гарантировать близость к глобальному оптимуму за некоторое число шагов. Я статьи сам еще не прочитал, прочитаю — доложусь.
"прочитаю — доложусь" — давай! Я буду тебе напоминать.

"Очень странная разметка у тебя :)" — у них тут какой-то агрессивный markdown. Я всего лишь поставил то ли два, то ли три пробела в начале двух параграфов "попроще: ..." и "посложнее: ..." и, видимо, эти пробелы послужили сигналами, что я цитирую код или что-то такое. Потом, почему английский подхватился жирным, а после // пошло сереньким синтезированным италиком, ну, я не хочу даже разбираться (посты здесь не пишу, нет смысла инвестировать внимание в это).
Интересно, не тренировали ли сеть на игру против конкретного человека? Просто меняя обучающую выборку. Это объяснило бы, почему игру Фан Хуэя так критиковали.
Не тренировали. Более того, ее даже не тренируют между матчами текущей партии для чистоты эксперимента.
Им нужна обучающая выборка как можно больше, поэтому они просто берут все игры, до которых могут дотянуться.
Вот неочевидно, что было бы, если бы из обучающей выборки исключили все игры Ли Седоля.
ничего бы не было. количество его (да и всех человеческих) игр, по сравнению с играми которые АльфаГо играла сама с собой пренебрежимо мало.
На пресс-конференции представитель гугла сказал, что в их базе партий Ли Седоля нет, по его словам я понял, что там вообще только партии сильных любителей были.
Ага, было известно что у них только онлайн-матчи в изначальной выборке для тренировки, но я как-то думал, профессионалы в онлайне тоже играют
Ыы, привет. Сто лет тут тебя не было видно :) Как раз недавно перечитывал твою старую статью про mem latency тут, вспоминал старый геймдев.ру. В общем, здорово тебя тут видеть снова.

Набрел, кстати, на этот ваш closedcircles (через gamedeff.com), даже зарегался. А инвайт дает какие-то преференции?
Привет :)

Только сразу заводит в правильный кружок.
Игру на 10 досках пока не осилит
Turns since… 8

Т.е., после 256-го хода у сети будет переполнение? #irony
Мне кажется там one-off encoding на все, поэтому это всего на 8 ходов :)
Так за счёт чего произошел прорыв то? Как раньше играли программы в GO? Можете объяснить тот же Monte Carlo Tree Search поподробней и почему его одного не хватает?
MCTS не хватает, потому что дерево ходов слишком широкое. Для каждой позиции в среднем есть 250 вариантов хода. А AlfaGo сразу отсекает по дерево перебора ширине, плюс по ходу перебора отсекает по глубине.
За счет эффективности эвалюации нодов в поиске. Если ценность и вес ноды определяются плохо, то MCTS должен пройти в дереве очень далеко, чтобы понять какой ход лучше. В Го настолько много возможных ходов, что обойти все раскрытием дерева — нереально, и MCTS с ограниченными ресурсами найдет не слишком хороший ход.
А если оценки ценности и веса дают возможность исследовать только интересные ходы, сразу все становится значительно лучше.
Sign up to leave a comment.

Articles