Автоматизированная система принятия решений для участника многоагентных взаимодействий в условиях неполноты информации - korshu.ru o_O
Главная
Поиск по ключевым словам:
страница 1
Похожие работы
Название работы Кол-во страниц Размер
Элементы управления ит 14 72 3620.47kb.
Памятк а для лиц, участвующих в Государственной программе по оказанию... 1 27.66kb.
Автоматизированная информационная система «государственный лесной... 12 1355.71kb.
Система электронного документооборота «счета-фактуры» 1 193.14kb.
Система интернет-банкинга для клиентов банков 12 517.05kb.
Автоматизированная обучающая система 42 1787.9kb.
Программа «Служба психолого-педагогического сопровождения» 1 190.84kb.
1. Запустить графический редактор (paint, PhotoShop, CorelDraw) 1 105.52kb.
Отчет научно-исследовательской работы по теме: Способы повышения... 3 830.13kb.
Колобова С. В. Трудовое право России 27 3472kb.
Тезисы лекций и задания для практических занятий участника курсов... 1 546.74kb.
Анализ работы муниципального бюджетного общеобразовательного учреждения... 20 2868.39kb.
Инструкция по работе с сервисом «sms-платеж» 1 218.94kb.

Автоматизированная система принятия решений для участника многоагентных взаимодействий - страница №1/1




Правительство Российской Федерации
Федеральное государственное автономное образовательное учреждение

высшего профессионального образования
«Национальный исследовательский университет
«Высшая школа экономики»

Факультет Бизнес-информатика

Отделение Программной инженерии

Кафедра Управление разработкой программного обеспечения

ВЫПУСКНАЯ КВАЛИФИКАЦИОННАЯ РАБОТА
На тему: Автоматизированная система принятия решений для участника многоагентных взаимодействий в условиях неполноты информации


Студент группы №472ПИ

______________ / Москалев П.А. /

« 29 » мая 2013 г.


Руководитель ВКР

доцент каф. УРПО, к.т.н.

_________________ / Брейман А.Д. /

« 29 » мая 2013 г.




Москва, 2013



Аннотация

В данной работе рассматривается разработка автоматизированной системы, способной принимать решения для участника игры покер Техасский холдем. Алгоритм принятия решений данной системой основывается сразу на нескольких подходах: игра на префлопе – на основе формулы Билла Чена, оценка текущей силы руки – на основе метод описанного Дарсом Биллингсом и Джонатаном Шаффером, вычисление вероятности аутов – используя метод Рой Раундера. Также в данной работе рассматриваются основные способы разработки систем подобного рода, рассмотрены наиболее интересные аналоги. В конце работы приводятся полученные результаты и указываются направления для дальнейшего развития данной темы.



Содержание

Введение…………………………………………………………………………

4

Глава 1. Основные понятия и обзор имеющихся аналогов………………

8

1.1. Правила Техасского холдема………………………………………….

8

1.2. Обзор имеющихся аналогов…………………………………………...

11

1.2.1. GS1…………………………………………………………………..

13

1.2.2. SARTRE…………………………………………………………….

14

Глава 2. Общий алгоритм принятия решений……………………………..

18

2.1. Игра на префлопе……………………………………………………….

18

2.2. Вычисление текущей силы руки……………………………………...

20

2.3. Вычисление аутов………………………………………………………

21

2.4. Изменение стиля игры…………………………………………………

22

Глава 3. Среда реализации и результаты работы………………………….

25

3.1. Среда реализации приложения………………………………………..

25

3.2. Результаты работы приложения……………………………………...

28

Заключение……………………………………………………………………...

30

Литература………………………………………………………………………

31

Введение

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



  1. Модуль, получающий необходимую информацию из покерного клиента;

  2. Модуль, принимающий решения.

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

Первые покерные роботы появились в 80-х годах прошлого века. В 1984 году, известный покерный игрок Майк Каро2 разработал первую подобную систему под названием «Орак». Данная программа в 1985 году показала достаточно хорошие результаты при игре с одними из лучших игроков того времени. Покерные роботы стали достаточно популярны в связи с огромным число людей, начавших играть в покер в интернете. Однако не стоит забывать об одной очень примечательной вещи – покер является игрой с неполной информацией. Вы не знаете карты противника, противник не знает ваших карт. Кроме того, никто не знает какие карты выйдут следующими на стол, поскольку они достаются из колоды случайным образом. Более того, покер является игрой, с огромным числом возможных состояний, который не то что человеку, а компьютеру обработать достаточно непросто.

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

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



В связи с этим разработка данной системы предполагает выполнение следующих задач:

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

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

  3. Интерпретация данных. После получения данных из клиента «в сыром виде» необходимо их каким-то образом преобразовать, для того чтобы дальше их можно было анализировать и работать с ними. Данная задача является одной из ключевых, поскольку точность полученных данных напрямую влияет на точность принимаемых решений, и даже малейшая ошибка, может привести к неправильной работе всей системы.

  4. Произведение необходимых вычислений для дальнейшего принятия решений. Этот пункт является основной научной составляющей данной работы. Сегодня существует несколько подходов и способов к оценке шансов игрока и силы комбинации. В данной работе планируется объединить некоторые из этих подходов и оценить их эффективность при игре с реальными игроками онлайн.

  5. Принятие решения на основе полученных данных. Принятие решений системой будет осуществляться на основе данных полученных с игрового стола и конкретными значениями, необходимыми для принятия решения.

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

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

Глава 1. Основные понятия и обзор имеющихся аналогов

1.1. Правила Техасского холдема [1]

Блайнды. В Техасском холдеме баттоном (от англ. «button» - «кнопка») отмечается номинальный дилер раздачи. Перед началом раздачи игрок, следующий по часовой стрелке после баттона, ставит малый блайнд – первую обязательную ставку. Следующий игрок ставит большой блайнд, который обычно в 2 раза больше малого блайнда, но зависит от ставок и структуры блайндов каждой конкретной игры.

В некоторых случаях игроки также должны поставить «анте» (еще один вид обязательной ставки, которая обычно меньше обоих блайндов и ставится всеми игроками).

После этого каждый игрок получает по две закрытых карты. Игроки делают свои ходы в порядке очереди по часовой стрелке, начиная с игрока в позиции «под прицелом» (англ. under the gun). Это позиция игрока, сидящего по часовой стрелке от большого блайнда.

Действия игрока. В холдеме, как и в большинстве других разновидностей покера, игрок может сделать «фолд», «бет», «колл» или «рейз». Доступность тех или иных действий зависит от действий предыдущих игроков. У любого игрока всегда есть возможность сделать фолд, то есть сбросить свои карты и отказаться от борьбы за банк. Если до Вас никто не сделал бет (ставку), то Вы можете сделать либо чек (отказаться от ставки, но не сбросить карты), либо ставку. Если один из игроков сделал ставку, то последующие игроки могут сделать фолд, колл или рейз. «Сделать колл» означает добавить в банк количество фишек, необходимое для уравнивания ставки предыдущего игрока. «Сделать рейз» означает добавить в банк количество фишек, превышающее ставку предыдущего игрока.

Префлоп. После того, как игроки получили свои закрытые карты, каждый из них может продолжить играть, сделав колл или рейз большого блайнда. Первым ходит игрок слева от большого блайнда. Он может сделать фолд, колл или рейз. Например, если большой блайнд равен $2, то колл подразумевает добавление в банк $2, а рейз – не менее $4. После этого ходит следующий игрок по часовой стрелке.

Каждый раунд торгов продолжается пока все активные игроки (которые не сделали фолд) не сделают равные ставки в банк.



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

Терн. После завершения торгов на флопе лицом вверх сдается «терн». Терн – это четвертая общая карта в холдеме. Происходит еще один раунд торгов, начиная с активного игрока, находящегося по часовой стрелке от баттона.

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

Вскрытие карт. Если после завершения последнего раунда торгов в раздаче осталось несколько активных игроков, то первым карты открывает игрок, который последним сделал бет или рейз. Если же в последнем раунде не было ставок, то первым открывает карты активный игрок, сидящий по часовой стрелке от баттона. Банк забирает игрок с лучшей комбинацией из пяти карт. Если несколько игроков собрали равносильные комбинации, то банк делится между ними поровну. В холдеме ни одна из мастей не имеет преимущества над другими.

После передачи банка в руки игрока, победившего в раздаче, начинается следующая раздача. Баттон перемещается к следующему по часовой стрелке игроку, ставятся блайнды и анте и сдаются новые закрытые карты.



Комбинации. На рисунке 1 приведен список возможных карточных комбинаций, отсортированный по старшинству (более сильные комбинации находятся выше).

Рис. 1. Комбинации в покере

Также, следует отметить, что существует несколько вариантов игры в Техасский холдем. Различают игру с фиксированными лимитами и без лимитов. В игре с фиксированными лимитами размеры ставок и повышений всегда строго определены. На первых двух стадиях, префлопе и флопе, размеры ставок и повышений равны размеру большой обязательной ставки, на последних двух – в два раза больше размера большой обязательной ставки. В игре без лимита ставка или повышение могут иметь любой размер, не меньший размера предыдущей ставки.
1.2. Обзор имеющихся аналогов

В наши дни тема большое число людей всерьез занимаются разработкой покерных роботов, но каждый это делает для своих собственных целей. Однако разработка подобного программного обеспечения имеет несколько серьезных проблем, которые необходимо решить. Одна из них – слишком большое количество вариантов состояний игры. Даже для самого «простого» Техасского холдема существует ровно 319,365,922,522,608 игровых состояний, в которых нужно принимать решение. В то же время, в этой разновидности покера всего 6378 различных паттернов ставок и все богатство игровых состояний обусловлено именно карточными комбинациями. Уже исходя из этих двух фактов, можно предположить, что даже самая современная техника порой не в состоянии просчитать все возможные варианты в кратчайшие сроки. На помощь приходят методы упрощения исходной игры, которые объединяют близкие в стратегическом плане состояния этой игры в неразличимые состояния новой игры, называемой абстракцией. Для покера можно выделить два класса проблем, решаемых переходом к абстракции [2]:



  1. Проблема ставок в безлимитных играх.

  2. Проблема представления рук игроков.

Особо остро проблема ставок стоит для безлимитных видов покера. Самым популярным способом в решении данной проблемы является дискретизация ставок, когда все ставки разбиваются на некие диапазоны, и все дальнейшие действия проводятся со ставками, принадлежащими конкретному диапазону.

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


Таблица 1

Количество возможных комбинаций карт

Круг торговли

Всего для двух игроков

Всего для одного игрока

Неэквивалентные для одного игрока

Префлоп

1,624,350

1,326

169

Флоп

28,094,757,600

25,989,600

1,286,792

Терн

1,264,264,092,000

1,221,511,200

55,190,538

Ривер

55,627,620,048,000

56,189,515,200

2,428,287,420

В первой колонке представлены варианты раздач карманных карт обеим игрокам в сочетании с общими картами на доске. Во второй колонке содержится та же информация, но для одного игрока, т.е. для сочетаний одной пары карманных карт и общих карт. И, наконец, последний столбец содержит в себе количество неэквивалентных классов карточных комбинаций для одного игрока. Эквивалентными комбинациями называются такие наборы карточных комбинаций, в которых заменой мастей можно получить любую другую комбинацию из этого же набора. Совершенно очевидно, что эквивалентные комбинации содержат в себе одну и ту же стратегическую информацию [2].

Исходя из перечисленных выше факторов, становится понятно, что написание умного покерного робота, является достаточно непростой задачей. В наши дни компьютерный покер – это прежде всего игра абстракций. И тот робот, чья абстракция качественнее и, что очень важно, меньше – тот и побеждает. Стратегия игры может быть построена, используя самые разные методы и подходы. Рассмотрим наиболее интересные имеющиеся аналоги.
1.2.1. GS1

GS1 агент использует теорию игр для игры в хедз-ап3. Покер – игра с достаточно враждебной средой, где целью каждого игрока является максимизация его прибыли. Теория игр представляет собой основу для объяснения рационального поведения в таких условиях. Разработчики GS1 попытались применить методы теории игр к реальной игре с неполной информацией. В отличие от своих предшественников, которые использовали теорию игр, GS1 требует очень мало конкретных знаний, вместо этого он анализирует дерево игры и определяет лучшие абстракции.

GS1 использует алгоритм «сжатия игры» [3]. Данные алгоритм получая на входе некое описание игры, на выходе проектирует абстракцию для этой игры, по которой в дальнейшем принимаются равновесные решения. Грубость абстракции зависит от порогового параметра. В первом раунде торговли есть 1326 (С252) различных возможных рук. В то же время есть только 169 стратегически разных рук, так как большая часть находится в одном классе эквивалентности. При оценке рук для следующего раунда используется уже пороговый параметр и стратегические классы уменьшаются до 2465. Оценка руки состоящей из 7 карт вычисляется заранее и хранится в базе данных под названием которая имеет 133 784 560 (С752) записей и используется во многих местах алгоритма. Еще одна база данных хранит ожидаемое количество побед и поражений (при условии нормального распределения) для рук из пяти карт 25989600 (С252 * С350) содержащая карты на флопе и на руках. Эта база используется для стратегического сравнения двух рук, похожих друг на друга.

GS1 тестировался на играх против Sparbot4, алгоритм принятия решений которого такжы был основан на теории игр. Особенность Sparbot является то, что все вычисления карт на руках протекают заранее и карты на префлопе никогда не сбрасываются. В результате после сыгранных 10000 раздач GS1 в среднем выигрывал 0.07 больших блайндов за раздачу.

Также оппонентом GS1 был и другой робот – Vexbot, разработанный также исследовательской группой Университета Альберта. Отличительной особенностью этого агента было то, что он использовал дерево игры для поиска оптимального решения. Также он мог подстраиваться под различных соперников, моделируя их поведение (например того же GS1), и опираясь на это, улучшать свою стратегию. После сыгранных 5000 раздач, матч завершился в ничью. На рисунке 2 приведены результаты обоих тестирований.

Рис. 2. Результаты тестирований GS1 против Sparbot и Vexbot [3]


1.2.2. SARTRE

SARTRE агент основан на использовании памяти для принятия решений в хедз-ап играх [3]. Этот робот использует историю рук, сыгранных предыдущими игроками для принятия собственных решений, вместо использования системы, принимающий решения относительно равновесных стратегий. Она использует историю раздач, сыгранную сильными игроками, для обучения и принятия дальнейших решений. База знаний этого агента основана на предыдущих играх AAAI CPC5. В 2008 робот Университета Альберты Hyperborean выиграл эти соревнования. База данных SARTRE была построена как раз на истории рук агента Hyperborean.

Каждый раунд торговли этого клиента представляется как путь в дереве, которые проверяет все возможные комбинации до текущего узла. Представляя два различных дерева, автор сделал попытку представить их разницу и объяснить свой выбор одного из двух путей. На рисунке 3 представлено это дерево, на котором «с» означает call, «f» - fold, and «r» - raise.

Рис. 3. Дерево последовательности действий [3]


Возможные комбинации рук данного агента разбиты на 10 возможных категории, а именно: старшая карта, пара, две пары, тройка, стрит, флеш, фулл-хаус, каре, стирт флеш, роял флеш. После того как на столе появляются первые три карты, данный агент уже может сформировать свою руку и определить ее силу. После терна и ривера данная рука может быть улучшена, так как заранее не было известно какие карты выйдут на стол. Также данный робот в процессе игры различает такие комбинации как стирт и флеш на предмет их старшинства. Например, если получился флеш, и туз, который также участвует в этой комбинации находится не на столе, а у вас на руках, то система также это определяет. Это позволяет ей делать выводы о том, что у вас самый старший флеш из возможных и наоборот.

База знаний SARTRE основана на играх проведенных на CPC роботом Hyperborean. После каждой сыгранной руки, информация о ней добавлялась в базу SARTRE. Всего в данной базе накопилось около миллиона всевозможных случаев, которые включали 201335 различных вариантов префлопа, 300577 флопа, 281559 терна и 216597 ривера. Во время игры, когда ход переходил в агенту SARTRE, он обращался к своей базе знаний, и на их основе выбирал наиболее похожие на текущую ситуацию. После чего строилось дерево вероятностей, такое как на рисунке 3, и SARTRE принимал решение, основываясь на вероятностях в этом дереве.

Для тестирования данного агента, он участвовал в играх против робота FellOmen26 и BluffBot7. Всего было проведено 6 игр, каждая из которых состояла из 6000 раздач против FellOmen2. Каждая такая игра, состояла из 3000 раздач, в которых роботам выдавались определенные карты, для снижения элемента случайности. После 3000 раздач, память обоих роботов очищалась, и следующие 3000 раундов, им выдавались на руки карты, другого робота. Таким образом, после сыгранных 36000 раздач SARTRE в среднем проигрывал 2.92 больших блайндов каждые 100 раздач. Как уже было отмечено, агент SARTRE играл по истории раздач робота Hyperborean, который в свою очередь выиграл матч против FellOmen2. Разработчики, говоря о поражении SARTRE против FellOmen2, ссылались на недостаточно точную работу алгоритма по определению категории рук и достаточно грубую выборку похожих вариантов дальнейших действий.

Что касается игр против BluffBot, то всего было сыграно 30000 раздач в обычном режиме, и результаты получились положительными. В среднем SARTRE выигрывал 7.48 больших блайндов каждые 100 раздач.

Исходя из информации о приведенных выше аналогах, можно сделать вывод, что существует два основных принципа, построения стратегии игры покерного агента:


  1. Основанная на поиске равновесного решения используя текущую информацию о раздаче;

  2. Основанная на запоминании история раздач, для дальнейшего применения на практике.

По приведенным выше аналогам, нельзя с уверенностью сказать, какая из данных стратегий является более выигрышной – моделирование поведения игрока по истории раздач или использование равновесных стратегий. Скорее всего, качество стратегии зависит от качества ее реализации. Основной задачей данной работы является реализация и оценка эффективности стратегии игры в Техасский холдем, основанной на методах теории вероятностей, предложенных различными авторами.

Глава 2. Общий алгоритм принятия решений.

В данной главе будет рассказано об основных подходах, которые были применены для разработки стратегии покерного агента.



2.1. Игра на префлопе

Для игры на префлопе, был использован метод, предложенный Биллом Ченом [4], в котором описывался алгоритм для подсчета силы карманных карт игрока. Суть метода, состоит в подсчете количества баллов, для карманных карт игрока и оценке их силы. Алгоритм имеет следующие шаги:



  1. Находим среди двух карт старшую, и добавляем 10 баллов если это туз, 8 – если король, 7 – если дама, 6 – если валет. Если старшая карта имеет достоинство <= 10, то добавляем половину от ее достоинства (Например если 8, то добавляем 4, если 5 – то 2,5).

  2. Если карманные карты образуют пару, то умножаем текущее количество баллов на 2 (Например если 77, то в итоге получается 7 баллов, если КК – то 16). При этом пара двоек оценивается в 5 баллов.

  3. Если обе карты одной масти, то добавляем еще 2 балла.

  4. Если между картами есть разрыв отнимаем баллы:

  • 0 баллов, если нет разрыва;

  • 1 балл, если разрыв в одну карту;

  • 2 балла, если разрыв в две карты;

  • 4 балла, если разрыв в три карты;

  • 5 баллов, если разрыв в 4 карты и более (для таких карманных карт как туз-два, туз-три и т.д. отнимать 5 баллов).

  1. Если между картами разрыв не более чем в одну карту, и обе они достоинством ниже дамы, то добавляем еще 1 балл;

  2. Округляем до целого числа к высшему баллу.

Таким образом, на основе полученного значения, система принимает решение при игре на префлопе.

Рассмотрим несколько примеров, для наглядной демонстрации работы этого алгоритма.



Ситуация 1. Предположим карманные карты - одномастные туз и король.

  1. Старшая карта туз: +10 баллов;

  2. Одномастные: +2 балла.

Итого: 12 баллов
Ситуация 2. Предположим карманные карты – одномастные 5 и 7.

  1. Старшая карта 7: +3,5 балла;

  2. Одномастные: +2 балла;

  3. Разрыв в одну карту: -1 балл;

  4. Разрыв в одну карту, причем обе достоинством ниже дамы: +1 балл.

Итого: 6 баллов (5,5 округляется до 6).
Ситуация 3. Предположим карманные карты – 2 и 7 разномастные.

  1. Старшая карта 7: +3,5 балла;

  2. Разрыв в четыре карты и более: -5 баллов.

Итого -1 балла (-1,5 округляется до -1).

Также, путем перебора всех карт, было обнаружено, что сила всех карманных комбинаций лежат в интервале от -1 до + 20 баллов. График распределения количества комбинаций различной силы представлен ниже.



Рис.4. Количество комбинаций различной силы на префлопе.


Также было посчитано и среднее значение силы руки = 4,01. Это значение также будет необходимо для работы алгоритма, по принятию решения.
2.2. Вычисление текущей силы руки

Для вычисления текущей силы руки в данной программе, был использован метод, описанный Дарсом Биллингсом и Джонатаном Шаффером [5]. Оценка силы руки является одним из ключевых компонентов работы всей системы, по принятию решений. Значение силы руки, показывает вероятность, с которой текущая комбинация игрока, будет сильнее комбинации оппонента. Данная оценка использует следующую формулу:



Пошагово данный метод можно описать следующей схемой:



  1. На флопе, терне или ривере определяется наиболее сильная комбинация для игрока.

  2. Путем перебора всех оставшихся в колоде карт, случайным образом выбираются две карты – считается, что это карманные карты оппонента.

  3. Оценивается какая комбинация сильнее, игрока или оппонента. Если сильнее комбинация игрока – к значению Na прибавляется единица, если они одинаковы – значению Nt прибавляется единица, если полученная комбинация оппонента, сильнее комбинации игрока – к значению Nb прибавляется единица.

  4. Таким образом перебираются все возможные комбинации карманных карт оппонента и высчитывается значение силы руки игрока.

Пример 1. Пусть у игрока на руках бубновый туз и трефовая дама. На флопе выходит червовая три, трефовая четыре и червовый валет. Оценим силу руки игрока. В данном случае если оппонент соберет тройку, две пары, пару или даже просто у него на руках туз и король – это сильнее комбинации игрока. Если у оппонента на руках туз и дама – это равносильно комбинации игрока, и наконец если у оппонента на руках карты ниже чем туз и дама, и при этом не имеется тройки, двух пар или пары, то комбинация игрока сильнее. В данном случае значения Na, Nt и Nb равны соответственно 628, 9 и 444. Таким образом значение HS = 0,585. Также следует не забывать, что полученное значение силы руки действует для игры против одного оппонента. Для вычисления значения силы руки при игре против нескольких оппонентов (что как раз и предполагает данная работа), необходимо полученное значение возвести в степень, соответствующую количеству игроков за столом в данный момент.

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



Пример 2. Пусть у игрока на руках червовые пять и два. На флопе выходит червовая три, трефовая четыре и червовый валет. На данный момент, используя только лишь метод определения силы руки, можно сделать вывод, что данная комбинация является очень слабой. Однако появление на столе хотя бы одной червовой карты, сделает эту руку выигрышной в большинстве случаев. Именно для этого система также должна учитывать возможное усиление комбинации игрока, а именно ауты.
2.3. Вычисление аутов

Следует начать с определения, что же такое аут. Аут – карта в колоде, которая может выйти на стол, собирая или улучшая комбинацию игрока. Вычисление аутов является не менее важным элементом системы, наряду с вычислением силы руки. Метод, используемый в данной работе, был предложен Рой Раундером [6]. Также вместе с вычислением аутов, он предложил метод вычисления шансов игрока и шансов банка. Для того чтобы данный метод стал более понятен, рассмотрим приведенный ниже пример.



Пример 1. Пусть у игрока на руках пиковые король и туз. На флопе выходит пиковая пять, трефовый валет и бубновая дама. Таким образом, исходя из определения аута, можно сделать вывод, что таковых после флопа у игрока 10. А именно три туза и три короля, которые дадут пару и четыре десятки, которые позволят игроку собрать стрит (пять карт подряд от десятки до туза). Таким образом, вероятность того, что на терне выпадет один из аутов = 10 / 47 (47 – оставшиеся в колоде карты, не учитывая карты других игроков, так как о них нет информации) = 21,2 %.

Что же касается вычисления шансов банка, то они нужны для того, чтобы система могла понять, на какую максимальную ставку оппонента игроку стоит ответить, или какую ставку поставить. Возвращаясь, к предыдущему примеру. Вероятность того, что на терне выйдет карта, улучшающая комбинацию игрока равно 21,2 %. Предположим, что в банке сейчас 1000 условных фишек. Оппонент ставит ставку размером в 250. Таким образом, в банке уже 1250. Чтобы продолжить игру, вам необходимо ответить оппоненту на ставку в 250.

250 / 1250 = 0,2.

0,2 < 0,212 (вероятность выхода на стол нужной игроку карты).

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

В данной работе, была предпринята попытка объединить вычисление текущей силы руки и вероятности выхода на стол аутов, для подсчета максимальной ставки для уравнивания или же ставки, которую необходимо поставить игроку. Данные два подхода составляют основу для принятия решений системой, рассмотренной в работе.


2.4. Изменение стиля игры

Разработанная система имеет возможность менять стиль игры. Основой для разработки этого элемента послужила идея, выдвинутая Динисом Феликсом [7]. Он предположил, что любого игрока в покер Техасский Холдем можно охарактеризовать по двум основным параметрам:



  • Открытый – зажатый;

  • Агрессивный – пассивный.

Степень открытости игрока зависит от того количества карманных карт, которые он играет, то есть от того количества раз, которые он «смотрит» флоп. Данный аспект игры является достаточно важным, поскольку его легко проследить и его можно в дальнейшем использовать в своих целях. В данной работе, для определения уровня открытости будет использоваться уже описанная формула Билла Чена и коэффициент открытости, который будет меняться от 0,0 до 1,0. Коэффициент 1,0, говорит о том, что система будет разыгрывать на префлопе абсолютно все карты, которые приходят игроку. При коэффициенте 0,1 будут разыгрываться карманные карты от 16 до 20 баллов и т.д.

Степень агрессивности игрока зависит от количества раз, когда игрок делает ставку либо повышает ее вместо того, чтобы ответить «колл». Данный коэффициент также меняется в пределах от 0,0 до 1,0 и при этом значение 0,5, говорит о том, что игрок делает ставку и уравнивает ставку противника примерно одинаковое количество раз.

Таким образом, в данной работе принятие решений осуществляется путем взаимодействия сразу нескольких подходов и методов. Общий алгоритм игры на префлопе представлен на рисунке 5. Алгоритм игры на флопе, терне и ривере представлен на рисунке 6.

Рис. 5. Алгоритм игры на префлопе



Рис 6. Алгоритм игры на флопе, терне и ривере



Глава 3. Среда реализации и результаты работы

3.1. Среда реализации приложения

Для реализации системы принятия решений, описанной в данной работе, были использованы средства Microsoft Visual Studio 2008, язык C#. В целом, для всех вычислений использовались стандартные библиотеки .Net Framework 4.0. Однако для получения информации непосредственно из клиента была использована библиотека WinApi. Перед использованием данной библиотеки при помощи инструмента Spy++ было обнаружено, что окно чата в покерном клиенте PokerTime имеет класс «RichEdit20W».


Рис. 7. Окно покерного клиента

Уже отталкиваясь от этого, был разработан алгоритм получения необходимой информации из клиента. Принцип работы данного алгоритма представлен на рисунке 8.

Рис. 8. Алгоритм получения информации из клиента

Что касается диаграммы классов разработанного приложения, то она представлена на рисунке 9. Следует сказать, что все класса, разработанные в данном приложении, можно разделить на три части:


  1. Классы, описывающие структуры данных, используемых в приложении;

  2. Классы, осуществляющие взаимосвязь между различными частями приложения;

  3. Классы, выполняющие основные функции данного приложения;

  4. Классы, описывающие различные настройки приложения.

К классам первого типа, относятся:

    • Bet.cs – описывает ставки, совершаемые игроками (размер и раунд);

    • Out.cs – описывает ауты (карта и комбинация);

    • Card.cs – описывает карты (достоинство и масть);

    • Deck.cs – колода (все карты, содержащиеся в колоде);

    • Player.cs – описывает игрок (игрок и его позиция за столом);

    • Hand.cs – описывает набор из пяти карт (карты, участвующие в наборе и силу комбинации)

    • Score.cs – описывает комбинацию, собранную из данных пяти карт (сила комбинации и старшая карта, участвующая в ней).


Рис. 9. Диаграмма классов

К классам второго типа относятся Program.cs и PokerTimeBot.cs.

К классам третьего типа относятся классы ParseData.cs, EvalCards.cs и RichEditCont.cs. Класс ParseData.cs осуществляет интерпретацию данных, полученных из чата клиента. Класс RichEditCont.cs осуществляет получение анных из чата клиента. Класс EvalCards.cs в свою очередь выполняет все основные функции данного приложения, а именно все вычисления и также отвечает за принятие решений.

К классам четвертого типа относится Settings.cs.

Интерфейс разработанного приложения представлен на рисунке 10.



Рис. 10. Интерфейс приложения



3.2. Результаты работы приложения

Для проведения оценка эффективности разработанной стратегии для игры в покер Техасский холдем, были сыграны по 50 раздач на каждой возможной комбинации коэффициентов открытости агрессивности. Затем были подсчитанные средние значения количества выигранных больших блайндов за раунд, по каждому коэффициенту и результаты данных тестов представлены на рисунках 11 и 12.



Рис. 11. Среднее количество выигранных больших блайндов за раунд для разных коэффициентов открытости


Рис. 12. Среднее количество выигранных больших блайндов за раунд для разных коэффициентов агрессивности


По представленным двум графикам можно сделать вывод о том, что наилучшие результаты система показала при коэффициентах открытости и агрессивности равных примерно 0,3 – 0,4. Это можно объяснить тем, что данное приложение тестировалось при игре на условные фишки, при котором, как известно, большинство пользователей играют достаточно агрессивно и открыто, совершая при этом большое количество ошибок. Система же, в свою очередь, разыгрывая только лишь действительно сильные руки, оставалась в выигрыше.

Заключение

В рамках данной работы были решены следующие задачи:



  • получение и интерпретации информации из покерного клиента PokerTime;

  • реализация метода Билла Чена для вычисления силы карманных карт;

  • реализация методов вычисления текущей силы руки и вероятности появления аутов;

  • реализация алгоритма изменения стиля игры;

  • реализация алгоритма принятия решения для участника игры покер Техасский холдем.

Принцип работы разработанной системы был основан на нескольких научных подходах, как профессиональных игроков в покер, так и ученых, занимающихся исследованием игр, с неполной информацией. Что касается результатов работы данной системы, то они являются достаточно оптимистичными при игре на условные фишки.

Данная система является, по сути, хорошей основой для дальнейшего развития данной темы. Среди направлений развития можно выделить следующие:



  • разработка системы для игры в хэдз-ап покер Техасский холдем, с возможностью анализа поведения оппонента;

  • разработка системы по моделированию поведения оппонента для дальнейшего принятия решений по его стратегии;

  • разработка системы принятия решений для участника игры в покер Техасский холдем на основе равновесных стратегий по Нэшу.

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

Литература:

        1. Правила Техасского холдема. Режим доступа: http//pokerstars.com/ru, свободный. (дата обращения: 09.04.2013)

        2. Абстракция в компьютерном покере. Режим доступа: http//habrahabr.ru, свободный. (дата обращения: 11.04.2013)

        3. Dizman, D. Review of four artificial intelligence agents for poker. Retrieved April 2, 2013, from website: http://static.dendiz.com

        4. Chen, B. & Ankenman, J. (2006). The mathematics of poker. New York: ConJelCo.

        5. Billings, D., Papp, D., Schaeffer, J. and Szafron, D. (1998). Opponent modeling in poker. Retreived April 13, 2013, from University of Alberta website: http://webdocs.cs.ualberta.ca/~darse/Papers/AAAI98.html

        6. Rounder, R. (2009). Poker math made easy. Roy Rounder Communications, Inc.

        7. Felix, D. (2008). Artificial intelligence techniques in games with incomplete information: opponent modelling in Texas holdem. Porto: FEUP.

1 Покер рум - проект, предоставляющий возможность игры в онлайн покер с людьми со всего мира. Покер рум по своей сути является виртуальным аналогом покерных клубов, только с большим количеством игровых столов и виртуальными дилерами [1].

2 Майк Каро. Родился 16 мая 1944 года. Специалист по стратегии, психологии и статистике. Так же известен как специалист по азартным играм. Автор и соавтор множества книг. Работал как консультант или менеджер во многих казино и покерных онлайн комнатах[1].

3Хедз-ап - является способом игры в покер, когда за столом играет только два человека. Кроме того, хедз-апом называется круг торговли, когда из всех игроков только двое остались в игре («остались в хедз-апе») [1].

4 Sparbot – разработан Университетом Альберты. Его особенность состоит в том, что он сам по себе не является выигрывающим роботом. Он скорее следит за действиями игрока, и при обнаружении слишком пассивной или слишом активной игры, использует это в своих целях [3].

5 AAAI CPC – соревнование по покеру (Техасский холдем) среди компьютеров.

6 FellOmen2 – робот, занявший второе место на соревнованиях CPC 2008. В основе стратегии данного робота лежит эволюционный метод нахождения равновесного решения.

7 BluffBot – робот, занявший второе место на соревнованиях CPC 2008. Стратегия игры этого агента основана на поиска равновесного решения по Нэшу.