Приближение к оптимальной стратегии покера

  1. TTR

    TTR Команда форума

    Сообщения: 29.140
    Симпатии: 2.562
    Введение

    За последнее десятилетие исследовательская группа Computer Poker Research Group (CPRG) Университета Альберты до предела расширила границы компьютерного покера. Наиболее активный член группы и ведущий автор обсуждаемой здесь публикации – Дейрс Биллингс.

    CPRG издала много важных статей на тему компьютерного моделирования игры в покер. Более того, они не просто получают важнейшие научные результаты. Их усилия направлены на создание конкурентоспособных покерных приложений, в том числе таких коммерческих продуктов как Poker Academy Pro, основанный на программном обеспечении Poki poker. Они также работают над Polaris – программой, которая успешно соревнуется с ведущими профессионалами покера.

    Большинство теоретических основ, используемых в Polaris, описаны в статье "Approximating Game-Theoretic Optimal Strategies for Full-scale Poker" / “Приближение к оптимальной стратегии покера”, опубликованной в трудах 18-й международной конференции по искусственному интеллекту в августе 2003г.

    Цель исследования этой статьи – поиск нового решения классической проблемы: человек vs. машина. В особенности интересует авторов усовершенствование алгоритмов игры в покер. Их цель – научить компьютер как можно лучше играть в покер, как это было сделано с игрой в шашки или шахматы.

    На практике это очень сложно, потому что покер имеет очень большое “игровое пространство”. Количество всевозможных вариантов развития событий для отдельной руки очень велико. Даже с современными компьютерными ресурсами невозможно решить относительно простую проблему – хедс-ап (heads up) в лимит-холдеме.

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

    В конце раздела 1 статьи авторы говорят о следующих результатах своего исследования: их упрощения сократили исследовательское пространство покерных игр до 11 степеней значимости. Их новые алгоритмы оказываются лучше других компьютерных оппонентов. Более того, эти новые алгоритмы часто могут оказывать конкуренцию сильному живому игроку в покер.

    Теория игр


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

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

    Третий раздел статьи знакомит читателя с основами игры в техасский холд’эм. Нет необходимости повторять такое введение для читателей данной статьи. Но важно отметить, что CPRG пытается решить проблему конкретной разновидности игры – хедс-ап лимит техас холд’эм. Это наименее сложная игра, поэтому вполне логично начинать именно с неё.

    Абстракции


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

    Первая из обсуждаемых абстракций – так называемый “изоморфизм равноценности мастей”. “Изоморфизм” допускает изменение чего-либо, не влияющего на результат. Например, игра с А:club: K:club: на флопе K:club: 8:heart: 3:diamond: считается идентичной игре с A:diamond: K:diamond: на флопе K:club: 8:club: 3:heart:. Проще говоря, это математический способ выражения идеи, что “Если у меня две одномастные или неодномастные карты, неважно, какой они масти, если на борде этих мастей нет”. Это знает любой игрок в покер. Эта абстракция не влияет на стратегию, и авторы используют её в своих алгоритмах.

    Авторы также обсуждают “ранговую равноценность” и “ранговую почти-равноценность”. Возможный пример “ранговой равноценности” таков: рука A:club: 7:heart: на борде 9:club: 9:club: 8:heart: 8:diamond: K:club: имеет такой же эквити, как и рука A:club: 3:heart: на том же борде. В этом случае 7 и 3 эквивалентны. Примером “ранговой почти-равноценности” могут служить руки К7s и К6s. У них одинаковое количество возможных триплетов или других лучших рук. Разница лишь в том, что с К7 чуть выше вероятность собрать руку с топ-парой. Тем не менее, я полагаю, большинство читателей согласится с тем, что оценка этих рук как равноценных по силе не слишком исказит эквити, если вообще исказит. Абстракции ранговой равноценности не изменят нашу стратегию; а ранговой почти-равноценности могут немного изменить, но лишь немного и в очень редких случаях. Так что авторы используют обе эти абстракции.

    Следующая абстракция – “редукция колоды”. Математические проблемы покера станут заметно проще, если мы сократим количество карт в колоде. Радикальный пример “редукции колоды” – AKQ-игра, описанная в “Mathematics of Poker”. Поскольку это слишком сильно бы изменило игру, авторы не могут эту абстракцию использовать для компьютерных программ игры в покер в таком виде.

    Точно так же можно сократить количество карт в руке у игроков или на борде. Авторы приводят пример такой абстракции из исследования Ши и Литтмана, которые рассматривают упрощённую игру в род-айлендский холд’эм. Эту публикацию, на которую они ссылаются, я обсуждал в своей статье для выпуска Two Plus Two Magazine за июнь 2009. Авторы используют эту абстракцию в ограниченной форме, мы вернёмся к этому позже более детально.

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

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

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

    Когда рассматривается только игра префлоп, они исключают более поздние раунды торговли. Вместо ставок на поздних раундах они увеличивают банк на некоторый процент, высчитывающийся с учётом эквити каждой руки. Они создали одну программу, которая данным способом исключает только торги на ривере, и другую, которая исключает торги на терне и ривере. Это позволяет упростить решения префлоп. Когда изучаются стратегии на тёрне и ривере, аналогично определяется размер банка в результате торгов префлоп, но не учитывается, кто именно был агрессором.
    Другая абстракция предполагает, что стратегии ставок в каждом из раундов независимы друг от друга. Она была тоже предложена Ши и Литтманом в их статье, и я тоже обсуждал последствия такого выбора в июньском номере. Авторы CPRG считают эту абстракцию слишком уязвимой, поскольку она умышленно исключает многораундовые стратегии.

    Другая абстракция, которую упоминают Ши и Литтман, – это “группировка”. Это объединение рук одинаковой силы, которые разыгрываются почти одинаково. Авторы воспользовались книгой Дэвида Склански и Мейсона Мальмута “Hold 'em Poker for Advanced Players” и их девятью группами стартовыми рук. Однако для своих целей они разбили все руки на шесть групп. Пять из них – для рук, уже обладающих какой-либо ценностью, а шестая – для рук, ценных лишь потенциально. Авторы не пишут, какая конкретно рука попадёт в какую группу, но они говорят, что потенциально ценные руки – это те, которые могут стать флешем или стритом. Так что можно предположить, что одномастные коннекторы, Ахs и руки типа 98off могут оказаться в шестой группе, наряду с какими-либо ещё.

    Авторы отмечают, что переход от 6 групп к 7 или 8 не будет существенным. Кроме того, многие успешные игроки-люди не делают настолько дробных градаций типов рук.

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

    Тестирование

    Чтобы проанализировать последствия некоторых принятых авторами абстракций, они создали несколько не сильно отличающихся друг от друга версий программного обеспечения, которые используют эти методы. Они также используют некоторые другие покерные боты, например, Poki, Anti-Poki (бот, специально использующий слабости Poki), Adapti (бот, разработанный для обнаружения и использования слабостей оппонента) и два бота с говорящими именами – "Always Call" и "Always Raise". Эти программы сыграли друг с другом по кругу 20,000 рук. Их винрейты можно сравнить.
    Важно заметить, что теоретически оптимальная покерная стратегия может быть определена скорее как “не проиграть”, чем “выиграть как можно больше”. Игрок, играющий оптимально, не должен проигрывать никакому оппоненту и при этом не обязательно должен обыгрывать даже слабого игрока. Чтобы максимизировать винрейт против плохого игрока, надо использовать его слабости, то есть играть не оптимально, но только при такой игре можно извлечь максимальную выгоду из ошибок соперника. Вообще, в разделе 5.1 рассматриваемой статьи всего в нескольких параграфах прекрасно описаны различия оптимальных и эксплуататорских стратегий.

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

    Интересный факт, на который стоит обратить внимание, – это выступление программы под названием "PsiOpti0". Эта программа работает по сложному алгоритму постфлоп, а её стратегия префлоп – просто всегда уравнивать. Она проиграла всего два матча – причём оба наиболее сложным программам, действующим по псевдооптимальной стратегии. К тому же, она действовала почти так же хорошо, как самые успешные программы, против наименеее мастеровитых оппонентов. Это поддерживает идею о том, что если кто-то хорошо играет постфлоп, он может стать успешным игроком, даже если плохо играет на префлопе.

    Затем две лучшие программы противостояли живым игрокам различного уровня мастерства: от новичков до игроков мирового класса, cпециализирующихся на играх в лимит-холд’эм с малым числом участников. Эксперты смогли обыграть программы, опытные игроки играли с ними на равных, а менее опытные и вовсе проиграли. Это немалое достижение, особенно учитывая то, что мы обсуждаем программы, которым в настоящее время уже 6 лет с момента создания.

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

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

    Выводы


    Лучшие машинные игроки в покер становятся всё совершеннее и совершеннее. Результаты Polaris версии 2008 года – лучшее тому подтверждение. Возможно, не далёк тот день, когда компьютеры будут обыгрывать любого живого человека хотя бы в пределах игры хедс-ап в техасский лимит-холд’эм.

    Добавление моделирования оппонента, компьютерный прогресс и усовершенствование используемых алгоритмов приведёт к тому, что лучшим живым игрокам в покер придётся улучшать свою игру только для того, чтобы быть на равных с компьютером. В таком случае мир покера скоро станет похож на мир шахмат. Хотя мы ещё далеки от полного решения проблемы игры в техасский холд’эм, но псевдооптимальные стратегии могут приблизить нас к нему за неожиданно короткий промежуток времени.
     
    Последнее редактирование: 19 окт 2016
  2. Ну, Покер Стратеджи, это понятно, школа номер один в плане бездепозитных бонус ов и теории, сама получила там свои первые 50, но есть же и другие сайты и школы покера где можно получить стартовый капитал для игры. И хочется почитать какой-нибудь альтернативной теории. Давайте пополнять список покерных сайтов.
     
  3. at the Two

    Section 2. Information about the Mission of Project Gutenberg-tm Project Gutenberg-tm is synonymous with the free distribution of electronic works in formats readable by the widest variety of computers including obsolete, old, middle-aged and new computers. It exists because of the efforts of hundreds of volunteers and donations from people in all walks of life. He took back to England but L400,http://cheapjordanshoes2m.webs.com/. He gave the Boston Yankees, too,jordans sale, rather a bad name in commercial transactions, saying: "There is no trading for a stranger with them but with a Grecian Faith which is not to part with your own ware without ready Money; for they are generally very backward in their payments; great censors about other Mens manner but Extremely Careless about their own. When you are dealing with 'em you must look upon 'em as at cross purposes and read 'em like Hebrew backward; for they seldom speak & mean the same thing but like the Watermen Look one way & row another." Josselyn gave them no better name, saying: "Their leading men are damnable rich, inexplicably covetous and proud; like Ethiopians, white in the teeth only; full of ludification and injurious dealing." Of Dunton's patrons the majority were ministers, and I hope all the reverend gentlemen were as prompt payers as they were liberal purchasers. The man staggered, and fell. I helped him up, sir; and I reckon he thought matters might be worse still, for he slowly walked off. "'D----d free country,' he muttered to me, in a kind of confidential tone. She was therefore rising to leave; but Papias held her back and entreated her so pathetically with his blue baby-eyes not to take him away and spoil his pleasure that she yielded, though the opportunity was favorable for moving unobserved, as the woman in front of her was preparing to go and was shaking hands with her neighbor. She had indeed risen from her seat when a little girl came in behind her and whispered,jordans for sale, loud enough for Dada's keen ears to catch the words: "Come mother, come home at once. He has opened his eyes and called for you. Except for the limited right of replacement or refund set forth in paragraph 1.F.3, this work is provided to you 'AS-IS' WITH NO OTHER WARRANTIES OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO WARRANTIES OF MERCHANTIBILITY OR FITNESS FOR ANY PURPOSE. 1.F.5. Some states do not allow disclaimers of certain implied warranties or the exclusion or limitation of certain types of damages.Related articles: As a proof of Bellarmin's abilities Eikon Basilike 207 Inscription on Dr differ with you
     
Загрузка...
Похожие темы - Приближение оптимальной стратегии Форум Дата
Теория оптимальной игры без статистики на NL200 c Виталием "Inferno". Обсуждение и поиск водов 17 фев 2016