Еще один шаг
Sep. 18th, 2015 04:37 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
kaipaПочти год назад наколеночная нейронная сеть научилась играть в шахматы просто имея массив готовых игр. В опубликованной недавно статье (магистрская работа) описывается шахматная программа, использующая нейронную сеть для оценки позиции и оптимизации перебора. По утверждению авторов программа играет в силу мастера.
Хотя это звучит круто-круто, на самом деле это круто, но не настолько :) Так как начальной точкой оптимизации была программа, основанная на традиционных алгоритмах, которая уже играла чуть хуже кандидата в мастера. Нейронные сети использовались для ее улучшения и замены некоторых алгоритмических частей на обучаемые.
Статья интересная, и ее стоит прочитать всем, кто интересуется этой темой. Нейронная сеть была использована для двух разных целей.
Для начала, авторы поставили задачу оценки позиции при помощи нейронный сети. Они построили и натренировали сеть так, чтобы получить функцию оценки максимально близкую к известной функции оценки Stockfish (есть массив позиций оцененных Stockfish). А потом проверили на позициях из Strategic Test Suite. Натренированная нейронная сеть смогла оценивать позиции на уровне лучших шахматных программ, не имея практически никаких априорных знаний -- только опыт обучения!
Следующая логичная задача, которую поставили перед собой авторы -- это использовать нейронную сеть для предсказания лучшего хода. Здесь они использовали нестандартный, как мне кажется, подход для определения глубины поиска: отсечение по вероятности выиграть. То есть для каждой позиции вычисляется вероятность выигрыша, перебор идет в сторону позиций с более высокой вероятностью (или отсечение низких). Это дает преимущество при оценке длинных "вынужденных" комбинаций, когда в позиции не очень много ходов, но ее надо просмотреть глубоко. Нейронная сеть была натренирована для предсказания этих вероятностей. По сравнению с вариантом вычисления вероятностей "в лоб" (чисто через оценку позиций), нейронная сеть "угадывала" наилучший ход несколько чаще, то есть и в этом случае удалось повторить (в смысле результата) и превзойти закодированный алгоритм!
В обоих случаях существующий жесткий алгоритм был заменен гибкой и обучаемой нейронной сетью, то есть при дальнейшем обучении (на лучших данных или в режиме self-play) можно ожидать еще большего роста качества игры.
Это, конечно, не так круто, как "научиться играть" по партиям, но все равно впечатляет.
Хотя это звучит круто-круто, на самом деле это круто, но не настолько :) Так как начальной точкой оптимизации была программа, основанная на традиционных алгоритмах, которая уже играла чуть хуже кандидата в мастера. Нейронные сети использовались для ее улучшения и замены некоторых алгоритмических частей на обучаемые.
Статья интересная, и ее стоит прочитать всем, кто интересуется этой темой. Нейронная сеть была использована для двух разных целей.
Для начала, авторы поставили задачу оценки позиции при помощи нейронный сети. Они построили и натренировали сеть так, чтобы получить функцию оценки максимально близкую к известной функции оценки Stockfish (есть массив позиций оцененных Stockfish). А потом проверили на позициях из Strategic Test Suite. Натренированная нейронная сеть смогла оценивать позиции на уровне лучших шахматных программ, не имея практически никаких априорных знаний -- только опыт обучения!
Следующая логичная задача, которую поставили перед собой авторы -- это использовать нейронную сеть для предсказания лучшего хода. Здесь они использовали нестандартный, как мне кажется, подход для определения глубины поиска: отсечение по вероятности выиграть. То есть для каждой позиции вычисляется вероятность выигрыша, перебор идет в сторону позиций с более высокой вероятностью (или отсечение низких). Это дает преимущество при оценке длинных "вынужденных" комбинаций, когда в позиции не очень много ходов, но ее надо просмотреть глубоко. Нейронная сеть была натренирована для предсказания этих вероятностей. По сравнению с вариантом вычисления вероятностей "в лоб" (чисто через оценку позиций), нейронная сеть "угадывала" наилучший ход несколько чаще, то есть и в этом случае удалось повторить (в смысле результата) и превзойти закодированный алгоритм!
В обоих случаях существующий жесткий алгоритм был заменен гибкой и обучаемой нейронной сетью, то есть при дальнейшем обучении (на лучших данных или в режиме self-play) можно ожидать еще большего роста качества игры.
Это, конечно, не так круто, как "научиться играть" по партиям, но все равно впечатляет.
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
no subject
Date: 2015-09-18 12:52 pm (UTC)К.Л.М.
no subject
Date: 2015-09-18 01:13 pm (UTC)no subject
Date: 2015-09-18 07:49 pm (UTC)Кроме того, зависимость результата (окончательных оценок позиций) от порядка обхода ветвей -- лишь следствие того, что граф обходится не полностью. А разве эта зависимость как-то мешает ?
К.Л.М.
p.s. Альфа-бета отсечение я когда-то ещё в школе делал для игры в шашки. Давно это было, мог позабыть чего...
no subject
Date: 2015-09-18 10:15 pm (UTC)Кстати, одно из следующих направлений исследований, которое предлагают авторы в статье, это использование сети для распределения времени на анализ тех или иных ветвей.
no subject
Date: 2015-09-19 04:05 pm (UTC)Если программы на нейросетях будут стабильно переигрывать другие программы на том же железе -- это будет для меня новостью, конечно.
К.Л.М.
no subject
Date: 2015-09-19 05:41 pm (UTC)Ну вот данный пример как раз показывает, что можно взять программу на жестких алгоритмах и заменить их или их части на мягкие нейросетевые с положительным эффектом. Модифицированная программа стала "сильнее" исходной на 150-200 пунктов рейтинга Эло.
По правде сказать, я раньше не особо верил в полезность генетических алгоритмов, из-за No Free Lunch. Во всяком случае для задач оптимизиации. Но в рамках Deep Learning они позволяют выявить закономерности, которые обычными методами найти чрезвычайно сложно, особенно в задачах высокой размерности. Эти ребята для оценочной функции закодировали позицию вектором размерности 350 или около того, там не только положения фигур, но и всякие тактические характеристики позиции. Половина успеха именно в способе представления.
Впрочем, тенденция последнего времени выявлять закономерности в данных, не пытаясь понять, как они там возникли. Это, как выразился один мой знакомый, замена науки "медициной", "почему" на "что".
no subject
Date: 2015-09-19 06:01 pm (UTC)Идее использования NN в шахматных программах уже десятки лет. Если бы эта идея была продуктивной -- все лучшие программы сейчас использовали бы NN. Ну, если не верить в теории заговора, конечно.
Вообще NN решает задачу подгонки произвольной неизвестной функции другой функцией, которая имеет огромное число параметров. Как говорил когда-то известный физик Ландау -- "дайте мне 5 параметров и я нарисую слона". Я не хочу сказать, что слонов рисовать не нужно. Но этот метод, отнюдь, не панацея. Его главные недостатки в том что "не понятно -- как это работает" и "не очевидно, что описав 1000 примеров с успехом, программа не даст какой-то катастрофический сбой на 1001-м". В каких-то областях, где примеров мало и сбои не так критичны (например OCR) -- это отлично работает.
Кроме того, если понимать задачу, решаемую NN, как задачу подгонки, то сразу отпадает всякая шелуха вроде "мозгоподобности". Просто берём набор данных, параметризованную функцию и "фитуем". Хорошая функция опишет данные хорошо, плохая плохо, функция же с малым количеством параметров поможет заодно и нам что-то о данных понять...
К.Л.М.
no subject
Date: 2015-09-19 09:08 pm (UTC)Возможно, что не хватало дешевых вычислительных мощностей и тестовых наборов (позиций, партий), которые в достаточном для обучения количестве стали открыто доступны в последние лет 5-10, не больше.
> Вообще NN решает задачу подгонки произвольной неизвестной функции другой функцией, которая имеет огромное число параметров.
Безусловно. Я как-то даже обсуждал этот вопрос менее абстрактно: http://ushastyi.livejournal.com/248444.html
Как говорил Ландау
Date: 2015-10-21 03:10 pm (UTC)О_О спасибо
Вот прям недавно с пытался объяснить плохи переоптимизация и подгонка параметров но похоже так и не донёс (дошёл аж до Колмогоровской сложности).
Re: Как говорил Ландау
Date: 2015-10-21 03:54 pm (UTC)К.Л.М.
Re: Как говорил Ландау
Date: 2015-10-22 09:38 am (UTC)А если более развёрнуто, то:
1. Переоптимизация -- плохо всегда (тут по определению просто что для одного проекта (способа задания свободных коннстант) "пере" то для другого вполне себе оптимизация).
2. Подгонка (в этой вселенной) -- плохо почти всегда.
те из 2х случаев (дающих сразу после коммита одинаковый эффект)
if (app_name == "gcc") {
RunSpecialGccOptimization()
}
или
// область определения 1.0 - 1.5
// 1.1 - 1.4 "плато" с примерно одинаковой производительностью
// было 1.25 -- ровно середина мы соптимизировали
#define DEFICITE_KOEF 1.203
Первый случай -- вполне может быть оправданным распространённым юз-кейсом
А второй -- почти наверняка чистая переоптимизация которая даёт эффект "здесь и сейчас" с учётом всех остальных коэффициентов и эвристик. И вопрос лишь в том когда (через неделю или месяц) она перестанет работать.