The Times They Are a-Changin’

десятка есть?

Без графика не верим.

больше полтинника 100%)
Но график, конечно, в качестве лечения надо бы принять!

Эпичнейший промах с моей стороны.

Не буду отставать от современной моды и тоже напишу пост про ГТО. Расскажу о своем хобби - о машинном гто. Начну с рассмотрения алгоритма расчетов , который можно уже назвать классическим. Авторы данного алгоритма ученые из института Альберты. Если у кого-то есть время, желание, знание английского и математическое образование то велком http://poker.cs.ualberta.ca/publications/NIPS07-cfr.pdf
Алгоритм очень хорошо себя зарекомендовал в лимитных HU играх. Эксплоитабилити лучших расчетов для лимитного холдема очень низкое. Насколько я помню точно ниже 1бб/100. Эксплоитабилити это величина на которую можно обыграть данный фиксированный алгоритм (то есть он заранее расчитан и не подстраивается под действия оппонента) зная его полное дерево стратегий для всех типов досок и строя к этому дереву полную контр стратегию. Как считается модель на основе данного алгоритма. Для начала нам нужно определиться с количеством различных сайзингов. Для примера предположим, что мы моделируем безлимитный покер, но с фиксированным стеком и одним размером сайзинга (то есть мы делаем всегда только одного размера опен рэйз например 2.5бб далее 3 бет 9бб и тд) Сначала строится дерево действий на основе этих сайзингов - всевозможные действия игроков которые могут быть уложены в 100бб стек. Для хэдзапа с фиксированным одним бетом получится дерево решений что-то около 500 нодов (точек развлетвления стратегии). Далее в каждом ноде у нас возможны действия ведущие в другой нод - рэйз, колл, чек и фолд ведущий к терминальному состоянию. Далее для каждого нода у нас есть набор рук. Рука для машины это немного не то что для человека. Машинная рука точка во всем пространстве покерных состояний, включает карманные карты игрока и доску (при этом без учета порядка прихода карт на доску). На флопе у нас примерно 1.5миллиона различных не абстрагированных рук, на терне и ривере это величины еще больше, но если умело группировать все еще не абстрагированные руки по терну и риверу то можно обойтись 7 миллионами рук. И для каждой руки каждого нода у нас есть параметр, отвечающий за стратегию, частоту игры данной руки и данного действия. Параметр назвается сожаление, а весь алгоритм cfrm - алгоритм минимизации сожаления. Как это работает. Допустим мы знаем начальное состояние всего дерева и в нем все сожаления для всех ситуаций во всех нодах в начале одинаковые, то есть нам без разницы как к примеру играть на префлопе АА. для начала мы их играем 50 на 50 между фолдом и рэйзом. Со временем сожаление от фолда будет возрастать, а сожаление от рэйза будет уменьшаться, что приведет к тому, что в дереве решений мы практически со 100% вероятность не будем фолдить тузов и будем с ними делать опен рэйз. с префлопом в общем-то проблем нет, там все довольно быстро сходится так как для каждого префлоп нода у нас всего 169 рук и стратегий для них. когда мы доходим до терминального нода, завершающего нашу игру (то есть до вскрытия или до фолда), то, то сколько денег мы выиграли или проиграли за данную иттерацию мы переводим в сожаление и последовательно меняем для всех нодов, лежащих выше в дереве. Допустим мы дошли до ривера и там был фолд. Для всех последовательностей действий-нодов, сначала на ривере, терне, флопе и далее на префлопе мы изменяем сожаление для данной руки и стратегии. так как нодов у нас много, а рук в каждом ноде дохера, то процесс оптимизации стратегии, чтобы насытить все редкие ноды и руки в них (например двойной чек-рэйз по флопу и терну это очень редкий нод) занимает триллионы итераций. при этом даже после такого огромного количества сыграных раздач (которое зачастую превосходит количество сыгранных раздач людьми), мы получим что основные ноды и руки в них будут довольно хорошо расчитаны, а вот более редкие ноды плохо. При этом есть физические ограничения на скорость расчетов и быстрее чем 9 триллионов раздач в месяц скорее всего в ближайшее время считать не получится. ну то есть возможно потолок повысится, но скорее всего не намного. Упирается все в скорость памяти и контроллера. Буржуи как-то умудряются распараллеливать алгоритм на суперкомпьютерах, но засчастую это ведет к ухудшению сходимости. Горшочек или дудочка.
Можно пойти через путь обобщения различных рук. К примеру мы говорим что на флопе в ноде где мы префлоп рэйзер и оппонент чекнул мы можем сгруппировать 1.5 миллиона рук для этого нода к примеру в 100 коробочек. Допустим у нас есть некоторый математический оракул, который знает что руку (АА) АК8 и рука (А8) ААК примерно одна и та же рука (хотя в реальности мы конечно выберем АА вместо А8 пусть и там и там у нас трипс) и уже редактировать стратегию не для всех рук данного нода а для только для коробочки, полагая что все руки мы будем играть одинаково. И тут мы встаем на скользкую тропу. Дело в том, что теория говорит нам о том, что равновесия в игре с не полной информацией для двух человек может быть гарантированно найдено лишь при ряде условий. в частности мы не должны абстрагировать руки в коробочки и при этом мы должны помнить для каждого нода из какой коробочки другого нода мы пришли (perfect recall). Так уж получилось что на пефект рекол все давно уже забили, потому что это просто нереально, а вот попытки считать не абстрагированное равновесие или слабо абстрагированное равновесия год от года предпринимаются. Каждый год, летом, проходит чемпионат среди покерных программ в лимитный и безлимитный холдем при стеках 200бб. как правило, победителем последних лет становились участники, использующие гто стратегии на основе cfrma. И как правило это были ребята и института Альберты с их алгоритмом Гипербореан. Насколько же хорошо они играют ? Для начала скажу, что тот же Гипербореан, считался с 10 сайзингами ставок для каждой улицы и 3мя рэйзами. Для 200бб стеков это просто дохрена нодов. При этом для участников есть немаловажное ограничение - размер алгоритма-программы в распакованном виде не должен превышать 120 гигабайт. Для сравнения, минимальный размер не абстрагированного нода по риверу 800 мегабайт, а учитывая что 90 процентов всех нодов - это ноды по риверу, получается печальная ситуация. На что может расчитывать игрок уровня нл10 против гипербореана в хэдзапе. Да он его порвет этого гиперборбореана минимум в 20бб/100. Но что если мы расчитаем не абстрагированный хэдзап только с одним сайзингом ? Всего один сайзинг, 500 нодов, но даже для этого нам потребовался сервер на 96 гигабайт оперативки и 3 месяца расчетов, при этом часть редких нодов все равно пришлось абстрагировать и руки в них запихивать в коробочки по 100к ячеек. Далее полученное дерево прикрутили к покер академии и начали играть в лимитированный безлимитный покер. По началу у меня и моих друзей не получалось обыграть алгоритм, потом я отдал его для тестирования игроку, который очень плохо играл в покер и он просто разорвал прогу. Начал разбирать как это у него получилось и оказалось, что все что делал этот слабый игрок - это бет или рэйз на любой улице. в результате программа попадала в далекие, слабо просчитанные ноды и почему то фолдила слегка чаще чем это было оптимально. Но при этом в ситуациях где было малое количество ставок, программа показывала все еще отличные результаты против игроков. To be continued

Выложу префлоп стратегию после нескольких дней расчетов (несколько сот миллиардов раздач). Что касается обозначений.
sb_bb3 означает что ход сб после того как он сделал рэйз и далее бб сделал 3 бет.
2 колонки это фолд и рэйз. 3 колонки это фолд колл рэйз
Важно.
Если рука не играется к примеру опен рэйзом, то все равно мы делаем расчеты для нее как она будет играться если вдруг когда-нибудь ее сыграют опен рэйзом, но эта стратегия довольно плохо расчитана.

strategy.rar (6 килобайт) Кол-во скачиваний: 863

для 3 января - нечитательно

Это NLHE 100bb стеки или 200bb?
Какие сайзинги 3, 4бета используются?
Некоторые странные действия, типа 100% пуш T5o или 100% колл 4бета с 74о,32о - это погрешности в вычислениях, или все-таки часть стратегии?

Спасибо.

100бб стеки. 2.5 опен, 9 трибет, 20 четыребет и далее пятьбетпуш. Т5о и 74о и 32о не играются на бб, поэтому они не трибетятся, поэтому не коллятся на 4 бет. но может там было несколько иттераций и прога с ними затащила в 4 бет поте поэтому там не нулевая стратегия. На более длинной дистанции в несколько десяткой триллионов раздач там это все вырождается. Поэтому если вы смотрите реакцию на 4 бет, желательно посмотреть, а 3 бетится ли эта рука вообще.

Больше всего меня конечно удивил 100% колл 4 бета с АА. Но с другой стороны когда там много всякого треша коллится на 4 бет, то это наверное не удивительно.

В прошлом году, Гипербореан сенсационно проиграл, при этом проиграл в хлам что-то в районе 10бб/100. Оппоненты использовали для расчетов новую стратегию частично моделирующую пефект реколл. Они не запоминали последовательности прихода карт, но делали публичные коробочки на постфлопе, учитывающие структуру доски. что-то в районе 300 публичных коробочек для флопа.Правда не представляю как они все это расчитывали, потому что любые попытки моделировать пефект реколл увеличивают сложность задачи даже не экспоненциально. допустим на терне у нас есть ситуация где есть возможность в позе поставить второй баррел. для этого нода у нас есть порядка 4 миллионов рук. Допустим мы хотим сделать пефект реколл для для этого нода и нода по риверу. Каждая рука у нас будет попадать очень примерно в 45 разных риверов (в зависимости от карты ривера) и получается что по риверу у нас будет уже 200 миллионов коробочек связанных с терном (конечно мы можем причесать в меньшее количество, но от этого не легче). в общем как только мы начинаем учитывать возможные перестановки то сложность увеличивается драматически. В этом году попробую пересчитать безлимитный лимитный хэдзап в полностью не абстрагированном варианте, чтобы в 3 и 4 бета потах не было просадки точности по терну и риверу и с частичным пефект реколом за счет учета текстуры доски. Если будет время то сделаю паблик версию с которой можно будет поиграть.

А в чём твоя мотивация писать подобные посты, да еще и страту выкладывать?

Пушер, а за что ты Урану -100 в рейтинг влепил, да еще с такими формулировками?

PusheeR @ 3.1.2015
А в чём твоя мотивация писать подобные посты, да еще и страту выкладывать?

PusheeR, Kansas City Shuffle.

PusheeR @ 3.1.2015
А в чём твоя мотивация писать подобные посты, да еще и страту выкладывать?

да синий он прост

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

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

Теперь перейду к теме машинного гто для 6 макса. Для игр больше 2х человек нет алгоритмов нахождения навновесия, но можно найти эпсилон не доминированную стратегию. Что касается технической стороны вопроса. Если мы строим дерево событий так же как делали в хэдзапе, то возникает еще больше проблем. К примеру распределение посещаемости различных веток в 6 макса. Нод где утг открывается, посещается со 100% вероятностью, в том же время, какой-нибудь нод по риверу в мультипоте на 6 человек может возникнуть один раз из миллиарда итераций. Допустим мы делаем упрощенную модель с одним сайзингом и стеками в 100бб у всех игроков. В нашем дереве решений получается примерно 10к нодов. При этом где-то 400 нодов будут обходиться, как наиболее часто встречающиеся процентах в 80 случаев, а все остальное крайне редко. Такие вот технические сложности, чтобы их хотя бы частично преодолеть, приходится жертвовать точностью решения в редких ситуациях и сильно их абстрагировать, то есть запихивать наши неабстрагированные руки во всем меньшее и меньшее количество коробочек в зависимости от степени посещаемости нода. Если сильно заморочиться, то можно все это собрать и поставить считаться. Расчет будет долгий, например, в текущей версия которая считается у меня уже пол года более менее сошелся только префлоп и флоп для часто возникающих ситуаций, что же касается мультипотов, то там все далеко от совершенства. Резюме.
Можно ли создать гто бота для 6 макса. Однозначный ответ - нет. Можно получить какие-то интересные расчеты по ранним улицам, но не более. То же самое и для хэдзапа, но с чуть менее строгими условиями.

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

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