Как использовать деревья MinMax с Q-Learning?

Question

Как использовать деревья MinMax с Q-Learning?

Я хочу реализовать агент Q-Learning connect 4 и слышал, что добавление в него деревьев MinMax помогает.

Answer 1

Q-learning - это Алгоритм временного различия . Для каждого возможного состояния (доска) он изучает значение доступных действий (ходов). Однако он не подходит для использования с Minimax , поскольку алгоритм Minimax нуждается в функции оценки, которая возвращает значение позиции, а не значение действия в этой позиции.

Тем не менее, методы временной разности могут быть использованы для изучения такой функции оценки. В частности, Джеральд Тесауро использовал алгоритм TD (λ) («TD lambda»), чтобы создать TD-Gammon , конкурентоспособную для человека программу игры в нарды. Он написал статью, описывающую подход, который вы можете найти здесь .

TD (λ) был позже расширен до TDLeaf (λ), специально для лучшей обработки минимаксных поисков. TDLeaf (λ) использовался, например, в шахматной программе KnightCap. Вы можете прочитать о TDLeaf в этой статье .

Answer 2

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