Создание искусственного интеллекта для игры в простую карточную игру
Как-то раз играл я с друзьями в простую карточную игру под названием «Тайное послание». Возник вопрос - а как считать вероятности и как построит оптимальную стратегию? Для получения ответов на мои вопросы и дается данная тема.
Особенность: тема дается на год (на два семестра), с зачетом в каждый семестр, для 1 и 2 курса задания отличаются. Задания могут варьироваться по согласованию с преподавателем.
Задания для 1 курса¶
Предполагаемые знания¶
Реализацию лучше всего делать на C/С++. На Python можно, но будет медленнее. Литература по теорверу и моделированию приведена ниже, но лучше уточнить у руководителя.
Первый семестр¶
Придумать и зафиксировать какую-нибудь «разумную» (и стохастическую) стратегию для игры в «Тайное послание», реализовать её на компьютере, а затем научиться вычислять вероятности с помощью проведения большого числа игр и простого подсчёта благоприятных и неблагоприятных результатов.
Второй семестр¶
Придумать еще несколько разумных стратегий, реализовать и сравнить их. Также надо реализовать другую стратегию, неразумную, и показать экспериментально, что она хуже. Доказать экспериментально, что вероятности событий типа «два барона в руке» являются условными, взяв одно и то же событие и посчитав его вероятность при разных стратегиях.
Задания для 2 курса¶
Предполагаемые знания¶
Моделирование игры лучше всего делать на C/С++. На Python тоже можно, но будет медленнее. Машинное обучение по сформированным признакам - на Python. Литература, детали и подсказки - у руководителя.
Первый семестр¶
Придумать и зафиксировать какую-нибудь «разумную» (и стохастическую) стратегию для игры в «Тайное послание», реализовать её на компьютере, а затем научиться вычислять вероятности с помощью проведения большого числа игр и простого подсчёта благоприятных и неблагоприятных результатов. Также надо реализовать другую стратегию, можно неразумную, и доказать экспериментально, что вероятности событий типа «два барона в руке» являются условными, взяв одно и то же событие и посчитав его вероятность при разных стратегиях.
Второй семестр¶
Но по какому принципу мы выбрали стратегию? Реализовали что-то «разумное»? А лучший ли это вариант? Хотелось бы что-то не просто разумное, но что-то лучшее, что-то в некотором смысле «оптимальное».
Поэтому задача на второй семестр: разработать «оптимальную» стратегию для игры в тайное послание. Как это можно сделать? Например так: за отправную точку взять «разумную» стратегию, затем заставить компьютер играть с самим собой и сформировать набор данных из партий, затем к полученному набору из партий применить машинное обучение для того, чтобы автоматически выделить ходы, которые с большей вероятностью приводят к победе. Далее можно будет сформировать новый набор данных из партий уже на основе стратегии с машинным обучением, а потом снова воспользоваться машинным обучением и подкорректировать стратегию… Думаю, что вполне можно будет обойтись классическим машинным обучением, но если выполняющий курсовую воспользуется обучением с подкреплением и объяснит его научному руководителю, научный руководитель не будет против.
В качестве конечного продукта хотелось бы получить искусственный интеллект, который оценивает каждый свой ход с точки зрения того, какая будет у него вероятность победить, если он походит именно вот так, и который выбирает наилучший вариант.
Описание игры¶
Суть игры такова. Есть 16 карт с разными персонажами: 5 стражниц, 2 священника, 2 барона, 2 служанки, 2 принца, 1 король, 1 графиня и 1 принцесса. Персонажи имеют вес от 1 до 8, а также некоторую способность, написанную на карте. В игру могут играть от 2х до 4х игроков. Игра состоит из нескольких раундов. Каждый игрок в начале раунда получает в закрытую на руку случайную карту (каждый игрок свою карту знает, но не знает изначально карты других игроков). Ещё одна карта в закрытую исключается из раунда для пущей стохастичности (исключенную карту не знает никто). Остальные карты образуют колоду. Колода перемешивается. Игроки ходят по очереди. В начале своего хода игрок берет в руку карту из колоды и разыгрывает одну из двух имеющихся на руках карт. Разыгранная карта отправляется в личный сброс игрока. Разыграв стражницу нужно попытаться угадать карту другого игрока и тем самым вывести его из раунда. Разыгранный священник позволяет посмотреть чужую карту не показывая её другим игрокам. Барон - сравниться в закрытую с другим игроком и вывести его из раунда, если вес карты этого игрока меньше, чем вес второй карты в руке разыгрывающего. Служанка защищает разыгрывающего от действий других игроков до следующего хода разыгрывающего. Принц позволяет заставить любого игрока сбросить карту и взять новую из колоды. Принца можно сыграть на себя. Если колода закончилась, то берется исключенная из раунда карта. Король позволяет поменяться картами с другим игроком. Графиню нужно сбросить, если она оказывается в паре вместе с принцем или королем. Графиню также можно сбросить просто так. У принцессы нет особого свойства, но тот, кто сбросит принцессу — выйдет из раунда. В раунде побеждает последний не выведенный из раунда игрок. Раунд также считается завершенным, если в колоде не осталось карт. В этом случае в раунде побеждает игрок, на руках у которого оказалась карта с наибольшим весом. Если таковых несколько, то учитывается сумма весов в личных сбросах игроков. Если и эта сумма совпала, то смотрят на порядок карт в личных сбросах. Карты с большим весом, которые попали в сброс позже, котируются выше. В игре побеждает тот, кто выиграл больше всего раундов.
Во время игры у меня возник вопрос: а можно ли посчитать вероятность того, что на руке у меня окажется, скажем, два барона? Ответ на этот вопрос, кажется, не так уж и прост: эта вероятность зависит от действий игроков в игре. Допустим, я получил в руку барона. Я ведь могу попридержать его и подождать другого барона, если не вижу его уже разыгранным на поле другим игроком (или не знаю, что у кого-то в закрытой руке есть барон, выяснив это с помощью священника). Это, если верить интуиции, должно повысить шанс получить на руке двух баронов. С другой стороны, я ведь могу разыгрывать барона сразу же, как только он попадает мне в руку. Даже если у меня на руке стражница. Такое поведение, если опять-таки интуиция меня не подводит, уменьшает вероятность получить во время раунда двух баронов в руке. Короче, обозначенная выше вероятность выглядит как условная и, вроде как, зависит как от моей стратегии, так и от стратегий других игроков. Для начала, я бы хотел уметь считать такого рода вероятности, а потом, на втором курсе, замахнуться и на создание ИИ в игре.
Литература¶
Общая литература по теории вероятностей и методу Монте Карло:
Ширяев А.Н., Вероятность-1, МЦНМО, 2011, 552 стр.
Reuven Y. Rubinstein, Dirk P. Kroese, Simulation and the Monte Carlo Method, Third Edition, Wiley Series in Probability and Statistics, 2016
Баллы¶
1 курс – 50+50 по семестрам, 2 курс – 50+50 по семестрам.
Руководитель¶
Гученко Роман Александрович