Рейтинг инвестиционных инструментов – Все инвестиции в одном рейтинге   
Понедельник, 24 июля
Медиа партнеры и спонсоры
           

Программа научилась принимать правильное решение​ в покере

12 сентября, 2016

Программа научилась принимать правильное решение​ в покере

В начале 2015 года в журнале Science вышла статья, в которой было объявлено об успешном завершении работы компьютерной программы, просчитывавшей одну из версий покера — хедз-ап в лимитном техасском холдеме. Программа научилась принимать правильное решение в каждом из примерно 3,19×1014 возможных состояний игры. Найденная таким образом стратегия на длинной дистанции должна обыгрывать остальные стратегии. Одним из результатов анализа стало доказательство того, что дилер имеет преимущество перед вторым игроком. Авторы статьи предлагают ведущим профессиональным игрокам в покер опробовать стратегию на практике и убедиться в ее оптимальности.

Техасский холдем (texas hold'em) — самая популярная разновидность покера. Игра ведется стандартной колодой из 52 карт. В начале каждого розыгрыша игроки получают по 2 карты (карманные карты). Они смотрят на свои карты, после чего происходит первый раунд торговли. Игрока, который начинает торговлю, называют дилером (или игроком на кнопке, см. Button (poker)), после каждого розыгрыша дилером становится следущий по кругу игрок. Во время торговли игрок может повысить ставку (raise), уравнять ставку соперника (call) или отказаться от дальнейшего участия в розыгрыше и сбросить карты (fold). В итоге после раунда торговли каждый оставшийся в розыгрыше игрок поставил на кон одну и ту же сумму денег. Далее для всех открываются три общие карты (flop), после чего происходит второй раунд торговли. После этого открывается еще одна карта (turn), происходит третий раунд торговли. Наконец, открывается пятая общая карта (river), и происходит последний, четвертый раунд торговли. Если в какой-то момент в игре остается только один игрок, он забирает весь банк. Если после четвертого раунда торговли в игре остается более одного игрока, то они вскрывают свои карманные карты и сравнивают получившиеся 5-карточные комбинации, которые каждый может построить из личных и общих карт. Тот, у кого комбинация лучше, забирает банк.

Хедз-ап (heads up) означает, что играют только два игрока. Лимитный покер — это версия игры, в которой ставки можно повышать на фиксированную величину, причем повышать ставку можно не более чем заранее оговоренное число раз. Поэтому лимитный техасский холдем — это конечная игра. Последовательные игры в теории игр принято задавать с помощью деревьев. Вершинам дерева будут соответствовать различные состояния игры. Каждой вершине приписано имя игрока, которому в этой вершине принадлежит ход. Ребрам, исходящим из этой вершины, соответствуют действия, которые может совершить этот игрок. Одним из участников игры является «природа» — так в теории игр называют искусственного игрока, выполняющего роль генератора случайных чисел. «Природа» случайным образом решает, какую карту сдать игрокам или открыть на столе.

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

Любую конечную последовательную игру с совершенной информацией можно просчитать с конца, используя алгоритм обратной индукции. Рассмотрев одну подыгру самого последнего уровня (то есть такую подыгру, на которой после принятия любого решения игра заканчивается и игроки подсчитывают полученные платежи), можно найти оптимальное действие игрока, которому принадлежит ход на этой подыгре. Далее точно так же можно найти оптимальные действия игроков на всех подыграх последнего уровня. После этого, зная, как будут вести себя рациональные игроки на подыграх последнего уровня, можно перейти к анализу игр предпоследнего уровня, и так далее. Рано или поздно, точно получится добраться до подыгры, совпадающей со всей игрой, после чего можно найти в ней оптимальное действие игрока, которому принадлежит первый ход. Таким образом, будет найдено оптимальное поведение всех игроков в любой возможной ситуации и будет выяснено, чем заканчивается игра при правильных действиях всех игроков. Именно так в 2007 году были просчитаны шашки — оказалось, что при правильной игре обеих сторон в шашках партия обязательно закончится вничью.

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

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

Наконец мы подошли к результату, который получили авторы статьи в Science. Для некоторого достаточно малого ε авторы предъявили ε-равновесие Нэша (ε настолько мало, что человеческой жизни не хватит на проверку отличия ε-равновесия Нэша от равновесия Нэша. 

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

Можно ли заработать, играя найденную стратегию? Да, если уметь воспроизводить действия, которые предписывает совершать стратегия в каждой позиции. Вряд ли на это будет способен человек — не хватит памяти. А вот против компьютера играть в лимитный хедз-ап теперь бесполезно. Скорее всего, это означает, что скоро лимитный хедз-ап покер пропадет с покерных сайтов — будет очень сложно проверять, что человек не использует специальные программы, помогающие найти оптимальные ответы. Однако игрокам в покер расстраиваться рано. Даже если про все вариации лимитного покера однажды всё станет известно, останется безлимитный покер (можно делать ставки любого размера), который не является конечной игрой. Из-за этого решить безлимитный покер модификациями алгоритма обратной индукции уже вряд ли получится...


Ссылка на источник   Ставки на спорт

21 июля, 2017

Фактические доходы от лотереи превысили вдвое ожидания

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

7 июня, 2017

В России впервые появится крупный зарубежный букмекер

Структура бизнесмена Александра Мамута при участии Rambler & Co запускает букмекерскую платформу bwin.ru...

19 мая, 2017

«Игра Престолов»: ставки на 7-й сезон

Сериал опережает книжную сагу, и никто не знает, чем завершится борьба за Железный трон, поэтому ставки на 7-й сезон «Игры престолов»...

20 апреля, 2017

Разработан законопроект о блокировке нелегальных букмекеров

Суть документа – обязать анонимайзеры и VPN-сервисы блокировать сайты из реестра запрещенных ресурсов...

11 апреля, 2017

ИИ сыграет в покер с мастерами из Китая

Обновленная версия покер-бота Libratus начала серию товарищеских игр с китайской командой игроков Team Dragons...

10 апреля, 2017

ФИФА инвестирует в ЧМ-2018 около $2 млрд

Самой большой статьей расходов являются средства, выделенные на организацию турнира "на местах" - $627 млн (32% от общей суммы), на втором месте - призовые...

29 марта, 2017

Путин подписал закон о рекламе и целевых отчислениях букмекеров

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

23 марта, 2017

Букмекеры оценили шансы Путина и Навального выиграть выборы президента

11 марта 2018 года в России состоятся президентские выборы. Букмекерские конторы принимают ставки на то, кто одержит победу и на шесть лет станет президентом страны...

Ставки на спорт

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

Индекс Инвестиционного Интереса: 7.6


21 июля, 2017 Фактические доходы от лотереи превысили вдвое ожидания

16 июня, 2017 Bwin запустят в России

7 июня, 2017 В России впервые появится крупный зарубежный букмекер





Самые перспективные акции на 2018 год Самые перспективные акции на 2018 год
Финансовые прогнозы и аналитика
CryptA Capital — новый инструмент для инвестиций в криптовалютыCryptA Capital — новый инструмент для инвестиций в криптовалюты
Финансовые статьи
Справедливое ICOСправедливое ICO
Финансовые статьи
Сколько стоит отдых на яхтеСколько стоит отдых на яхте
Финансовые статьи
Лучшие ПАММ-счета в июне
Финансовые статьи
Глава цифрового банка WB21 в России: «Мы поддерживаем криптовалюты» Глава цифрового банка WB21 в России: «Мы поддерживаем криптовалюты»
Инвестиционный взгляд эксперта
Обзор инвестиционных прогнозов экспертов за первое полугодие 2017 г.Обзор инвестиционных прогнозов экспертов за первое полугодие 2017 г.
Топ 10 инвестиций
Обзор инвестиционных идей июня 2017 г.Обзор инвестиционных идей июня 2017 г.
Топ 10 инвестиций
ТОП 10 инвестиций июня 2017ТОП 10 инвестиций июня 2017
Топ 10 инвестиций
Инвестиции в жилую недвижимость России: быть или не быть?Инвестиции в жилую недвижимость России: быть или не быть?
Финансовые статьи

Новости инвестиций
Форекс
Биткоин
Акции
Облигации
Драгоценные металлы
ПАММ счета
Банковские депозиты
Недвижимость
Наличные деньги
Доверительное управление
Ставки на спорт
Бинарные опционы
Венчурные инвестиции
Структурные ноты
ПИФы
Искусство, антиквариат
Индивидуальный инвестиционный счет (ИИС)
Хедж-фонды
Деривативы
Нефть, газ, сырье
Автомобили, яхты, самолеты
Драгоценные камни
Металлы
Накопительные программы
Фьючерсы на индексы
Сельхоз продукция
Образование
Шоу бизнес
Здоровье
Необычные инвестиции


Поделиться материалом: