AlphaZero. Нейронная сеть играет в шахматы

Не вижу в тексте где написано что ветви в Турнирной версии АльфаГо строятся не до конца партии. Возможно это из-за моего плохого английского, но не нашел такого.

Сочетание MCTS с НС.

Играется до конца.

Даже с точки зрения простой логики - доиграть "до конца" узким деревом шириной в один полуход - не долго, но в MCTS это в любом случае даст улучшение оценки выданной НС.
То есть мы, доигрывая партии до конца, имеем константные потери в производительности, которые имеют компенсацию, либо доигрывая на неполной оценке - даже потерь в производительности не имеем.
Поэтому нелогично не доигрывать до конца, ни в процессе обучения, ни в процессе игры. Хотя опять-таки возможно я ошибаюсь.

В этом как раз и разница между альфа-бетой и MCTS. В том что доиграть в MCTS до конца малозатратно. Относительно потраченных ресурсов чтоб добраться до листа дерева.
Но опять-таки всегда есть варианты типа IDEA в Аквариуме, которая именно наращивает дерево, но это уже не классический MCTS. Ну и из-за плохого понимания английского я мог что-то пропустить в статье.

Это абзац из параграфа Reinforcement learning of policy networks. Это об обучении, а не игре речь.

А где написано о том что в турнирном (игровом) режиме играет не до конца? Можете процитировать?

И далее так-же написано что используются все этапы Рис.3, в том числе и "моделирование продолжается до конца"

Т.е., пытаясь объяснить "на пальцах", можно констатировать, что "проигрывает тот, кто ошибается последним", на таком уровне равносильно (равновероятно?) утверждению "проигрывает тот, кто ошибается первым"?
В таком разе: условия единоборства не очень равны, как мне кажется.
А Вам?
Эдак эндшпильные таблицы и вовсе не нужны...

Я в английском тоже не силен. Но вроде это тоже про обучение. Там и в начале этой статьи METHODS ставится проблема как правильно вычислить коэффициенты нейронной сети. И выделенное о том же говорит: At each of these time-steps, t ≥ L, actions are selected by both players according to the rollout policy. Раз об обоих игроках говорится, значит речь о том, что Альфа Зеро сама с собой играет, то есть об обучении.

Точно так-же нужны. Мы обрываем партию ни когда мат на доске, или ничья по правилам, а когда достигли ЭБ.
Соответственно оценка (результат) точнее, ну и длина вариантов (просмотренных узлов до конечного результата) меньше.

О чем вы? В матче условия были не равны? Да, то что у Стока отобрали дебютную - это было нечестно.
А ЭБ помогло бы и Альфе, и Стоку. И есть подозрение что Альфе она наоборот нужнее. Странно что не прикрутили.
Или прикрутили?

Мне лично всегда больше нравился Монте-Карло, а грубая сила никогда не нравилась

Это суть MCTS - движок в процессе выбора хода (в турнирном, игровом режиме) играет партии до конца сам с собой, делая ходы по очереди за каждую сторону. Конечно-же речь об обоих игроках.

нЕ когда мат (коту (SF?) ясно), а когда достигли, наконец-то, чего-либо доступного всеобщему пониманию?
32menEGTB доступны — допустимо?

Матч начинается с первой партии, первая партия начинается с первого хода — оспоримо? — первым ошибся — проиграл матч — оспоримо?! Есть смысл о чём-то рассуждать дальше?
I.M.H.O., условия единоборства изначально абсолютно не равны!

Мне непонятно в чем вообще смысл в игре досчитывать до конца? Что это дает? При обучении понятно. Таким образом статистику набираем, чтобы потом коэффициенты нейронной сети пересчитать. Но в игре это делать бессмысленно.

И сама суть метода MCTS это расширение игрового дерева в сторону наиболее перспективных ходов. Причем здесь досчитывание до конца?

Не придумывайте. Суть MCTS - в доигрывании партий до конца. В серии тестовых партий. MCTS может искать лучший ход вообще без ОФ, потому что может в качестве оценки узла (и хода) использовать статистику по результатам партий.

Любая дебютная книга - это некий аналог MCTS, в каждом узле есть статистика - сколько раз был сделан тот или иной ход, какой процент очков набрали после того или иного хода, ну и сколько раз были в узле, и какой процент очков был набран из узла.
Построение дебютной библиотеки в рыбке - вот это очень похоже на MCTS. Играется серия партий, и по результатам партий собирается статистика, строится дебютная книга.

Вы пробовали писать программы на MCTS? Если не пробовали, то попробуйте - если программа заиграет, то это даст понимание того, как монте-карловские переборные алгоритмы устроены, и как они работают. Я выше давал ссылки - я не теоретизирую, а я автор в том числе и играющей программы в Го-подобную игру Symple, использующей MCTS, достаточно успешно выступившей в чемпионате Голландии. То есть я не фантазирую, а немного в теме разговора.

NS, поражаюсь выдержке!
Вот что значит настоящий гроссмейстер ИКЧФ!

И что, чтобы пользоваться дебютной книгой во время партии, нужно доигрывать варианты до конца? Бред же.

Точно также и готовая (обученная) нейронная сеть доигрывать варианты до конца не обязана и обычно этого естественно не делает.

Да, похоже. Чтобы обучить нейронную сеть нужно играть партии до конца. С этим никто не спорит.

Я рад что мы достигли такого огромного прогресса. Остался маленький шаг.
В шахматах очень большое количество возможных позиций, и как правило средняя игровая позиция - или не встречалась вообще в процессе обучения, либо встречалась очень редко. Не говоря о том что так-же как есть программы на Альфа-бете, которых не обучали, так-же есть и программы на MCTS - которых не обучали, у которых нет дебютных книг, и у которых нет никаких деревьев, и соответственно ничего ни про одну позицию они не знают.

И так-же как альфа-бете чтоб сделать лучший ход - сначала нужно построить дерево перебора, а потом сделать ход с максимальной оценкой, так и программе на MCTS - игровую позицию она видит впервые, и никакой "дебютной книги" еще нет. И чтоб выбрать ход - ей сначала нужно построить эту "дебютную книгу" наигрывая партии, а потом уже сделать ход с наилучшей статистикой.

При всем уважении - не совсем так. Как в том, что в уже ставшей классической схемой MCTS - (UCT+RAVE+Eval) - нет рандомности. У каждого хода есть вес по формуле, и в каждом узле делается не случайный ход, а ход с максимальным весом.
Так и в коренном отличии классических схем MCTS от классической Альфа-беты.
А разница в том, что ширина дерева альфа-беты, даже если используется не полный перебор - больше единицы. И время для достижения конечного узла, независимо от глубины перебора, даже если оценка вызывается в каждом узле - только чуть больше чем время оценки позиции в этом конечном узле, чем время оценки одной позиции. И сыграть партию из листа дерева до конца, оценивая в каждом узле позицию - слишком дорого. Мы замедляем программу в десятки раз.

И ровно наоборот в MCTS. Время потраченное на достижение некоторой глубины - равно времени необходимом для оценки одной позиции, помноженном на достигнутую глубину, так как у нас чисто линейный вариант. И доигрывая партию до конца, мы замедляем программу всего в пару раз. Не говоря уже о том, что программа на MCTS может быть совсем без ОФ - соответственно считает она очень быстро, на оценку не тратится, а затраты идут практически только на генерацию и исполнение ходов, и сбор и использование статистики. И в качестве оценки - ей нечего использовать кроме результата партии.

То есть теоретически конечно MCTS может считать не до конца, а до неких терминальных позиций. И конечно никто не помешает добавить в альфу-бету корректировку оценки на основании сыгранной до конца партии (или партий). Но практически можно утверждать что это одно из основных отличий методов.

Ну и вопрос в другом - доигрываются ли в АльфаГо, и в шахматной Альфе партии до конца? Я не вижу ни малейших упоминаний о том что нет. Но как я написал выше - возможно это из-за моего очень плохого английского.

В АльфаГоЗеро не доигрываются. Но при этом сила игры уменьшается.

Сложно поверить, что такой подход может давать хорошие результаты. По крайней мере в шахматах. Таким способом оценка позиции замедляется раз в пятьдесят, а ради чего непонятно.

Может и не замедляется. Эти расчеты выполняются на CPU, а процессор может быть не догружен.

Поясните дилетанту. У него в результате обучения остается база партий, дебютная книга, дерево анализов типа IDEA или что-нибудь в этом роде? Или в процессе обучения лишь подкручивалась оценочная функция, а никаких "знаний" о проанализированных позициях не сохранялось?

У него (а конкретно у нейросети) остаётся гигантская трёхмерная таблица, состоящая из одних лишь коэффициентов. Чтобы оценить игровую позицию, мы её оцифровываем, многократно перемножаем на коэффициенты нейросети, а на выходе получаем оценку этой позиции и рекомендуемые ходы с вероятностями. Что происходит внутри нейросети с точки зрения логического анализа, трудно понять.

В смысле на CPU? Насколько я понимаю в Альфа Зеро две нейронных сети. Первая занимается оценкой позиций. Вторая - поиском ходов-кандидатов. Чтобы доиграть партию до конца нам нужно брать лучший ход-кандидат. То есть все равно нужно нейронку использовать и GPU нагружать.

Не обязательно. Для оценки можно использовать только роллауты (rollouts), а они нейросетями не являются. По сути это просто шаблоны + MCTS. Вот хорошая статья, как их используют:
https://habrahabr.ru/post/282522/

P.S. Их достоинство заключается в том, что они очень быстрые. Намного быстрее любой нейросети.

Случайными или шаблонными ходами обыграть Стокфиш, использующий почти честный перебор на огромную глубину? Это явно не научная фантастика.

—- добавлено: 15 дек 2017 —-

Как с помощью нейронки оценивать позиции вроде более-менее понятно. А кто-нибудь понимает как с помощью нейронной сети можно находить ходы-кандидаты? Что там вообще на входе нейронной сети?

Поэтому роллауты применяют совместно с нейросетью. Когда процессор отправит нейросети позицию для оценки, он чем будет заниматься целых 12,5 микросекунд до получения результата? Простаивать. Конечно можно использовать меньше процессоров, но можно и занять их чем-нибудь.

Допустим MCTS прогнала ветку на 50 полуходов. При этом 50 раз было сделано обращение к НС.
Чтоб досчитать до 100 полуходов нужно сделать еще 50 обращений. Замедление в 2 раза, а не в 50.

Насчет обрыва партий:

https://arxiv.org/pdf/1712.01815.pdf

На входе позиция, на выходе ходы-кандидаты и оценка. Нейросеть одна, но она выполняет обе функции.

Если правильно понял, элемент эвристики присутствует?
"На Аллаха надейся, но на жену паранджу надевать не забывай..."

В Зеро не присутствует, шаблоны там специально отключены. В АльфаГоЗеро никаких роллаутов нет. А в АльфаЗеро - там слишком поверхностная статья, но возможно что тоже.

Слушайте, ну это ж вообще фигня какая-то. Позиция 49-го хода черных:


Нам предлагается поверить, что "Стокфиш" в этой позиции пошел Rf8 вместо Кf8.
Запустил на своем ноутбуке: секунд 20 показывает Rf8, затем забраковывает его и дает Kf8. На Rf8 показывает, что это грубая ошибка и показывает, что это выигранная позиция за белых.

Что за "Стокфиш" у них там был, если ему не хватило минуты на то, чтобы это сосчитать?
После такого нет сомнений, что не только железо было слабое, но и "Стокфишу" выставили неполную силу игры - процентов 50-70.