ДонНТУ   Портал магистров

О себе Реферат Научные труды Индивидуальный раздел

АЛГОРИТМ ОБУЧЕНИЯ КЛАССИЧЕСКИМ ИГРАМ В КОНТЕКСТЕ ОБУЧЕНИЯ С ПОДКРЕПЛЕНИЕМ

Клипаков С. А., Таращанский М. Т. Алгоритм обучения классическим играм в контексте обучения с подкреплением // Вестник Луганского государственного университета имени Владимира Даля. — 2023. — № 11. — С. 149-151.

Клипаков С. А., Таращанский М. Т.

Аннотация

В работе рассматривается задача обучения агентов игре в различные классические игры, такие как шахматы, шашки, нарды и другие, с помощью методов обучения с подкреплением. Авторы предлагают дополненный алгоритм обучения с подкреплением, который сочетает в себе идеи из классического обучения с подкреплением и уже реализованный алгоритм AlphaZero. Будет описана общая концепция использования RL для обучения играм на двоих. Алгоритм также включает в себя механизм начальной обработки весов с использованием имеющейся базы данных «сильных» игроков.

Ключевые слова: обучение с подкреплением, игры на двоих.

Введение

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

В последние годы было предложено несколько прорывных алгоритмов обучения с подкреплением для классических игр, таких как AlphaZero, MuZero и Expert Iteration. Эти алгоритмы используют глубокие нейронные сети для аппроксимации стратегии и функции ценности, а также монте-карло поиска для усиления своих решений. Однако, в данной публикации авторами опущена работа с нейронными сетями (см., например, [3-5]), а основной упор сделан на выведении общего алгоритма обучения играм на двоих в контексте обучения с подкреплением. В данной работе поведение агента выражено классической функцией ценности, вместо нейронной сети как, например, в AlphaZero.

Краткий экскурс в обучение с подкреплением

Концепция обучения с подкреплением [1] (далее RL) строится на взаимодействии агента и среды, которое выражено в цикличном обмене: в момент времени \(t\) агент получает от среды наблюдение \(o\), отвечает на него действием \(a\) и получает награду \(r\), после чего среда меняет свое состояние \(s\), время меняется на \(t+1\) и цикл начинается заново. Получив одну или несколько наград, агент меняет свое поведение, увеличивая или уменьшая вероятность выполнения действия \(a\) в состоянии \(s\) в будущем в зависимости от награды. Схематично взаимодействие агента со средой представлено на рис. 1.

Математическая модель RL описывается набором параметров \((S, A, P, O, R, \sigma, r)\), где:

• \(S = \{s\}\) – множество возможных состояний среды;
• \(A = \{a\}\) – множество возможных действий агента;
• \(P_a^{s s'} : S \times A \times S \to [0, 1]\) – функция перехода, возвращающая вероятность перехода среды из состояния \(s\) в состояние \(s'\) при совершении агентом действия \(a\);
• \(O = \{o\}\) – множество возможных наблюдений агента;
• \(\sigma(s, o) : S \times O \to [0, 1]\) – функция наблюдения, возвращающая вероятность получения агентом наблюдения \(o\) в состоянии \(s\);
• \(R = \{r\}\) – множество значений наград;
• \(r(s, a, s') : S \times A \times S \to R\) – функция вознаграждения, получаемого агентом при совершении действия \(a\) в состоянии \(s\) и при переходе среды в состояние \(s'\).

Схематично математическая модель RL представлена на рис. 2.

Статистика уже реализованного алгоритма для обучения в играх шахматы, сёги и го (AlphaZero). С использованием подхода RL созданы обученные агенты, выраженные нейронными сетями, которые показывают сверхчеловеческий уровень в играх шахматы, сёги и го. Также, исходя из статистики, приведенной в работе [2], данные агенты показывают результаты выше, чем программы, использующие другие подходы. Таким образом, имеет место утверждение об универсальности использования методов RL для обучения классическим играм на двоих.

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

Игра. Под игрой в данной работе будет пониматься ориентированный граф (\(E\)), вершинами которого являются состояния (\(s\)), а направленными ребрами – действия \(a\). Пример такого графа приведен на рис. 3.

Таким образом, для каждой игры есть множество состояний \(S = \{s_1, s_2, ..., s_n\}\), где \(n \in \mathbb{N}\) и множество действий \(A = \{A(s_1), A(s_2), ..., A(s_n)\}\), где \(A(s_i) = \{a_m^1, a_m^2, ..., a_m^i\}\), \(m \in \mathbb{N}\). Игроки совершают ходы поочередно.

Обучаемый игрок. Поведение игрока определяет функция ценности хода \(Q(a)\), схематично показанная на рис. 4. Q-функция возвращает число в соответствии с парой (состояние, действие). Значение Q-функции отображает количество побед и поражений обучаемого игрока после выполнения действия \(a\) в состоянии \(s\) (в данной работе верхний левый индекс действия обозначает номер состояния и Q-функция принимает на вход только действия).

В начале обучения все значения Q-функции равны нулю и изменяются по мере накопления опыта игроком. Процесс накопления опыта осуществляется посредством изменения весов Q-функции по формуле:

\( Q^{new}(a) = Q^{old}(a) + f(n) \cdot R \),

где \(Q^{old}(a)\) – веса действий игрока до изменения, \(Q^{new}(a)\) – измененные веса, \(f(n)\) – некоторая убывающая функция с областью значений [0,1], зависящая от номера хода (для начальных ходов в партии ее значение близко к 0, а в терминальном состоянии 1) и \(R\) – награда. Действия в каждом состоянии выбираются как

\( \max(Q^i(a)) \)

(максимум среди весов действий в \(i\)-м состоянии), если таких максимумов несколько, то выбирается случайный из них.

Оценкой игры для игрока выступает награда \(R\), отображающая исход партии. Например, награда может принимать значения -1 – за поражение, 0 – за ничью, 1 – за победу.

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

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

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

• задание правил игры графом (правила также задают терминальное состояние и награду);
• формирование начальных (учительских) весов Q-функции для ускорения обучения;
• формирование поведения соперника;
• накопление опыта и корректировка Q-функции на партиях с соперником;
• получившуюся политику поведения можно корректировать до получения необходимого результата, изменяя поведение соперника или дополняя начальные (учительские) веса с помощью новых отобранных данных;

Заключение

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

Л и т е р а т у р а

1. Петренко В.И. Классификация задач мультиагентного обучения с подкреплением // Известия Кабардино-Балкарского научного центра РАН – 2021. № 3 (101) – С.32-44.
2. David Silver, Thomas Hubert, Julian Schrittwieser, Ioannis Antonoglou, Matthew Lai, Arthur Guez, Marc Lanctot, Laurent Sifre, Dharshan Kumaran, Thore Graepel, Timothy Lillicrap, Karen Simonyan, Demis Hassabis. A general reinforcement learning algorithm that masters chess, shogi, and Go through self-play // Silver et al., Science – 2018. 362, P.1140–1144.
3. Seyed Sajad Mousavi, Michael Schukat, and Enda Howley. Deep Reinforcement Learning: An Overview // Proceedings of SAI Intelligent Systems Conference (IntelliSys) – 2016. – P.426-440.
4. Бородин Г.Д. Краткий обзор и классификация искусственных нейронных сетей // Известия ТулГУ. Технические науки - 2021. - Вып. 11 – C.45-53.
5. Судхарсан Равичандиран. Глубокое обучение с подкреплением на Python. OpenAI Gym иTensorFlow для профи. СПб.: Питер, 2019. – 251 с.