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

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

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


algorithm approximation
person user2566092    schedule 22.10.2014    source источник

Ответы (2)


arrow_upward
5
arrow_downward

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

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

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

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

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

person fairidox    schedule 22.10.2014
comment
Если сэмплирование — это современный уровень техники, то я думаю, что так оно и есть. Печально, однако, что все еще очень мала вероятность того, что некоторые из вычисленных оценок вероятности выигрыша далеки от истины. И есть (52 выберите 2) шансы на то, что это произойдет. Спасибо за ваш ответ. - person user2566092; 23.10.2014
comment
@user2566092 user2566092 нет никаких шансов, что оценки далеки от вас - можно ли ограничить это сверху, если у нас есть эмпирическое среднее значение $m = 1/n \sum_i X_i$, из IE Хеффдинга мы получаем, что Pr(|m - E [m]| › t) ‹= exp{-2nt^2}, полагая RHS = \delta и учитывая, что X ‹= 1, имеем, что |m - E[m]| ‹= sqrt(log(1/\delta)/(2n)) + 1*(\delta). Учитывая вашу точность (4 знака после запятой или что-то еще), вы можете определить требуемое значение для «n» - person fairidox; 24.10.2014
comment
Я согласен со всем, что вы говорите, но факт остается фактом: вы можете оценить вероятность выигрыша как 1,0, хотя на самом деле она больше похожа на 0,5, если вам очень, очень не повезло в вашей выборке. Я знаю, что говорю о шансах, которые могут быть намного меньше, чем вероятность ошибки вычислений из-за космического излучения, если размер выборки достаточно велик. Но все же шанс есть. Невозможно использовать выборку, чтобы когда-либо получить вероятность большого отклонения, равную 0. - person user2566092; 24.10.2014
comment
На самом деле существует только 169 значимых стартовых рук (а не 52 выбора 2). Вероятность того, что As5c выиграет, будет такой же, как вероятность того, что As5h и т. д. Таким образом, существует 13c2 = 78 пар различных карт, которые могут быть одномастными или разномастными (для 156 вариантов) и 13 возможных карманных пар. Время, необходимое для расчета очень надежных таблиц эквити для каждой из них, не так уж велико. - person Julian; 26.10.2014

arrow_upward
0
arrow_downward

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

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

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

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

person Lee Harrison    schedule 22.10.2014
comment
Но даже предварительное вычисление, похоже, требует каких-то уловок, если желательны точные вероятности, потому что для 8 случайных рук оппонента в холдеме есть что-то вроде 10 ^ 21 возможностей для рук оппонентов, игнорирующих порядок оппонентов, и она увеличивается. до 10^24 возможностей, если средние 5 карт еще не сданы. В Омахе количество возможных рук для 8 оппонентов примерно на 10-20 порядков даже больше. - person user2566092; 23.10.2014