В предыдущей части мы реализовали проигрыватель, который использует таблицу для изучения функции Q. Это сработало довольно хорошо. В частности, потому что у Tic Tac Toe очень мало состояний, и у каждого состояния очень мало возможных ходов. Для более сложной игры, такой как го или шахматы, табличный подход не применим.

Что, если бы мы могли написать программу, имитирующую поведение функции Q, без необходимости сохранять точное значение для каждого состояния и действия? Очевидно, что после небольшой практики люди могут определять определенные закономерности в игровой позиции и выводить общие правила, как на них реагировать. Можем ли мы научить программу делать что-то подобное?

Именно в этом заключается идея при использовании нейронной сети. Нейронные сети обычно используются для выполнения одного из двух следующих действий:

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

Мы воспользуемся вторым вариантом использования и обучим нейронную сеть имитировать функцию Q. В идеале, используя значительно меньше места, чем это делает табличная функция Q.

Время для некоторых благодарностей:

Большую часть того, что я знаю об обучении с подкреплением с помощью TensorFlow, я почерпнул из отличных руководств от Артура Джулиани.

После этого я прочитал Обучение с подкреплением - Введение Ричарда С. Саттона и Эндрю Дж. Барто для более глубокого понимания темы.

Мне также показался интересным и полезным учебник Джонатана Лэнди Глубокое обучение с подкреплением, боевой корабль. Однако, по крайней мере, для меня, довольно неортодоксальный выбор передать вознаграждение в сеть через скорость обучения, я нахожу несколько озадачивающим. Я подозреваю, что математически это как-то эквивалентно подаче награды через этикетку, но как именно это работает, мне не очевидно.

Препараты

Чтобы выполнить код в этом блокноте, вам необходимо установить TensorFlow. На момент написания этой статьи инструкции о том, как это сделать, можно найти здесь. Если ссылка больше не работает, быстрый Google сможет указать вам правильное направление.

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

Если у вас нет современного графического процессора, выбор прост: установка без поддержки графического процессора.

Если у вас есть современный графический процессор, вы можете попробовать установить версию с графическим процессором, но это гораздо более сложный и трудный процесс, чем установка версии без графического процессора. В частности, вам нужно будет установить все виды библиотек графического процессора, прежде чем вы сможете установить TensorFlow. Делайте это только в том случае, если вам комфортно со сложной установкой программного обеспечения и если вы можете справиться с неприятными последствиями, которые неизбежно произойдут, если вы застрянете в середине процесса и вам придется откатить то, что вы сделали до сих пор. Однако если вам это удастся, код в этом и следующих ноутбуках будет работать заметно быстрее, чем без поддержки графического процессора.

Краткое введение в искусственные нейронные сети

Искусственные нейронные сети состоят из узлов. Узел принимает один или несколько входов. Он комбинирует входы линейно, то есть умножает каждый вход i_x на специальный вес w_x для этого входа и складывает их все. Вдобавок к этому добавляется еще одно значение, так называемое смещение. Затем он применяет функцию активации f_a к результату и отправляет его на один или несколько выходов O:

Боковое примечание: bias эффективно превращает линейную функцию узла в аффинную линейную функцию, то есть линию, которая не обязательно проходит через точку (0,0). Без этого, что бы ни говорили обученные веса, выход для входа 0 всегда был бы 0. Есть и другие способы достижения этого, и вы действительно найдете их в некоторых книгах. Например. добавляя еще один вход к каждому узлу с фиксированным входным значением 1. Математически это то же самое.

Функция активации позволяет добиться нелинейности. Без него мы могли бы имитировать только линейные функции. Кроме того, без него многоуровневые сети не имели бы смысла. Они будут просто комбинацией линейных функций, и, как нам скажет любой учебник по алгебре: комбинация линейной функции - это не более чем сама линейная функция. Т.е. мы могли бы просто свернуть все слои в один и выполнять все вычисления более эффективно.

Узлы, которые не имеют входящих подключений, называются входными узлами, а узлы, не имеющие выходных подключений, называются выходными узлами. Узлы расположены по слоям, первый слой состоит из узлов ввода, а последний слой - из узлов вывода. Другие слои также часто называют скрытыми слоями, поскольку пользователь будет взаимодействовать только со слоями ввода и вывода.

Простая сеть с одним скрытым слоем может выглядеть так (источник Википедия):

Устанавливая веса в узлах правильно, нейронная сеть может имитировать другие сложные функции с таким же количеством входных и выходных значений.

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

Более подробное введение в искусственные нейронные сети можно найти в Википедии или в любом количестве других источников, которые быстро найдет Google.

Краткое введение в TensorFlow

TensorFlow - это фреймворк машинного обучения с открытым исходным кодом от Google. Это позволяет нам определять, обучать и запускать искусственные нейронные сети на очень высоком уровне в Python. Я не буду здесь подробно рассказывать, как это работает или как его использовать. Я буду комментировать код, который мы используем, по ходу дела, но если вы застряли, и все это просто не имеет никакого смысла, пожалуйста, прочтите некоторые вводные ресурсы в TensorFlow Get Started или аналогичных руководствах по TensorFlow, а затем вернитесь сюда. и попробуйте еще раз.

Нейронная сеть для игры в крестики-нолики

Чтобы обучить нейронную сеть игре в крестики-нолики, нам нужно определить следующие вещи:

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

Базовый обучающий график Tic Tac Toe Q

Мы поэкспериментируем с разными графиками, но основная форма всегда будет следующей:

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

Есть много других способов сделать это:
Мы могли бы передать действие в сеть вместе с состоянием платы и получить одно выходное значение, указывающее значение этого действия.
Мы также могли бы просто иметь одно выходное значение, кодирующее значение состояния, и использовать его в качестве прокси для пар «Состояние / Действие», которые приводят к этому состоянию.
И многое другое.

Входной слой

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

Однако общепринято считать, что нейронные сети лучше всего работают в подобных случаях с двоичными массивами в качестве входных данных. Слепо доверяя этой мудрости, наш вход будет массивом из 27 (= 3 * 9) битов с первыми 9 битами, установленными на 1 в позициях крестиков, следующими 9 битами, установленными на 1 в позиции Naughts и последние 9 бит установлены в 1 в пустых позициях:

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

Выходной слой

Выходной слой будет иметь 9 узлов / выходных значений, по одному для каждой позиции доски, которую мы могли бы воспроизвести. Мы будем интерпретировать значение узла как значение Q соответствующего движения.

Мы будем игнорировать тот факт, что для определенного состояния правления некоторые позиции уже были бы заняты и больше не были бы вариантом. Игрок учитывает это при выборе хода и игнорирует недопустимые ходы независимо от того, каковы их значения Q. То есть мы не пытаемся научить нейронную сеть, какие ходы допустимы, а какие нет. Опять же, общий совет, который вы найдете, заключается в том, что это лучший подход - мы должны быть осторожны, чтобы также игнорировать эти шаги при вычислении maxaQ (S ', a) для обновления Q Value.

Пора взглянуть на код

Первую версию нашего Neural Network Q-Learning Player можно найти в файле SimpleNNQPlayer.py.

Давайте посмотрим на некоторые выбранные части кода. В файле определены два класса:

  • QNetwork, который строит граф TensorFlow.
  • NNQPlayer, который реализует логику игры и использует класс QNetwork для определения ходов.

Подробнее QNetwork

Класс QNetwork имеет 2 важных метода add_dense_layer и build_graph.

Метод add_dense_layer - служебный метод, который просто добавляет новый слой размера output_size с функцией активации activation_fn поверх слоя input_layer. При желании он также будет прикреплять к слою имя name.

Метод build_graph - это то место, где строится фактический график.

Этот метод создает заполнители для ввода платы (self.input_positions), а также целевых значений Q, которые мы предоставим в обучении (self.target_input).

Затем он строит граф TensorFlow, начиная с входного слоя. Он добавляет один скрытый слой с 9-кратным количеством узлов входного слоя (BOARD_SIZE * 3), то есть 243 узла. Количество узлов было выбрано более или менее произвольно. Несмотря на то, что разные значения, скорее всего, будут работать по-разному. Почувствуйте желание поэкспериментировать и отчитаться.

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

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

Есть еще один слой self.probabilities, который преобразует значения Q в соответствующие вероятности действий с помощью функции Softmax. Если мы выбрали действие в соответствии с его вероятностью в self.probabilities, мы будем выбирать действия с высокими значениями Q пропорционально чаще, чем действия с низкими значениями Q. Мы можем использовать это для исследования, когда мы не всегда хотим двигаться с единственным наивысшим значением Q.

В целом это очень простая сеть с одним небольшим скрытым слоем:

Зеленые узлы - это то место, где мы вводим данные в сеть, а оранжевые узлы - это то, где мы получаем результаты.

Присмотритесь к NNQPlayer

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

Фактически, он играет ход с наибольшим значением Q среди всех допустимых ходов. В этой реализации мы не пытаемся научить Сеть распознавать и отбрасывать недопустимые ходы - мы просто игнорируем их, делая ход.

Во время игры мы записываем данные, которые нам понадобятся позже для обучения сети. Мы записываем все состояния доски, значения Q всех ходов в этих состояниях, все ходы, сделанные во время игры, и максимальное значение Q всех ходов в новом состоянии для каждого хода (то есть значение Q, которое мы передаем с помощью скидка).

По окончании игры мы обновляем значение Q для каждого хода по формуле:

Q (S, A) = γ ∗ maxaQ (S ′, a)

где γ - коэффициент дисконтирования, а maxaQ (S ′, a) - максимальное значение Q всех возможных ходов в состоянии S ′, причем S ′ - это состояние, в котором мы оказались после выполнения хода A в состоянии S.

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

Значения Q для состояния платы можно вычислить в get_probs:

Расчет следующего хода происходит в move:

Новые оценки значения Q вычисляются в calculate_targets:

И нейронная сеть обучается final_result:

Время запустить код

Итак, насколько хорошо работает эта сеть? Давай поиграем в пару игр и посмотрим.

Резюме

Как мы в целом прошли? Вот краткое изложение наших результатов с этим очень простым проигрывателем на основе нейронной сети:

Player      |  NN Player 1st          |  NN Player 2nd  
==============================================================
Random      | Not bad but not perfect | Kind of but not really
Min Max     | Mixed — All or nothing  | Mixed — All or nothing
Rnd Min Max | Sometimes / Mixed       | Nope

Не так хорошо, как я надеялся, учитывая, что освоение Tic Tac Toe не является особенно сложной задачей - по крайней мере, для человека, даже в очень молодом возрасте. Так что же происходит? Присоединяйтесь к нам снова в следующий раз, когда мы попытаемся выяснить, почему мы получаем эти довольно неутешительные результаты, и сможем ли мы найти способ построить лучшие сети, которые преодолеют эти ограничения.

Остальные части этой серии можно найти здесь:

Исходный код и записные книжки Jupyter для всех частей этой серии доступны на GitHub.