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

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

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

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

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

Про монетку

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

Блекджек

Задача: научиться играть в блекджек против дилера с фиксированной стратегией.

Правила игры: игроку и дилеру сдаётся по две карты. Если у игрока 21 очко при сдаче, то дилер открывает свою руку и они сравниваются. Если этого не произошло, то игра продолжается по правилам, описанным далее. Игрок видит свои карты и одну карту дилера. Каждый ход игрок выбирает одну из двух возможностей: взять еще карту или остановиться. Ходы игрока продолжаются до тех пор, пока он не выберет "остановиться" или не наберёт больше 21 очка. Карты имеют следующую стоимость в очках: туз --- 1 или 11 по выбору игрока, остальные картинки 10, остальные карты по своему значению. Если игрок набрал больше 21, то он считается проигравшим. Если игрок остановился, то дилер начинает набирать карты.

Стратегия 1: Дилер набирает, пока у него не будет 17 или больше, и останавливается.

Стратегия 2: Дилер набирает, пока у него не будет столько же, сколько у игрока, и останавливается.

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

OCR

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

1. Построить сеть (HMM или любую другую модель) для которой будет решаться задача MAP (поиск наиболее вероятного набора значений переменных при заданных свидетельствах).

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

3. Реализовать распознование отдельного символа (на основе нейронной сети или как вам будет угодно). Базу для обучения можно взять тут: http://www.ee.surrey.ac.uk/CVSSP/demos/chars74k/

4. Реализовать разбиение картинки на отдельные слова и символы.

5. Объединить все вышеописанное.