Как reinforcement learning сохраняет найденную оптимальную стратегию?

Question

[Олег Петров]

Продолжаю разбирать код программы https://github.com/Smeilz/Tic-Tac-Toe-Reinforcemen...
1)Программа симулирует 200000 партий в игру 2 оппонентов в крестики-нолики 3x3
2)Сохраняет стратегию в файл при помощи pickle
3) Можно поиграть с обученной стратегий, она загружается опять же при помощи pickle

Я вывел через print сохраняемый объект, там вывелся огромный текст

'X', '0', '0', 'X', 'X', '0'), 3): 1.0, (('X', 'X', ' ', ' ', ' ', ' ', ' ', '0', '0'), 3): 1.203194073499, (('X', 'X', ' ', ' ', ' ', ' ', ' ', '0', '0'), 4): 0.97, (('X', 'X', ' ', ' ', ' ', ' ', ' ', '0', '0'), 5): 1.0, (('X', 'X', ' ', ' ', ' ', ' ', ' ', '0', '0'), 6): 1.0, (('X', 'X', ' ', ' ', ' ', ' ', ' ', '0', '0'), 7): 1.8822040593129998, (('X', 'X', ' ', '0', 'X', ' ', ' ', '0', '0'), 3): 0.92401, (('X', 'X', ' ', '0', 'X', ' ', ' ', '0', '0'), 6): 0.43899999999999995, (('X', 'X', ' ', '0', 'X', ' ', ' ', '0', '0'), 7): 1.8999999669669685, (('X', 'X', ' ', '0', 'X', ' ', '0', '0', '0'), 3): 1.0, (('X', 'X', ' ', '0', 'X', ' ', '0', '0', '0'), 6): 1.0, (('0', ' ', '0', ' ', 'X', ' ', 'X', ' ', ' '), 2): 1.899999952809955, (('0', ' ', '0', ' ', 'X', ' ', 'X', ' ', ' '), 4): 0.707281, (('0', ' ', '0', ' ', 'X', ' ', 'X', ' ', ' '), 6): 1.6262611862579543, .............

upd: Формат сохранения такой.
[Result1 of Q-function, Situation1 on the board, Cell number where do we go this round] : [Result2 of Q-function, Situation2 on the board, Cell number where do we go this round] : etc

Подскажите, если q-learning - это по сути функция накопления полезности действий игрока, то каким образом можно воссоздать сохраненную оптимальную стратегию агента для участия в последующих партий?
С нейросетью все ясно - сохраняем веса и потом воссоздаем сеть для другого набора данных.
А как быть с результатом обучения на Q-learning. Или он сохранил всю цепочку игр для всех позиций и в итоге просто сравнивает все возможные продолжения с любого места игры?
И затем уже выбирает только то продолжение, у которого индекс полезности(функция Q) Была max?
я верно понял логику программы?

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

Answer 1

[xmoonlight]

С нейросетью все ясно - сохраняем веса и потом воссоздаем сеть для другого набора данных.
А как быть с результатом обучения на Q-learning.

учите Q-learning
Слайды

PS: Здесь понятнее код и правильнее!

Comments

[Олег Петров]

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

[xmoonlight]

Олег Петров, сохраняется (и вызов в самом низу кода файла: agent.save_v_table()), но загрузку я не вижу тут что-то.

[Олег Петров]

Кстати интересно почему считаете второй код правильнее? Более грамотно описан Q-learning? Я попробовал сыграть против противника, обученного по первому коду в крестики-нолики, реально невозможно обыграть.

[Олег Петров]

Кстати код из Гитхаба, который вы привели запустил, он реально учится в десятки раз медленнее. Может из-за записи в csv?

[Олег Петров]

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

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

[xmoonlight]

Олег Петров, простой вопрос: какие алгоритмы машинного обучения Вы уже изучали/смотрели, кроме Q-Learning?

[Олег Петров]

xmoonlight, Деревья решений, случайный лес, логистическая регрессия.

[Олег Петров]

Знаю про Xgboost, но не изучал принцип его работы.

[xmoonlight]

Олег Петров, отлично. Объясняю: каждый цикл - делаете новое "дерево". Затем "складываете" его с основным "деревом" (через слияние/наложение/merge). Если нода стала отрицательной - "отрезаем" её (и все её "ветки" отпадут сами, разумеется). Таким образом будет основное "дерево" ("дерево" знаний системы) накапливать только продуктивные цепочки действий, позволяющие максимально приблизиться к заданным целям (коэффициентам).

[Олег Петров]

xmoonlight, И это дерево знаний по сути и "сохраненяется" после окончания обучения для использования в новых партиях?

[xmoonlight]

Олег Петров, да. При принятии решения на каждом шаге одного этапа - алгоритм такой:
1. смотрим на основное дерево при полном совпадении пути/ветки(при наложении)
2. есть дочерние ветки ноды - идём по ветке с максимальным весом, нет - просто выбираем случайным образом одно из двух направлений: 50/50 и продолжаем наращивать промежуточное "дерево" (циклическое, которое новое для каждого цикла результата).
3. Делаем merge промежуточного к основному (пересчитывая коэффициенты, разумеется).
4. Оптимизируем ветки, удаляя бесполезные (ветвящиеся и промежуточные в цепочках) и увеличивая тем самым доступный объём знаний (аналог, типа дефрагментации).
5. Полученное основное "дерево" - это и будут обновлённые знания.

Answer 2

[ivodopyanov]

Похоже, что массив из 9 символов 'X', 'O', ' ' - это текущее состояние игры; целое число после него - это номер клетки, куда делаем ход; вещественное число - полезность хода.
Да, при прогоне для каждой текущей позиции получаем пары <возможный ход>-<его полезность>, и берем максимальный

Comments

[Олег Петров]

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

[Олег Петров]

Та же Flappy bird как-то сохраняет найденное решение или все же там демонстрируется только процесс обучения, но без возможности применить на практике?

[ivodopyanov]

1. "Сохранить решение" - это не тот термин. "Сохранить" - это обычно значит скопировать на жесткий диск.
2. Q-learning выучивает таблицу [S,A] -> R (S - состояние игры, A - действие, R - награда за это действие). Если состояний много (как в шахматах), то таблица действительно получается просто огромной. Решение - давайте вместо таблицы будем хранить какую-то функцию f(S,A) = R, которая будет эту таблицу аппроксимировать. Как подобрать нужную функцию? В этом помогут нейронные сети и тот факт, что они являются универсальным аппроксиматором, то есть при должном количестве весов могут аппроксимировать любую функцию.
3. Из-за большого количества состояний возникает еще одна проблема - по какой стратегии выбирать ходы при обучении? Иначе модель легко может начать активно изучать варианты в каком-то бесполезном направлении. Например, дебюты в шахматах, когда мы крайней пешкой ходим.

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

[ivodopyanov]

Олег Петров, эта программа обучает при помощи генетических алгоритмов, а не Q-Learning.

[Олег Петров]

ivodopyanov, Спасибо за ответы, про "сохранение решений" исчерпывающе объяснили.

[Олег Петров]

ivodopyanov, Тогда возникает вопрос есть ли реализация генетического алгоритма для крестиков ноликов на том же Python?
Было бы интересно сравнить эффективность. Например, чтобы программа, обученная Qlearning сыграла против программы на генетических алгоритмах. Ясное дело, что при игре 3x3 там всегда должна быть ничья, но можно ведь увеличить размеры полей.

[Олег Петров]

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

[ivodopyanov]

Олег Петров, "как сохранить" - это вопрос конкретной библиотеки и конкретного языка. Можно как бинарный файл, можно как текстовый, можно как xml, вариантов куча, и это чисто прикладной вопрос.

Q-learning, генетические алгоритмы, алгоритм обратного распространения ошибки - это общие алгоритмы для машинного обучения, и выучить они в теории могут всё, что угодно. Что будет лучше в конкретном случае - это часто вопрос ресурсов, которые имеются для обучения; объема доступных данных; наличия прямых рук и мозгов у разработчиков. AlphaZero от DeepMind играет в шахматы значительно лучше предыдущей топового ИИ Stockfish, но там для обучения использовали вычислительные мощности гугла, которые пока что недоступны простым смертным.

Также часто вполне может быть, что рукописный алгоритм без всякого машинного обучения может работать не хуже, чем ИИ с машинным обучением. Для крестиков-ноликов, например, такой написать довольно просто. Для Flappy Bird тоже понятно как.

[Олег Петров]

Кстати я сделал любопытное открытие.
В том же Github есть реализация другой игры Asteroid на том же алгоритме.
В результате там даже за 200 итераций алгоритм ничему не может научиться и постоянно проигрывает.

Так вот интересный факт.
Игру Flappy bird поставили 3459 звезд и 401 fork, за то, что алгоритм так быстро научился играть в эту игру. Хотя по факту - это просто подстройка под существующий простой механизм генерации препятствий. Усложни игру и алгоритм программы уже будет бессилен.
А к игре https://github.com/xviniette/AsteroidsLearning всего 35 звезд и 17 fork, так как алгоритм ее не осилил. А по факту причина в большом количестве одновременных препятствий, под которые не подстроиться из-за бесчисленного числа сочетаний.
Это называется human result oriented. =)

[Олег Петров]

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

[Олег Петров]

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