Огромное количество состояний в расчете q-обучения

Question

Я реализовал игру 3x3 OX с помощью q-learning (она отлично работает в AI против AI и AI против человека), но я не могу сделать еще один шаг к игре 4x4 OX, так как она пожирает всю память моего компьютера иcrash.

Вот моя текущая проблема: Нарушение доступа в огромном массиве?

В моем понимании, игра OX 3x3 имеет всего 3 (пробел, белый, черный) ^ 9 = 19683 возможных состояний.(тот же самый шаблон различный угол все еще считается)

Для игры 4x4 OX общее состояние будет 3 ^ 16 = 43 046 721

Для обычной игры в го, доска 15x15, общее состояние будет3 ^ 225 ~ 2,5 x 10 ^ 107

Q1.Я хочу знать, мой расчет правильный или нет.(для игры 4x4 OX мне нужен массив 3 ^ 16?)

Q2.Так как мне нужно вычислить каждое значение Q (для каждого состояния, каждого действия), мне нужно такое большое количество массивов, это ожидается?Есть ли способ избежать этого?

Answer 1

Рассмотрим симметрии.Фактическое количество возможных конфигураций намного меньше, чем 9 ^ 3 на плате 3x3.Например, в основном есть только 3 различные конфигурации с одним x на плате.

Вращения

Есть много конфигураций платы, которые должны все привести к одному и тому жеРешение принято вашим ИИ, потому что они одинаковы по модулю симметрии.Например:

x - -    - - x    - - -    - - -  
- - -    - - -    - - -    - - - 
- - -    - - -    - - x    x - - 

Это все одинаковые конфигурации.Если вы относитесь к ним индивидуально, вы тратите время на тренировки.

Зеркальное отображение

Существует не только симметрия вращения, но вы также можете отражать доску, не изменяя фактическую ситуацию.Следующие элементы в основном одинаковы:

0 - x    x - 0    - - -    - - -  
- - -    - - -    - - -    - - - 
- - -    - - -    0 - x    x - 0

Исключить конфигурации "не может быть"

Далее следует учесть, что игра заканчивается, когда один игрок выигрывает.Например, у вас есть 3 ^ 3 конфигурации, которые выглядят так:

x 0 ?
x 0 ?    // cannot happen
x 0 ?

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

Исключить больше "не может произойти"

Более того, вы значительно переоцениваете размер конфигурациипробел с 9^3, потому что игроки ходят по очереди.Например, вы не можете получить конфигурацию, подобную этой:

x x -
x - -    // cannot happen
- - - 

Как получить все необходимые конфигурации?

В двух словах, это то, как я бы подошелпроблема:

• определить operator< для вашей платы
• используя отношение <, вы можете выбрать одного представителя для каждого набора «похожих» конфигураций (например, тот, которыйна < больше, чем все остальные в наборе)
• написать функцию, которая для заданной конфигурации возвращает вам репрезентативную конфигурацию
• перебор всех возможных ходов (только возможные ходы!совершать поочередные ходы игроков, пока игра не будет выигранаПри этом вы
  • рассчитываете репрезентативную для каждой встречающейся конфигурации
  • помните все репрезентативные конфигурации (обратите внимание, что они появляются несколько раз из-за симметрии)

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

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

Answer 2

Если вы пропустите повторное изобретение колеса, вот что было сделано для решения этой проблемы:

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

https://arxiv.org/pdf/1312.5602v1.pdf

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

https://neuro.cs.ut.ee/demystifying-deep-reinforcement-learning/

Answer 3

У меня есть схема перечисления, но для нее требуется массив целых чисел. Если вы можете сжать массив целых чисел до одного значения Q (и обратно), то это может сработать.

Сначала идет N, количество фигур на доске.

Затем идет массив элементов ceil (N / 2), X штук. Каждое число - это количество пустых допустимых пробелов из предыдущей фигуры Х (или начала доски). ВАЖНО: пробел недействителен, если это приведет к окончанию игры. Здесь правило 5 в конце строки помогает нам уменьшить домен.

Затем идет массив напольных (N / 2) предметов, O штук. Применяется та же логика, что и для массива X.

Итак, для этой доски и 3-х частей правила:

XX.
X.O
..O

у нас есть следующий массив:

N: 5
X: 0 (с начала доски), 0 (из предыдущего X), 0 (верхний правый угол недействителен для X, потому что это может закончить игру)
O: 2 (с начала доски, минус все предыдущие X), 2 (с предыдущего O)

и это массив [5, 0, 0, 0, 2, 2]. Учитывая этот массив, мы можем воссоздать доску выше. Появление небольших чисел более вероятно, чем появление больших чисел. В обычной игре с доской 19x19 фигуры по большей части будут сгруппированы, поэтому в следующей строке будет много нулей, единиц, двойок, разделенных случайным «большим» числом.

Теперь вам нужно сжать этот массив, используя тот факт, что маленькие числа встречаются чаще, чем большие. Алгоритм сжатия общего назначения может помочь, но некоторые специализированные могут помочь больше.

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

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

Кроме того, нам на самом деле не нужно первое число в массиве, N. Длина массива дает эту информацию.