Машинное обучение 2012

Лектор - Николенко С. И.

Домашние задания

1. Крестики-нолики.

Требуется написать программу, которая обучается играть за первого игрока (крестики) против фиксированной стратегии второго игрока (нолики). В случае ничейного результата партия считается проигранной крестиками. В качестве стратегии второго использовать следующую: если нолики могут своим ходом составить ряд из трех нолей, то они делают этот ход. Если такого хода нет, то ход выбирается случайно равновероятно из всех незанятых клеток. Попробовать две стратегии обучения: TD (когда после хода ценность позиции сдвигается в сторону ценности новой позиции) и стратегию, которая премирует все позиции которые встретились в партии, если крестики победили и депремирует, если проиграли. В качестве стратегии выбора хода крестиков реализовать \epsilon-жадную и температурную. Программа должна, непрерывно обучаясь, провести 100 раз по 1000 партий и для каждой тысячи вывести число побед крестиков в консоль или в файл. Задача зачитывается при наличии кода и четырёх файлов (для всех сочетаний стратегии поведения и стратегии обучения), показывающих динамику числа побед.

2. Про монетку.

Рассмотрим следующую игру: У вас есть сумма от 1 до 99 монет, вы делаете ставку и подбрасываете монетку. Если выпал "орёл", то ставка удваивается, иначе теряется. Цель игры набрать ровно 100 монет. Зафиксируем базовую стратегию: Если сумма меньше или равна 50 монетам, то ставим всё, иначе недостающую до 100 сумму. Пользуясь данной стратегией, проэмулировать по 100 игр из каждого начального состояния. По результатам эмуляции для каждого положения вычислить "взвешенный успех" --- долю игр, прошедших через это состояние, закончившихся успехом. По результатам вычисления выбрать новую стратегию ставок --- жадную, по отношению к новым весам позиций. Повторить такую процедуру до схождения стратегии (до момента, когда ставки перестанут меняться). Провести такое моделирование для разной вероятности выпадения орла --- 0.4, 0.5, 0.6 и вывести получившиеся оптимальные стратегии. Задача зачитывается при наличии кода и трёх файлов (для трёх вероятностей выпадения орла), содержащих полученную стратегию в виде пар чисел "состояние"--"ставка".

3. Блек-Джек. Задача научиться играть в Блек-Джек против диллера с фиксированной стратегией. Правила игры: игроку и диллеру сдается по две карты. Если у игрока 21 очко при сдаче, то диллер открывает свою руку и они сравниваются. Если этого не произошло, то игра продолжается по правилам описанным далее. Игрок видит свои карты и одну карту диллера. Каждый ход игрок выбирает одну из двух возможностей: взять еще карту или остановиться. Ходы игрока продолжаются до тех пор пока он не выберет "остановиться" или не наберет больше 21 очка. Если игрок набрал больше 21, то он считается проигравшим. Если игрок остановился, то диллер начинает набирать карты. Стратегия 1: Диллер набирает пока у него не будет 17 или больше и останавливается. Стратегия 2: Диллер набирает пока у него не будет столько же сколько у игрока и останавливается. Карты имеют следующую стоимость в очках: Туз --- 1 или 11 по выбору игрока, остальные картинки 10, остальные карты по своему значению. Предполагая, что каждая следующая карта достается из новой колоды, обучить стратегию поведения игрока. Начав со стратегии останавливаться на 20 и 21 проэмулировать ряд партий и построить вес успешности позиций, считая, что победа дает одно очко, поражение --- минус одно, ничья --- ноль. В качестве новой стратегии взять жадную стратегию при полученных весах. Повторять до сходимости. Позицией считать сумму карт в руке, открытую карту (ее стоимость) диллера и факт наличия в руке туза, которого вы считаете за 11. Задача зачитывается при наличии кода и описания полученных стратегий игрока, для двух стратегий диллера. Стратегия игрока описывается, как решения игрока (взять или остановится) при заданном числе очков в руке, открытой карты диллера и наличия в руке туза за 11 очков.