Как работает программное обеспечение, которое рассчитывает вероятность выигрыша в Техасском Холдеме или Омахе против 8 случайных рук противника?

Question

Итак, есть компьютерные игры Texas Hold'em, в которых вы играете до 8 противников, и, предположительно, некоторые из этих компьютерных игр говорят вам, что ваша вероятность выигрыша при условии, что ваши противники будут случайными. В случае, если кто-то не знает, в Холдеме каждому игроку раздаются 2 частных карты, а затем в среднем 5 общих карт раздаются посередине (первые 3, затем 1, затем еще 1), а победителем является игрок, который может сделайте лучшую 5-карточную покерную комбинацию, в которой они могут использовать любую комбинацию из 2 личных карт и 5 общих карт. В Омахе каждому игроку раздаются 4 частных карты, а еще 5 общих карт, а победитель - игрок, который может сделать лучшую 5-карточную покерную комбинацию с использованием 2 частных карт и 3 общих карт.

Итак, в Hold'em, для личной руки любого игрока, существует более 10^24 способов, которыми можно было бы обмануть частные руки противников и 5 общих карт. Итак, как они вычисляют/оценивают вашу вероятность выигрыша в начале, если ваши руки противников 8 случайны? В Омахе ситуация еще хуже, хотя я никогда не видел компьютерную игру в Омахе, которая на самом деле дает вам ваши шансы против рук 8 случайных противников. Но так или иначе, есть ли какие-либо программные трюки, которые могут получить эти расчеты вероятности выигрыша (или сказать, исправить в пределах 3 или 4 десятичных знаков), быстрее, чем грубая сила? Я надеюсь, что кто-то может ответить здесь, кто написал такую ​​программу, прежде чем она пройдет достаточно быстро, поэтому я спрашиваю здесь. И я надеюсь, что ответ не предполагает оценку случайных выборок, потому что всегда есть небольшая вероятность, что это может быть далеко.

Answer 1

Как вы определили, ожидаемая скорость выигрыша - это невероятно большое суммирование и должна быть аппроксимирована. Стандартный подход заключается в использовании метода Монте-Карло, который включает в себя одновременное моделирование различных рук и принятие эмпирического среднего значения: # побед/# игр.

Интересно, что ошибка (MSE) этого приближения не зависит от размерности (количества комбинаций), в частности, позволяя X = 1, если вы выиграете, 0, если вы проиграете, MSE = var (X)/N = p * (1-p)/N где p = Prob (X = 1) (неизвестно), а N - количество выборок.

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

Редактирование: просто увидели, что вы ищете подход, основанный на неслучайном приближении. Я сомневаюсь, что у вас будет большая удача в подходах с детерминированными приближениями, я знаю, что современное состояние в области вычислений в покере использует методы Монте-Карло для вычисления эти вероятности, хотя и с несколькими трюками с уменьшением дисперсии.

Относительно «потому что всегда есть небольшой шанс, который может быть удален», вы всегда можете получить вероятность высокой вероятности ошибки с неравенством Хёффдинда.

Answer 2

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

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

Вот ссылка к неполному таблице шансов: http://www.learn-texas-holdem.com/texas-holdem-odds-probabilities.htm

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