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



Правительство Русской Федерации


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

высшего проф образования


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


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

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

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


ВЫПУСКНАЯ КВАЛИФИКАЦИОННАЯ РАБОТА


На тему: Автоматическая система принятия решений для участника многоагентных Автоматизированная система принятия решений для участника многоагентных взаимодействий в условиях неполноты информации взаимодействий в критериях неполноты инфы



Студент группы №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 онлайн. Обычно подобные системы состоят из последующих частей:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Каждый раунд торгов длится пока все активные игроки (которые не сделали фолд) не сделают равные ставки в Автоматизированная система принятия решений для участника многоагентных взаимодействий в условиях неполноты информации банк.

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

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

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

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

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

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




Рис. 1. Композиции в покере

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


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

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

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

  2. Неувязка представления рук игроков.

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

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


Таблица 1

^ Количество Автоматизированная система принятия решений для участника многоагентных взаимодействий в условиях неполноты информации вероятных композиций карт

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

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

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

Неэквивалентные для 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-го игрока, т.е. для сочетаний одной пары карманных карт и общих карт. И, в конце концов, последний столбец содержит внутри себя количество неэквивалентных классов карточных композиций Автоматизированная система принятия решений для участника многоагентных взаимодействий в условиях неполноты информации для 1-го игрока. Эквивалентными комбинациями именуются такие наборы карточных композиций, в каких подменой мастей можно получить всякую другую комбинацию из этого же набора. Совсем разумеется, что эквивалентные композиции содержат внутри себя одну Автоматизированная система принятия решений для участника многоагентных взаимодействий в условиях неполноты информации и ту же стратегическую информацию [2].

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


1.2.1. GS1

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

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

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.

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




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


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

База познаний 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. Находим посреди 2-ух карт старшую, и добавляем 10 баллов если это туз, 8 – если повелитель, 7 – если дама, 6 – если валет Автоматизированная система принятия решений для участника многоагентных взаимодействий в условиях неполноты информации. Если старшая карта имеет достоинство <= 10, то добавляем половину от ее плюсы (К примеру если 8, то добавляем 4, если 5 – то 2,5).

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

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

  4. Если меж картами Автоматизированная система принятия решений для участника многоагентных взаимодействий в условиях неполноты информации есть разрыв отнимаем баллы:

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

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

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


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

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

Пример 1. Пусть у игрока на руках пиковые повелитель и туз. На флопе выходит Автоматизированная система принятия решений для участника многоагентных взаимодействий в условиях неполноты информации пиковая 5, трефовый валет и бубновая дама. Таким макаром, исходя из определения аута, можно прийти к выводу, что таких после флопа у игрока 10. А конкретно три туза и три короля, которые дадут пару Автоматизированная система принятия решений для участника многоагентных взаимодействий в условиях неполноты информации и четыре 10-ки, которые позволят игроку собрать стрит (5 карт попорядку от 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. Классы, описывающие разные опции приложения.

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




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

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

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

К классам 4-ого типа относится Settings.cs.

Интерфейс разработанного приложения Автоматизированная система принятия решений для участника многоагентных взаимодействий в условиях неполноты информации представлен на рисунке 10.



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

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

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



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




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


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

Заключение

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

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

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

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

Литература:

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

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

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

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

5 AAAI CPC – соревнование по покеру (Техасский холдем Автоматизированная система принятия решений для участника многоагентных взаимодействий в условиях неполноты информации) посреди компов.

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

7 BluffBot – бот, занявший 2-ое место на соревнованиях CPC 2008. Стратегия игры этого агента Автоматизированная система принятия решений для участника многоагентных взаимодействий в условиях неполноты информации базирована на поиска сбалансированного решения по Нэшу.



avtoblokirovka-poluavtoblokirovka-elektrozhezlovaya-sistema-naznachenie-i-princip-dejstviya.html
avtobus-iz-elisti-popal-v-dtp-pod-tveryu-odin-chelovek-pogib-shest-postradali-informacionnoe-agentstvo-regnum-04082012.html
avtobus-otbival-cherez-desyat-dnej-i-vse-visipali-na-palubu.html